As we all know, any quantum circuit that uses only Clifford gates can be efficiently simulated on a classical computer using a stabilizer simulator. It sounds pretty good at first; you get X, Z, H, S, and CNOT, with just a polynomial overhead (n^2). But the thing is, as far as I can tell it is not possible to simulate a universal classical computer using only Clifford gates. So the classical computer simulating a quantum computer (with only Clifford gates) cannot simulate a classical computer. If that is true, it seems that we aren’t using the classical computer to the fullest of its ability. By running a stabilizer simulator we are losing computational power of some kind. That makes me wonder if maybe there is a better way to simulate a quantum computer.
What do you think?
March 17, 2008 at 11:25 am |
So maybe the Clifford group is not classical universal but if you could simulate a quantum computer that has just a Toffoli and a NOT then you could use that quantum computer to simulate a universal classical computer. Of course there isn’t much quantum about a quantum computer with only those two gates and so it still sucks.
March 22, 2008 at 9:04 am |
Actually, X and CNOT are universal for classical computation by themselves if you allow “classical” magic states. Shor showed that one can simulate a Toffoli gate using the state (|000> + |001> + |010> + |100>)/2 and CNOT gates. This state has a natural classical “pbit” analogue (000 + 001 + 010 + 100)/4, which allows CNOT to simulate TOF in the same way. Of course, you have to distill such a state, which can only be done approximately using CNOT and X gates. In other words, the Clifford group is ‘BPP-universal.” I don’t know the answer to the question of whether Clifford gates allow “P-universality.” My guess is that they don’t, but I don’t have a proof.
March 31, 2008 at 12:50 pm |
That’s some good information, Andrew. Thanks for that.
I still haven’t convinced myself that the Clifford group is indeed BPP-universal. I still have to think about it a bit more.