PaperlayerView exact revision on arXiv

Source-linked AI summary

Geometry of quantum complexity

Roberto Auzzi, Stefano Baiguera, G. Bruno De Luca, Andrea Legramandi, Giuseppe Nardelli, Nicolò Zenoni

arXiv:2011.07601v3hep-thquant-ph

TL;DR

The paper addresses the open question of how to define geometric quantum complexity and select penalties for operations. It studies progressive penalties and relates unitary geometry to state complexity, finding evidence for exponential maximal complexity in a large-α regime.

  • Problem

    Geometric quantum complexity remains ambiguous, including in the choice of penalties assigned to quantum operations.

    Source: §I · p. 2

  • Method

    The paper studies progressive penalties and uses conjugate points in unitary space alongside a Riemannian-submersion framework for relating unitary and state geometry.

    Source: §I · p. 3, §VII · pp. 21–22

  • Results

    The authors report robust evidence that progressive penalties yield exponential complexity for large α, based on conjugate-point analysis.

    Source: §VII · p. 22

  • Takeaways & Limitations

    The submersion framework allows state-space geodesics to be computed without first knowing the metric on the state space.

    Source: §VII · p. 21

    Conjugate points do not generally determine maximal complexity because a geodesic may reach its cut point earlier; the analysis relies on a regime where the conjugate point approaches the identity.

    Source: §VII · p. 22

Abstract

from arXiv · show

Computational complexity is a new quantum information concept that may play an important role in holography and in understanding the physics of the black hole interior. We consider quantum computational complexity for $n$ qubits using Nielsen's geometrical approach. We investigate a choice of penalties which, compared to previous definitions, increases in a more progressive way with the number of qubits simultaneously entangled by a given operation. This choice turns out to be free from singularities. We also analyze the relation between operator and state complexities, framing the discussion with the language of Riemannian submersions. This provides a direct relation between geodesics and curvatures in the unitaries and the states spaces, which we also exploit to give a closed-form expression for the metric on the states in terms of the one for the operators. Finally, we study conjugate points for a large number of qubits in the unitary space and we provide a strong indication that maximal complexity scales exponentially with the number of qubits in a certain regime of the penalties space.

I. INTRODUCTION

The introduction frames geometric quantum complexity as a way to quantify the cost of implementing unitaries, while noting that penalty choices remain unsettled. It motivates progressive penalties and connects unitary geometry to state complexity and exponential maximal-complexity scaling.

I. INTRODUCTION

  • The motivating target is maximal complexity that scales exponentially with qubit number; uniform penalties do not provide that scaling, while non-uniform penalties may do so in some parameter regions.The introduction presents geometric complexity as a way to sharpen the heuristic notion of circuit cost.Source: §I · pp. 1–2
  • For progressive penalties with constant α > 1, a large-α expansion studies complexity geometry order by order; leading-order sectional curvatures scale as α^0, with closed-form curvatures through next-to-leading order α^-1.Source: §I · p. 3
  • Unitary and state complexity are related by a Riemannian submersion: state geodesics project from horizontal unitary geodesics, and state curvatures follow from O’Neill’s formula.The introduction also states that the unitary-space metric is homogeneous but not isotropic, whereas the state-space metric is neither homogeneous nor isotropic.Source: §I · p. 3
  • The paper studies conjugate points and finds evidence that maximal complexity scales exponentially with n for progressive penalties at large α.A geodesic stops minimizing after its first conjugate point, though it may stop minimizing earlier.Source: §I · p. 3

II. UNITARY COMPLEXITY

  • The unitary-complexity framework uses a right-invariant metric on SU(2^n), with generator penalties organized by generalized-Pauli weight, the number of non-identity Pauli factors.The introduction distinguishes unitary complexity from state complexity, which measures the difficulty of transforming a reference state into a target state.Source: §II · pp. 3–4, §I · p. 3, A. Comments on the choice of basis · p. 4

A. Comments on the choice of basis

  • In the generalized-Pauli basis, diagonal metrics assign each generator a penalty factor q_σ, and the commutator penalty q_[σ,τ] is defined as 1 when the generators commute.The basis elements either commute or anticommute.Source: A. Comments on the choice of basis · p. 4

B. Connection and geodesic equation

The section derives geodesic and curvature tools for unitary complexity using a right-invariant metric. It identifies a simple geodesic class, gives constraints on sectional curvature, and cautions that scalar curvature is not a proven criterion for ergodicity.

