A computation model which relies on quantum-mechanic phenomena, such as entanglement and superposition. This generalizes the probabilistic model of computation.

learn more… | top users | synonyms

0
votes
0answers
15 views

Trying to decide when specialization should I choose for my masters [closed]

Ok So I am a mathematics and computer science graduate (double major) and I want to do masters in the university of waterloo (thesis based) as I want to do a PHD afterwards. I like research and I ...
1
vote
1answer
26 views

Computing a partial density matrix from an amplitude vector

Suppose you're given the list $2^{2n}$ complex coefficients defining the state of a $2n$ qubit register. You want to compute the $2^n \times 2^n$ density matrix of the first $n$ qubits. Is it ...
6
votes
1answer
69 views

Are there any problems that require exponential time in quantum computing?

Given the fact that the qbits have superpositions, and have more representational power compared to circuits, are there any problems that require at least exponential time to guarantee a solution with ...
0
votes
1answer
33 views

How many operations to produce this superposition of 3 qubits?

Suppose I have three qubits that of course represent $2^3=8$ states. I want to put these qubits so that they are in the particular superposition say... $$a|000\rangle + b|001\rangle + c|010\rangle + ...
1
vote
2answers
37 views

Constructing the matrix of a controlled quantum operation

How do we construct a matrix that takes into account whether the first qubit is set? I am trying to construct the controlled-V matrix, but there is no quantum computational paper that describes it so ...
1
vote
1answer
21 views

Why does quantum cost on gates formed from specific qubit gates not factor swap gates into account?

I've been reading a number of quantum computation research papers that claim quantum cost's that do not add up. For instance, in this paper - there is a claim that the MTSG gate is a quantum cost of ...
0
votes
0answers
16 views

Are qubits written in a big-endian or little-endian order when grouped?

Say for instance you layout a quantum simulator like follows: amps = [0] * 8 # 3 qubits Therefore you are left with the following in binary: ...
1
vote
1answer
71 views

Can you take classical code and compile it to quantum code?

Is there anyway for example, to take a trivial program from C such as: int main() { int i = 1 + 1; return 0; } And compile this down to some form of Quantum ...
9
votes
3answers
1k views

Is there any proof that quantum computers are more efficient than classical computers?

Shor's algorithm is often used as the argument. It can solve the factorization problem faster than any known algorithm for classical computers. Yet, we have no proof classical computers can't also ...
1
vote
0answers
20 views

2 qubits, correct way CNOT a 3rd qubit with the 1st? [duplicate]

Suppose I have 2 qubits in the state a|00>+b|01>+c|10>+d|11>. And suppose I want to perform some operation between only the 1st qubit and a 3rd qubit - for example a CNOT operation. What would be ...
1
vote
1answer
49 views

Applying a multi qubit quantum gate to specific qubits

A controlled not gate matrix looks like this: $$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}$$ ...
3
votes
1answer
71 views

Does entangling 100 qubits require a 2^100 X 2^100 Hadamard gate?

Suppose I have 100 qubits that I want to entangle and put into superposition. To do so I construct a Hadamard gate to do this. By definition, the Hadamard is going to be a 2^100 X 2^100 matrix - which ...
4
votes
2answers
86 views

Looking for interesting unanswered questions within complexity theory for a project [closed]

I'm looking for interesting open questions in complexity theory that someone with an undergraduate degree in math and comp/sci could theoretically tackle. I have strong interest in the polynomial ...
2
votes
2answers
36 views

Is it possible to entangle more than 2 qubits? If so, is it useful?

