Source-linked AI summary
Elementary gates for quantum computation
A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, H. Weinfurter
TL;DR
The paper addresses quantum logic-gate construction from the perspective of classical reversible computation. It shows that introducing one workspace bit reduces the implementation time for a family of ∧m gates from Θ(m2) to Θ(m).
Problem
Quantum logic-gate construction is considered from the perspective of classical reversible computation.
Method
The paper considers quantum logic-gate networks that can be constructed with no workspace and examines constructions involving one workspace bit.
Results
Introducing one workspace bit reduces the implementation time for a family of ∧m gates from Θ(m2) to Θ(m).
Takeaways & Limitations
Workspace can substantially reduce the time required to implement the ∧m gate family.
Takeaways & Limitations
The proof of Lemma 7.1 is omitted.
Abstract
from arXiv · showhide
We show that a set of gates that consists of all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (that maps Boolean values $(x,y)$ to $(x,x \oplus y)$) is universal in the sense that all unitary operations on arbitrarily many bits $n$ (U($2^n$)) can be expressed as compositions of these gates. We investigate the number of the above gates required to implement other gates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2) transformation to one input bit if and only if the logical AND of all remaining input bits is satisfied. These gates play a central role in many proposed constructions of quantum computational networks. We derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two-and three-bit quantum gates, the asymptotic number required for $n$-bit Deutsch-Toffoli gates, and make some observations about the number required for arbitrary $n$-bit unitary operations.
1 Background
Quantum computation extends reversible computation by allowing arbitrary unitary evolution on superposed and entangled qubit states. This paper develops elementary-gate constructions and efficient schemes for assembling such transformations.
- 1 Background: Quantum evolution is reversible through unitary operators, while quantum states can occupy superpositions and become entangled across qubits.An n-qubit gate acts as a unitary operation in a Hilbert space of dimension 2^n.
- 1 Background: Quantum computers can access unitary-operation spaces whose dimension grows exponentially with the number of physical qubits.The paper contrasts this with classical systems, whose attainable unitary dimension is bounded by the apparatus's classical degrees of freedom.
- 1 Background: Quantum gate arrays generalize combinational circuits: gates have equal input and output counts, and n-input gates implement operations in U(2^n).Wires carry qubits, each a two-dimensional quantum system, and gate arrays use quantum wires without fanout or feedback.
- 1 Background: The paper shows that a non-universal classical two-bit gate, combined with arbitrary one-bit quantum gates, forms a universal quantum-gate repertoire.This complements prior constructions using universal three-bit gates and other two-bit universal gates.
- 1 Background: The authors also develop efficient constructions for classes of n-bit operations, extending earlier five-gate constructions of the Toffoli gate.They state that some resulting gate-assembly schemes have no obvious connection with previous constructions.
2 Introduction
The paper establishes that classical two-bit gates together with one-bit quantum operations generate arbitrary unitary transformations, and develops workspace-free constructions for generalized Toffoli gates. It also shows that one workspace bit can reduce exact implementation time from Θ(m^2) to Θ(m).
- Generalized Toffoli operators ∧m(U) apply U to the target bit exactly when all m control bits are 1.The construction treats ∧0(U) as an ordinary one-bit operation and ∧m(U) as a Toffoli-gate generalization.
- Classical two-bit gates combined with one-bit quantum operations can construct any unitary transformation in a network.
- The paper gives explicit constructions of ∧m(U) from ∧1(U) gates whose size can be polynomial in m.These constructions are compared with polynomial constructions for the analogous classical reversible gates.
- Quantum logic gates can be constructed without any workspace, unlike classical constructions that require work bits for intermediate results.
- Adding one workspace bit reduces the exact implementation time for a family of ∧m gates from Θ(m^2) to Θ(m).
3 Notation
The paper adopts notation for controlled U(2) gates and Toffoli gates, and treats one-bit gates and XOR as the basic operations used in its networks.
- The paper uses Feynman’s notation for ∧m(U) and Toffoli gates.
- The XOR maps Boolean inputs as a reversible operation and plays a prominent role in the constructions.
- The basic operations are a one-bit ∧0(U) gate and the two-bit XOR gate.
- Gate-array diagrams read from left to right, with the left-most gate operating first.
4 Matrix Properties
This section characterizes one-qubit unitary matrices through rotation, phase, and Pauli factors, and establishes a decomposition useful for controlled-gate simulations.
- Every 2 × 2 unitary matrix can be decomposed into a phase factor and rotations Rz, Ry, and Rz.
- Special unitary matrices have determinant 1, allowing the overall phase factor to be absorbed up to a sign.
- The section defines rotations about the y and z axes, phase shifts, and the Pauli-x negation.
- For any W ∈ SU(2), matrices A, B, and C can satisfy A·B·C = I and A·σx·B·σx·C = W.
5 Two-Bit Networks
The paper develops increasingly specialized networks for simulating controlled one-qubit unitaries, reducing their basic-gate cost for important matrix classes.
- The general construction uses A, B, and C so the target transformation occurs only when the control bit is 1, while the identity occurs when it is 0.
- Phase differences and special SU(2) cases can yield further simplifications, including cases involving the Deutsch gate.
- Any controlled one-qubit unitary ∧1(U) can be simulated with at most six basic gates: four ∧0 gates and two XOR gates.
- A two-sided construction with A and B ∈ SU(2) exists exactly for W matrices of the form characterized in Lemma 5.4.
- The specialized constructions cover rotations such as Ry and Rz, but not Rx in the Lemma 5.4 form.
- For arbitrary U, the alternative construction still uses at most six basic gates, replacing two XOR gates with two controlled V gates for a suitable V.
6 Three-Bit Networks
The section extends controlled-gate simulations to three-bit networks, giving a sixteen-basic-gate construction for ∧2(U) and identifying when phase-congruent implementations are acceptable.
- 6 Three-Bit Networks: Any ∧2(U) gate can be simulated with at most sixteen basic gates: eight one-bit gates and eight XOR gates.
- 6 Three-Bit Networks: The construction chooses V with V^2 = U, applying V conditioned on each of the first two bits and V† conditioned on their XOR.
- 6 Three-Bit Networks: When both control bits are 1, the target receives V·V = U; otherwise the applied transformations cancel to the identity.
- 6 Three-Bit Networks: For U = σx, the construction simulates the three-bit Toffoli gate, the primitive gate for classical reversible logic.
- 6 Three-Bit Networks: Phase-congruent networks may differ by ±1 amplitude phases, which is acceptable for classical reversible computation or when paired gates cancel the phase, but dangerous with non-classical unitaries.
7 n-Bit Networks
The section develops constructions for generalized controlled-U gates, establishing exponential exact simulations for some cases, quadratic upper bounds for arbitrary controls, and linear bounds for important restricted cases.
- Small-n exact constructions: For n = 3, 4, 5, 6, 7, and 8, the grey-code construction is the most efficient known method, but it requires Θ(2^n) gates and becomes inefficient for large n.With mergers, the construction uses 3·2^(n−1)−4 controlled-NOT gates and 2·2^(n−1) controlled identities.
- Ancilla-state behavior: The construction works without initially clearing uninvolved bits and restores those bits to their initial values after the gate operation.This state-independence supports recursive constructions in which ancillary or uninvolved bits need not begin in 0.
- Linear simulation of ∧n−2(σx): A controlled-σx gate with n−2 controls can be simulated using 8(n−5) three-bit Toffoli gates, or 48n−204 basic operations, for n ≥ 7.Most Toffoli gates require only six basic operations, while four gates involving the last bit require sixteen each.
- General ∧n−1(U) simulation: 48n^2 + O(n) basic operations simulate any ∧n−1(U) gate on an n-bit network.The construction recursively reduces the target gate to controlled-σx gates and smaller controlled-unitary gates.
- Lower bound: Any nonscalar ∧n−1(U) gate requires at least n−1 basic operations, leaving open whether subquadratic exact simulation is possible.The lower bound follows because fewer than n−1 controlled-NOT gates disconnect the network into tensor-factorized components.
8 Efficient general gate constructions
The section studies general constructions from arbitrary two-bit gates, using dimension counting and unitary decompositions to bound exact synthesis costs while emphasizing their exponential scaling and limited practical usefulness.
- Dimension counting: Six arbitrary U(4) gates suffice for an arbitrary three-bit unitary, reaching the full 64-dimensional U(8) parameter space.The dimensionality increases from 16 after one gate to 28 after two, then by nine per succeeding gate until six gates reach 64.
- Lower-bound intuition: The dimension-counting pattern suggests a lower bound on two-bit gates for arbitrary n-bit unitaries, and almost all such transformations require exponentially many operations.The paper presents this as a conjectural lower-bound argument based on preliminary four-bit tests and dimensionality growth.
- Exact arbitrary-unitary synthesis: Any U(2^n) operation can be simulated exactly with Θ(n^3 4^n) arbitrary two-bit gates and no work bits.The construction decomposes the unitary into two-dimensional rotations and simulates each rotation through grey-code-controlled operations.
- Practical limitation: The exact construction is mathematically convenient but is unlikely to yield a useful polynomial-time method for the special unitaries most relevant to quantum computation.The authors identify the exponential scaling as a serious practical problem and leave the search for an efficient design methodology open.