2
$\begingroup$

I've read this paper by Bravyi and Kitaev and got confused by this paragraph.

It is well-known that these operations are not sufficient for universal quantum computation (unless a quantum computer can be efficiently simulated on a classical computer). More specifically, the Gottesman-Knill theorem states that by operations from $\mathcal O_{ideal}$ one can only obtain quantum states of a very special form called stabilizer states. Such a state can be specified as an intersection of eigenspaces of pairwise commuting Pauli operators, which are referred to as stabilizers. Using the stabilizer formalism, one can easily simulate the evolution of the state and the statistics of measurements on a classical probabilistic computer...

My question is they said that the Clifford operations are not sufficient for universal quantum computation unless a quantum computer can be efficiently simulated on a classical computer.

Does it mean that if the quantum computer can be efficiently simulated on a classical computer, the Clifford operations will be sufficient for universality.

$\endgroup$
3
  • 2
    $\begingroup$ IIRC, Clifford circuits are not known to be universal for classical computation (I cannot immediately lay my hands on a reference, but there's another complexity class that is related to parity? that is believed to be less than P). If that's the case, then even if a quantum computer can be efficiently simulated on a classical computer, it wouldn't be enough for Clifford to be universal for quantum. $\endgroup$
    – DaftWullie
    Commented Jun 22, 2023 at 6:39
  • 1
    $\begingroup$ Here's the reference I was after: arxiv.org/abs/quant-ph/0406196 $\endgroup$
    – DaftWullie
    Commented Jun 22, 2023 at 6:43
  • $\begingroup$ see also quantumcomputing.stackexchange.com/questions/32332/… $\endgroup$ Commented Jun 26, 2023 at 12:24

0

Your Answer

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

Browse other questions tagged or ask your own question.