I have heard this is the case but can not find a source even discussing this.

Can any problem that can be solved by a Quantum Computer, also be solved by the quantum circuit model?

I realise that even if this is true, it won't always be the best option, I mean theoretically.

And I have heard that CNOT gate combined with arbitrary rotations allow to implement any gate. But nothing that makes it clear that the circuit can do anything.


The quantum circuit model is one of the possible models for quantum computation. It is the most studied, because it is quite practical.

Back to the origins, you can look at papers by David Deutsch, like:

Quantum computational networks Proc. R. Soc. Lond. A 425, 73-90 (1989)

For a slow start, I suggest to read Nielsen and Chuang's book and maybe Scott Aaronson's lecture notes (Section 16.2.2).


A Toffoli gate is in fact NAND gate (when target qubit is in state $|1\rangle$, othwerwise it implements AND gate). Since NAND gate allows to implement any classical logical function and hence any classical algorithm, any gate based quantum computer is universal from classical point of view.

Note that Toffoli gate can be realized with CNOT, H, S and T gates. This combination of gates also enable to implement any unitary gate on quantum computer.

To have a universal quantum computer, we need a gate preparing superposition. This can be done with Hadamard gate.

There are other gate sets which are universal, for example CNOT, H, S and z-rotation, or CNOT and x,y and z rotations etc.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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