REVIEW 25 cited by
A geometric approach to quantum circuit lower bounds
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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.
Forward citations
Cited by 25 Pith papers
-
Quantum circuit complexity and unsupervised machine learning of topological order
Nielsen quantum circuit complexity is positioned as a topological distance for unsupervised learning of topological order, with theorems linking it to Bures distance and entanglement to yield practical fidelity- and e...
-
Complexity measures in holographic cascading theories with multiscale dynamics
In holographic B8 gauge theories, complexity growth flattens near a walking conformal regime, while Krylov oscillation periods track the infrared scale and persist in screened, non-confining phases.
-
Page transition for the complexity of an evaporating black hole
The complexity of radiation from an evaporating black hole is argued to undergo a sharp Page-like transition, dominated after the Page time by the volume of an island in the entanglement wedge.
-
Krylov complexity, mode-resolved complexity and entanglement entropy across phase transitions in the non-Hermitian extended Su-Schrieffer-Heeger model
Mode-resolved Krylov complexity and entanglement entropy signal exceptional-point and topological transitions and dynamical phases in the non-Hermitian extended SSH model.
-
The Normalised Wigner Negativity Rate as a Second-Moment Probe of Infall in AdS$_3$
Normalized Krylov-Wigner negativity rate matches Krylov variance growth and equals tidal stretch rate R ∝ C P_ρ if and only if Δ=1 in AdS3.
-
Controlled Chaos in 4D SCFTs
Orbifolds of N=4 SYM produce SCFTs whose dilatation operator in a subsector is realized by a tunable spin chain whose eigenvalue statistics exhibit chaos for specific marginal couplings.
-
Holographic Subregion Complexity and Fidelity Susceptibility in Noncommutative Yang--Mills Theory
In the noncommutative Yang–Mills dual, holographic subregion complexity acquires a lower bound and a minimum-length scale, and strong subadditivity fails exactly at that scale.
-
Quantum Cosmology in Krylov Space: Complexity and Entropy
In a sharply peaked Gaussian state of a flat FLRW universe with a massless scalar clock, Krylov state complexity grows as σ²(φ−φ0)²/4 and operator complexity is exactly twice that, in both Wheeler-DeWitt and loop quan...
-
CFT Complexity and Penalty Factors
A submersion-based method turns weighted generator costs into state-complexity metrics for CFTs, giving analytic formulas in simple limits and constraints on which weight choices are viable.
-
Spread complexity and the saturation of wormhole size
For finite-N DSSYK, the chord basis is the early part of the physical Krylov basis, and spread complexity, taken as the non-perturbative ER bridge size, saturates after a universality-class-dependent peak and slope.
-
On volume subregion complexity in Vaidya spacetime
In the AdS3 Vaidya geometry, the extremal volume defining holographic subregion complexity is genuinely x-dependent during the quench, so the standard x-independent ansatz fails at intermediate times; early and late t...
-
DeComp2: Description Complexity aware Decomposition
Adding a description-length term to the quantum-compiler objective changes the chosen circuit on ~0.3% of tested single-qubit targets, showing gate-count-only compilation discards genuinely structured alternatives.
-
Holographic complexity of de-Sitter black holes
In SdS black hole holography, CV and CV2.0 complexities grow linearly while CA growth vanishes due to finite action, with matching rates between static patch and dS/CFT schemes.
-
Krylov complexity from a simple quantum mechanical model for a radiating black hole
A simplified mini-BMN matrix model for a radiating black hole exhibits early-time chaotic growth of Krylov complexity followed by late-time saturation to a plateau consistent with equilibration.
-
Emergence of Krylov complexity through quantum walks: An exploration of the quantum origins of complexity
Reducing a graph walk to distance-layers reproduces Krylov/spread complexity, yielding analytic finite-q SYK Lanczos coefficients and hypercube complexity D sin²(t/D), with faster saturation than classical-walk circuits.
-
Krylov Complexity for Open Quantum System: Dissipation and Decoherence
Krylov complexity saturates in the full high-temperature Caldeira-Leggett system, reproduces dissipative features when decoherence is suppressed, shows oscillations when dissipation is suppressed, and remains insensit...
-
Generalized Krylov Complexity
The paper defines generalized Krylov complexity for multi-generator unitary evolutions, computes it for U(1)xU(1), a U(1)xU(1) subgroup of SO(10), and SU(2), and introduces a weighted version.
-
Generalized CV Conjecture and Krylov Complexity in Two-Mode Hermitian Systems via Information Geometry
Krylov complexity equals Fubini-Study volume for closed and open two-mode squeezed states, providing analytic support for the generalized CV conjecture via information geometry.
-
Universal Euler-Cartan Circuits for Quantum Field Theories
Presents a universal parametrized quantum circuit ansatz based on Euler-Cartan decompositions, benchmarked on energy spectra of lattice QFT models with short- and long-range interactions.
-
Holographic complexity of the Klebanov-Strassler background
Studies holographic complexity in the Klebanov-Strassler background, reporting common scaling with confinement scale across functionals and more complex UV divergences than in AdS.
-
Nielsen complexity with multiple cost factors
Generalizes Nielsen complexity to multiple cost factors, derives modified Euler-Arnold and Jacobi equations, and examines effects on conjugate points in single-qubit and SYK systems.
-
Quantum information in Riemannian spaces
A coordinate-invariant phase-space entropy for quantum states on Riemannian manifolds is defined and computed for oscillator states in flat and AdS2 spacetimes.
-
Holographic entanglement entropy and complexity for the cosmological braneworld model
Time-dependent holographic entanglement entropy and complexity are computed perturbatively for braneworld FLRW universes with radiation, matter, and exotic matter by using time-dependent brane positions in black brane...
-
Reflections on Virasoro circuit complexity and Berry phase
A claimed identification of Virasoro circuit complexity with the Berry connection fails a basic consistency check for pure rotations.
-
Quantum Dynamics in Krylov Space: Methods and Applications
Krylov subspace methods efficiently describe quantum evolution, operator growth, and chaos in many-body systems, with metrics like Krylov complexity and applications in open systems, QFT, and quantum computing.
Discussion (0). Continue with ORCID to comment.