dorsal/arxiv
View SchemaA geometric approach to quantum circuit lower bounds
| Authors | Michael A. Nielsen |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0502070 |
| URL | https://arxiv.org/abs/quant-ph/0502070 |
Abstract
What is the minimal size quantum circuit required to exactly implement a specified n-qubit unitary operation, U, without the use of ancilla qubits? We show that a lower bound on the minimal size is provided by the length of the minimal geodesic between U and the identity, I, where length is defined by a suitable Finsler metric on SU(2^n). The geodesic curves of such a metric have the striking property that once an initial position and velocity are set, the remainder of the geodesic is completely determined by a second order differential equation known as the geodesic equation. This is in contrast with the usual case in circuit design, either classical or quantum, where being given part of an optimal circuit does not obviously assist in the design of the rest of the circuit. Geodesic analysis thus offers a potentially powerful approach to the problem of proving quantum circuit lower bounds. In this paper we construct several Finsler metrics whose minimal length geodesics provide lower bounds on quantum circuit size, and give a procedure to compute the corresponding geodesic equation. We also construct a large class of solutions to the geodesic equation, which we call Pauli geodesics, since they arise from isometries generated by the Pauli group. For any unitary U diagonal in the computational basis, we show that: (a) provided the minimal length geodesic is unique, it must be a Pauli geodesic; (b) finding the length of the minimal Pauli geodesic passing from I to U is equivalent to solving an exponential size instance of the closest vector in a lattice problem (CVP); and (c) all but a doubly exponentially small fraction of such unitaries have minimal Pauli geodesics of exponential length.
{
"annotation_id": "861a0a76-d910-4e2a-aa6a-21ec5eaeb6f1",
"date_created": "2026-03-02T18:02:13.571000Z",
"date_modified": "2026-03-02T18:02:13.571000Z",
"file_hash": "a8c1db389fd3a4c1d9190b3c08b1ddbc5e0b14e0a2aecb6df07fe06d1079e36a",
"private": false,
"record": {
"abstract": "What is the minimal size quantum circuit required to exactly implement a\nspecified n-qubit unitary operation, U, without the use of ancilla qubits? We\nshow that a lower bound on the minimal size is provided by the length of the\nminimal geodesic between U and the identity, I, where length is defined by a\nsuitable Finsler metric on SU(2^n). The geodesic curves of such a metric have\nthe striking property that once an initial position and velocity are set, the\nremainder of the geodesic is completely determined by a second order\ndifferential equation known as the geodesic equation. This is in contrast with\nthe usual case in circuit design, either classical or quantum, where being\ngiven part of an optimal circuit does not obviously assist in the design of the\nrest of the circuit. Geodesic analysis thus offers a potentially powerful\napproach to the problem of proving quantum circuit lower bounds. In this paper\nwe construct several Finsler metrics whose minimal length geodesics provide\nlower bounds on quantum circuit size, and give a procedure to compute the\ncorresponding geodesic equation. We also construct a large class of solutions\nto the geodesic equation, which we call Pauli geodesics, since they arise from\nisometries generated by the Pauli group. For any unitary U diagonal in the\ncomputational basis, we show that: (a) provided the minimal length geodesic is\nunique, it must be a Pauli geodesic; (b) finding the length of the minimal\nPauli geodesic passing from I to U is equivalent to solving an exponential size\ninstance of the closest vector in a lattice problem (CVP); and (c) all but a\ndoubly exponentially small fraction of such unitaries have minimal Pauli\ngeodesics of exponential length.",
"arxiv_id": "quant-ph/0502070",
"authors": [
"Michael A. Nielsen"
],
"categories": [
"quant-ph"
],
"title": "A geometric approach to quantum circuit lower bounds",
"url": "https://arxiv.org/abs/quant-ph/0502070"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "211ab2bd-7ffd-46b3-a9f1-d327c047cff0",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}