B. Connection and geodesic equation

  • Exponentials of eigenvectors of the penalty operator G form a simple class of geodesics, termed exponential geodesics, whose conjugate points are studied later.The connection and geodesic equation follow from the Koszul formula and yield the Euler-Arnold equation.Source: B. Connection and geodesic equation · p. 4

C. Riemann tensor

  • The Riemann tensor component R_ρστμ vanishes unless the product of the corresponding generalized Pauli matrices is proportional to the identity, and subgroup curvature depends only on metric data within that subgroup.This follows from the curvature expression's dependence on commutators.Source: C. Riemann tensor · p. 5

D. Sectional curvatures

  • Only a sufficiently large penalty for the commutator [ρ, σ] can make the sectional curvature K(ρ, σ) negative; at least two of the three independent one-qubit sectional curvatures remain positive.The sectional curvature is nonlinear in the plane orientation, so basis-plane values alone do not determine curvature on arbitrary planes.Source: D. Sectional curvatures · p. 5

E. Ricci tensor and curvature

  • Negative scalar curvature is proposed as an ergodicity detector, but the authors know of no rigorous theorem linking its sign to geodesic ergodicity.Some one-qubit sectional curvatures are always positive, so the theorem for manifolds with entirely negative sectional curvature does not directly apply.Source: E. Ricci tensor and curvature · p. 6

III. FEW QUBITS EXAMPLES

The few-qubit examples show how penalty choices shape curvature, singular limits, and maximal complexity. In the two-qubit case, the intuitive choice of penalizing weight-2 generators keeps curvature positive without a singularity, while other choices can produce negative curvature or unbounded complexity.

A. One qubit

  • For one qubit, two of the three sectional curvatures remain positive throughout parameter space, while the plotted regions distinguish positive sectional curvature from negative scalar curvature.The scalar and sectional curvatures diverge when Q grows with the other penalty fixed; sending P and Q to infinity together with a fixed unequal ratio instead keeps sectional curvature finite and the scalar curvature small.Source: A. One qubit · pp. 6–7, Figure 1 · p. 7

P 2 . (III.6)

  • When P and Q grow together with a fixed ratio β ≠ 1, sectional curvatures approach constants and scalar curvature tends to −2(β − 1)^2.In this limit maximal complexity diverges, unlike the case where the remaining easy generators suffice to build any unitary.Source: P 2 . (III.6) · p. 7

B. Two qubits

  • The two-qubit system is the simplest setting in which to examine penalties based on how many qubits a generator entangles simultaneously.The examples distinguish weight-1 and weight-2 generators and their different curvature behavior.Source: B. Two qubits · p. 7
  • For two qubits, penalizing weight-2 generators while leaving weight-1 generators easy gives positive sectional curvatures, with no curvature singularity as q → ∞.The scalar curvature is always positive for this penalty assignment.Source: B. Two qubits · pp. 7–8
  • Penalizing weight-1 generators instead yields negative curvature at sufficiently large p, and this generator-class structure can arise whenever one class is a maximal subalgebra.In the stated limiting cases, maximal complexity diverges when the only easy generator produces rotations about the x axis; it does not diverge when the remaining easy generators can build any unitary.Source: P 2 . (III.6) · p. 7, B. Two qubits · p. 8

IV. MANY QUBITS

The many-qubit analysis compares weight-dependent penalty schemes against curvature and complexity requirements motivated by scrambling and the switchback effect. Progressive penalties yield nonsingular curvature behavior in the large-penalty expansion, while the draconian scheme requires exponentially growing penalties and becomes singular.

IV. MANY QUBITS

  • The motivating target is curvature behavior compatible with scrambling and switchback dynamics, avoiding divergent sectional curvatures as n grows.The cited toy-model expectations place typical curvature at order 1/n or 1/n^2, depending on the model variant.Source: §IV · p. 8

A. Draconian penalties

  • The draconian scheme produces negative scalar curvature only when q grows exponentially with n, leaving the scalar curvature dominated by polynomially many sectional curvatures of magnitude |K| ≈ q ≈ 4^n.This is a singular limit associated with unwanted scrambling and switchback properties.Source: A. Draconian penalties · p. 9

B. Towards a more sustainable taxation policy

  • The text calls these “progressive” penalties and says that scaling as 4k at large k is generalized as αk.Source: B. Towards a more sustainable taxation… · p. 10
  • For progressive penalties, sectional curvatures remain bounded at large α, unlike the moderate scheme whose curvatures diverge as α grows.The progressive scheme is expected to have maximal complexity diverge at fixed n as α → ∞, because one-qubit operators cannot generate all unitaries.Source: B. Towards a more sustainable taxation… · p. 10

