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
17 views

IS $L=QMA$ an open problem?

Having read several chapters of Computational Complexity: A Modern Approach, I see no time or space hierarchy theorem which applies to this case. As far as I can see, we know the following inclusions: ...
5
votes
1answer
41 views

Computing Von Neumann Entropy Efficiently

The Von Neumann entropy $S$ of a density matrix $\rho$ is defined to be $S(\rho)= -\text{tr}(\rho \lg \rho)$. Equivalently, $S$ is the classical entropy of the eigenvalues $\lambda_k$ treated as ...
1
vote
1answer
62 views

How correct was Justin Trudeau's explanation of Quantum Computing?

Recently, Canada's Prime Minister - Justin Trudeau - gave an impromptu explanation of Quantum Computing, much to the crowd's astonishment. I certainly thought that I "got" Quantum Computing a little ...
3
votes
2answers
35 views

Why does 9 qubit Shor code have distance 3?

Distance of a Stabilizer code($S$) is defined by minimum weight of an element in $N(S)-S$ . Why 9 qubit Shor code has distance 3? Is there a way to directly see $N(S)-S$ from $S$?
1
vote
1answer
32 views

How does equality works for qubit-vectors?

A bitvector of length N has 2^N different values. How many different values has a quantum bit vector of length ...
2
votes
1answer
79 views

Quantum computer simulators with proper measurements

I have been looking for quantum computer simulators and came across QCAD (http://qcad.osdn.jp/). It is stated on their website that "Measurement gates on QCAD are different from real measurements." ...
3
votes
1answer
54 views

CNOT, Hadamard and Φ quantum gates

How can somebody use these gates to create other gates like pauli's or other gates? Also how can somebody go from pauli's to CNOT, Hadamard and Φ quantum gates?
1
vote
1answer
38 views

Computing a partial density matrix from an amplitude vector

Suppose you're given the list of $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
78 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
40 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
44 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
26 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 ...
1
vote
1answer
28 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: ...
3
votes
1answer
92 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 ...
10
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
21 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
67 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}$$ ...
4
votes
1answer
82 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
92 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
45 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
41 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, ...
2
votes
1answer
61 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
27 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
221 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
25 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
87 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
79 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, ...
12
votes
3answers
261 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
138 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
55 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
111 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
31 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 ...
14
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
23 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
35 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
94 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
63 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
139 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
80 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 ...
11
votes
1answer
238 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
167 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 ...
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
396 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
60 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
58 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
110 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
284 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
423 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 ...