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 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 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
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.
We study the Krylov state complexity of the Sachdev-Ye-Kitaev (SYK) model for N ≤ 28 Majorana fermions with q -body fermion interaction with q = 4 , 6, 8 for a range of sparse parameter k that controls the number of remaining terms in the original SYK model after sparsification. The critical value of k below which the model ceases to be holographic, denoted k c , has been subject of several recent investigations. Using Krylov complexity as a probe, we find that the peak value of complexity does not change as we increase k beyond k ≥ k min at large temperatures. We argue that this behavior is related to the change in the holographic nature of the Hamiltonian in the sparse SYK-type models such that the model is holographic for all k ≥ k min ≈ k c . Our results provide a novel way to determine k c in SYK-type models.
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.
Abstract The Sachdev-Ye-Kitaev (SYK) model describes a strongly correlated quantum system that shows a strong signature of quantum chaos. Due to its chaotic nature, the simulation of real-time dynamics becomes quickly intractable by means of classical numerics, and thus, quantum simulation is deemed to be an attractive alternative. Nevertheless, quantum simulations of the SYK model on noisy quantum processors are severely limited by the complexity of its Hamiltonian. In this work, we simulate the real-time dynamics of a sparsified version of the SYK model with 24 Majorana fermions on a trapped-ion quantum processor. We adopt a randomized quantum algorithm, TETRIS, and develop an error mitigation technique tailored to the algorithm. Leveraging the hardware’s high-fidelity quantum operations and all-to-all connectivity of the qubits, we successfully calculate the Loschmidt amplitude for sufficiently long times so that its decay is observed. Based on the experimental and further numerical results, we assess the future possibility of larger-scale simulations of the SYK model by estimating the required quantum resources. Moreover, we present a scalable mirror-circuit benchmark based on the randomized SYK Hamiltonian and the TETRIS algorithm, which we argue provides a better estimate of the decay of fidelity for local observables than standard mirror-circuits.
Simulating the time dynamics of an observable under Hamiltonian evolution is one of the most promising candidates for quantum advantage as we do not expect efficient classical algorithms for this problem except in restricted settings. Here, we introduce such a setting by showing that Majorana Propagation, a simple algorithm combining Trotter steps and truncations, efficiently finds a low-degree approximation of the time-evolved observable as soon as such an approximation exists. This provides the first provable guarantee about Majorana Propagation for Hamiltonian evolution. As an application of this result, we prove that Majorana Propagation can efficiently simulate the time dynamics of any sparse quartic Hamiltonian up to time tmax(u) depending on the interaction strength u. For a time horizon t≤tmax(u), the runtime of the algorithm is NO(log(t/ε)) where N is the number of Majorana modes and ε is the error measured in the normalized Frobenius norm. Importantly, in the limit of small u, tmax(u) goes to +∞, formalizing the intuition that the algorithm is accurate at all times when the Hamiltonian is quadratic.