C. Progressive penalties

  • At leading order in α, progressive penalties give negative scalar curvature for n ≥ 3, from sectional-curvature values K = 1 and K = −3.The average sectional curvature becomes tiny at large n and α.Source: C. Progressive penalties · p. 10
  • The analysis has no generic-n analytic expression for higher orders in α, although exact all-orders results are computable for fixed, not-too-large n.For n = 10, the expansion converges slowly near the minimum.Source: C. Progressive penalties · p. 10
  • The exact average sectional curvature has a finite-α minimum that becomes steeper and shifts to lower α as n increases.For n = 20, the leading-order average is already close to the exact result for α ≥ 4; at n = 10, expansion through α^-5 is needed to capture the minimum.Source: C. Progressive penalties · p. 10, Figure 2 · p. 11

V. STATE COMPLEXITY AND SUBMERSIONS

State complexity is formulated on a quotient of unitary space that identifies operations preparing the same state up to phase. The resulting Riemannian submersion connects state-space geometry to unitary-space geometry and yields an explicit state metric.

V. STATE COMPLEXITY AND SUBMERSIONS

  • State complexity is the minimum unitary complexity among transformations that prepare the same state up to phase, so the state space is a quotient of unitary space.Requiring state complexity to be a length on that space gives a Riemannian submersion.Source: §V · p. 11

A. Submersions

B. Submersions and complexity geometry

  • For the complexity geometry, minimizing the infinitesimal operator that changes state coordinates sets the fiber-coordinate components to zero, yielding a closed-form state metric from the unitary metric.The construction generalizes a prior result to arbitrary numbers of qubits and gives a Riemannian submersion.Source: B. Submersions and complexity geometry · p. 13

C. Submersions and curvature

O’Neill’s formula expresses state-space sectional curvature as a unitary-space curvature plus a nonnegative contribution from horizontal-vector commutators. The section also identifies which unitary geodesics project to state-space geodesics and relates their conjugate points.

C. Submersions and curvature

  • State-space sectional curvature equals the curvature of a corresponding plane in unitary space plus a positive-definite contribution from the commutator of horizontal vectors.This relation gives a lower bound on state curvature and permits its computation without first knowing the state metric.Source: C. Submersions and curvature · p. 13

D. Submersions and geodesics

  • A horizontal geodesic projects to a state-space geodesic, but projecting a nonhorizontal geodesic does not generally produce a state-space geodesic.For complete unitary manifolds, every state-space geodesic can be built as the projection of a horizontal geodesic.Source: D. Submersions and geodesics · p. 14
  • Exponentials of penalty-matrix eigenvectors orthogonal to the unbroken subgroup provide a class of state-space geodesics.With distinct penalties for each weight, only the specified s = 0 broken unitaries are penalty eigenstates; in the draconian model, degeneracy allows more broken unitaries to generate projectable exponential geodesics.Source: D. Submersions and geodesics · pp. 14–15
  • A first conjugate point along a horizontal geodesic implies a conjugate point along its projected state-space geodesic at or before that parameter value.The paper constructs horizontal directions by choosing broken generators orthogonal to the unbroken subgroup.Source: D. Submersions and geodesics · pp. 14–15

VI. TOWARDS AN EXPONENTIAL COMPLEXITY

The section uses conjugate points to investigate when geodesics stop minimizing, applying the Raychaudhuri equation to exponential geodesics. Its estimate of conjugate-point distance provides initial evidence for exponential growth with the number of qubits.

VI. TOWARDS AN EXPONENTIAL COMPLEXITY

A. Conjugate points and Raychaudhury equation

  • The Raychaudhuri equation tracks expansion Θ; when Θ approaches −∞, it signals conjugate points beyond which the geodesic no longer minimizes distance.The expansion measures the time derivative of an infinitesimal transverse volume.Source: A. Conjugate points and Raychaudhury… · p. 15

B. An application to a simple class of geodesics

  • For exponential geodesics, neglecting the positive shear-squared term yields an analytic upper bound on where a conjugate point may occur.These geodesics have constant Ricci contraction along their path.Source: B. An application to a simple class of… · p. 15
  • In the approximation, a conjugate point occurs only when B = Rαβuαuβ > 0, and the resulting λ0 bounds the actual conjugate-point distance from above.The solution is matched to the flat-space behavior at small λ.Source: B. An application to a simple class of… · p. 16
  • With Ricci curvature fixed, λ0 scales exponentially with n because d−1≈2^n, providing first evidence for exponential maximal complexity.The estimate concerns conjugate-point distance, not a direct proof of maximal complexity.Source: B. An application to a simple class of… · p. 16

