The Sachdev–Ye–Kitaev (SYK) model is a prominent model of strongly interacting fermions that serves as a toy model of quantum gravity and black hole physics. In this work, we study the Trotter error and gate complexity of the quantum simulation of the SYK model using Lie–Trotter–Suzuki formulas. Building on recent results by Chen and Brandão \cite{Anthony} — in particular their uniform smoothing technique for random matrix polynomials — we derive bounds on the first- and higher-order Trotter error of the SYK model, and subsequently find near-optimal gate complexities for simulating these models using Lie–Trotter–Suzuki formulas. For the k -local SYK model on n Majorana fermions, at time t , our gate complexity estimates for the first-order Lie–Trotter–Suzuki formula scales with O ~ ( n k + 5 2 t 2 ) for even k and O ~ ( n k + 3 t 2 ) for odd k , and the gate complexity of simulations using higher-order formulas scales with O ~ ( n k + 1 2 t ) for even k and O ~ ( n k + 1 t ) for odd k . Given that the SYK model has Θ ( n k ) terms, these estimates are close to optimal. These gate complexities can be further improved upon in the context of simulating the time evolution of an arbitrary fixed input state | ψ ⟩ , leading to a O ( n 2 ) -reduction in gate complexity for first-order formulas and O ( n ) -reduction for higher-order formulas.We also apply our techniques to the sparse SYK model, which is a simplified variant of the SYK model obtained by deleting all but a Θ ( n ) fraction of the terms in a uniformly i.i.d. manner. We find the average (over the random term removal) gate complexity for simulating this model using higher-order formulas scales with
The Sachdev–Ye–Kitaev (SYK) model is a prominent model of strongly interacting fermions that serves as a toy model of quantum gravity and black hole physics. In this work, we study the Trotter error and gate complexity of the quantum simulation of the SYK model using Lie–Trotter–Suzuki formulas. Building on recent results by Chen and Brandão \cite{Anthony} — in particular their uniform smoothing technique for random matrix polynomials — we derive bounds on the first- and higher-order Trotter error of the SYK model, and subsequently find near-optimal gate complexities for simulating these models using Lie–Trotter–Suzuki formulas. For the k -local SYK model on n Majorana fermions, at time t , our gate complexity estimates for the first-order Lie–Trotter–Suzuki formula scales with O ~ ( n k + 5 2 t 2 ) for even k and O ~ ( n k + 3 t 2 ) for odd k , and the gate complexity of simulations using higher-order formulas scales with O ~ ( n k + 1 2 t ) for even k and O ~ ( n k + 1 t ) for odd k . Given that the SYK model has Θ ( n k ) terms, these estimates are close to optimal. These gate complexities can be further improved upon in the context of simulating the time evolution of an arbitrary fixed input state | ψ ⟩ , leading to a O ( n 2 ) -reduction in gate complexity for first-order formulas and O ( n ) -reduction for higher-order formulas.We also apply our techniques to the sparse SYK model, which is a simplified variant of the SYK model obtained by deleting all but a Θ ( n ) fraction of the terms in a uniformly i.i.d. manner. We find the average (over the random term removal) gate complexity for simulating this model using higher-order formulas scales with
We study the Sachdev-Ye-Kitaev (SYK) model---an important toy model for quantum gravity on IBM's superconducting qubit quantum computers. By using a graph-coloring algorithm to minimize the number of commuting clusters of terms in the qubitized Hamiltonian, we find the gate complexity of the time evolution using the first-order product formula for N Majorana fermions is $\mathcal{O}({N}^{5}{J}^{2}{t}^{2}/\ensuremath{\epsilon})$ where J is the dimensionful coupling parameter, t is the evolution time, and $\ensuremath{\epsilon}$ is the desired precision. With this improved resource requirement, we perform the time evolution for N=6, 8 with maximum two-qubit circuit depth and gate count of 343. We perform different error mitigation schemes on the noisy hardware results and find good agreement with the exact diagonalization results on classical computers and noiseless simulators. In particular, we compute vacuum return probability after time t and out-of-time order correlators which is a standard observable of quantifying the chaotic nature of quantum systems.
Abstract Quantum simulation is a promising application of future quantum computers. Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. For an accurate product formula approximation, the state-of-the-art gate complexity depends on the number of terms in the Hamiltonian and a local energy estimate. In this work, we give evidence that product formulas, in practice, may work much better than expected. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states, while the existing estimate is for the worst states. For general k-local Hamiltonians and higher-order product formulas, we obtain gate count estimates for input states drawn from any orthogonal basis. The gate complexity significantly improves over the worst case for systems with large connectivity. Our typical-case results generalize to Hamiltonians with Fermionic terms, with input states drawn from a fixed-particle number subspace, and with Gaussian coefficients (e.g., the SYK models). Technically, we employ a family of simple but versatile inequalities from non-commutative martingales called uniform smoothness, which leads to Hypercontractivity, namely p-norm estimates for k-local operators. This delivers concentration bounds via Markov’s inequality. For optimality, we give analytic and numerical examples that simultaneously match our typical-case estimates and the existing worst-case estimates. Therefore, our improvement is due to asking a qualitatively different question, and our results open doors to the study of quantum algorithms in the average case.
The circuit complexity for Hamiltonian simulation of the sparsified SYK model with N Majorana fermions and q = 4 (quartic interactions), which retains holographic features (referred to as ‘minimal holographic sparsified SYK’) with k ≪ N 3 / 24 (where k is the total number of interaction terms times 1/ N ) using the second-order Trotter method and Jordan-Wigner encoding is found to be O ˜ ( k α N 3 / 2 log N ( J t ) 3 / 2 ε − 1 / 2 ) where t is the simulation time, ε is the desired error in the implementation of the unitary U = exp ( − i H t ) measured by the operator norm, J is the disorder strength, and constant α < 1 . This complexity implies that with less than a hundred logical qubits and about 10 6 gates, it might be possible to achieve an advantage in this model and simulate real-time dynamics.
The Sachdev-Ye-Kitaev (SYK) model has been identified as a promising candidate to run on early fault-tolerant quantum computers due to the relatively modest resources required to probe non-trivial physics (namely holographic duality and AdS/CFT correspondence). As such, it is crucial that the details of how to run such a simulation are well understood. Using PsiQuantum's Construct platform, we implement and analyze three different approaches to simulate the SYK model: Trotterization, qDRIFT, and asymmetric qubitization with Quantum Signal Processing. We provide an open-source library containing implementations for SYK simulation using all three methods, which we use to obtain quantum resource estimates for qubit and T gate count as functions of the number of Majorana modes and precision. We find that while qDRIFT and Trotterization benefit from a lower qubit count, the large number of T gates required lead to asymmetric qubitization being advantageous in most cases. This reinforces previous theoretical considerations. We intend both the implementations and the estimates to be useful for researchers to continue to study the SYK model and understand how the techniques and resources vary.
A bstract The Sachdev-Ye-Kitaev (SYK) model is a system of N Majorana fermions with random interactions and strongly chaotic dynamics, which at low energy admits a holographically dual description as two-dimensional Jackiw-Teitelboim gravity. Hence the SYK model provides a toy model of quantum gravity that might be feasible to simulate with near-term quantum hardware. Motivated by the goal of reducing the resources needed for such a simulation, we study a sparsified version of the SYK model, in which interaction terms are deleted with probability 1 −p . Specifically, we compute numerically the spectral form factor (SFF, the Fourier transform of the Hamiltonian’s eigenvalue pair correlation function) and the nearest-neighbor eigenvalue gap ratio r (characterizing the distribution of gaps between consecutive eigenvalues). We find that when p is greater than a transition value p 1 , which scales as 1/ N 3 , both the SFF and r match the values attained by the full unsparsified model and with expectations from random matrix theory (RMT). But for p < p 1 , deviations from unsparsified SYK and RMT occur, indicating a breakdown of holography in the highly sparsified regime. Below an even smaller value p 2 , which also scales as 1/ N 3 , even the spacing of consecutive eigenvalues differs from RMT values, signaling a complete breakdown of spectral rigidity. Our results cast doubt on the holographic interpretation of very highly sparsified SYK models obtained via machine learning using teleportation infidelity as a loss function.
Recent work has deployed linear combinations of unitaries techniques to reduce the cost of fault-tolerant quantum simulations of correlated electron models. Here, we show that one can sometimes improve upon those results with optimized implementations of Trotter-Suzuki-based product formulas. We show that low-order Trotter methods perform surprisingly well when used with phase estimation to compute relative precision quantities (e.g. energies per unit cell), as is often the goal for condensed-phase systems. In this context, simulations of the Hubbard and plane-wave electronic structure models with N < 10 5 fermionic modes can be performed with roughly O ( 1 ) and O ( N 2 ) T complexities. We perform numerics revealing tradeoffs between the error and gate complexity of a Trotter step; e.g., we show that split-operator techniques have less Trotter error than popular alternatives. By compiling to surface code fault-tolerant gates and assuming error rates of one part per thousand, we show that one can error-correct quantum simulations of interesting, classically intractable instances with a few hundred thousand physical qubits.