Elementary gates for quantum computation

For a unitary 2×2 matrix W, a ∧1(W) gate can be simulated by the stated network with A, B, C in SU(2) if and only if W is in SU(2).

“Lemma 5.1: For a unitary 2 × 2 matrix W , a ∧ 1 ( W ) gate can be simulated by a network of the form”

• Also stated in: § 5.1 Simulation of General ∧ 1 ( U ) Gates · p. 10 · plain

  “where A , B , and C ∈ SU (2) , if and only if W ∈ SU (2) .”

For any unitary 2×2 matrix U, a ∧1(U) gate can be simulated by at most six basic gates: four 1-bit gates (∧0) and two gates (∧1(V)), where V = R_z(α)·R_y(θ)·R_z(α)·σx.

“Corollary 5.6: For any unitary 2 × 2 matrix U , a ∧ 1 ( U ) gate can be simulated by at most six basic gates: four 1-bit gates ( ∧ 0 ), and two gates ( ∧ 1 ( V ) ), where V is of the form V = R z ( α ) · R y ( θ ) · R z ( α ) · σ x .”

To implement a family of ∧m gates exactly, the time required can be reduced from Θ(m^2) to Θ(m) merely by introducing one bit for workspace.

“Still, the presence of a workspace plays an important role in the quantum gate constructions - we find that to implement a family of ∧ m gates exactly, the time required for our implementation can be reduced from Θ( m 2 ) to Θ( m ) merely by the introduction of one bit for workspace.”

For any unitary 2×2 matrix U, a ∧2(U) gate can be simulated by the stated network where V is unitary.

“Lemma 6.1: For any unitary 2 × 2 matrix U , a ∧ 2 ( U ) gate can be simulated by a network of the form”

• Also stated in: § 6.1 Simulation of General ∧ 2 ( U ) Gates · p. 14 · plain

  “where V is unitary.”

A ∧1(W) gate can be simulated by the stated network with A and B in SU(2) if and only if W is of the stated form with real α and θ.

“Lemma 5.4: A ∧ 1 ( W ) gate can be simulated by a network of the form”

• Also stated in: § Lemma 5.4: A ∧ 1 ( W ) gate can be simulated by a network of the form · p. 12 · plain

  “where A and B ∈ SU (2) if and only if W is of the form”

• Also stated in: § Lemma 5.4: A ∧ 1 ( W ) gate can be simulated by a network of the form · p. 12 · plain

  “where α and θ are real-valued.”

For any unitary 2×2 matrix U, a ∧2(U) gate can be simulated by at most sixteen basic gates: eight 1-bit gates (∧0) and eight XOR gates (∧1(σx)).

“Corollary 6.2: For any unitary 2 × 2 matrix U , a ∧ 2 ( U ) gate can be simulated by at most sixteen basic gates: eight 1-bit gates ( ∧ 0 ) and eight XOR gates ( ∧ 1 ( σ x ) ).”

There exist explicit constructions of ∧m(U) using ∧1(U) that are polynomial in m.

“We will also exhibit a number of explicit constructions of ∧ m ( U ) using ∧ 1 ( U ), which can all be made polynomial in m .”

For any special unitary matrix W, there exist matrices A, B, and C in SU(2) such that A·B·C = I and A·σx·B·σx·C = W.

“Lemma 4.3: For any special unitary matrix W ( W ∈ SU (2) ), there exist matrices A , B , and C ∈ SU (2) such that A · B · C = I and A · σ x · B · σ x · C = W .”

For any unitary 2×2 matrix U, a ∧1(U) gate can be simulated by at most six basic gates: four 1-bit gates (∧0) and two XOR gates (∧1(σx)).

“Corollary 5.3: For any unitary 2 × 2 matrix U , a ∧ 1 ( U ) gate can be simulated by at most six basic gates: four 1-bit gates ( ∧ 0 ), and two XOR gates ( ∧ 1 ( σ x ) ).”

