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.
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.
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.
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:
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".
