What additional gates are needed for a set of classical universal gates to do universal quantum computation? We answer this question by proving that any single-qubit real gate suffices, except those that preserve the computational basis. The result of Gottesman and Knill[quant-ph/9807006] implies that any quantum circuit involving only the Controlled-NOT and Hadamard gates can be efficiently simulated by a classical circuit. In contrast, we prove that Controlled-NOT plus any single-qubit real gate that does not preserve the computational basis and is not Hadamard (or its alike) are universal for quantum computing. Previously only a ``generic'' gate, namely a rotation by an angle incommensurate with pi, is known to be sufficient in both problems, if only one single-qubit gate is added.
What additional gates are needed for a set of classical universal gates to do universal quantum computation? We prove that any single-qubit real gate suffices, except those that preserve the computational basis. The Gottesman-Knill Theorem implies that any quantum circuit involving only the Controlled-NOT and Hadamard gates can be efficiently simulated by a classical circuit. In contrast, we prove that Controlled-NOT plus any single-qubit real gate that does not preserve the computational basis and is not Hadamard (or its like) are universal for quantum computing. Previously only a generic gate, namely a rotation by an angle incommensurate with \pi, is known to be sufficient in both problems, if only one single-qubit gate is added.
What additional gates are needed for a set of classical universal gates to do universal quantum computation? We answer this question by proving that any single-qubit real gate suffices, except those that preserve the computational basis. The result of Gottesman and Knill[quant-ph/9807006] implies that any quantum circuit involving only the Control-NOT and Hadamard gates can be efficiently simulated by a classical circuit. In contrast, we prove that Control-NOT plus any single-qubit real gate that does not preserve the computational basis and is not Hadamard (or its alike) are universal for quantum computing. Previously only a ``generic'' gate, namely a rotation by an angle incommensurate with pi, is known to be sufficient in both problems, if only one single-qubit gate is added.
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant
δ>0, it
ε-approximates an arbitrary single-qubit gate using
O(log1+δ(1/ε)) clean ancillae, Hadamard and
T single-qubit gates,
O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard,
T, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth
O(loglog(1/ε)), and we prove a matching
Ω(loglog(1/ε))-depth lower bound. Overall, we establish that
Θ(loglog(1/ε))-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis.
These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-
d QAC circuit can be simulated in depth
O(d) using only Hadamard,
X, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity
∈/QAC
0 to proving a Parity lower bound against circuits consisting only of Hadamard,
X, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.
Abstract A universal set of gates for (classical or quantum) computation is a set of gates that can be used to approximate any other operation. It is well known that a universal set for classical computation augmented with the Hadamard gate results in universal quantum computing. Motivated by the latter, we pose the following question: can one perform universal quantum computation by supplementing a set of classical gates with a quantum control, and a set of quantum gates operating solely on the latter? In this work we provide an affirmative answer to this question by considering a computational model that consists of 2n target bits together with a set of classical gates controlled by log (2n + 1) ancillary qubits. We show that this model is equivalent to a quantum computer operating on n qubits. Furthermore, we show that even a primitive computer that is capable of implementing only SWAP gates, can be lifted to universal quantum computing, if aided with an appropriate quantum control of logarithmic size. Our results thus exemplify the information processing power brought forth by the quantum control system.