The Pauli matrices σx, σy, and σz are examples of matrices of the form of Lemma 5.5.

“Examples of matrices of the form of Lemma 5.5 are the Pauli matrices”

• Also stated in: § Lemma 5.4: A ∧ 1 ( W ) gate can be simulated by a network of the form · p. 13 · plain

  “(as well as σ x itself).”

When U = σx, the construction gives a simulation of the 3-bit Toffoli gate ∧2(σx).

“A noteworthy case is when U = σ x , where we obtain a simulation of the 3-bit Toffoli gate ∧ 2 ( σ x ), which is the primitive gate for classical reversible logic [4].”

• cites [4] [4] T. Toffoli 'Reversible Computing', in Automata, Languages and Programming , eds. J. W. de Bakker and J. van Leeuwen (Springer, New York, 1980), p. 632; Technical Memo MIT/LCS/TM-151, MIT Lab. for Comp. Sci. (unpublished). -Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Quantum logic gates can always be constructed with no workspace whatsoever.

“By contrast, we show that the quantum logic gates can always be constructed with the use of no workspace whatsoever.”

The set of all one-bit quantum gates (U(2)) together with the two-bit exclusive-or gate is universal: every unitary operation on arbitrarily many bits n (U(2^n)) can be expressed as a composition of these gates.

“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 ⊕ 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.”

By combining the quantum gate constructions introduced here with the decomposition formulas of Reck et al. [15], an explicit, exact simulation of any unitary operator on n bits can be constructed using Θ(n^3 4^n) two-bit gates (basic operations) and no work bits.

“Finally, we mention that by combining the quantum gate constructions introduced here with the decomposition formulas for unitary matrices as used by Reck al. [15], an explicit, exact simulation of any unitary operator on n bits can be constructed using a finite number (Θ( n 3 4 n )) of two-bit gates, and using no work bits.”

• Also stated in: § 8 Efficient general gate constructions · p. 28 · plain

  “There are O (4 n ) T 's in the product above, so the total number of basic operations to simulate any U (2 n ) matrix exactly is Θ( n 3 4 n ).”

• cites [15] [15] M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani, 'Experimental realization of any discrete unitary operator', Phys. Rev. Lett. 73 , 58 (1994). -Not checked yet

  Not checked in the free run.

Any arbitrary three-bit unitary operation can be performed using six two-bit gates, if the two-bit gates may implement any member of U(4).

“It is natural to ask, how many two-bit gates are required to perform any arbitrary three-bit unitary operation, if the two-bit gates were permitted to implement any member of U(4)? The answer is six, as in the gate arrangement shown here.”

More efficient simulations of three-bit gates are possible if phase shifts of quantum states other than zero are permitted.

“We now show that more efficient simulations of three-bit gates are possible if phase shifts of the quantum states other than zero are permitted.”

For any unitary U, a ∧^{n-2}(U) gate can be simulated by an n-bit network of the illustrated form, where the initial value of one bit (the second to last) is fixed at 0 and incurs no net change.

“Lemma 7.11: For any unitary U , a ∧ n -2 ( U ) gate can be simulated by an n -bit network of the form”

• Also stated in: § 7.5 Linear Simulation of General ∧ n -2 ( U ) Gates on n -Bit Networks With One Bit Fixed · p. 25 · plain

  “(illustrated for n = 9 ), where the initial value of one bit (the second to last) is fixed at 0 (and it incurs no net change).”

Using the gate-counting mentioned in Corollary 7.4, the number of basic operations to simulate a ∧^{n-1}(U) gate is 48n^2 + O(n).

“In fact, we find that using the gate-counting mentioned in Corollary 7.4, the number of basic operations is 48 n 2 + O ( n ).”

For the specific W ∈ SU(2) used in Section 5, a transformation congruent modulo phase shifts to the n-bit Toffoli gate ∧^{n-1}(σ_x) can be simulated linearly.

