1
$\begingroup$

Has it ever been shown that simulation of a quantum algorithm (e.g., using PyQuil or something?) on a classical computer has out-performed a purely classical algorithm? From what I can tell the answer is no, given the large memory, etc., for a classical computer to simulate a quantum algorithm, but I'm curious what others think.

$\endgroup$
3
  • 4
    $\begingroup$ maybe I'm misunderstanding what you're trying to say, but a "simulation of a quantum algorithm" on a classical computer is a classical algorithm. So it's not clear how this could "outperform classical algorithms". Or are you asking about "quantum-inspired" classical algorithms? these are just classical algorithms that have been found thinking about quantum stuff. $\endgroup$
    – glS
    May 13, 2023 at 21:57
  • 3
    $\begingroup$ Actually, the simulation of a quantum algorithm is a classical algorithm itself :). $\endgroup$
    – narip
    May 14, 2023 at 10:49
  • $\begingroup$ See related: quantumcomputing.stackexchange.com/questions/25879/… $\endgroup$
    – jecado
    May 15, 2023 at 14:57

2 Answers 2

2
$\begingroup$

A simulation cannot outperform the environment in which it is being simulated so yes the answer would be no.

If you're asking whether simulations of quantum algorithms show that they can outperform classical ones, then surely they would, given that quantum algorithms exist with smaller complexity than their classical "equivalents". But under the constraints of simulation that advantage would be more of a prospect than an immediately useful advantage, inherent to the simulation itself.

$\endgroup$
1
$\begingroup$

If a quantum circuit consists of Clifford gates only, for example CNOT, H, X, Y, Z or S, then it can be simulated classically in polynomial time (this is Gottesman-Knill theorem). However, once non-Clifford gates like T or Toffoli are involved, the simulation is always exponentially complex. To have a quantum computer universal, you always need at least one non-Clifford gate in its native gate set. This means that simulation of universal quantum computer is always exponentially complex.

In sum, this means that it is impossible to simulate classically a quantum algorithm with less resources than in case the algorithm runs on actual quantum computer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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