Models of quantum complexity growth

Abstract

The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high energy physics. The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state. It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a short-cut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions. To go further, one may study more generic models of complexity growth. We provide a rigorous connection between complexity growth and unitary $k$-designs, ensembles which capture the randomness of the unitary group. This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity. We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind. Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.

64 pages, 4 figures, many diagrams

References in corpus (47)

• Black holes as mirrors: quantum information in random subsystems
• Symmetric Informationally Complete Quantum Measurements
• Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order
• Complexity Equals Action
• Complexity and Shock Wave Geometries
• Operator Spreading in Random Unitary Circuits
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• Complexity, action, and black holes
• Scalable Noise Estimation with Random Unitary Operators
• Chaos and complexity by design
• Towards the fast scrambling conjecture
• Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
• Evenly distributed unitaries: on the structure of unitary designs
• Local random quantum circuits are approximate polynomial-designs
• The Second Law of Quantum Complexity
• Comments on Holographic Complexity
• Most quantum states are too entangled to be useful as computational resources
• Emergent statistical mechanics of entanglement in random unitary circuits
• Liouville Action as Path-Integral Complexity: From Continuous Tensor Networks to AdS/CFT
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• On the Time Dependence of Holographic Complexity
• Holographic Complexity
• Chaos, Complexity, and Random Matrices
• Complexity of Formation in Holography
• Tight informationally complete quantum measurements
• Multiqubit Clifford groups are unitary 3-designs
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Subsystem Complexity and Holography
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Holographic Complexity Equals Which Action?
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• Decoupling with unitary approximate two-designs
• Unitary designs from statistical mechanics in random quantum circuits
• Entanglement, quantum randomness, and complexity beyond scrambling
• Mixing properties of stochastic quantum Hamiltonians
• Efficient Quantum Tensor Product Expanders and k-designs
• Spectral decoupling in many-body quantum chaos
• Guaranteed recovery of quantum processes from few measurements
• Qubit stabilizer states are complex projective 3-designs
• Weak multiplicativity for random quantum channels
• Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality
• Improving compressed sensing with the diamond norm
• Black Holes and Complexity Classes
• Note on the saturation of the norm inequalities between diamond and nuclear norm
• Unitary $t$-designs from $relaxed$ seeds
• Universal Hamiltonians for Exponentially Long Simulation

Cited by in corpus (82)

• Quantum chaos and the complexity of spread of states
• Preparing random states and benchmarking with many-body quantum chaos
• Linear growth of quantum circuit complexity
• Many-body quantum magic
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Quantum Computational Complexity -- From Quantum Information to Black Holes and Back
• Quantum Dynamics in Krylov Space: Methods and Applications
• Holographic tensor network models and quantum error correction: A topical review
• Preparation of matrix product states with log-depth quantum circuits
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Random Matrix Theory for Complexity Growth and Black Hole Interiors
• Experimental single-setting quantum state tomography
• Aspects of The First Law of Complexity
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Quantum complexity in gravity, quantum field theory, and quantum information science
• Transport and entanglement growth in long-range random Clifford circuits
• Analysing quantum systems with randomised measurements
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Learning quantum states and unitaries of bounded gate complexity
• A single $T$-gate makes distribution learning hard
• Emergent statistical mechanics from properties of disordered random matrix product states
• Bounds on quantum evolution complexity via lattice cryptography
• Crystalline Quantum Circuits
• Resource theory of quantum uncomplexity
• Complexity of quantum circuits via sensitivity, magic, and coherence
• Designs via Free Probability
• Quantifying quantum chaos through microcanonical distributions of entanglement
• Typical Correlation Length of Sequentially Generated Tensor Network States
• Collective randomized measurements in quantum information processing
• Fluctuations of subsystem entropies at late times
• Observation of a non-Hermitian supersonic mode on a trapped-ion quantum computer
• Dynamics of Pseudoentanglement
• Estimating the randomness of quantum circuit ensembles up to 50 qubits
• Mixing and localisation in random time-periodic quantum circuits of Clifford unitaries
• Data-driven discovery of statistically relevant information in quantum simulators
• Designs from Local Random Quantum Circuits with SU(d) Symmetry
• Unitary k-designs from random number-conserving quantum circuits
• Absence of localization in two-dimensional Clifford circuits
• Unitarity estimation for quantum channels
• Complexity is not Enough for Randomness
• Operational Quantum Average-Case Distances
• Exploring Quantum Average-Case Distances: proofs, properties, and examples
• On the generic increase of observational entropy in isolated systems
• Empirical Sample Complexity of Neural Network Mixed State Reconstruction
• Complexity-constrained quantum thermodynamics
• Toward Super-polynomial Quantum Speedup of Equivariant Quantum Algorithms with SU($d$) Symmetry
• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
• Evolving Quantum Circuits
• Holographic deep thermalization for secure and efficient quantum random state generation
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Unraveling long-time quantum dynamics using flow equations
• Saturation and recurrence of quantum complexity in random local quantum dynamics
• Wavefunction branching: when you can't tell pure states from mixed states
• Probabilistic state synthesis based on optimal convex approximation
• Quantum complexity phase transitions in monitored random circuits
• Universal distributions of overlaps from generic dynamics in quantum many-body systems
• Toward Instance-Optimal State Certification With Incoherent Measurements
• Properties of Krylov state complexity in qubit dynamics
• Generalized holographic complexity of rotating black holes
• Generation of Pseudo-Random Quantum States on Actual Quantum Processors
• All you need is spin: SU(2) equivariant variational quantum circuits based on spin networks
• On the average-case complexity of learning output distributions of quantum circuits
• Non-Haar random circuits form unitary designs as fast as Haar random circuits
• Efficient approximate unitary designs from random Pauli rotations
• Random Circuits in the Black Hole Interior
• Subsystem Complexity and Measurements in Holography
• Quantum circuit complexity and unsupervised machine learning of topological order
• Orbital Expansion Variational Quantum Eigensolver: Enabling Efficient Simulation of Molecules with Shallow Quantum Circuit
• Krylov-space anatomy and spread complexity of a disordered quantum spin chain
• Attention to Quantum Complexity
• Fundamental solutions of heat equation on unitary groups establish an improved relation between $\epsilon$-nets and approximate unitary $t$-designs
• Average relative entropy of random states
• Optimal quantum reservoir learning in proximity to universality
• On the stabilizer complexity of Hawking radiation
• More global randomness from less-random local gates
• Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians
• Realizing Unitary $k$-designs with a Single Quench
• Quantum chaos measures for Floquet dynamics
• Probing the localization effects in Krylov basis
• Hybrid Reward-Driven Reinforcement Learning for Efficient Quantum Circuit Synthesis
• Comparing quantum complexity and quantum fidelity