Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1806.02793 · Physical Review A

Quantum simulation of the Sachdev-Ye-Kitaev model by asymmetric qubitization

Ryan Babbush, Dominic William Berry, Hartmut Neven

Published Apr 4, 2019• 82 citations
arXivHTMLPDF

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 $\ensuremath{\epsilon}$ with gate complexity $O({N}^{7/2}t+{N}^{5/2}t\phantom{\rule{0.16em}{0ex}}\mathrm{polylog}(N/\ensuremath{\epsilon}))$. In addition to scaling sublinearly in the number of Hamiltonian terms, this gate complexity represents an exponential improvement in $1/\ensuremath{\epsilon}$ and large polynomial improvement in $N$ and $t$ over prior state-of-the-art algorithms which scale as $O({N}^{10}{t}^{2}/\ensuremath{\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\ensuremath{\rangle}\ensuremath{\mapsto}|A\ensuremath{\rangle}$ and $B|0\ensuremath{\rangle}\ensuremath{\mapsto}|B\ensuremath{\rangle}$, such that $H=\ensuremath{\langle}B|U|A\ensuremath{\rangle}$. 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.

DOI
10.1103/physreva.99.040301

Related papers

Quantum Resource Estimation for Simulating the SYK Model with Trotterization, qDRIFT, and Asymmetric Qubitization

Brian Goldsmith, Larissa Kroell, Nishna Aerabati

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.

quant-pharXiv:2608.27573•Aug 31, 2026•0 citations

Hamiltonian Simulation by Qubitization

Guang Hao Low, Isaac L. Chuang

We present the problem of approximating the time-evolution operator e−iH^t to error ϵ , where the Hamiltonian H^=(⟨G|⊗I^)U^(|G⟩⊗I^) is the projection of a unitary oracle U^ onto the state |G⟩ created by another unitary oracle. Our algorithm solves this with a query complexity O(t+log⁡(1/ϵ)) to both oracles that is optimal with respect to all parameters in both the asymptotic and non-asymptotic regime, and also with low overhead, using at most two additional ancilla qubits. This approach to Hamiltonian simulation subsumes important prior art considering Hamiltonians which are d -sparse or a linear combination of unitaries, leading to significant improvements in space and gate complexity, such as a quadratic speed-up for precision simulations. It also motivates useful new instances, such as where H^ is a density matrix. A key technical result is `qubitization', which uses the controlled version of these oracles to embed any H^ in an invariant SU(2) subspace. A large class of operator functions of H^ can then be computed with optimal query complexity, of which e−iH^t is a special case.

arXiv:1610.06546•Quantum•Jul 12, 2019•1,228 citations

Parallel Quantum Algorithm for Hamiltonian Simulation

Zhicheng Zhang, Qisheng Wang, Mingsheng Ying

We study how parallelism can speed up quantum simulation. A parallel quantum algorithm is proposed for simulating the dynamics of a large class of Hamiltonians with good sparse structures, called uniform-structured Hamiltonians, including various Hamiltonians of practical interest like local Hamiltonians and Pauli sums. Given the oracle access to the target sparse Hamiltonian, in both query and gate complexity, the running time of our parallel quantum simulation algorithm measured by the quantum circuit depth has a doubly (poly-)logarithmic dependence polylog⁡log⁡(1/ϵ) on the simulation precision ϵ . This presents an exponential improvement over the dependence polylog⁡(1/ϵ) of previous optimal sparse Hamiltonian simulation algorithm without parallelism. To obtain this result, we introduce a novel notion of parallel quantum walk, based on Childs' quantum walk. The target evolution unitary is approximated by a truncated Taylor series, which is obtained by combining these quantum walks in a parallel way. A lower bound Ω(log⁡log⁡(1/ϵ)) is established, showing that the ϵ -dependence of the gate depth achieved in this work cannot be significantly improved.Our algorithm is applied to simulating three physical models: the Heisenberg model, the Sachdev-Ye-Kitaev model and a quantum chemistry model in second quantization. By explicitly calculating the gate complexity for implementing the oracles, we show that on all these models, the total gate depth of our algorithm has a polylog⁡log⁡(1/ϵ) dependence in the parallel setting.

arXiv:2105.11889•Quantum•Jan 15, 2024•28 citations

Digital Quantum Simulation of Minimal AdS/CFT

Laura García-Álvarez, I. L. Egusquiza, Lucas Lamata +3 more

We propose the digital quantum simulation of a minimal AdS/CFT model in controllable quantum platforms. We consider the Sachdev-Ye-Kitaev model describing interacting Majorana fermions with randomly distributed all-to-all couplings, encoding nonlocal fermionic operators onto qubits to efficiently implement their dynamics via digital techniques. Moreover, we also give a method for probing nonequilibrium dynamics and the scrambling of information. Finally, our approach serves as a protocol for reproducing a simplified low-dimensional model of quantum gravity in advanced quantum platforms as trapped ions and superconducting circuits.

arXiv:1607.08560•Physical Review Letters•Jul 25, 2017•178 citations

Supersymmetric Sachdev-Ye-Kitaev models

Wenbo Fu, Davide Gaiotto A, JUAN M. MALDACENA +1 more

We discuss a supersymmetric generalization of the Sachdev-Ye-Kitaev (SYK) model. These are quantum mechanical models involving $N$ Majorana fermions. The supercharge is given by a polynomial expression in terms of the Majorana fermions with random coefficients. The Hamiltonian is the square of the supercharge. The $\mathcal{N}=1$ model with a single supercharge has unbroken supersymmetry at large $N$, but nonperturbatively spontaneously broken supersymmetry in the exact theory. We analyze the model by looking at the large $N$ equation, and also by performing numerical computations for small values of $N$. We also compute the large $N$ spectrum of ``singlet'' operators, where we find a structure qualitatively similar to the ordinary SYK model. We also discuss an $\mathcal{N}=2$ version. In this case, the model preserves supersymmetry in the exact theory and we can compute a suitably weighted Witten index to count the number of ground states, which agrees with the large $N$ computation of the entropy. In both cases, we discuss the supersymmetric generalizations of the Schwarzian action which give the dominant effects at low energies.

Physical review. D/Physical review. D.•Jan 13, 2017•354 citations

Ground State Preparation via Qubitization

Charles Marteau

We describe a protocol for preparing the ground state of a Hamiltonian $H$ on a quantum computer. This is done by designing a quantum algorithm that implements the imaginary time evolution operator: $e^{-τH}$. The method relies on the so-called ``qubitization'' procedure of Low and Chuang which, assuming the existence of a unitary encoding of the Hamiltonian $H = \langle G| U_H |G\rangle$, produces a new operator $W_H$ whose moments are the Chebyshev polynomials of $H$ when projected on $|G\rangle$. Using this result and the expansion of $e^{-τH}$ in terms of Chebyshev polynomials we construct a circuit that implements an approximation of the imaginary time evolution operator which, at large time, projects any state on the ground state, provided a non-trivial initial overlap between the two. We illustrate our method on two models: the transverse field Ising model and a single qubit toy model.

arXiv:2306.14993•Jun 26, 2023•3 citations
We show that one can quantum simulate the dynamics of a Sachdev-Ye-Kitaev model with NNN Majorana modes for time ttt to precision \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ with gate complexity O(N7/2t+N5/2tpolylog(N/\ensuremathϵ))O({N}^{7/2}t+{N}^{5/2}t\phantom{\rule{0.16em}{0ex}}\mathrm{polylog}(N/\ensuremath{\epsilon}))O(N7/2t+N5/2tpolylog(N/\ensuremathϵ)). In addition to scaling sublinearly in the number of Hamiltonian terms, this gate complexity represents an exponential improvement in 1/\ensuremathϵ1/\ensuremath{\epsilon}1/\ensuremathϵ and large polynomial improvement in NNN and ttt over prior state-of-the-art algorithms which scale as O(N10t2/\ensuremathϵ)O({N}^{10}{t}^{2}/\ensuremath{\epsilon})O(N10t2/\ensuremathϵ). Our approach involves a variant of the qubitization technique in which we encode the Hamiltonian HHH as an asymmetric projection of a signal oracle UUU onto two different signal states prepared by state oracles, A∣0\ensuremath⟩\ensuremath↦∣A\ensuremath⟩A|0\ensuremath{\rangle}\ensuremath{\mapsto}|A\ensuremath{\rangle}A∣0\ensuremath⟩\ensuremath↦∣A\ensuremath⟩ and B∣0\ensuremath⟩\ensuremath↦∣B\ensuremath⟩B|0\ensuremath{\rangle}\ensuremath{\mapsto}|B\ensuremath{\rangle}B∣0\ensuremath⟩\ensuremath↦∣B\ensuremath⟩, such that H=\ensuremath⟨B∣U∣A\ensuremath⟩H=\ensuremath{\langle}B|U|A\ensuremath{\rangle}H=\ensuremath⟨B∣U∣A\ensuremath⟩. Our strategy for applying this method to the Sachdev-Ye-Kitaev model involves realizing BBB using only Hadamard gates and realizing AAA as a random quantum circuit.
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.
We present the problem of approximating the time-evolution operator e−iH^t to error ϵ , where the Hamiltonian H^=(⟨G|⊗I^)U^(|G⟩⊗I^) is the projection of a unitary oracle U^ onto the state |G⟩ created by another unitary oracle. Our algorithm solves this with a query complexity O(t+log⁡(1/ϵ)) to both oracles that is optimal with respect to all parameters in both the asymptotic and non-asymptotic regime, and also with low overhead, using at most two additional ancilla qubits. This approach to Hamiltonian simulation subsumes important prior art considering Hamiltonians which are d -sparse or a linear combination of unitaries, leading to significant improvements in space and gate complexity, such as a quadratic speed-up for precision simulations. It also motivates useful new instances, such as where H^ is a density matrix. A key technical result is `qubitization', which uses the controlled version of these oracles to embed any H^ in an invariant SU(2) subspace. A large class of operator functions of H^ can then be computed with optimal query complexity, of which e−iH^t is a special case.
We study how parallelism can speed up quantum simulation. A parallel quantum algorithm is proposed for simulating the dynamics of a large class of Hamiltonians with good sparse structures, called uniform-structured Hamiltonians, including various Hamiltonians of practical interest like local Hamiltonians and Pauli sums. Given the oracle access to the target sparse Hamiltonian, in both query and gate complexity, the running time of our parallel quantum simulation algorithm measured by the quantum circuit depth has a doubly (poly-)logarithmic dependence polylog⁡log⁡(1/ϵ) on the simulation precision ϵ . This presents an exponential improvement over the dependence polylog⁡(1/ϵ) of previous optimal sparse Hamiltonian simulation algorithm without parallelism. To obtain this result, we introduce a novel notion of parallel quantum walk, based on Childs' quantum walk. The target evolution unitary is approximated by a truncated Taylor series, which is obtained by combining these quantum walks in a parallel way. A lower bound Ω(log⁡log⁡(1/ϵ)) is established, showing that the ϵ -dependence of the gate depth achieved in this work cannot be significantly improved.Our algorithm is applied to simulating three physical models: the Heisenberg model, the Sachdev-Ye-Kitaev model and a quantum chemistry model in second quantization. By explicitly calculating the gate complexity for implementing the oracles, we show that on all these models, the total gate depth of our algorithm has a polylog⁡log⁡(1/ϵ) dependence in the parallel setting.
We propose the digital quantum simulation of a minimal AdS/CFT model in controllable quantum platforms. We consider the Sachdev-Ye-Kitaev model describing interacting Majorana fermions with randomly distributed all-to-all couplings, encoding nonlocal fermionic operators onto qubits to efficiently implement their dynamics via digital techniques. Moreover, we also give a method for probing nonequilibrium dynamics and the scrambling of information. Finally, our approach serves as a protocol for reproducing a simplified low-dimensional model of quantum gravity in advanced quantum platforms as trapped ions and superconducting circuits.
We discuss a supersymmetric generalization of the Sachdev-Ye-Kitaev (SYK) model. These are quantum mechanical models involving NNN Majorana fermions. The supercharge is given by a polynomial expression in terms of the Majorana fermions with random coefficients. The Hamiltonian is the square of the supercharge. The N=1\mathcal{N}=1N=1 model with a single supercharge has unbroken supersymmetry at large NNN, but nonperturbatively spontaneously broken supersymmetry in the exact theory. We analyze the model by looking at the large NNN equation, and also by performing numerical computations for small values of NNN. We also compute the large NNN spectrum of ``singlet'' operators, where we find a structure qualitatively similar to the ordinary SYK model. We also discuss an N=2\mathcal{N}=2N=2 version. In this case, the model preserves supersymmetry in the exact theory and we can compute a suitably weighted Witten index to count the number of ground states, which agrees with the large NNN computation of the entropy. In both cases, we discuss the supersymmetric generalizations of the Schwarzian action which give the dominant effects at low energies.
We describe a protocol for preparing the ground state of a Hamiltonian HHH on a quantum computer. This is done by designing a quantum algorithm that implements the imaginary time evolution operator: e−τHe^{-τH}e−τH. The method relies on the so-called ``qubitization'' procedure of Low and Chuang which, assuming the existence of a unitary encoding of the Hamiltonian H=⟨G∣UH∣G⟩H = \langle G| U_H |G\rangleH=⟨G∣UH​∣G⟩, produces a new operator WHW_HWH​ whose moments are the Chebyshev polynomials of HHH when projected on ∣G⟩|G\rangle∣G⟩. Using this result and the expansion of e−τHe^{-τH}e−τH in terms of Chebyshev polynomials we construct a circuit that implements an approximation of the imaginary time evolution operator which, at large time, projects any state on the ground state, provided a non-trivial initial overlap between the two. We illustrate our method on two models: the transverse field Ising model and a single qubit toy model.