Source-linked AI summary
Polynomial Equivalence of Complexity Geometries
Adam R. Brown
TL;DR
Different complexity geometries can differ exponentially at short distances, yet some may still match the computational power of quantum circuits. This paper establishes polynomial equivalence for a broad class of such geometries, including gate-counting.
Problem
Complexity geometries can differ exponentially at short distances, raising the question of which still have the computational power of quantum circuits.
Source: §1 · p. 3Method
The paper studies right-invariant metrics on the unitary group and bounds cross-metric approximation slowdown by a polynomial in length and qubit count and inverse-polynomial in permitted error.
Source: §1 · pp. 3–4Results
A broad class of complexity geometries, including gate-counting, is polynomially equivalent in computational power to quantum circuits.
Source: §1 · p. 3Takeaways & Limitations
The equivalence class provides an alternative definition of efficiently performable quantum tasks using primitive operations more permissive than gate or cliff-metric definitions.
Source: §1 · p. 4The sufficient condition cannot be fully relaxed to depend only on the penalty matrix spectrum without regard to its diagonalizing basis.
Source: §7.5.1 · p. 32
Abstract
from arXiv · showhide
This paper proves the polynomial equivalence of a broad class of definitions of quantum computational complexity. We study right-invariant metrics on the unitary group -- often called `complexity geometries' following the definition of quantum complexity proposed by Nielsen -- and delineate the equivalence class of metrics that have the same computational power as quantum circuits. Within this universality class, any unitary that can be reached in one metric can be approximated in any other metric in the class with a slowdown that is at-worst polynomial in the length and number of qubits and inverse-polynomial in the permitted error. We describe the equivalence classes for two different kinds of error we might tolerate: Killing-distance error, and operator-norm error. All metrics in both equivalence classes are shown to have exponential diameter; all metrics in the operator-norm equivalence class are also shown to give an alternative definition of the quantum complexity class BQP. My results extend those of Nielsen et al., who in 2006 proved that one particular metric is polynomially equivalent to quantum circuits. The Nielsen et al. metric is incredibly highly curved. I show that the greatly enlarged equivalence class established in this paper also includes metrics that have modest curvature. I argue that the modest curvature makes these metrics more amenable to the tools of differential geometry, and therefore makes them more promising starting points for Nielsen's program of using differential geometry to prove complexity lowerbounds.
1 Introduction & Summary
The paper extends polynomial equivalence with quantum circuits beyond the cliff metric to a broad class of complexity geometries. It gives sufficient penalty-schedule conditions for emulation in both directions and distinguishes criteria by the tolerated error metric.
1.1 Introduction & Summary
- The paper extends Nielsen et al.’s cliff-metric result [2] to less draconian penalty schedules, with sufficient conditions for polynomially equivalent path lengths.The criterion requires at most polynomial penalties on 2-local directions, a condition the paper says can be significantly relaxed.Source: §1 · p. 4, §1.1.1 · p. 5
- Some geometries in the equivalence class have modest curvature, unlike the highly curved cliff metric, and are presented as more amenable to differential-geometric lower-bound tools.The paper also frames the result as long-distance polynomial equivalence despite exponentially different short-scale behavior.Source: §1 · p. 4
1.1 Summary of results
- The theorems cover metrics diagonal in the generalized-Pauli basis and establish efficient emulation both from geometries to gates and from gates to geometries.The penalty schedule sets the cost of each basis direction; larger penalty factors make motion in that direction more expensive.Source: §1.1 · p. 4
1.1.2 Complexity geometries that can be efficiently emulated by gates
- For gate emulation, Killing-close requires polynomially many directions below any polynomial penalty, while operator-norm closeness has harmonic-sum or weighted-count sufficient tests.The paper evaluates these sufficient conditions on example penalty schedules in Table 1; its columns use Killing/Frobenius and operator-norm error, respectively.Source: §1.1.2 · p. 5
- Operator-norm-equivalent geometries satisfying the stated conditions yield the same high-probability decision problems as BQP.This follows because operator-norm-close unitaries give close output states on the same input state.Source: §1.1.2 · p. 5
2 Defining distance functions on the unitary group
The section defines distances on the unitary group and relates the Killing metric, penalty-based complexity geometries, gate count, and matrix-norm distances. These definitions provide distinct ways to measure paths or separation, with bi-invariance giving a useful error-composition property.
2 Defining distance functions on the unitary group
- Right-invariant distances are unchanged when the same unitary is multiplied on the right, and the paper considers them on the unitary group of N-qubit transformations.The generalized Pauli operators form an orthonormal basis for the tangent space; their weight counts the qubits on which they act nontrivially.Source: §2 · p. 7, §2.1 · p. 7
2.1 Killing metric (bi-invariant Riemannian)
- The Killing distance is the length of the shortest path between unitaries, is bi-invariant, and never exceeds π.Bi-invariance means the distance is unchanged by multiplying both unitaries on either side.Source: §2.1 · p. 8
2.2 Complexity geometry
- Complexity geometries replace the Killing metric’s identity weights with a positive penalty matrix; the paper’s theorems cover matrices diagonal in the generalized-Pauli basis.A penalty factor stretches its basis direction, making motion more expensive when the factor is larger.Source: §2.2 · pp. 8–9
2.3 Gate complexity
- Gate distance counts gates in the shortest circuit, using arbitrary two-qubit unitaries as primitive operations; the cliff metric is bounded above by π times that count.The paper notes that this continuous gate set is polynomially equivalent, in complexity and targeted error, to discrete universal gate sets.Source: §2.3 · pp. 9–10
2.4 Bi-invariant matrix norms
- Bi-invariant matrix norms define distances by the norm of the difference between unitaries, and their bi-invariance makes product errors add at most.The triangle inequality combined with invariance under left and right multiplication gives this composition bound.Source: §2.4 · p. 11
2.4.1 Frobenius norm
- The normalized Frobenius distance is a chord rather than an arc: it agrees with Killing distance infinitesimally but is shorter at finite separation.The paper states that normalized Frobenius distance can be used to bound Killing distance and is often easier to work with.Source: §2.4.1 · pp. 11–12, Figure 1 · p. 12
2.4.2 Operator norm
- Operator-norm closeness requires similar effects on every state, including the worst-case state; the paper bounds the norm using Frobenius and generalized-Pauli quantities.For equal-magnitude eigenvalues the operator norm is at the lower end of the stated range, while highly unequal eigenvalues place it at the upper end.Source: §2.4.2 · p. 13, Table 3 · p. 14
3 Approximating geodesics with gates
The section approximates paths through complexity geometries with two-local gate circuits using pruning, averaging, and Trotterization. It bounds the resulting errors and gate complexity for Killing-distance and operator-norm targets.
3 Approximating geodesics with gates
- For a broad class of penalty schedules, paths of length L can be approximated with two-local gates using a number polynomial in L and the error.This generalizes the polynomial-equivalence result for the cliff schedule [2].Source: §3 · p. 15
3.1 Approximation 1: prune expensive operators
- Pruning removes Hamiltonian terms whose penalty factors exceed a threshold, with separate upper bounds established for Killing-distance and operator-norm error.The operator-norm error is larger than the Killing error.Source: §3.1 · p. 15, §3.1.1 · p. 16, §3.1.2 · p. 16
3.2 Approximation 2: average Hamiltonian
- The path is divided into equal segments and each segment is approximated using its average Hamiltonian, with per-segment error bounds for both distance measures.Averaging replaces following every twist and turn of the path.Source: §3.2 · p. 16, §3.2.1 · p. 17, §3.2.2 · p. 17
3.3 Approximation 3: Trotterize unitary
- Each average Hamiltonian is Trotterized into constituent generalized Pauli operators, with per-segment error bounds for Killing distance and operator norm.The method uses the first-order Trotter approximation.Source: §3.3 · p. 17, §3.3.1 · p. 17, §3.3.2 · p. 17
3.4 Total error from combining segments
- Segment errors add in either metric, and the combined bounds apply when δ < N^-1/2; keeping δ small and the penalty cutoff I large controls the error budget.The total bound sums each segment's error contributions across S = L/(Γδ) segments.Source: §3.4 · p. 18
3.5 Lemma: making monomial unitaries
- A monomial unitary generated by a k-local generalized Pauli can be synthesized exactly with at most 2k − 3 two-local gates.The construction uses the two-local gate model described in the proof.Source: §3.5 · p. 18
3.6.1 The gate complexity of getting Killing close
- For Killing-close targets, the derived gate bound yields a sufficient criterion for polynomial equivalence, with the proof checking that its segment-size condition is self-consistent.The argument uses Γ^2 ≥ 1 and defines N_I as the number of generalized Pauli operators with penalty at most I.Source: §3.6.1 · p. 19
3.6.2 The gate complexity of getting operator-norm close
- For operator-norm targets, the derived bounds give sufficient polynomial-equivalence criteria; the Killing-distance target is easier to reach than the operator-norm target.The paper derives bounds from both terms in a minimum, which may be tighter or looser relative to each other.Source: §3.6.2 · p. 20
4 Bounds for example metrics
The example bounds show that gate equivalence depends on both the penalty schedule and the tolerated error metric. The cliff and binomial metrics meet polynomial gate bounds under stated conditions, while the exponential metric gives only quasi-polynomial bounds for Killing closeness and no tight operator-norm bound from this method.
4.1.1 Cliff metric, Killing close
- Exponential I_cliff makes C_gates polynomial in L and s(error) for polynomial values of both; I_cliff > 4N extends the bound to all values.The super-polynomial but sub-exponential case only covers polynomial L and s(error), not a polynomial gate bound for all values.Source: §4.1.1 · p. 21, §4.1.3 · p. 21
4.1.2 Binomial metric, Killing close
- For the binomial metric, α > 0 gives polynomial equivalence for any L and s(error).The penalty factor for a k-local direction is the αth power of the number of k-local directions.Source: §4.1.2 · p. 21
4.1.3 Exponential metric, Killing close
- For x > 1, the exponential metric gives quasi-polynomial rather than polynomial equivalence for Killing closeness.The gate bound scales like L^(log N/log x), so its exponent grows with N.Source: §4.1.3 · pp. 21–22
4.2.1 Cliff metric, operator-norm close
- For operator-norm closeness, exponentially large 2^-N I_cliff yields polynomial C_gates for polynomial L and error; 2^-N I_cliff > 4N extends the bound to all values.The exponential condition is 2^-N I_cliff > α^N for some α > 1.Source: §4.2.1 · p. 22
4.2.2 Binomial metric, operator-norm close
- For the binomial metric, α > 1 makes polynomial L and operator-norm error imply polynomial C_gates.The derivation uses the bound on the sum of terms given for α ≥ 1.Source: §4.2.2 · p. 22
4.2.3 Exponential metric, operator-norm close
- For the exponential metric, the method gives no tight gate-complexity bound for polynomial-length paths at x = O(1), unless N̄_k is exponentially large.This limitation applies when operator-norm closeness is required.Source: §4.2.3 · p. 23
5 State complexity
State-space complexity assigns a pair of states the complexity of the least-complex unitary connecting them to within inner-product error. Under the stated penalty conditions, polynomial-length state-space paths can be approximated to polynomially small inner-product error with polynomially many gates.
5 State complexity
- State-space distance between two states is the distance from the origin of the least distant unitary connecting them.The relative complexity of a state pair is the complexity of the least-complex unitary connecting them, with inner-product error ϵ allowed.Source: §5 · p. 23
- Relative gate complexity of a state pair is lower-bounded by its separation in the cliff metric or any less punitive state-space geometry.An upper bound requires tolerating error.Source: §5 · p. 23
- Small Killing-distance error need not give close outputs for a particular input state, whereas operator-norm closeness guarantees closeness even for the worst-case input.The Frobenius-norm guarantee is averaged over input states, not necessarily the chosen input.Source: §5 · p. 23
- Under either sufficient penalty condition, any pair of states connected by a polynomial-length state-space path can be approximated to polynomially small inner-product error with polynomially many gates.The state-space path length is L[|ψ1⟩, |ψ2⟩], and the approximation error is ϵ.Source: §5 · p. 24
6 Implications for diameter of complexity geometry
The section derives exponential diameter lower bounds for complexity geometries on the unitary group and Hilbert space. The unitary-group bound applies to some metrics beyond the polynomial-equivalence class, while a large unitary-group diameter alone does not establish a large Hilbert-space diameter.
6.1 Diameter of complexity geometry of unitary group
- All three example unitary-group metrics have exponential diameter when I_cliff is exponential, α > 0, and x > 1.Source: §6.1 · p. 25
- The bound for typical unitaries establishes exponential diameter for the delayed cliff metric, although its gate count is not always polynomial in path length and inverse error.The proof needs polynomial equivalence only for typical unitaries, not all unitaries.Source: §6.1 · pp. 25–26
6.2 Diameter of complexity geometry of Hilbert space
- A large diameter on the unitary group does not imply a large diameter for the corresponding Hilbert-space geometry, because the latter involves a minimization.Some penalty schedules yield a proven exponential unitary-group diameter without a proven exponential state-space diameter.Source: §6.2 · p. 26
- For x > 10.27..., the bounds establish an exponentially large state-space diameter for the exponential metric, although it meets neither sufficient condition for polynomial equivalence.The cliff and binomial metrics have matching sufficient conditions for exponential diameter and polynomial equivalence of polynomial lengths.Source: §6.2 · pp. 26–27
7 Discussion
The discussion examines how approximate geodesic simulation establishes polynomial equivalence for a broad class of complexity geometries, their relationships to BQP and differential geometry, and the limits and possible improvements of current methods. It also bounds Killing distance relative to normalized Frobenius distance and identifies the unitary farthest from the identity.
7.1 Overview of method
- The principal challenge is approximating geodesics with gates: small geometric steps are cheap but each nonzero gate costs at least one, while following many Hamiltonian directions incurs a Pythagorean penalty.The proposed approach approximates paths with zig-zag segments, pruning expensive directions and balancing truncation error against the slowdown for cheap directions.Source: §7.1 · pp. 27–28
7.2 Complexity geometries and BQP
- Geometries satisfying Eq. 3 and Eq. 5 or 6 define BQP when small operator-norm error is allowed.Geometries can simulate circuits exactly when I2 is at-worst polynomially large, while the reverse simulation and worst-case error guarantees yield the BQP correspondence.Source: §7.2 · pp. 28–29
7.3 The role of the binomial metric
- For operator-norm approximation, the binomial schedule has a critical threshold: α > 1 satisfies the pruning condition, while α ≥ 1 satisfies the condition relating complexity distance to operator norm.For α ≤ 1, polynomial-length paths may require superpolynomially many gates to approximate; for α < 1, short complexity-distance paths may fail to be short in operator norm.Source: §7.3 · pp. 29–30
7.4 Equivalence class of complexity geometries
- The geometrical significance is that right-invariant metrics meeting the sufficient conditions are polynomially equivalent to one another, even when their short-distance penalty assignments differ exponentially.The paper frames this as evidence that long-distance approximate synthesis can be insensitive to substantial short-distance differences.Source: §7.4 · p. 30
7.5.1 Incremental improvements
- Improved bounds may come from higher-order simulation, structured commutators, or changing penalty assignments while retaining a cheap set whose nested commutators generate the algebra.The discussion also suggests that commutation structure could improve bounds and that qubit and Majorana exponential metrics can be quasi-polynomially equivalent under Killing error; however, a criterion based only on the spectrum of a non-diagonal penalty matrix is ruled out by cheap Haar-random directions.Source: §7.5.1 · pp. 31–32
7.5.2 Errors as measured in complexity geometry do not compose
- A divide-and-conquer proof cannot generally sum small segment errors in the complexity geometry because right invariance alone does not ensure errors compose subadditively.Even if each segment has small complexity-geometry error, composing the segments can produce an unacceptably erroneous path.Source: §7.5.2 · p. 33
7.5.3 Beyond divide-and-conquer
- A holistic simulation strategy might outperform divide-and-conquer, as ball-box results and single-qubit examples suggest zero-error reachability and decreasing error-elimination cost with distance.These hints are non-constructive, and the paper leaves open how to find such a path or strategy.Source: §7.5.3 · pp. 33–34
7.6 Curvature and complexity
- The enlarged equivalence class includes modest-curvature metrics such as the binomial metric, unlike the highly curved cliff metric, potentially making differential-geometric lower-bound tools more useful.Slowly growing penalty schedules have modest curvature when Ik+m−1 ≲ IkIm.Source: §7.6 · p. 35
A.1 Upperbounding s in terms of the Frobenius distance
- Killing geodesics are generated by time-independent Hamiltonians, and the shortest one is selected by minimizing TrH2t among the possible logarithms.The matrix logarithm is not unique, so a unitary admits multiple such Hamiltonians.Source: §A.1 · pp. 35–36
- The antipodal unitary −1 is farthest from the identity, at Killing distance s = π.Its eigenvalue phases are λ_i = π for all eigenvalues.Source: §A.1 · p. 36
- The Killing distance is at most π/2 times the normalized Frobenius distance, by an eigenvalue-wise ratio bound and bi-invariance.The passage states that the eigenvalue-wise ratio is below π/2 and that bi-invariance yields Eq. 37.Source: §A.1 · p. 36
A.2 Bounding the error from pruning
The section bounds the error introduced by pruning terms with penalty factors above a chosen threshold.
A.2 Bounding the error from pruning
- Pruning drops all terms whose penalty factor exceeds a chosen critical value I.Source: §A.2 · p. 36
- The pruning error is then bounded using a relation that applies to any bi-invariant norm.Source: §A.2 · p. 36
- The bound is obtained by controlling the right-hand side with Eq. 45.Source: §A.2 · p. 37
A.2.1 Pruning error for Frobenius norm
The appendix bounds errors from pruning, segment-wise Hamiltonian averaging, and Trotterization, treating Frobenius/Killing and operator norms separately where stated.
A.2.1 Pruning error for Frobenius norm
- The normalized-Frobenius pruning error is bounded by combining Eqs. 122 and 123.Source: §A.2.1 · p. 37
A.2.2 Pruning error for operator norm
- Two operator-norm pruning bounds are developed, one using subadditivity and another applying Eq. 39.Source: §A.2.2 · pp. 37–38
A.3 Bounding the error from averaging
- Averaging replaces the Hamiltonian in each segment with its segment average, and its norm error is bounded using the Dyson expansion.Source: §A.3 · p. 38
A.3.1 Averaging error for Killing distance
- For Killing distance, Frobenius-norm product bounds and the Hamiltonian normalization are used to bound the averaging error.Source: §A.3.1 · p. 38
A.3.2 Averaging error for operator norm
- For operator norm, submultiplicativity is used to bound the averaging error.Source: §A.3.2 · p. 39
A.4 Bounding the error from Trotterization
A.4.1 Trotter error for Killing distance
- For Killing distance, distinct commutators are orthogonal, so the terms inside the norm add without interference.Source: §A.4.1 · p. 39
A.4.2 Trotter error for operator norm
The operator-norm Trotter error is bounded by Eq. 145.
A.4.2 Trotter error for operator norm
- The operator-norm Trotter error is bounded by Eq. 145.Source: §A.4.2 · p. 40
B How does Trotter error scale with N?
Interference can worsen the Frobenius error of a first-order Trotter expansion, but reordering terms can make interference destructive. The enhanced bound remains conditional on controlling higher-order terms.
B How does Trotter error scale with N?
- When commutators overlap, constructive interference can increase the Frobenius norm by up to √n; the worst case is n = N, an N-factor deterioration.Source: B How does Trotter error scale with N? · pp. 40–41
- Ordering changes signs in the O(δ^2) error sum, allowing terms to interfere destructively rather than constructively.Source: B How does Trotter error scale with N? · p. 41
- The proposed ordering greedily places each monomial at the front or back to minimize the Frobenius error from terms already placed.Source: B How does Trotter error scale with N? · pp. 41–42
- Judicious ordering makes the first-order Trotter expansion’s O(δ^2) Frobenius error smaller than the no-interference bound.The paper says the error can be parametrically smaller in N than under worst-case ordering.Source: B How does Trotter error scale with N? · pp. 41–42
- The enhanced Frobenius bound needs proof that O(δ^3) terms do not dominate O(δ^2); if established, it would improve the geometry-diameter lower bound to match [7].Source: B How does Trotter error scale with N? · p. 42
- The procedure reaches only 2N of the N! possible orderings, leaving unused freedom that might help generalize it to higher-order Suzuki-Trotter formulas.Source: B How does Trotter error scale with N? · p. 42
C When does close in complexity geometry imply close in operator norm?
The paper gives a sufficient penalty-schedule condition under which closeness in complexity geometry implies closeness in operator norm, and identifies schedules satisfying it.
C When does close in complexity geometry imply close in operator norm?
- A sufficiently punitive penalty schedule ensures that polynomially small complexity distance implies polynomially small operator-norm distance.Source: C When does close in complexity… · p. 43
- The condition holds for the cliff metric when I_cliff > 4N and for the binomial metric when α ≥ 1.The paper identifies α = 1 as a critical binomial schedule.Source: C When does close in complexity… · p. 43
- The paper also states an operator-norm distance bound, L/Γ ≤ s ≤ π.Source: C When does close in complexity… · p. 43
- The lower bound is saturated by monomial unitaries generated by short steps in the most expensive generalized-Pauli directions.Source: C When does close in complexity… · p. 43