PaperlayerView exact revision on arXiv

Source-linked AI summary

The geometry of quantum computation

Mark R. Dowling, Michael A. Nielsen

arXiv:quant-ph/0701004v1quant-ph

TL;DR

The paper addresses how geometric methods can help analyze quantum circuit complexity when the circuit picture offers few principles for deriving locally optimal constructions. It studies a weighted geometry of unitary operations and derives geodesic invariants, while noting that identifying useful target unitaries and globally minimal paths remains a challenge.

Abstract

from arXiv · show

Determining the quantum circuit complexity of a unitary operation is closely related to the problem of finding minimal length paths in a particular curved geometry [Nielsen et al, Science 311, 1133-1135 (2006)]. This paper investigates many of the basic geometric objects associated to this space, including the Levi-Civita connection, the geodesic equation, the curvature, and the Jacobi equation. We show that the optimal Hamiltonian evolution for synthesis of a desired unitary necessarily obeys a simple universal geodesic equation. As a consequence, once the initial value of the Hamiltonian is set, subsequent changes to the Hamiltonian are completely determined by the geodesic equation. We develop many analytic solutions to the geodesic equation, and a set of invariants that completely determine the geodesics. We investigate the problem of finding minimal geodesics through a desired unitary, U, and develop a procedure which allows us to deform the (known) geodesics of a simple and well understood metric to the geodesics of the metric of interest in quantum computation. This deformation procedure is illustrated using some three-qubit numerical examples. We study the computational complexity of evaluating distances on Riemmanian manifolds, and show that no efficient classical algorithm for this problem exists, subject to the assumption that good pseudorandom generators exist. Finally, we develop a canonical extension procedure for unitary operations which allows ancilla qubits to be incorporated into the geometric approach to quantum computing.

I. INTRODUCTION

The paper frames quantum circuit complexity as a geometric path-length problem and develops the geometry needed to analyze it. It connects a weighted metric on unitary operations to gate complexity, then outlines tools for studying geodesics and their limitations.

I. INTRODUCTION

  • The paper develops geometric tools for circuit complexity because general principles for finding efficient circuits or proving their absence remain scarce.It derives the Levi-Civita connection and studies geodesics, invariants, curvature, Jacobi fields, and conjugate points.Source: §I · p. 1

II. QUANTUM CIRCUIT COMPLEXITY AND GEOMETRY

  • The metric distance from the identity to a unitary is related to the number of gates needed to synthesize it, making distance a measure of synthesis difficulty.For the standard metric, distance lower-bounds exact gate complexity and upper-bounds approximate gate complexity.Source: §I · p. 1, §II · p. 3

I. INTRODUCTION

  • Optimal Hamiltonian evolutions satisfy a universal geodesic equation, with constants of motion and exact solutions that include the general three-qubit case.Once the initial Hamiltonian is set, the equation determines its subsequent evolution.Source: §I · p. 1
  • A geodesic-deformation procedure seeks paths to target unitaries by smoothly transforming geodesics of a well-understood metric, with numerical examples including random unitaries and the quantum Fourier transform.Jacobi fields and conjugate points inform conditions for the geodesic derivative used in the procedure.Source: §I · pp. 1–2
  • The paper identifies obstacles to geometric complexity analysis, including a likely lack of efficient classical algorithms for general geodesic finding under stated assumptions, and introduces canonical extensions to incorporate ancillas.The authors suggest that lower-bound proofs may need non-generic properties of specific unitaries.Source: §I · p. 2

III. THE CONNECTION

The section derives the Levi-Civita connection by expressing the metric in local Pauli coordinates near the identity and then using right-invariance. The resulting connection formulas apply across the manifold and simplify for right-invariant vector fields.

III. THE CONNECTION

  • The derivation rewrites the metric in Pauli coordinates to compute the Christoffel coefficients, then obtains coordinate-independent formulas for the connection.The approach also introduces notation used in later sections and supports curvature calculations.Source: §III · p. 4
  • Pauli coordinates express a nearby unitary as U = e^-iX, with the coefficients of X in the Pauli basis serving as coordinates for evaluating the connection at the identity.Right-invariance then extends the resulting connection expression across the manifold.Source: §III · pp. 4–5
  • For right-invariant vector fields, the connection formula simplifies, holds everywhere, and satisfies ⟨X, ∇Y Z⟩ = −⟨∇Y X, Z⟩.The formula’s derivation extends beyond Pauli matrices when the basis is orthonormal under the trace inner product.Source: §III · p. 5

