Quantum Chaos is Quantum

Abstract

It is well known that a quantum circuit on $N$ qubits composed of Clifford gates with the addition of $k$ non Clifford gates can be simulated on a classical computer by an algorithm scaling as $\text{poly}(N)\exp (k)$[1]. We show that, for a quantum circuit to simulate quantum chaotic behavior, it is both necessary and sufficient that $k=O(N)$. This result implies the impossibility of simulating quantum chaos on a classical computer.

References in corpus (19)

• Quantum Computational Supremacy
• Operator Spreading in Random Unitary Circuits
• Chaos in quantum channels
• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• Operator spreading and the emergence of dissipative hydrodynamics under unitary evolution with conservation laws
• Chaos and complexity by design
• Random Quantum Circuits are Approximate 2-designs
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Lieb-Robinson and the butterfly effect
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Multiqubit Clifford groups are unitary 3-designs
• Emergent irreversibility and entanglement spectrum statistics
• Single T gate in a Clifford circuit drives transition to universal entanglement spectrum statistics
• Recovering quantum gates from few average gate fidelities
• Conditional Mutual Information of Bipartite Unitaries and Scrambling
• Isospectral twirling and quantum chaos
• Random Matrix Theory of the Isospectral twirling
• A Separation of Out-of-time-ordered Correlation and Entanglement
• Ensembles of physical states and random quantum circuits on graphs

Cited by in corpus (80)

• Stabilizer Rényi entropy
• Quantifying nonstabilizerness of matrix product states
• Scalable measures of magic resource for quantum computers
• Measuring magic on a quantum processor
• Magic-state resource theory for the ground state of the transverse-field Ising model
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• On the practical usefulness of the Hardware Efficient Ansatz
• Scrambling is Necessary but Not Sufficient for Chaos
• Measuring nonstabilizerness via multifractal flatness
• Phase transition in magic with random quantum circuits
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Magic spreading in random quantum circuits
• Efficient quantum algorithms for stabilizer entropies
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Stabilizer entropy dynamics after a quantum quench
• Learning t-doped stabilizer states
• Entanglement-magic separation in hybrid quantum circuits
• Pseudomagic Quantum States
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Transitions in Entanglement Complexity in Random Circuits
• Isospectral twirling and quantum chaos
• Unscrambling Quantum Information with Clifford decoders
• Stabilizer entropy in non-integrable quantum evolutions
• Magic-induced computational separation in entanglement theory
• Performance analysis of multi-shot shadow estimation
• Scrambling and quantum chaos indicators from long-time properties of operator distributions
• Phase transition in Stabilizer Entropy and efficient purity estimation
• Retrieving information from a black hole using quantum machine learning
• Nonstabilizerness of Permutationally Invariant Systems
• Magic of quantum hypergraph states
• Exact solution of long-range stabilizer Rényi entropy in the dual-unitary XXZ model
• Magic Resources of the Heisenberg Picture
• Probing quantum complexity via universal saturation of stabilizer entropies
• Quantifying non-stabilizerness via information scrambling
• Operational Metric for Quantum Chaos and the Corresponding Spatiotemporal Entanglement Structure
• Stabilizer Entropy and entanglement complexity in the Sachdev-Ye-Kitaev model
• Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
• Efficient mutual magic and magic capacity with matrix product states
• Gravitational back-reaction is magical
• Chaos and magic in the dissipative quantum kicked top
• Doped stabilizer states in many-body physics and where to find them
• Stabilizer entropy of quantum tetrahedra
• Entanglement and Stabilizer entropies of random bipartite pure quantum states
• Entanglement of random hypergraph states
• Stabilizer Tensor Networks with Magic State Injection
• Quantifying scrambling in quantum neural networks
• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates
• Entanglement complexity of the Rokhsar-Kivelson-sign wavefunctions
• Non-Stabilizerness of Sachdev-Ye-Kitaev Model
• Learning quantum states of continuous variable systems
• Nonstabilizerness in the unitary and monitored quantum dynamics of XXZ-staggered and SYK models
• Long-range nonstabilizerness and phases of matter
• Bridging Entanglement and Magic Resources within Operator Space
• Entanglement phase diagrams from partial transpose moments
• Extracting randomness from magic quantum states
• Interplay of entanglement structures and stabilizer entropy in spin models
• A nonstabilizerness monotone from stabilizerness asymmetry
• Random unitaries, Robustness, and Complexity of Entanglement
• Absence of localization in two-dimensional Clifford circuits
• Classical route to ergodicity and scarring in collective quantum systems
• Quantum Chaos and Circuit Parameter Optimization
• Operational interpretation of the Stabilizer Entropy
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Stabilizer-Accelerated Quantum Many-Body Ground-State Estimation
• Non-Clifford Cost of Random Unitaries
• Rise and fall of nonstabilizerness via random measurements
• Robust Estimation of Nonlinear Properties of Quantum Processes
• Non-stabilizerness and entanglement from cat-state injection
• Nearly query-optimal classical shadow estimation of unitary channels
• Magic of discrete lattice gauge theories
• Complexity of Quantum Trajectories
• Harvesting stabilizer entropy and non-locality from a quantum field
• Optimal quantum reservoir learning in proximity to universality
• On the stabilizer complexity of Hawking radiation
• Generalized group designs: constructing novel unitary 2-, 3- and 4-designs
• Experimental characterization of the hierarchy of quantum correlations in top quark pairs
• Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudo-Magic States
• Quantum Chaos and Universal Trotterisation Behaviours in Digital Quantum Simulations
• Van Hove singularities in stabilizer entropy densities