Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization

Abstract

We show that one can quantum simulate the dynamics of a Sachdev-Ye-Kitaev model with $N$ Majorana modes for time $t$ to precision $\epsilon$ with gate complexity $O(N^{7/2}t+N^{5/2}t\mathrm{polylog}(N/\epsilon ))$. In addition to scaling sublinearly in the number of Hamiltonian terms, this gate complexity represents an exponential improvement in $1/\epsilon$ and large polynomial improvement in $N$ and $t$ over prior state-of-the-art algorithms which scale as $O(N^{10}{t}^2/\epsilon )$. Our approach involves a variant of the qubitization technique in which we encode the Hamiltonian $H$ as an asymmetric projection of a signal oracle $U$ onto two different signal states prepared by state oracles, $A|0⟩\mapsto |A⟩$ and $B|0⟩\mapsto |B⟩$, such that $H=⟨B|U|A⟩$. Our strategy for applying this method to the Sachdev-Ye-Kitaev model involves realizing $B$ using only Hadamard gates and realizing $A$ as a random quantum circuit.

arXiv comment8 pages, 1 figure. This version adds a more complete analysis in appendix

References in corpus (21)

• The Large N Limit of Superconformal Field Theories and Supergravity
• Surface codes: Towards practical large-scale quantum computation
• Gapless Spin-Fluid Ground State in a Random Quantum Heisenberg Magnet
• Comments on the Sachdev-Ye-Kitaev model
• Characterizing Quantum Supremacy in Near-Term Devices
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Elucidating Reaction Mechanisms on Quantum Computers
• Chaos in AdS${}_2$ holography
• The Spectrum in the Sachdev-Ye-Kitaev Model
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Toward the first quantum simulation with quantum speedup
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Random Quantum Circuits are Approximate 2-designs
• Halving the cost of quantum addition
• Low Depth Quantum Simulation of Electronic Structure
• Digital Quantum Simulation of Minimal AdS/CFT
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Decoupling with random quantum circuits
• Exact convergence times for generation of random bipartite entanglement

Cited by in corpus (56)

• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Efficient and Noise Resilient Measurements for Quantum Chemistry on Near-Term Quantum Computers
• Variational Fast Forwarding for Quantum Simulation Beyond the Coherence Time
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Operator complexity: a journey to the edge of Krylov space
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Krylov Localization and suppression of complexity
• Measurement reduction in variational quantum algorithms
• Thermofield dynamics: Quantum Chaos versus Decoherence
• Concentration for random product formulas
• Lindbladian dissipation of strongly-correlated quantum matter
• Preparation of excited states for nuclear dynamics on a quantum computer
• Quantum Gravity in the Lab: Teleportation by Size and Traversable Wormholes
• Spectral Filtering Induced by Non-Hermitian Evolution with Balanced Gain and Loss: Enhancing Quantum Chaos
• Matrix Model simulations using Quantum Computing, Deep Learning, and Lattice Monte Carlo
• Efficient quantum computation of molecular forces and other energy gradients
• Quantum simulation of gauge theory via orbifold lattice
• Randomizing multi-product formulas for Hamiltonian simulation
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• Simulating groundstate and dynamical quantum phase transitions on a superconducting quantum computer
• Quantum Information Scrambling: From Holography to Quantum Simulators
• On the complexity of implementing Trotter steps
• Quenched vs Annealed: Glassiness from SK to SYK
• A Sparse Model of Quantum Holography
• Quantum computation of stopping power for inertial fusion target design
• Quantum tunneling dynamics in a complex-valued Sachdev-Ye-Kitaev model quench-coupled to a cool bath
• Toward simulating Superstring/M-theory on a quantum computer
• Sachdev-Ye-Kitaev model on a noisy quantum computer
• Refined quantum Lyapunov exponents from replica out-of-time-order correlators
• Composite Quantum Simulations
• Stabilizer Entropy and entanglement complexity in the Sachdev-Ye-Kitaev model
• A model of randomly-coupled Pauli spins
• Variational Preparation of the Sachdev-Ye-Kitaev Thermofield Double
• Average-case Speedup for Product Formulas
• Sachdev-Ye-Kitaev circuits for braiding and charging Majorana zero modes
• Probing quantum chaos in multipartite systems
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians
• Quantum simulation of operator spreading in the chaotic Ising model
• Parallel Quantum Algorithm for Hamiltonian Simulation
• On Quantum Simulation Of Cosmic Inflation
• Symmetry classes, many-body zero modes, and supersymmetry in the complex Sachdev-Ye-Kitaev model
• Conductance and thermopower fluctuations in interacting quantum dots
• The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver
• Hamiltonian simulation of minimal holographic sparsified SYK model
• Experimental error mitigation using linear rescaling for variational quantum eigensolving with up to 20 qubits
• Precise Low-Temperature Expansions for the Sachdev-Ye-Kitaev model
• Probing Entanglement Dynamics in the SYK Model using Quantum Computers
• Quantum simulations of complex systems
• Exploring new variational quantum circuit ansatzes for solving $SU(2)$ matrix models
• Two-local modifications of SYK model with quantum chaos
• Sachdev-Ye-Kitaev physics from the Hubbard model: A Floquet engineering approach
• Trotter error and gate complexity of the SYK and sparse SYK models
• Sparse SYK and traversable wormholes
• Near-Equilibrium Approach to Transport in Complex Sachdev-Ye-Kitaev Models
• A proposal to extract and enhance four-Majorana interactions in hybrid nanowires
• Many-body spectral transitions through the lens of the variable-range SYK2 model