“In this case, we obtain a linear simulation of a transformation congruent modulo phase shifts to the n -bit Toffoli gate ∧ n -1 ( σ x ).”

The technique for simulating ∧2(U) gates in Lemma 6.1 generalizes to ∧m(U) gates for m > 2.

“The technique for simulating ∧ 2 ( U ) gates in Lemma 6.1 generalizes to ∧ m ( U ) gates for m > 2.”

For n = 3, 4, 5, 6, 7, and 8, taking account of mergers, the simulation of arbitrary ∧^{n-1}(U) and ∧^{n-1}(σ_x) gates requires 3·2^{n-1}-4 ∧^1(σ_x) gates and 2·2^{n-1} ∧^0 gates.

“For some specific small values of n (for n = 3, 4, 5, 6, 7, and 8), this is the most efficient technique that we are aware of for simulating arbitrary ∧ n -1 ( U ) gates as well as ∧ n -1 ( σ x ) gates; taking account of mergers (see Corollary 6.2), the simulation requires 3 · 2 n -1 -4 ∧ 1 ( σ x )'s and 2 · 2 n -1 ∧ 0 's.”

For any n ≥ 5 and m ∈ {2, ..., n-3}, a ∧^{n-2}(σ_x) gate can be simulated by a network consisting of two ∧^m(σ_x) gates and two ∧^{n-m-1}(σ_x) gates of the illustrated form.

“Lemma 7.3: For any n ≥ 5 , and m ∈ { 2 , . . . , n -3 } a ∧ n -2 ( σ x ) gate can be simulated by a network consisting of two ∧ m ( σ x ) gates and two ∧ n -m -1 ( σ x ) gates which is of the form”

If n ≥ 5 and m ∈ {3, ..., ⌈n/2⌉}, then a ∧^m(σ_x) gate can be simulated by a network consisting of 4(m-2) ∧^2(σ_x) gates of the illustrated form.

“Lemma 7.2: If n ≥ 5 and m ∈ { 3 , . . . , ⌈ n 2 ⌉} then a ∧ m ( σ x ) gate can be simulated by a network consisting of 4( m -2) ∧ 2 ( σ x ) gates that is of the form”

Any simulation of a nonscalar ∧^{n-1}(U) gate (where U ≠ Ph(δ)·I) requires at least n-1 basic operations.

“Lemma 7.7: Any simulation of a nonscalar ∧ n -1 ( U ) gate (i.e. where U = Ph ( δ ) · I ) requires at least n -1 basic operations.”

In the six-gate construction of an arbitrary three-bit unitary operation, after the third gate the dimensionality increases by nine for each succeeding gate until it reaches exactly 64 at the sixth gate.

“At this point the dimensionality increases by nine for each succeeding gate, until the dimensionality reaches exactly 64, the dimension of U(8), at the sixth gate.”

An alternative simulation of a gate congruent to ∧2(σx) modulo phase shifts, with the same phase shifts as the previous one, is given by the stated network with B = R_y(3π/4).

“An alternative simulation of a gate congruent to ∧ 2 ( σ x ) modulo phase shifts (whose phase shifts are identical to the previous one) is given by”

• Also stated in: § 6.2 Three-bit gates congruent to ∧ 2 ( U ) · p. 16 · plain

  “where B = R y ( 3 π 4 ).”

To simulate a ∧3(U) gate for any unitary U, one sets V so that V^4 = U and constructs the stated network.

“For example, to simulate a ∧ 3 ( U ) gate for any unitary U , set V so that V 4 = U and then construct a network as follows.”

For any unitary U, a ∧^{n-2}(U) gate can be simulated by Θ(n) basic operations in an n-bit network, where the initial value of one bit is fixed and incurs no net change.

