2003/03/31 by Stephen S. Bullock, Igor L. Markov
Physics and Astronomy · #quant-ph
published as Quantum Information & Computation, vol 4, no 1, 027-047 (2004) · v3 improves the results in v1 and achieves asymptotically optimal gate counts v4 makes dimension counting argument rigorous
arxiv created 2003/08/08 · arxiv updated 2009/12/01
A unitary operator U=∑ uj,k |k><j| is called diagonal when uj,k=0 unless j=k. The definition extends to quantum computations, where j and k vary over the 2n binary expressions for integers 0,1 ..., 2n-1, given n qubits. Such operators do not affect outcomes of the projective measurement <j| ; 0 <= j <= 2n-1 but rather create arbitrary relative phases among the computational basis states |j> ; 0 <= j <= 2n-1. These relative phases are often required in applications. Constructing quantum circuits for diagonal computations using standard techniques requires either O(n2 2n) controlled-not gates and one-qubit Bloch sphere rotations or else O (n 2n) such gates and a work qubit. This work provides a recursive, constructive procedure which inputs the matrix coefficients of U and outputs such a diagram containing 2n+1-3 alternating controlled-not gates and one-qubit z-axis Bloch sphere rotations. Up to a factor of two, these circuits are the smallest possible. Moreover, should the computation U be a tensor of diagonal one-qubit computations of the form Rz(α)=e-i α/2|0><0|+ ei α/2 |1><1|, then a cancellation of controlled-not gates reduces our circuit to that of an n-qubit tensor.