dorsal/arxiv
View SchemaOn the Quantum Circuit Complexity Equivalence
| Authors | Milosh Drezgich, Shankar Sastry |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0703082 |
| URL | https://arxiv.org/abs/quant-ph/0703082 |
Abstract
Nielsen \cite{Nielsen05} recently asked the following question: "What is the minimal size quantum circuit required to exactly implement a specified $% \mathit{n}$-qubit unitary operation $U$, without the use of ancilla qubits?" Nielsen was able to prove that a lower bound on the minimal size circuit is provided by the length of the geodesic between the identity $I$ and $U$, where the length is defined by a suitable Finsler metric on $SU(2^{n})$. We prove that the minimum circuit size that simulates $U$ is in linear relation with the geodesic length and simulation parameters, for the given Finsler structure $F$. As a corollary we prove the highest lower bound of $O(\frac{% n^{4}}{p}d_{F_{p}}^{2}(I,U)L_{F_{p}}(I,\tilde{U})) $and the lowest upper bound of $\Omega (n^{4}d_{F_{p}}^{3}(I,U))$, for the standard simulation technique. Therefore, our results show that by standard simulation one can not expect a better then $n^{2}$ times improvement in the upper bound over the result from Nielsen, Dowling, Gu and Doherty \cite{Nielsen06}. Moreover, our equivalence result can be applied to the arbitrary path on the manifold including the one that is generated adiabatically.
{
"annotation_id": "baa32f8d-7d2c-4aa0-bb42-46ce8fde4556",
"date_created": "2026-03-02T18:02:34.710000Z",
"date_modified": "2026-03-02T18:02:34.710000Z",
"file_hash": "6058337db81d59e3f229974accc10f7fbd12139ae451f1e786d4877c7ed2bd9f",
"private": false,
"record": {
"abstract": "Nielsen \\cite{Nielsen05} recently asked the following question: \"What is the\nminimal size quantum circuit required to exactly implement a specified $%\n\\mathit{n}$-qubit unitary operation $U$, without the use of ancilla qubits?\"\nNielsen was able to prove that a lower bound on the minimal size circuit is\nprovided by the length of the geodesic between the identity $I$ and $U$, where\nthe length is defined by a suitable Finsler metric on $SU(2^{n})$. We prove\nthat the minimum circuit size that simulates $U$ is in linear relation with the\ngeodesic length and simulation parameters, for the given Finsler structure $F$.\nAs a corollary we prove the highest lower bound of $O(\\frac{%\nn^{4}}{p}d_{F_{p}}^{2}(I,U)L_{F_{p}}(I,\\tilde{U})) $and the lowest upper bound\nof $\\Omega (n^{4}d_{F_{p}}^{3}(I,U))$, for the standard simulation technique.\nTherefore, our results show that by standard simulation one can not expect a\nbetter then $n^{2}$ times improvement in the upper bound over the result from\nNielsen, Dowling, Gu and Doherty \\cite{Nielsen06}. Moreover, our equivalence\nresult can be applied to the arbitrary path on the manifold including the one\nthat is generated adiabatically.",
"arxiv_id": "quant-ph/0703082",
"authors": [
"Milosh Drezgich",
"Shankar Sastry"
],
"categories": [
"quant-ph"
],
"title": "On the Quantum Circuit Complexity Equivalence",
"url": "https://arxiv.org/abs/quant-ph/0703082"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "88bbc192-4132-4c3e-b815-920a05ce9b65",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}