Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Smaller Circuits for Arbitrary n-qubit Diagonal Computations



Stephen Bullock, I L. Markov


A unitary operator U=Sj,ku j,k|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(n22n) controlled-not gates and one-qubit Bloch sphere rotations or else O(n2n)$ 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 diagrams are the smallest possible. Moreover, they respect the tensor product in the following sense. Should the computation U be a tensor of diagonal one-qubit computations of the form Rz( a) = te-i a/2|1>
Quantum Information & Computation


character, diagonal quantum computation, relative phase


Bullock, S. and Markov, I. (2003), Smaller Circuits for Arbitrary n-qubit Diagonal Computations, Quantum Information & Computation, [online], (Accessed May 23, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created February 25, 2003, Updated February 17, 2017