IV. GEODESICS

The section derives a geodesic equation that determines locally optimal Hamiltonian evolution on the right-invariant metric. Geodesics are necessary, but not sufficient, for identifying globally minimal paths.

A. The geodesic equation

  • A geodesic is a curve whose tangent Hamiltonian is parallel transported along the curve, yielding the geodesic equation for its evolution.The equation can be written in terms of the dual L = G(H), and the standard metric gives a simplified form.Source: A. The geodesic equation · p. 6
  • The universal geodesic equation determines minimal-length paths through the evolution of the Hamiltonian from its initial value.In the standard circuit model, the Hamiltonian may instead have arbitrary time dependence; the geometric approach may include exponentially small three- and higher-body terms.Source: A. The geodesic equation · p. 6
  • Being a geodesic is necessary but not sufficient for global minimality, so finding paths to a target unitary is only a first step toward determining its distance.Multiple geodesics may connect the identity and the target, and not all are globally minimizing.Source: A. The geodesic equation · p. 6

B. Constants of the motion

The paper identifies constants of motion that determine geodesics and develops analytic solutions, including constant-Hamiltonian paths and a three-qubit solution in the large-penalty limit. These results do not by themselves identify the globally minimal path to a target unitary.

B. Constants of the motion

  • The matrix U(t)†L(t)U(t) is constant along geodesics and completely determines them; for the standard metric, one-body Hamiltonian coefficients are also conserved.The latter conservation follows because the relevant commutator contributes no one-body terms.Source: B. Constants of the motion · pp. 6–7

C. Analytic solutions to the geodesic equation

  • The paper develops partial and full analytic solutions, including a formal power-series approach to the geodesic equation.The solution methods are mostly specialized to projective metrics.Source: C. Analytic solutions to the geodesic… · p. 7

1. Geodesics where the Hamiltonian is constant

  • For projective metrics in the large-q case, a geodesic has constant Hamiltonian exactly when [Q(H), P(H)] = 0.Under the standard metric, any Hamiltonian containing only one- and two-body terms therefore generates a geodesic through exp(−iHt).Source: §1 · p. 7

2. Geodesics for three qubits

  • For three qubits, the standard metric admits an exact geodesic solution in the q → ∞ limit, but which such geodesic minimizes length to a given target remains unclear.The section’s derivation uses commutation relations among the one-, two-, and three-body Hamiltonian subspaces.Source: §2 · pp. 7–8

3. Formal solution of the geodesic equation

The section develops a formal power-series solution for bilinear geodesic equations by working with the dual variable and vectorizing the equation. This framework includes the geodesic equation for any right-invariant metric.

3. Formal solution of the geodesic equation

  • The formal series is developed for the dual variable L(t), which obeys ˙L = i[L, F(L)].The section then expresses the vectorized solution |L(t)) through the derivatives of L at t = 0.Source: §3 · pp. 8–9
  • Vectorization makes the derivatives of L(t) easier to evaluate than computing them directly from the geodesic equation.It converts matrices into vectors and linear maps on matrices into matrix operations on vectors.Source: §3 · pp. 8–9
  • For any equation of the form ˙L = E(L, L) with bilinear E, the formal-solution framework applies, including to geodesic equations for right-invariant metrics.Vectorization turns the matrix equation into an equation for |L).Source: §3 · p. 8

V. GEODESIC DEFORMATION AND CONJUGATE POINTS

This section develops tools for locating minimal geodesics to a target unitary, including tests for when geodesics cease to minimize and a method for deforming geodesics while holding endpoints fixed. Its lifted Jacobi equation characterizes local changes in geodesics as the metric varies.

