dorsal/arxiv
View SchemaSmaller Circuits for Arbitrary n-qubit Diagonal Computations
| Authors | Stephen S. Bullock, Igor L. Markov |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0303039 |
| URL | https://arxiv.org/abs/quant-ph/0303039 |
| Journal | Quantum Information & Computation, vol 4, no 1, 027-047 (2004) |
Abstract
A unitary operator U=\sum u_{j,k} |k><j| is called diagonal when u_{j,k}=0 unless j=k. The definition extends to quantum computations, where j and k vary over the 2^n binary expressions for integers 0,1 ..., 2^n-1, given n qubits. Such operators do not affect outcomes of the projective measurement {<j| ; 0 <= j <= 2^n-1} but rather create arbitrary relative phases among the computational basis states {|j> ; 0 <= j <= 2^n-1}. These relative phases are often required in applications. Constructing quantum circuits for diagonal computations using standard techniques requires either O(n^2 2^n) controlled-not gates and one-qubit Bloch sphere rotations or else O (n 2^n) 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 2^{n+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 R_z(\alpha)=e^{-i \alpha/2}|0><0|+ e^{i \alpha/2} |1><1|, then a cancellation of controlled-not gates reduces our circuit to that of an n-qubit tensor.
{
"annotation_id": "2924a3c9-a8b1-4fdd-b73d-55c9dd1e89ab",
"date_created": "2026-03-02T18:01:56.266000Z",
"date_modified": "2026-03-02T18:01:56.266000Z",
"file_hash": "f59813ff9b521d14ccf5288365bb1abde7cebbc8bd9d26f3a9ec4ca8bad89d67",
"private": false,
"record": {
"abstract": "A unitary operator U=\\sum u_{j,k} |k\u003e\u003cj| is called diagonal when u_{j,k}=0\nunless j=k. The definition extends to quantum computations, where j and k vary\nover the 2^n binary expressions for integers 0,1 ..., 2^n-1, given n qubits.\nSuch operators do not affect outcomes of the projective measurement {\u003cj| ; 0 \u003c=\nj \u003c= 2^n-1} but rather create arbitrary relative phases among the computational\nbasis states {|j\u003e ; 0 \u003c= j \u003c= 2^n-1}. These relative phases are often required\nin applications.\n Constructing quantum circuits for diagonal computations using standard\ntechniques requires either O(n^2 2^n) controlled-not gates and one-qubit Bloch\nsphere rotations or else O (n 2^n) such gates and a work qubit. This work\nprovides a recursive, constructive procedure which inputs the matrix\ncoefficients of U and outputs such a diagram containing 2^{n+1}-3 alternating\ncontrolled-not gates and one-qubit z-axis Bloch sphere rotations. Up to a\nfactor of two, these circuits are the smallest possible. Moreover, should the\ncomputation U be a tensor of diagonal one-qubit computations of the form\nR_z(\\alpha)=e^{-i \\alpha/2}|0\u003e\u003c0|+ e^{i \\alpha/2} |1\u003e\u003c1|, then a cancellation\nof controlled-not gates reduces our circuit to that of an n-qubit tensor.",
"arxiv_id": "quant-ph/0303039",
"authors": [
"Stephen S. Bullock",
"Igor L. Markov"
],
"categories": [
"quant-ph"
],
"journal_ref": "Quantum Information \u0026 Computation, vol 4, no 1, 027-047 (2004)",
"title": "Smaller Circuits for Arbitrary n-qubit Diagonal Computations",
"url": "https://arxiv.org/abs/quant-ph/0303039"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "96f10f01-fb9f-4b77-8f68-bb1bedc85566",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}