With 2 qubits, there are 4 ways to entangle the qubits - the four maximally entangled two-qubit Bell states, of which one is $1/\sqrt{2}(|00\rangle + |11\rangle)$. (from ...
2
votes
1answer
39 views

Why does the Toffoli gate output c XOR (a AND b) instead of just a AND b?

The Toffoli gate takes in three inputs and gives out three outputs, and is often referred to as the quantum AND gate. It takes in a,b,c and gives out a, b, c XOR (a AND b). Why does it do that, ...
1
vote
1answer
36 views

How do you apply a multi qubit gate to specific qubits in a multi qubit circuit?

Let's say that you have a 6 qubit system and you want to apply a Hadamard gate to qubits 2 and 4. How would you construct a matrix that did that, while leaving the state of the other qubits alone?
3
votes
0answers
26 views

How are quantum computers able to process certain tasks faster than regular computers? [duplicate]

I've read posts everywhere and watched videos but still I don't understand one part of it. How are they able to process all these operations in parallel. So based on the landscape example here. How ...
2
votes
1answer
23 views

Must you work with all qubits in a circuit when applying a gate?

When looking at this question: How to apply a 1-qubit gate to a single qubit from an entangled pair? And other questions, it makes it seem like when you have a quantum circuit involving $N$ qubits, ...
6
votes
1answer
200 views

Does a Hadamard Gate have uses outside of pure and evenly mixed states?

The standard usage cases for the Hadamard gate seem to be passing a pure $|0\rangle$ or $|1\rangle$ state in to get an even amplitude (probability) mixed state which has either matching or mismatching ...
-1
votes
1answer
20 views

How do Quantum Computers destructively interfere the wrong answer? [duplicate]

From various sources (one being this), I've heard that quantum computers find the correct answer in a sea of possible ones by destructively interfering the wrong ones with each other, and the right ...
3
votes
2answers
72 views

How do Quantum Computers find the Global Minimum?

If I understand correctly, quantum computers work by trying multiple methods of solving a problem simultaneously, using quantum superposition. However, if you try to "look" at a superposition-ed atom, ...
1
vote
1answer
72 views

Where does entanglement fit into quantum computing?

I've been reading up on quantum computing online from various sources, including this link http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm. I get how quantum gates work, ...
11
votes
3answers
236 views

What specifically makes quantum computers useful?

I know that quantum computers are able to process a superposition of all possible states with a single pass through the logic. That seems to be what people point to as being what makes quantum ...
1
vote
2answers
114 views

Can quantum computer become perfect chess player?

Can quantum computer become perfect chess player? Can it determine whether (when both players are perfect) win white or black? (or is it dead heat?)
0
votes
1answer
46 views

Quantum computer memory size

Quantum computers are going to have enormous number of operations per second (in some situations exponentially more than classic computers). Does it also hold for memory size? Are QC going to have ...
4
votes
0answers
92 views

If BQP is contained in any level of the Polynomial Hierarchy, does it then follow that $NP \subseteq BQP$ implies $PH \subseteq BQP$?

I think this is implied in this paper by Aaronson (http://www.scottaaronson.com/papers/bqpph.pdf) but I am not sure. Begin with $NP \subseteq BQP$ (*) $\Sigma_{2}^{P} = NP^{NP} \subseteq BQP^{BQP} = ...
3
votes
1answer
30 views

What can a quantum query to a function do?

The $n$-qubit Hadamard gate acts as, $$H (\otimes^n \vert 0 \rangle ) = \otimes ^n ( H | 0 \rangle ) = \otimes ^n ( \frac { |0\rangle + |1\rangle }{\sqrt{2} } ) = \frac{1}{\sqrt{2^n} } \sum_{x \in ...
13
votes
5answers
4k views

Why is a quantum computer not capable of solving more problems than a classical computer?

On the Wikipedia page for quantum algorithm I read that [a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are ...
1
vote
0answers
22 views

Will the growth of calculation speed of personal computer end after that of classical computer will end? [closed]

According to the answer of Andrew Yeats in this link, quantum computer's advantage is so narrow that personal computer is not likely to benefit from the development of quantum computer. I think this ...
2
votes
1answer
33 views

Question about the Simon's algorithm

This comes from trying to understand the "Simon's algorithm". So we have a set of $2^n$ kets $|x_i \rangle$ one each for $i \in \{0,1\}^n$. Each $x_j \in \{0,1\}^n$. And we have the further ...
3
votes
1answer
28 views

How many inputs does the Hadamard gate have?

Look at the diagram in the middle of page 6-3 here, http://stellar.mit.edu/S/course/6/fa14/6.845/courseMaterial/topics/topic3/lectureNotes/qctlec6/qctlec6.pdf I am confused as to how should one think ...
1
vote
2answers
89 views

How is quantum function $f(x) = a^x \mod N$ constructed in Shor's algorithm?

I can't see how I can apply quantum function $a^x\mod N$ to initial states. Explanations of Shor's algorithm often skips this part, and I do not see what unitary matrix this algorithm would correspond ...
-1
votes
0answers
62 views

How would a for loop differ in quantum computing? [closed]

Consider for example the following code: Array A = {a, b, c, d}; for ( int i = 0, i < A.length, i++){ if A[i]=="c" print["1"]; else print["0"] } and ...
2
votes
1answer
127 views

Evaluating Grover's algorithm on 3-SAT

I recently asked this very similar question on how Grovers algorithm must be modified in order to solve 3-SAT and learned that it actually needs no modification at all. However, what I still don't ...
3
votes
2answers
74 views

How must Grovers algorithm be modified in order to solve 3-SAT?

Grover's algorithm was designed for a database with exactly one item that matches a given search criterion, and can be used to find that very item. However, when checking whether a given formula is ...
10
votes
1answer
226 views

What type of algorithms are faster with a quantum computer?

I am a beginning CS student and I am learning algorithms. I heard that even with quantum computers, that general sorting algorithms can never have better than $n\log n$ time. However, I also know that ...
4
votes
1answer
133 views

Creating bigger controlled nots from single qubit, Toffoli, and CNOT gates, without workspace

Exercise 4.29 from Quantum Computation and Quantum Information by Nielsen and Chuang has me stumped. Find a circuit containing $O(n^2)$ Toffoli, CNOT and single qubit gates which implements a ...
0
votes
0answers
20 views

In Grover and Shor Algorithms 2 registers of qubits are handled at books, but it's really just one seen as 2?

I found in the literature that we require at least two quantum registers for arithmetics operation. Example: The function $f(x)=x^2$ is then a unitary evolution of the two registers, in this ...
1
vote
0answers
24 views

Quantum multi valued decision diagrams

I recently came across the paper "QMDD: A Decision Diagram Structure for Reversible and Quantum Circuits" by Thornton and Miller. It deals with a way of compactly representing transformation matrix ...
6
votes
2answers
367 views

Can a quantum computer (theoretically) do things a classical computer (literally) can't?

I've been searching the net for an answer to this question, but it's guetting quite confusing. I want to know if there are some undecidable problems for a classical computer that a quantum computer ...
4
votes
1answer
58 views

Is $BQP$ in $P^{NP}$?

I read in the introduction of this paper http://www.scottaaronson.com/papers/uncompute.pdf that there is a problem $B$ such that $BQP^B \not\subset P^{NP^B}$, and that $B$ is in $BPP$. But, using ...
2
votes
1answer
50 views

Quantum state probabilities and amplitudes - absolute value squared?

It has just appeared to me that I've overlooked a possibly important fact. When we want to calculate probability $p_x$ of measuring the state $X$ and we know the amplitude of $X$ is $\alpha$, we know ...
1
vote
2answers
92 views

Multi-qubit gates matrix representation

Consider the gate used in Simon's Algorithm. It operates on a control register and target register, changing state like: $|\textbf{x}\rangle|\textbf{y}\rangle->|\textbf{x}\rangle|\textbf{y}\oplus ...
5
votes
1answer
279 views

What happens to multi-qubit quantum state after one of qubits is measured?

If we have a quantum state consisting of (let's say) 3 entangled qubits and we read the value of one of them, what happens to the probabilities of the remaining possible states? For example, if we ...
4
votes
2answers
382 views

Quantum computers and computable functions

A quantum computer can possibly calcluate computable functions faster, but it can't calculate functions which a normal computer can't calculate? If a function is not computable? Does this mean it ...
4
votes
1answer
99 views

Trying to understand how the first Hadamard gate in Deutsch–Jozsa algorithm works

I'm still a beginner in the quantum aspect of computer science (self-studying). So please bear with me if this may sound like a stupid question. I know Hadamard gate transforms qubit into a ...
3
votes
1answer
98 views

Measure two qubits, one from entangled pair, in Bell basis?

In quantum teleportation we require both sender (Alice) and receiver (Bob) to share an entangled pair of qubits in the $|\beta_{00}\rangle$ Bell state. Then, if Alice wants to teleport a quibt ...
2
votes
3answers
134 views

How to apply a 1-qubit gate to a single qubit from an entangled pair?

Reading about superdense coding I came upon a calculation I can not understand. We have an EPR entangled pair of qubits $\frac{1}{\sqrt2}(|00\rangle + |11\rangle)$ and we want to apply a Pauli X gate ...
3
votes
1answer
43 views

Why $\theta/2$ in common qubit representation?

If we take angle names as shown on the Bloch sphere below and a typical qubit representation written as $\cos(\theta/2)|0\rangle + \mathrm{e}^{-\mathrm{i}\phi}\sin(\theta/2)|1\rangle$, why do we ...
1
vote
1answer
64 views

Can a CS grad student work on quantum field theory and string theory problems? [closed]

The mathematical aspect of particle physics theory are interesting and there seems to be a lot more connections being made to computation and information (like with complexity theory having some ...