What do we mean by Classical Simulation of Quantum Algorithm

[JK423]

In the quest of searching what are the basic ingredients of quantum theory that provide exponential speed-up to some quantum algorithms, a basic question that is pursued in the literature is when a quantum circuit (or algorithm) can be classically simulated efficiently. One example is this paper by Mari and Eisert: http://arxiv.org/pdf/1208.3660.pdf

Can someone explain to me what we mean by classical simulation of a quantum algorithm?
I would be grateful.

 

[ShayanJ]

Maybe I'm not the best person to answer but this is what I think:
At first it should be mentioned that quantum algorithms are designed with the possibility of quantum phenomena in mind. So they may use entanglement and superposition. But in a classical computer(which almost completely operates on classical laws), such phenomena can't happen. Therefore, it seems to me, that the first step is simulating a quantum computer on the classical computer. The next way is just running the algorithm on the simulated quantum computer. But I didn't read the paper and I don't know what part of the problem is the author talking about.

 

[Truecrimson]

It's all about the asymptotic scaling of the running time of the algorithm with respect to the input size. Roughly speaking, a problem is in P if it there is an algorithm that can solve the problem in time polynomial in length of the input. (Requiring an exact scaling will only make the theoretical analysis cumbersome and machine-dependent.) Usually people say that problems in P can be solved efficiently on a classical deterministic computer. Analogously, problems in BPP are said to be efficiently solvable on a classical probabilistic computer.

The set of problems efficiently solvable on a universal quantum computer is believed (because of e.g. Shor's factoring algorithm, but not proved) to be strictly larger than P or BPP. So it is unlikely that we can simulate a universal quantum computation using classical computers. But we can definitely simulate a subset of quantum processes efficiently on a classical computer; a classical computation itself on a physical level is quantum! But there're other interesting classes of classical simulatable quantum computation like stabilizer and matchgate circuits. Whenever we found algorithms that can simulate these circuits (that solve some problems) in polynomial time on a classical computer, we know that these problems are not just in BQP but also in P or BPP.