# Is the gate-based model of QC universal?

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).

• Is it a "universal" model though? Commented Jul 23, 2020 at 19:25
• Yes, it is. Equivalent (but more practical) to the Quantum Turing Machine. Commented Jul 23, 2020 at 20:33
• @QurakNerd This was Deutsch's original paper where he proved it is universal. royalsocietypublishing.org/doi/abs/10.1098/rspa.1985.0070 Commented Jul 23, 2020 at 21:32

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.