V. GEODESIC DEFORMATION AND CONJUGATE POINTS

  • The section addresses finding a minimal geodesic from the identity to a specified unitary using conjugate-point analysis and fixed-endpoint geodesic deformation.The deformation approach is intended to address the high dimensionality that makes traditional shooting methods ineffective.Source: §V · p. 9
  • Jacobi fields and conjugate points connect local curvature properties to whether a geodesic is globally minimizing.They identify examples that are local length minima but not global minima, including one- and two-body Hamiltonian geodesics beyond certain times.Source: §V · p. 9

A. Lifted Jacobi equation

  • The lifted Jacobi equation describes local changes in a base geodesic as the metric varies, and its solutions correspond to families of geodesics for the varying metrics.It generalizes the conventional Jacobi equation, which describes nearby geodesics for a fixed metric.Source: A. Lifted Jacobi equation · pp. 9–10
  • With initial position and tangent held fixed, the lifted-Jacobi solution is obtained from the conventional Jacobi propagator and an integral determined by the metric derivative.The equation is a linear, inhomogeneous second-order differential equation.Source: A. Lifted Jacobi equation · p. 10

B. Lifted Jacobi equation for varying penalty

For the penalty family Gq = P + qQ, the paper specializes the lifted Jacobi equation to right-invariant metrics and obtains an explicit solution when the Hamiltonian is constant. In that case, the geodesic does not change as q varies.

B. Lifted Jacobi equation for varying penalty

  • The analysis uses the parameterized metric family Gq = P + qQ, for which G′ = Q, and derives a formal lifted-Jacobi solution for right-invariant metrics.An explicit solution is obtained along geodesics with constant Hamiltonian H.Source: B. Lifted Jacobi equation for varying… · pp. 10–11
  • For a general right-invariant metric, the lifted Jacobi equation is an inhomogeneous first-order linear equation in K, the first-order Hamiltonian perturbation, which can be integrated and then integrated again to obtain J(t).The conventional Jacobi equation is recovered when G′ = 0.Source: B. Lifted Jacobi equation for varying… · p. 11
  • For constant-H geodesics, the lifted and conventional Jacobi equations coincide, so the geodesic remains unchanged as the penalty q varies.The inhomogeneous contribution vanishes along a constant-H geodesic.Source: B. Lifted Jacobi equation for varying… · pp. 10–11

C. Conjugate points

Conjugate points provide a way to establish that a geodesic is no longer minimizing, although their absence does not guarantee minimality. The paper applies this test to fixed-Hamiltonian geodesics and reports a three-qubit transverse Ising example.

C. Conjugate points

  • A geodesic is no longer minimizing past its first conjugate point, which can be detected when the Jacobi propagator block E2 becomes singular.The conjugate-point test can be computed by integrating the Jacobi equation, with resources scaling polynomially in the manifold dimension in this setting.Source: C. Conjugate points · pp. 11–12
  • For sufficiently long times, fixed-Hamiltonian geodesics are not minimizing; for e^-iZt, applying −Z is more efficient when π > t > π/2.Over sufficiently short periods, such geodesics are guaranteed to be globally minimal.Source: C. Conjugate points · p. 12
  • The conjugate-point condition is sufficient but not necessary for non-minimality: a shorter global path may exist before a conjugate point is reached.Thus the test can certify non-minimality, but failure to find a conjugate point does not establish minimality.Source: C. Conjugate points · p. 12
  • For three qubits with h = 1 and q = 64, the first conjugate point occurs at tc ≈ 1.54, after which the studied geodesic is no longer minimizing.The authors infer non-minimality by studying conjugate points rather than explicitly finding a shorter geodesic.Source: C. Conjugate points · p. 12, Figure 1 · p. 12

D. Geodesic derivative

The geodesic derivative describes how a geodesic’s initial tangent changes as the metric varies, and it is uniquely defined exactly when the endpoints are not conjugate. The paper uses this derivative to deform geodesics toward target unitaries, with numerical examples and caveats about conjugate points and minimality.

D. Geodesic derivative

  • The geodesic derivative is the change in the initial tangent as the metric varies while the endpoints remain fixed.It is defined from a family of geodesics with fixed endpoints.Source: D. Geodesic derivative · pp. 12–13
  • A geodesic derivative exists and is unique if and only if the endpoints are not conjugate along the geodesic.The proof also shows that a derivative satisfying Equation (81) remains valid when uniqueness fails.Source: D. Geodesic derivative · p. 13

