2
$\begingroup$

Or alternatively phrased, is it believed that the complexity class P is a complete subset of BQP? Consider the following diagram à la MIT OpenCourseWare, which seems to explicitly state as much.

Complexity Zoo - MIT OpenCourseWare

$\endgroup$
3
  • 1
    $\begingroup$ Doesn't the diagram show precisely what you ask? And what do you mean by complete subset? $\endgroup$ – Norbert Schuch Jan 3 at 20:59
  • $\begingroup$ @NorbertSchuch By complete subset I meant $|P| \neq |BQP|$. It might have been less ambiguous if I had referred to this as a proper or strict subset. Yes the Venn diagram implied as much, but I couldn't reason about whether this was actually the case, hence my question. $\endgroup$ – Eoin Dowling Jan 5 at 23:00
  • $\begingroup$ Proving strict inclusion would have all kind of severe implications which are believed to be true but have never been proven, so (i) it is likely true and (ii) it is unlikely that it will be proved any time soon. $\endgroup$ – Norbert Schuch Jan 5 at 23:32
9
$\begingroup$

It is indeed true that $P \subset BQP$ and so any problem solvable on a classical computer is solvable on a quantum computer.

Physics intuition

The physics intuition behind $P \subset BQP$ is based on the correspondence principle which says that under suitable conditions quantum mechanics reproduces classical physics. The principle is grounded in the common sense observation that most of the time macroscopic world behaves classically despite being fundamentally quantum mechanical at the microscopic level. Therefore, any classical computer can be viewed as a quantum system and thus simulated by a quantum computer to any accuracy with reasonable overhead.

Computer science argument

A more rigorous argument is provided by computer science and consists of two parts. First, we establish that any classical computation can be performed reversibly. Second, we establish that any reversible classical computation can performed on a quantum computer.

Any classical computation can be viewed as a function $f: \{0, 1\}^n \to \{0, 1\}^m$. Each component $f_i$ of $f$ for $i=1,2,\dots,m$ is a boolean function for which we can write down the truth table. Given the truth tables we can build a classical circuit consisting of the AND, OR and NOT gates that computes $f$. Now, AND, OR and NOT gates can all be implemented using the NAND gate. Thus, NAND gate is universal for classical computation.

Next, we prove that any classical computation can be done reversibly. This follows from the fact that the NAND gate - which is not reversible - can be implemented reversibly using the Toffoli gate. This is done by setting the control bits of the Toffoli gate to the inputs of the NAND gate and by setting Toffoli's target bit to $1$. Fully rigorous argument also shows that the overhead incurred by uncomputation is polynomial.

Finally, quantum computer can implement the classical Toffoli gate using the quantum Toffoli gate. In essence, the quantum computer simulates the classical computater using only computational basis states such as $|01011\dots0\rangle$ without ever entering in superposition. Each such state directly corresponds to the state of a classical binary register.

Practicality

Quantum computers lack the benefit of decades of improvements that have made classical computers very fast. Moreover, quantum computers require error correction which incurs significant time and space overhead and indeed requires a fast classical computer running alongside the quantum device. Therefore, in practice quantum computers are very unlikely to be competitive with classical computers on classically tractable problems. Consequently, quantum computers are likely to remain special-purpose devices for solving problems for which quantum mechanics offers exponential speed-up that overcomes the overheads of quantum error correction.

$\endgroup$
2
$\begingroup$

I would think that if a problem is tractable on a classical computer then it is tractable on a quantum computer as any classical circuit can be replaced by an equivalent circuit containing only reversible gates with little overhead and thus can be simulated on a quantum computer.

You can look at Mike and Ike "Quantum Computation and Quantum Information" section 1.4.1, 'Classical Computations on a quantum computer' for more details.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.