TransWikia.com

Is the gate-based model of QC universal?

Quantum Computing Asked by QurakNerd on July 27, 2020

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.

2 Answers

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

Answered by Michele Amoretti on July 27, 2020

A Toffoli gate is in fact NAND gate (when target qubit is in state $|1rangle$, 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.

Answered by Martin Vesely on July 27, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP