Elementary gates for quantum computation

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

What the sources say

• ?Not matched

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

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

In the paper

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

In the paper

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

In the paper

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

What the sources say

• Not checked yetcites [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). -

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

“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 paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

What the sources say

• Not checked yetcites [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)

In the paper

“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 〉 ).”

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

In the paper

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

What the sources say

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

In the paper

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

What the sources say

• Not checked yetcites [31] [31] D. Deutsch, A. Barenco, and A. Ekert, 'Universality in quantum computation', submitted to Proc. R. Soc. Lond. (1995). -
• Not checked yetcites [29] [29] A. Barenco, 'A universal two-bit gate for quantum computation', preprint (1994). -

In the paper

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

In the paper

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

In the paper

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

What the sources say

• ?Not matched

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

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

In the paper

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

In the paper

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

In the paper

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

What the sources say

• Not checked yetcites [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). -

In the paper

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