E. Numerically finding geodesics

  • The procedure starts from a q = 1 Hamiltonian generating the target, then varies q while integrating the change in the initial Hamiltonian given by the geodesic derivative.The paper uses a computationally convenient expression for the corresponding change in the initial dual Hamiltonian.Source: E. Numerically finding geodesics · pp. 13–14
  • For Haar-random three-qubit unitaries, canonical-Hamiltonian deformations empirically show no conjugate points and converge in the large-q limit.The figure shows the q = 64 trajectory reaching the target at T = 1.Source: E. Numerically finding geodesics · p. 14, Figure 2 · p. 15
  • Some alternative starting Hamiltonians can encounter endpoint conjugate points, making deformation not well-defined, although the numerical procedure sometimes still reaches the target.For these starts, the initial dual Hamiltonian tends not to converge as q grows.Source: E. Numerically finding geodesics · p. 14
  • For the three-qubit quantum Fourier transform, the propagator becomes nearly singular near q ≈ 6, yet deformation still yields a geodesic reaching the target at q = 16.The smallest eigenvalue is approximately 10^-6; the authors report that the derivative appears non-unique in this regime.Source: E. Numerically finding geodesics · p. 14, Figure 3 · p. 15
  • Geodesic lengths increase monotonically with q, but new geodesics may appear at large q that cannot be reached by deforming a q = 1 geodesic.The proposed search can restrict q = 1 starts to a finite set when testing for a length below a threshold; endpoint conjugate points are another caveat.Source: E. Numerically finding geodesics · pp. 14, 16
  • Any geodesic from the identity to a target gives an upper bound on its distance, but further mathematical study is needed to establish the deformation procedure’s usefulness for finding minimal curves.In the large-q limit, the paper says such geodesics can be approximated by sequences of one- and two-qubit gates using [5].Source: E. Numerically finding geodesics · p. 16

VI. WHAT CAN GEOMETRY TEACH US ABOUT QUANTUM COMPUTATION?

The paper examines obstacles to using geometry to analyze quantum circuit complexity, including the computational difficulty of distance evaluation. It proves a conditional classical hardness result for the standard metric, discusses ancilla extensions, and concludes that substantial further progress is needed.

VI. WHAT CAN GEOMETRY TEACH US ABOUT QUANTUM COMPUTATION?

  • The paper develops a basic understanding of the metric’s geometry, but says substantial further progress is needed for new quantum algorithms or computational-complexity limits.Source: §VI · p. 16
  • The geometric bounds discussed apply only to circuits without ancillary working qubits; the paper introduces a canonical extension procedure to incorporate ancillas.Source: §VI · p. 16

A. The Razborov-Rudich theorem and the computational complexity of finding geodesics

  • If good classical pseudorandom generators exist, no efficient classical algorithm can distinguish unitaries requiring small quantum circuits from those requiring large ones.The argument also rules out efficient evaluation of the distance function under the stated setting.Source: A. The Razborov-Rudich theorem and the… · p. 17
  • If classical pseudorandom generators exist, no classical algorithm polynomial in 2^n can accurately approximate the standard-metric distance on SU(2^n) when q > 4^n.For q = 1, the distance can be evaluated in polynomial time.Source: A. The Razborov-Rudich theorem and the… · p. 17
  • The authors describe the Razborov-Rudich result as a barrier any approach to proving circuit lower bounds must address, not as an obstacle unique to geometry.Source: A. The Razborov-Rudich theorem and the… · p. 17

B. Extending the geometric picture to take account of ancilla

Ancillas complicate the geometric approach because low-gate extensions can be cheaper to synthesize than the original unitary. The section develops canonical extensions that connect ancilla-assisted complexity to geometric distances for many, but not all, unitaries.