“Corollary 7.12: For any unitary U , a ∧ n -2 ( U ) gate can be simulated by Θ( n ) basic operations in n -bit network, where the initial value of one bit is fixed and incurs no net change.”

For most of the gate constructions considered, numerical study provides compelling evidence that the stated gate counts are minimal.

“In no case do we have a proof that this is the most economical method for producing each of these functions; however, for most of these examples we have compelling evidence from numerical study that these are in fact minimal[44].”

• cites [44] [44] D. P. DiVincenzo and J. Smolin, 'Results on two-bit gate design for quantum computers', Proceedings of the Workshop on Physics and Computation, PhysComp '94 (Los Alamitos: IEEE Comp. Soc. Press, 1994), p. 14. (cond-mat/9409111)Not checked yet

  Not checked in the free run.

The gates ∧2(W) and ∧2(σx) can be regarded as congruent modulo phase shifts, because the latter maps |111> to -|110> instead of |110>.

“then the gates ∧ 2 ( W ) and ∧ 2 ( σ x ) can be regarded as being 'congruent modulo phase shifts', because the latter gate differs only in that it maps | 111 〉 to -| 110 〉 (instead of | 110 〉 ).”

For any SU(2) matrix W, a ∧^{n-1}(W) gate can be simulated by a network of the illustrated form, where A, B, and C ∈ SU(2).

“Lemma 7.9: For any SU(2) matrix W , a ∧ n -1 ( W ) gate can be simulated by a network of the form”

For any n ≥ 3 and any unitary 2×2 matrix U, a ∧^{n-1}(U) gate can be simulated by an n-bit network consisting of 2^{n-1}-1 ∧^1(V) and ∧^1(V†) gates and 2^{n-1}-2 ∧^1(σ_x) gates, where V is unitary.

“Lemma 7.1: For any n ≥ 3 and any unitary 2 × 2 matrix U , a ∧ n -1 ( U ) gate can be simulated by an n -bit network consisting of 2 n -1 -1 ∧ 1 ( V ) and ∧ 1 ( V † ) gates and 2 n -1 -2 ∧ 1 ( σ x ) gates, where V is unitary.”

For any unitary U, a ∧^{n-1}(U) gate can be simulated in terms of Θ(n^2) basic operations.

“Corollary 7.6: For any unitary U , a ∧ n -1 ( U ) gate can be simulated in terms of Θ( n 2 ) basic operations.”

In preliminary tests on four-bit operations, the same rules for the increase of dimensionality applied.

“In preliminary tests on four-bit operations, we found that the same rules for the increase of dimensionality applied.”

For any unitary 2×2 matrix U, a ∧^{n-1}(U) gate can be simulated by a network of the illustrated form, where V is unitary.

“Lemma 7.5: For any unitary 2 × 2 matrix U , a ∧ n -1 ( U ) gate can be simulated by a network of the form”

The stated sequence of operations is equivalent to performing V^4 on the fourth bit if and only if x1∧x2∧x3 = 1, which is the ∧3(V^4) gate.

“it can be verified that the above sequence of operations is equivalent to performing V 4 on the fourth bit iff x 1 ∧ x 2 ∧ x 3 = 1, which is the ∧ 3 ( V 4 ) gate.”

Each T(x1,x2) operation can be simulated in Θ(n^3) basic operations.

“Since m , the number of elements in the grey code sequence, cannot exceed n + 1, the number of operations to simulate T ( x 1 , x 2) is Θ( n 3 ).”

For any W ∈ SU(2), a ∧^{n-2}(W) gate can be simulated by Θ(n) basic operations.

“Corollary 7.10: For any W ∈ SU (2) , a ∧ n -2 ( W ) gate can be simulated by Θ( n ) basic operations.”

Reversible computation is a small subset of quantum mechanics: the time evolution of a classical reversible computer is described by unitary operators whose matrix elements are only zero or one, not arbitrary complex numbers.