C. One qubit

The one-qubit examples relate conjugate points to Ricci curvature and show how penalty limits affect geodesic minimization and complexity. The section also projects horizontal unitary geodesics to the state space and gives its metric in Bloch-sphere coordinates.

C. One qubit

  • For each exponential geodesic Gk, a conjugate point occurs in the parameter region where the corresponding Ricci component Rk is positive.Exact cases include Gx for P = Q, Gy for P = 1, and Gz for Q = 1.Source: C. One qubit · p. 16
  • As P = 1 and Q → ∞, Gy’s conjugate point approaches θy = π/Q and λ = π/√Q, leaving the geodesic minimizing only near the origin.A shortcut of length scaling as 1/√Q is available just beyond the conjugate point, indicating low maximal complexity and a singular limit.Source: C. One qubit · p. 17
  • As P = Q → ∞, Gx has an exact conjugate point at λ = πP, while Gy and Gz have conjugate points at distances that diverge as their coordinates approach finite values.The authors report no geodesic singularity in this limit; numerical computations place large-complexity points near the conjugate point.Source: C. One qubit · p. 17
  • Horizontal unitary geodesics project to state-space geodesics, as verified numerically, and the state metric is expressed in Bloch-sphere coordinates.For reference state |0⟩, the σx and σy directions are horizontal and projectable.Source: C. One qubit · p. 17
  • For P = Q = 10, the maximal-complexity region lies just before the σy conjugate point; that point lies inside the drop delimited by the black curve’s self-intersection, which no geodesic shorter than λ can enter.Source: C. One qubit · pp. 17–18

D. Draconian model

The draconian model illustrates limits of conjugate-point evidence for maximal complexity, while the progressive model gives a strong indication of exponential scaling. That conclusion depends on the penalty regime and remains an indication rather than a proof.

D. Draconian model

  • For unpenalized weights, the cut-point bound keeps maximal complexity below π/2, independently of n.This follows from the conjugate-point estimate in the large-n, q(w) = 1 case.Source: D. Draconian model · p. 18
  • In the draconian model, w ≥ 4 geodesics have conjugate points at order-one coordinate values and exponentially large lengths, but the authors lack strong evidence that these are cut points.For w = 3, the conjugate point is near the identity but at order-one distance, so it does not establish exponential complexity; draconian penalties are singular by construction.Source: D. Draconian model · p. 19

E. Progressive model

  • For progressive penalties, large-weight geodesics in the window 2^n/3 < w < n are expected to remain minimizing at large n, supporting exponential maximal complexity.The analysis requires α > 4 for small θ0 and a sufficiently large α for the leading-order approximation to hold.Source: E. Progressive model · p. 20
  • With progressive penalties increasing slightly faster than n, such as quadratically, the authors find a strong indication that maximal complexity scales exponentially with n, not a rigorous proof.The argument neglects the shear term, which may cause conjugate points to appear earlier.Source: E. Progressive model · p. 20
  • The progressive-model calculation for weight w = n also applies to state complexity through projectable directions, though a state-space conjugate point may occur earlier.The relevant directions are orthogonal to the vertical space and are penalty eigenvectors.Source: E. Progressive model · p. 20

VII. CONCLUSIONS

The paper relates curvature in unitary complexity geometry to generator penalties and develops the state-space geometry through Riemannian submersions. It finds that progressive penalties avoid singular geometry and provide robust evidence for exponential complexity scaling in a specified large-penalty regime.

VII. CONCLUSIONS

  • Negative sectional curvature in unitary space is directly related to a large penalty for the commutator of the two directions.Negative curvature requires that commutator penalty to dominate the penalties of the two directions.Source: §VII · p. 21
  • The one-qubit space is a closed subsector of the n-qubit space, and at least some sectional curvatures in the full complexity geometry are always positive.In the generic one-qubit parameter space, at least two of the three sectional curvatures in an orthogonal basis are positive.Source: §VII · p. 21
  • For progressive penalties at large α, complexity diverges at fixed n without singular sectional curvatures, while scalar curvature is negative.By contrast, draconian penalties at large q and fixed n leave complexity finite while the geometry becomes singular.Source: §VII · p. 21
  • State-space geodesics arise by projecting horizontal unitary-space geodesics, and the two spaces’ curvatures are related by O’Neill’s formula.The framework also yields a closed-form state metric and reproduces the known one-qubit metric with arbitrary penalties.Source: §VII · pp. 21–22
  • Progressive penalties give robust evidence for exponentially scaling complexity at large α, using conjugate points whose angular positions approach the identity to estimate a lower bound.The argument expects the cut point to coincide with the conjugate point in this limit.Source: §VII · p. 22