B. Extending the geometric picture to take account of ancilla

  • The method applies to many, not all, unitaries: circuits with ancillas are put into canonical form, including for permutation-function and computational-basis-diagonal unitaries.The section presents this as a way to apply geometric analysis when ancillas are allowed.Source: B. Extending the geometric picture to… · p. 17
  • An m + 1-fold canonical extension Um lets the complexity of an ancilla-assisted unitary be bounded using the complexity and geometric distance of a fixed unitary without ancillas.The bounds relating approximate ancilla-assisted complexity to the extension’s distance go in one direction; an approximate-complexity analogue supplies a bound in the other direction.Source: B. Extending the geometric picture to… · pp. 17–18
  • For Boolean functions, the quantum complexity of computing f is essentially captured by the special-extension complexities of Uf and Vf, so the extension bounds apply to these unitaries.Uf computes f into a target bit, while Vf encodes f as a phase.Source: B. Extending the geometric picture to… · pp. 18–19
  • If G∞(U) ∼ ˜G∞(U), a distance d(I, Un2) exceeding a suitable quadratic-scale threshold implies at least Ω(n2) gates to synthesize U.The excess beyond (c2/c1)n2 contributes to the gate-complexity bound.Source: B. Extending the geometric picture to… · p. 19
  • The proposition shows rapid scaling in G∞(U, ε) implies rapid scaling in d(I, U^m); as a result, approximation difficulty implies exact-computation difficulty, even with ancillas.Source: B. Extending the geometric picture to… · p. 19
  • Under the stated conditions, exponential growth in approximate complexity yields exponential lower bounds on exact complexity with ancillas.The section gives a conditional example based on G∞(U, 1/10) = Ω(2^c1n).Source: B. Extending the geometric picture to… · p. 19

VII. CONCLUSION

The paper develops the basic geometry of quantum computation and a procedure for deforming geodesics to connect the identity to a desired unitary.

VII. CONCLUSION

  • The paper develops the Levi-Civita connection, geodesic equation, its solutions and invariants, and the basic curvature quantities.Together, these results give a more or less complete picture of the basic geometry of quantum computation.Source: §VII · p. 19
  • A geodesic-deformation procedure can find geodesics from the identity I to a desired unitary U in many cases of interest.The authors describe this work as a foundation for more detailed understanding.Source: §VII · pp. 19–20

APPENDIX A: CURVATURE

The appendix derives curvature quantities for the standard metric, starting from an explicit curvature-tensor expression. It also characterizes sectional curvature and gives Ricci-tensor results useful for studying metric flow.

1. Curvature tensor

  • For the standard metric, the curvature tensor’s basic expression has additional sparsity conditions: nonzero components require specified commutation and anticommutation relations among the indices.The expression is used to derive other curvature quantities.Source: Appendix A · p. 20, §1 · p. 21

2. Sectional curvature

  • For q > 4/3, sectional curvature can take both positive and negative values.The appendix obtains this from its sectional-curvature formula.Source: §2 · p. 21

3. Ricci tensor

  • The Ricci tensor is diagonal, and the appendix derives its entries and weight-dependent formulas for metrics whose diagonal entries depend only on Pauli weight.These formulas also provide expressions useful for numerically simulating normalized Ricci flow.Source: §3 · pp. 21–22
  • Numerical investigations suggest that normalized Ricci flow takes the standard metric to the bi-invariant metric with q = 1, up to an overall scaling factor.For weight-dependent diagonal metrics, the appendix derives expressions for the Ricci tensor and scalar curvature used to simulate the flow.Source: §3 · p. 22

4. Scalar curvature

The scalar curvature is related to sectional curvature and is necessarily negative when q ∼ 4n. The appendix notes that the corresponding relationship for smaller q remains unresolved.

4. Scalar curvature

  • When q ∼ 4n, scalar curvature is necessarily negative; whether a relationship like Equation (5) holds for smaller q remains open.The proof in that Equation (5) holds also requires q ∼ 4n or larger.Source: §4 · p. 23
  • Scalar curvature is the average of sectional curvature, and typical sectional-curvature values are suggested to be negative.The authors conjecture that this may produce ergodic and mixing geodesic-flow behavior on at least parts of the manifold, with possible implications for quantum computation.Source: §4 · p. 23
Loading quant-ph/0701004v1…