“While reversible computation is contained within quantum mechanics, it is a small subset: the time evolution of a classical reversible computer is described by unitary operators whose matrix elements are only zero or one - arbitrary complex numbers are not allowed.”

The classical analogue of the assertion that all invertible Boolean functions can be implemented with ∧1(0 1 1 0) and ∧0(0 1 1 0) gates is false.

“This is a remarkable result from the perspective of classical reversible computation because it is well known that the classical analogue of this assertion-which is that all invertible boolean functions can be implemented with ∧ 1 ( 0 1 1 0 ) and ∧ 0 ( 0 1 1 0 ) gates[38] - is false.”

• cites [38] [38] The only non-trivial one-bit classical invertible operation is ( 0 1 1 0 ) . -Not checked yet

  Not checked in the free run.

Almost any single ∧1(U) gate is universal: by successive application to pairs of bits in an n-bit network, any unitary transformation may be approximated with arbitrary accuracy.

“As shown by one of us [31, 29], 'almost any' single ∧ 1 ( U ) gate is universal in the sense that: by successive application of this gate to pairs of bits in an n -bit network, any unitary transformation may be approximated with arbitrary accuracy.”

• cites [31] [31] D. Deutsch, A. Barenco, and A. Ekert, 'Universality in quantum computation', submitted to Proc. R. Soc. Lond. (1995). -Not checked yet

  Not checked in the free run.

• cites [29] [29] A. Barenco, 'A universal two-bit gate for quantum computation', preprint (1994). -Not checked yet

  Not checked in the free run.

A quantum computer with m physical bits can perform unitary operations in a space of 2^m dimensions, exponentially larger than its physical size.

“By contrast a quantum computer with m physical bits (see definition of the state above) can perform unitary operations in a space of 2 m dimensions, exponentially larger than its physical size.”

Almost all unitary transformations will be computationally uninteresting, since they will require exponentially many operations to implement.

“It is clear that 'almost all' unitary transformations will be computationally uninteresting, since they will require exponentially many operations to implement.”

Toffoli showed that the classical ∧m gates could not be built without work bits to store intermediate results.

“Toffoli showed[4] that the classical ∧ m 's could not be built without the presence of some 'work bits' to store intermediate results of the calculation.”

• cites [4] [4] T. Toffoli 'Reversible Computing', in Automata, Languages and Programming , eds. J. W. de Bakker and J. van Leeuwen (Springer, New York, 1980), p. 632; Technical Memo MIT/LCS/TM-151, MIT Lab. for Comp. Sci. (unpublished). -Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

The above constructions require at least one extra bit: an n-bit network is required to simulate the (n-1)-bit gate ∧^{n-2}(σ_x).

“The above constructions, though asymptotically efficient, requires at least one 'extra' bit, in that an n -bit network is required to simulate the ( n -1)-bit gate ∧ n -2 ( σ x ).”

Since the number of gates in the Lemma 7.1 simulation is Θ(2^n), that simulation is very inefficient for large values of n.

“However, since this number is Θ(2 n ), the simulation is very inefficient for large values of n .”

If two networks approximate each other within ε, then for any event the probability of the event differs by at most 2ε between the two networks.

“Suppose that two networks that are approximately the same (in the above sense) are executed with identical inputs and their outputs are observed. Then the probability distributions of the two outcomes will be approximately the same in the sense that, for any event, its probability will differ by at most 2 ε between the two networks.”

• cites [33] [33] D. Coppersmith, 'An approximate Fourier transform useful in quantum factoring', IBM Research Report RC19642 (1994); R. Cleve, 'A note on computing Fourier transforms by quantum programs', unpublished note (1994). -Not checked yet

  Not checked in the free run.

The strict upper bound Θ(n^3 4^n) differs only by a polynomial factor from the expected lower bound quoted earlier.

“So, we see that this strict upper bound differs only by a polynomial factor (which likely can be made better than n 3 ) from the expected lower bound quoted earlier”