The ground state of random Hamiltonians with all-to-all interactions such as the quantum Sherrington-Kirkpatrick (SK) model and the Sachdev-Ye-Kitaev (SYK) model follow volume-law entanglement and are expected to be hard to model using tensor networks. In recent years, some progress has been made to push the limit of classical methods using neural quantum states. However, it remains an open question whether there exist quantum algorithms that could offer a quantum advantage over the state-of-the-art classical methods in simulating random Hamiltonians. In this work, we show that one such algorithm, TETRIS-ADAPT-VQE, can construct accurate ground states for dense and sparse SYK models containing up to $N=20$ Majorana fermions achieving fidelities $\geq 99.3\%$ and for the quantum SK model with up to $L=18$ sites achieving fidelities $\geq 99.9998\%$. We find that while the preparation of ground states is efficient (in terms of operator pool size and circuit depth) for the SK model, it is not efficient for either dense or moderately sparse SYK models.
The ground state of random Hamiltonians with all-to-all interactions such as the quantum Sherrington-Kirkpatrick (SK) model and the Sachdev-Ye-Kitaev (SYK) model follow volume-law entanglement and are expected to be hard to model using tensor networks. In recent years, some progress has been made to push the limit of classical methods using neural quantum states. However, it remains an open question whether there exist quantum algorithms that could offer a quantum advantage over the state-of-the-art classical methods in simulating random Hamiltonians. In this work, we show that one such algorithm, TETRIS-ADAPT-VQE, can construct accurate ground states for dense and sparse SYK models containing up to N=20 Majorana fermions achieving fidelities ≥99.3% and for the quantum SK model with up to L=18 sites achieving fidelities ≥99.9998%. We find that while the preparation of ground states is efficient (in terms of operator pool size and circuit depth) for the SK model, it is not efficient for either dense or moderately sparse SYK models.
Finding the ground state of strongly-interacting fermionic systems is often the prerequisite for fully understanding both quantum chemistry and condensed matter systems. The Sachdev–Ye–Kitaev (SYK) model is a representative example of such a system; it is particularly interesting not only due to the existence of efficient quantum algorithms preparing approximations to the ground state such as Hastings–O'Donnell (STOC 2022), but also known no-go results for many classical ansatzes in preparing low-energy states. However, this quantum-classical separation is known to not persist when the SYK model is sufficiently sparsified, i.e., when terms in the model are discarded with probability 1 − p , where p = Θ ( 1 / n 3 ) and n is the system size. This raises the question of how robust the quantum and classical complexities of the SYK model are to sparsification.In this work we initiate the study of the sparse SYK model where p ∈ [ Θ ( 1 / n 3 ) , 1 ] and show there indeed exists a certain robustness of sparsification. We prove that with high probability, Gaussian states achieve only a Θ ( 1 / n ) -factor approximation to the true ground state energy of sparse SYK for all p ≥ Ω ( log n / n 2 ) , and that Gaussian states cannot achieve constant-factor approximations unless p ≤ O ( log 2 n / n 3 ) . Additionally, we prove that the quantum algorithm of Hastings–O'Donnell still achieves a constant-factor approximation to the ground state energy when p ≥ Ω ( log n / n ) . Combined, these show a provable separation between classical algorithms outputting Gaussian states and efficient quantum algorithms for the goal of finding approximate sparse SYK ground states whenever p ≥ Ω ( log n / n ) , extending the analogous p = 1 result of Hastings–O'Donnell.
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.
We study the Sachdev-Ye-Kitaev (SYK) Hamiltonian HSYK on n Majorana modes with k-body interactions, and prove that E∥HSYK∥op=(1−o(1))⋅2n/k for super-constant k≤o(n), where the expectation is over the disorder variables in the Hamiltonian. This confirms predictions due to Garcia-Garcia, Jia and Verbaarschot and answers a question posed by Feng, Tian, and Wei. Our results extend to the sparse SYK Hamiltonian. As a corollary, we obtain that a dissipative quantum algorithm due to Basso, Chen, and Dalzell provably computes the ground state energy of the SYK Hamiltonian up to an O(1)-multiplicative factor for all k<n/4.
Our key technical idea is identifying an explicit, deterministic linear operator x such that a fixed quadratic form of x2ℓ exactly equals the expected trace moments of the SYK Hamiltonian for every n and k. This linear operator can be naturally viewed as a twisted model of bosons on the space of hyperedges of a hypergraph. The problem thus reduces to identifying the spectral edge of x, which we show is dominated by the spectrum of a natural (kn)-dimensional matrix from the Johnson scheme and is straightforward to compute using known results. To show that our bound is sharp, we construct a witness state with a large quadratic form on x and transform it into a certificate of a lower bound on the largest quadratic form on HSYK.
Beyond the SYK Hamiltonian, our techniques also apply to the k−local quantum spin glass (QSG), yielding E∥Hk−QSG∥op≤O(n/k) for all 1≤k≤n/2, thus improving the standard O(n) bound by a factor of k.
We study the preparation of thermal states of the dense and sparse Sachdev-Ye-Kitaev (SYK) model using a variational quantum algorithm for 6≤N≤12 Majorana fermions over a wide range of temperatures. Utilizing IBM's 127-qubit quantum processor, we perform benchmark computations for the dense SYK model with N=6, showing good agreement with exact results. The preparation of thermal states of a non-local random Hamiltonian with all-to-all coupling using the simulator and quantum hardware represents a significant step toward future computations of thermal out-of-time order correlators in quantum many-body systems.
Approximating the ground states of strongly interacting electron systems in quantum chemistry and condensed matter physics is expected to be one of the earliest applications of quantum computers. In this paper, we prepare highly accurate ground states of the Fermi-Hubbard model for small grids of up to six sites (12 qubits) by using an interpretable, adaptive variational quantum eigensolver (VQE) called ADAPT-VQE [H. R. Grimsley et al., Nat. Commun. 10, 3007 (2019)]. In contrast with nonadaptive VQE, this algorithm builds a system-specific ansatz by adding an optimal gate built from one-body or two-body fermionic operators at each step. We show this adaptive method outperforms the nonadaptive counterpart in terms of fewer variational parameters, short gate depth, and scaling with the system size. The fidelity and energy of the prepared state appear to improve asymptotically with ansatz depth. We also demonstrate the application of adaptive variational methods by preparing excited states and Green's functions using a proposed ADAPT-SSVQE algorithm. Lower depth, asymptotic convergence, noise tolerance of a variational approach [A. Peruzzo et al., Nat. Commun. 5, 4213 (2014); J. R. McLean et al., New J. Phys. 18, 023023 (2016); K. Sharma et al., New J. Phys. 22, 043006 (2020)], and a highly controllable, system-specific ansatz make the adaptive variational methods particularly well suited for noisy intermediate-scale quantum devices.
The fundamental problem in much of physics and quantum chemistry is to optimize a low-degree polynomial in certain anticommuting variables. Being a quantum mechanical problem, in many cases we do not know an efficient classical witness to the optimum, or even to an approximation of the optimum. One prominent exception is when the optimum is described by a so-called “Gaussian state”, also called a free fermion state. In this work we are interested in the complexity of this optimization problem when no good Gaussian state exists. Our primary testbed is the Sachdev–Ye–Kitaev (SYK) model of random degree-q polynomials, a model of great current interest in condensed matter physics and string theory, and one which has remarkable properties from a computational complexity standpoint. Among other results, we give an efficient classical certification algorithm for upper-bounding the largest eigenvalue in the q=4 SYK model, and an efficient quantum certification algorithm for lower-bounding this largest eigenvalue; both algorithms achieve constant-factor approximations with high probability.