REVIEW 11 cited by
Linear growth of quantum circuit complexity
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
Quantifying quantum states' complexity is a key problem in various subfields of science, from quantum computing to black-hole physics. We prove a prominent conjecture by Brown and Susskind about how random quantum circuits' complexity increases. Consider constructing a unitary from Haar-random two-qubit quantum gates. Implementing the unitary exactly requires a circuit of some minimal number of gates - the unitary's exact circuit complexity. We prove that this complexity grows linearly with the number of random gates, with unit probability, until saturating after exponentially many random gates. Our proof is surprisingly short, given the established difficulty of lower-bounding the exact circuit complexity. Our strategy combines differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.
Forward citations
Cited by 11 Pith papers
-
Computational Cosmic Censorship
A two-gap divergence in holographic complexity obstructs both reaching extremality and reaching a naked singularity, unifying the third law and weak cosmic censorship.
-
Quantum Simulation of Random Unitaries from Clebsch-Gordan Transforms
Clebsch-Gordan transforms give exact compressed oracles for Haar-random unitary group actions, with efficient circuits for U(d).
-
Universal Time Evolution of Holographic and Quantum Complexity
Holographic complexity measures show universal linear growth followed by late-time saturation, proven necessary and sufficient via pole structures in the energy basis using the residue theorem, arising from random mat...
-
Bridging Krylov Complexity and Universal Analog Quantum Simulator
Generalized Krylov complexity predicts the minimum time to realize target operations in analog quantum simulators such as Rydberg atom arrays.
-
Nonlocal Nonstabilizerness from Holographic Schwinger Pair Production
Holographic Schwinger pair creation generates nonlocal magic for spacetime dimensions d>2, as shown by a non-flat entanglement spectrum that can be read from the probe brane free energy.
-
Computational Cosmic Censorship
Relative holographic complexity (CA and CV) diverges logarithmically from subextremal to extremal and from extremal to naked RN-AdS, obstructing finite-time transitions and motivating the third law and weak cosmic censorship.
-
Computational Cosmic Censorship
Naked singularities produce divergent holographic complexity via the singularity boundary term when the near-origin metric scales as r^{-p} with p > D-3, implying an operational computational form of cosmic censorship.
-
The Quantum Complexity of String Breaking in the Schwinger Model
Quantum complexity measures applied to the Schwinger model reveal nonlocal correlations along the string and show that entanglement and magic give complementary views of string formation and breaking.
-
Thermalization with partial information
A maximum channel entropy principle, backed by a microcanonical-style derivation, identifies the canonical noisy channel that models thermalization under partial information.
-
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.
-
Nonlocal Nonstabilizerness from Holographic Schwinger Pair Production
In holographic Schwinger pair production, the excess capacity of entanglement is √λ(d−2)/(d−1)³ — positive for d>2, zero for d=2 — so the produced pair carries nonlocal magic for d>2.
Discussion (0). Sign in to comment.