dorsal/arxiv
View SchemaAsymptotically Optimal Quantum Circuits for d-level Systems
| Authors | Stephen S. Bullock, Dianne P. O'Leary, Gavin K. Brennen |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0410116 |
| URL | https://arxiv.org/abs/quant-ph/0410116 |
| DOI | 10.1103/PhysRevLett.94.230502 |
| Journal | Physical Review Letters, volume 94, 230502 (2005) |
Abstract
As a qubit is a two-level quantum system whose state space is spanned by |0>, |1>, so a qudit is a d-level quantum system whose state space is spanned by |0>,...,|d-1>. Quantum computation has stimulated much recent interest in algorithms factoring unitary evolutions of an n-qubit state space into component two-particle unitary evolutions. In the absence of symmetry, Shende, Markov and Bullock use Sard's theorem to prove that at least C 4^n two-qubit unitary evolutions are required, while Vartiainen, Moettoenen, and Salomaa (VMS) use the QR matrix factorization and Gray codes in an optimal order construction involving two-particle evolutions. In this work, we note that Sard's theorem demands C d^{2n} two-qudit unitary evolutions to construct a generic (symmetry-less) n-qudit evolution. However, the VMS result applied to virtual-qubits only recovers optimal order in the case that d is a power of two. We further construct a QR decomposition for d-multi-level quantum logics, proving a sharp asymptotic of Theta(d^{2n}) two-qudit gates and thus closing the complexity question for all d-level systems (d finite.) Gray codes are not required, and the optimal Theta(d^{2n}) asymptotic also applies to gate libraries where two-qudit interactions are restricted by a choice of certain architectures.
{
"annotation_id": "45678c2d-9163-4159-9b55-48a8cc9546f6",
"date_created": "2026-03-02T18:02:10.343000Z",
"date_modified": "2026-03-02T18:02:10.343000Z",
"file_hash": "ebf830d0d160ab2f0456c167a4266d07915fb6ae20049e7b49a58d4d95637e29",
"private": false,
"record": {
"abstract": "As a qubit is a two-level quantum system whose state space is spanned by |0\u003e,\n|1\u003e, so a qudit is a d-level quantum system whose state space is spanned by\n|0\u003e,...,|d-1\u003e. Quantum computation has stimulated much recent interest in\nalgorithms factoring unitary evolutions of an n-qubit state space into\ncomponent two-particle unitary evolutions. In the absence of symmetry, Shende,\nMarkov and Bullock use Sard\u0027s theorem to prove that at least C 4^n two-qubit\nunitary evolutions are required, while Vartiainen, Moettoenen, and Salomaa\n(VMS) use the QR matrix factorization and Gray codes in an optimal order\nconstruction involving two-particle evolutions. In this work, we note that\nSard\u0027s theorem demands C d^{2n} two-qudit unitary evolutions to construct a\ngeneric (symmetry-less) n-qudit evolution. However, the VMS result applied to\nvirtual-qubits only recovers optimal order in the case that d is a power of\ntwo. We further construct a QR decomposition for d-multi-level quantum logics,\nproving a sharp asymptotic of Theta(d^{2n}) two-qudit gates and thus closing\nthe complexity question for all d-level systems (d finite.) Gray codes are not\nrequired, and the optimal Theta(d^{2n}) asymptotic also applies to gate\nlibraries where two-qudit interactions are restricted by a choice of certain\narchitectures.",
"arxiv_id": "quant-ph/0410116",
"authors": [
"Stephen S. Bullock",
"Dianne P. O\u0027Leary",
"Gavin K. Brennen"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevLett.94.230502",
"journal_ref": "Physical Review Letters, volume 94, 230502 (2005)",
"title": "Asymptotically Optimal Quantum Circuits for d-level Systems",
"url": "https://arxiv.org/abs/quant-ph/0410116"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c5dad758-3e59-40eb-87f9-c307c79e2063",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}