APPENDIX

The appendices give a combinatorial count of non-vanishing sectional curvatures and explicit progressive-penalty calculations, including their large-α scaling.

Appendix A: Counting non-vanishing sectional curvatures

  • The counting method parameterizes commutator weights for pairs of generators by their weights and an integer label r, then counts the associated non-vanishing sectional curvatures.The commutator weight ranges from a minimum at l = 1 and m = min(N −1, M −1) to a maximum at l = 1 and m = 0.Source: Appendix A · pp. 22–23
  • The counting formulas account for whether N ≤ M or N > M and restrict r according to the qubit count and generator weights.The appendix gives an explicit count R(M, N, r) of generators whose commutator with a fixed generator has the specified weight parameter.Source: Appendix A · p. 22

Appendix B: Explicit calculations for the progressive penalties case

  • For progressive penalties, sectional curvatures at large α scale at most as α^0 + O(α^-1).The appendix calculates the curvature expressions separately for N ≤ M and N > M.Source: Appendix B · p. 23

1. Leading order

The leading-order calculations identify positive and negative sectional-curvature contributions, while the next order gives corrections. The qutrit application derives a state metric and finds curvature behavior controlled by penalty P.

1. Leading order

  • At leading order, r = 0 contributes sectional curvature K = 1, while the maximal allowed r contributes K = −3 for M, N > 1.The negative contribution occurs at r = N −1 when M ≥ N and at r = M −1 when M < N.Source: §1 · pp. 23–24

2. Next to leading order

  • At order α^-1, nonzero sectional-curvature corrections occur in specified weight and r cases, but cancellations leave Ricci-tensor corrections only for weight w = 2.The listed cases include M = N = 2 with δK = 4 and M = N + 1, N ≥ 3, r = 0 with δK = −2.Source: §2 · p. 24

Appendix C: State complexity for 1 qutrit

  • For the one-qutrit state space, the metric depends on angular coordinates but not phases, and the Ricci scalar depends only on θ1.For 0 < P < 1 curvature is positive; at P = 1 it is R = 24; for P > 1 a negative-curvature region appears and grows with P.Source: Appendix C · p. 26
  • In the qutrit state-space limit P → ∞, the Ricci scalar is negative and singular; in the opposite limit P → 0, it is positive and divergent.The P → 0 divergence contains a term proportional to P^-1.Source: Appendix C · p. 26

Appendix D: Submersion for 1 qubit

The one-qubit appendix applies the submersion method to map unitary geometry onto the Bloch-sphere state space. It computes state-space curvature from horizontal vectors and checks its relation to unitary curvature.

Appendix D: Submersion for 1 qubit

  • The one-qubit state is obtained by projecting a unitary transformation, and the horizontal vector fields are defined as orthogonal to the vertical direction.These horizontal fields are then used to calculate curvature in the state space.Source: Appendix D · pp. 26–28
  • The calculated state-space curvature matches the direct result from the state metric, and its difference from unitary sectional curvature matches O’Neill’s formula.The paper also plots unitary curvature, state curvature, and their difference for selected penalty values.Source: Appendix D · p. 28

Appendix E: Shear tensor equation

The appendix identifies which Ricci and Weyl tensor components contribute to the shear equation. In the one-qubit special cases, zero initial shear remains zero along the geodesic.

Appendix E: Shear tensor equation

  • The projected trace-free part of Rμν is identified as a tensor entering the shear analysis.The excerpt also introduces the Weyl tensor and its contraction with normalized velocity.Source: Appendix E · p. 28
  • The Weyl tensor components relevant to the contraction have μ = ν = ρ ≠ σ.The passage derives this from the diagonal metric and Ricci tensor and the stated vanishing conditions.Source: Appendix E · p. 28
  • Only components with ρ ≠ σ enter the tensor in the shear equation.The Weyl tensor contraction with normalized velocity and the tensor entering the shear equation have this component pattern.Source: Appendix E · p. 28
  • For one qubit, the relevant tensor components vanish for Gx when P = Q, Gy when P = 1, and Gz when Q = 1.In these cases, zero shear tensor remains zero along the entire geodesic.Source: Appendix E · p. 28
Loading 2011.07601v3…