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
1answer
44 views

A question on the power of the operator in Grover's quantum algoritm

I'm new to quantum computing, so while studying Grover's algorithm I (and, I think a lot of other people too) could not help but notice that exactly the same operator is applied $\sqrt{N}$ times: $$U ...
1
vote
2answers
44 views

How is the oracle function for Grover's Search algorithm obtained?

I've been using the IBM quantum experience to learn about and simulate Grover's algorithm. When they create the algorithm, they use a different set of gates depending on which oracle function $f(x)$ ...
2
votes
0answers
22 views

Quantum circuits for multiplication

Classically, multiplication can be done in $O(n \ \lg(n) \ 8^{\lg^* n})$ steps on a multi-tape Turing machine via Fürer's algorithm. Using that algorithm, combined with uncomputing, you can make a ...
30
votes
5answers
5k views

Can Quantum Computing solve Problems not even a Turing Machine can solve?

In his book "The Fabric of Reality", Penguin Books 1998, p. 218, David Deutsch says that the first quantum computer (built 1989 in the office of Charles Bennet, IBM Reasearch) "became the first ...
3
votes
1answer
39 views

Hadamard gate on entangled qubit

TL;DR: If you have two entangled qubits in the state $|00\rangle + |11\rangle$, what is the result of applying the Hadamard gate on the second qubit, and why? I am trying to understand $\text{...
1
vote
3answers
86 views

Quantum CNot algorithm problem

I have a very simple quantum algorithm: Let's start with two qubits in the state $|00\rangle$. I apply a Hadamard gate to the first one. Then I apply a CNot gate, with the first one as a control. ...
4
votes
0answers
41 views

Cloning the output of a quantum program with unknown input but known measurements

Suppose Alice asks to use Eve's quantum computer. Alice loads her hidden quantum state into the computer, then gives Eve a program to run. The program will apply unitary operations and measurements to ...
4
votes
2answers
90 views

Are there any useful deterministic quantum algorithms for decision problems?

The vast majority of known interesting quantum algorithms are probabilistic. The only deterministic quantum algorithms that I know of (which aren't trivially equivalent to a classical algorithm) are (...
4
votes
1answer
64 views

Known problems in BQP \ NP?

The introduction to Nielsen and Chuang has an Euler diagram of the suspected relationships between various complexity classes which shows $\text{BQP}$ extending slightly outside of $\text{NP}$. Is $\...
3
votes
0answers
67 views

IS $LOGSPACE\subsetneq QMA$ an open problem?

Having read some 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
61 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 ...
0
votes
1answer
70 views

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

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
39 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
39 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
82 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
65 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
39 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
86 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
46 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
48 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
31 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
29 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
103 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
22 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
82 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
94 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
94 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
3answers
61 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)$. Is it possible to entangle more ...
2
votes
1answer
44 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
68 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
30 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
244 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
132 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
87 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
286 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
192 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
58 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 ...
5
votes
0answers
121 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
38 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
31 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
96 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
68 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
147 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
84 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 ...