# To what extent is it true that quantum computation cannot be simulated on classical computers, and how can we prove it?

I have read several times, for example in chapter 3 of Computer-aided-design Methods for Emerging Quantum Computing Technologies by David Dov Yehuda Feinstein (PhD thesis, Southern Methodist University, 2008), statements to the effect that

quantum computation cannot be simulated on classical computers.

However, I am not able to get a clear logical proof for this. How can we say this? Is there any law or theorem that proves this? Please help me understand.

• If you define your terms, then people unlucky enough to not get that page in their randomly selected preview can answer your question. In general a quantum computer with n bits might be simulated by a computer with n^n bits but that gets impractical fast if you have large quantum computers. – Timaeus Jun 12 '15 at 18:09

The statement is either false or unproven, depending on how you take it.

Scenario 1: "Quantum Computers Cannot Be Simulated, Even Given Infinite Time and Space"

This statement would be one in which we wish to know the outcome of a quantum computation, but we lack a quantum computer. In this case, is there anyway we can make a classical computer do the computation for us, but maybe it would take much longer? In fact we can. Our quantum computer must have some algorithm, given as a series of gates, which can be written as unitary operation $U$ on the initial state $\left| \psi \right\rangle$. So the quantum computation can be duplicated if we calculate the final state, $U \left| \psi \right\rangle$. This is very hard to do in general--it requires computing an $2^n \times 2^n$ dimensional matrix times a $2^n$ dimensional vector. But it's not impossible, and given lots of time and space you can do it--there's nothing magic about vector multiplication.

(A more sophisticated argument using path-integral analogy can show that quantum computing is possible in polynomial space but exponential time, actually, but let's not worry about it.)

Scenario 2: "Quantum Computers Cannot Be Efficiently Simulated"

This question is slightly different. The question is: suppose a quantum computer can solve a problem in polynomial time--so if it takes $n$ input or output qubits, the runtime is proportional to $n^k$, where $k$ is some finite number. Then does there exist a classical algorithm that does the same problem, although maybe with a different $k$?

Nobody knows. Seriously. We know that there are quantum examples of better $k$'s, as in Grover's algorithm (classical: $k = 1$, quantum: $k = 1/2$). We know that there are quantum polynomial algorithms to solve problems that appear to be exponential in classical computers (factoring; the hidden subgroup problem in general). That said, there is no known proof that a quantum computer can generically do things in polynomial time that a classical computer cannot do. Factoring, for instance, seems to be hard for classical computers, but there is no proof that it definitely is. Many people believe this is so, but complexity theory is a very tricky thing and the logical proof is not there. Perhaps all the problems that look easy for quantum are also easy for classical, and we just haven't figured them out yet. Note that LOTS of time and research is dedicated to running simulations of quantum systems, and it appears to be very difficult to simulate a quantum many-body system. But perhaps we're just not good at it.

In complexity-theory language, we have not yet proven a separation between $BQP$ ("bounded-error quantum polynomial") and $BPP$ ("bounded-error probabilistic polynomial"), the complexity classes of problems efficiently solvable on a quantum and classical computer.

• Or, to be more explicit, problems like factoring can be solved efficiently by quantum computers and not by any known classical algorithms - but this might yet change! For all we know, factoring is efficiently solvable (i.e. in P). – Emilio Pisanty Jun 29 '16 at 18:14
• @EmilioPisanty yes precisely! This is what I meant by saying "appear to be exponential." I'll edit later to reflect I think – zeldredge Jun 29 '16 at 18:18
• Do you have a reference for using path-integrals to show that quantum computing is possible in polynomial space? – tparker Jul 9 '16 at 21:14
• It is not necessary to store the state to simulate a quantum computation where there is a measurement at the end. All that is needed to be done to simulate the computation is to evaluate the amplitude corresponding to the accept state of the output, which can be done by keeping track of all (the exponentially many) possible paths from the input state to the accept state. For a reference, check out this lecture of Scott Aaronson's. – Abhinav Jul 11 '16 at 20:33
• For a paper that showed this, look at Theorem 8.4 of Bernstein-Vazirani's paper that introduced BQP. – Abhinav Jul 11 '16 at 20:33

Quantum computations can be simulated in a classical computer, at least theoretically. Quantum computers (if they end up existing), it is thought (see comments below) that at most a speed advantage over classical computers, such as being capable of speeding up a problem from, an exponential speed on the input length to a polynomial time in input length (if $P\neq NP$) . This cannot seem like a lot, but it means that there are practical problems that a standard computer will not be able to solve as it would require more resources that those available in the entire universe. A quantum computer can overcome this limitation for many sets of problems.

But the set of problems that both can solve in theory are the same. The algorithms that a quantum computer is capable to solve is the same set as the set of algorithms that a standard computer can in principle solve. This is the set of Turing computable problems. Thus the difference between a classical and a quantum computer is fundamentally one of speed and smaller required resources.

• (Though note that the exponential-to-polynomial speed advantage is at present widely believed but still unproven.) – Emilio Pisanty Jun 29 '16 at 18:17
• To say that quantum computers are "faster" doesn't really convey the difference between being able to solve a problem in polynomial time vs. only being able to solve it in exponential time. In the jargon of software development, we would not say that the quantum computer is faster, we would say that it has better scalability. Unfortunately, my imagination fails me when I try to think of a good, non-software analogy for the concept. – Solomon Slow Jun 29 '16 at 18:18
• @jameslarge thanks for the semantic clarification anyways – Wolphram jonny Jul 9 '16 at 21:21
• @EmilioPisanty of course I agree with you, If what you mean by that is the formalism of QM actually works in the physical world, or is QM is only an approximate theory – Wolphram jonny Jul 9 '16 at 21:22
• No, that's not what I mean at all. Regardless of whether QM is or isn't a good theory for what goes on in the world, the set of problems that quantum computers can solve efficiently, BQP, is a perfectly well-defined notion. There is, at present, no known problem that is efficiently solvable in BQP but has been proven to be exponentially harder for classical computers. Problems like factoring are believed to be hard for classical computers, but this is not yet proved and could very well still be false. – Emilio Pisanty Jul 9 '16 at 22:44

Simulating quantum computers may be intractable, but it's not impossible.

What quantum computers do is still computable. They don't violate the Church-Turing thesis. But they probably violate the extended variant of that thesis (where 'compute' is strengthened to 'efficiently compute').

Proving the computability of a quantum computer is easy. Just formalize what you mean by quantum computer:

• The state space is a vector of amplitudes mapping to a Hilbert space.
• Measurement picks a state with probability proportional to amplitude squared.
• You can apply Hadamard gates, Controlled-not gates, and Z^(1/4) gates.

Then write a classical simulation program that does those things, even if it scales poorly or is a toy one like Quirk. The math is unambiguous about what has to happen at each step, so just do the math.

(I'm sure there's people out there that have non-standard definitions of "quantum computer". And perhaps those non-standard definitions contain incomputable elements [Penrose's 'orchestrated reduction' comes to mind]. But your standard H+T+CX gate model quantum computer is simulable.)

So we can simulate quantum computers, but does the simulation have to be inefficient? Proving the difficulty of quantum simulation is not to easy. Proving lower bounds in complexity theory is really hard. You-can-win-a-million-dollars-for-doing-it levels of hard. Nevertheless, simulating quantum computers seems exponentially hard. Not impossible, but intractable past 50 qubits.

Anytime you hear someone say "quantum computers can't be simulate by classical computers", you should hear the tiny little implied "in a remotely reasonable amount of time, although we haven't technically proven that yet".