Do there exist problems known to be computationally intractable for quantum computer, but tractable for classical computer?

Question

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.

Answer 1

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

Physics intuition

The physics intuition behind $P \subseteq 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.

Answer 2

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.

Answer 3

Other great answers address the question in the body of the posting, specifically about the relationship between BPP and BQP.

However the question in the title can be construed a bit more broadly. Indeed, in some instances a 'quantum computer' need not be a BQP-machine, and we can ask if there is any type of quantum computer cannot do all that a classical computer can.

There are indeed a couple of such restricted quantum computing models that have been explored. Perhaps a handful that are well known are (1) those associated with linear optical quantum computing and experiments with Boson Sampling, (2) the instantaneous quantum computing (IQP) schemes of Brenner, Jozsa, and Sheperd and (3) those associated with the "one clean qubit" or DQC1 model of computation, which was commonly explored in the context of NMR-based quantum computers but is interesting in its own right, given how little entanglement seems to play a role with such models.

I learned recently that, if the classical post-processing capabilities of such a one-clean qubit model were sufficiently shallow, then it's very likely that P$\not\subseteq$DQC1, and we might have a Venn diagram where DQC1 is not a strict superset of P, but even includes some problems outside of NP, such as evaluating the Jones polynomial of the trace closure of a knot. The same or something similar can be said about the linear-optical sampling computers and, I'm pretty sure, the IQP computers.