Trotter error and gate complexity of the SYK and sparse SYK models
- URL: http://arxiv.org/abs/2502.18420v1
- Date: Tue, 25 Feb 2025 18:16:56 GMT
- Title: Trotter error and gate complexity of the SYK and sparse SYK models
- Authors: Yiyuan Chen, Jonas Helsen, Maris Ozols,
- Abstract summary: We study the Trotter error and gate complexity of the quantum simulation of the SYK model using Lie-Trotter- Suzuki formulas.<n>We find near-optimal gate complexities for simulating these models using Lie-Trotter- Suzuki formulas.
- Score: 0.8192907805418583
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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 Brandao (arXiv:2111.05324), 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, our gate complexity estimates for the first-order Lie-Trotter-Suzuki formula scales with $O(n^{k+\frac{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+\frac{1}{2}}t)$ for even $k$ and $O(n^{k+1}t)$ for odd $k$. Given that the SYK model has $\Theta(n^k)$ terms, these estimates are close to optimal. These gate complexities can be further improved when simulating the time-evolution of an arbitrary fixed input state $|\psi\rangle$, leading to a $O(n^2)$-reduction in gate complexity for first-order formulas and $O(\sqrt{n})$-reduction for higher-order formulas. We also apply our techniques to the sparse SYK model, a simplified variant of the SYK model obtained by deleting all but a $\Theta(n)$ fraction of the terms in a uniformly i.i.d. manner. We compute the average (over the random term removal) gate complexity for simulating this model using higher-order formulas to be $O(n^2 t)$, a bound that also holds for a general class of sparse Gaussian random Hamiltonians. Similar to the full SYK model, we obtain a $O(\sqrt{n})$-reduction simulating the time-evolution of an arbitrary fixed input state $|\psi\rangle$.
Related papers
- Coarse Graining with Neural Operators for Simulating Chaotic Systems [78.64101336150419]
Predicting the long-term behavior of chaotic systems is crucial for various applications such as climate modeling.<n>An alternative approach to such a full-resolved simulation is using a coarse grid and then correcting its errors through a temporalittext model.<n>We propose an alternative end-to-end learning approach using a physics-informed neural operator (PINO) that overcomes this limitation.
arXiv Detail & Related papers (2024-08-09T17:05:45Z) - Sparsity dependence of Krylov state complexity in the SYK model [0.0]
We study the Krylov state complexity of the Sachdev-Ye-Kitaev (SYK) model for $N le 28$ Majorana fermions with $q$-body fermion interaction.<n>We find that the peak value of complexity does not change as we increase $k$ beyond $k ge k_textmin$ at large temperatures.
arXiv Detail & Related papers (2024-07-30T05:57:14Z) - Hamiltonian simulation of minimal holographic sparsified SYK model [0.0]
Hamiltonian simulation of the sparsified SYK model with $N$ Majorana fermions and $q=4$ (quartic interactions)<n>This complexity implies that with less than a hundred logical qubits and about $106$ gates, it will be possible to achieve an advantage in this model and simulate real-time dynamics up to scrambling time.
arXiv Detail & Related papers (2024-04-23T06:49:34Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
Single-Index Models are high-dimensional regression problems with planted structure.
We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
arXiv Detail & Related papers (2024-03-08T18:50:19Z) - Sachdev-Ye-Kitaev model on a noisy quantum computer [1.0377683220196874]
We study the SYK model -- an important toy model for quantum gravity on IBM's superconducting qubit quantum computers.
We compute return probability after time $t$ and out-of-time order correlators (OTOC) which is a standard observable of quantifying the chaotic nature of quantum systems.
arXiv Detail & Related papers (2023-11-29T19:00:00Z) - Fast Rates for Maximum Entropy Exploration [52.946307632704645]
We address the challenge of exploration in reinforcement learning (RL) when the agent operates in an unknown environment with sparse or no rewards.
We study the maximum entropy exploration problem two different types.
For visitation entropy, we propose a game-theoretic algorithm that has $widetildemathcalO(H3S2A/varepsilon2)$ sample complexity.
For the trajectory entropy, we propose a simple algorithm that has a sample of complexity of order $widetildemathcalO(mathrmpoly(S,
arXiv Detail & Related papers (2023-03-14T16:51:14Z) - On the complexity of implementing Trotter steps [2.1369834525800138]
We develop methods to perform faster Trotter steps with complexity sublinear in number of terms.
We also realize faster Trotter steps when certain blocks of Hamiltonian coefficients have low rank.
Our result suggests the use of Hamiltonian structural properties as both necessary and sufficient to implement Trotter synthesis steps with lower gate complexity.
arXiv Detail & Related papers (2022-11-16T19:00:01Z) - What Makes A Good Fisherman? Linear Regression under Self-Selection Bias [32.6588421908864]
In the classical setting of self-selection, the goal is to learn $k$ models, simultaneously from observations $(x(i), y(i))$.
In this work, we present the first computationally and statistically efficient estimation algorithms for the most standard setting of this problem where the models are linear.
arXiv Detail & Related papers (2022-05-06T14:03:05Z) - Average-case Speedup for Product Formulas [69.68937033275746]
Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems.
We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states.
Our results open doors to the study of quantum algorithms in the average case.
arXiv Detail & Related papers (2021-11-09T18:49:48Z) - Hamiltonian simulation with random inputs [74.82351543483588]
Theory of average-case performance of Hamiltonian simulation with random initial states.
Numerical evidence suggests that this theory accurately characterizes the average error for concrete models.
arXiv Detail & Related papers (2021-11-08T19:08:42Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
We show that model-based MARL achieves a sample complexity of $tilde O(|S||B|(gamma)-3epsilon-2)$ for finding the Nash equilibrium (NE) value up to some $epsilon$ error.
We also show that such a sample bound is minimax-optimal (up to logarithmic factors) if the algorithm is reward-agnostic, where the algorithm queries state transition samples without reward knowledge.
arXiv Detail & Related papers (2020-07-15T03:25:24Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
We describe a series of algorithms that efficiently implement Gaussian model-X knockoffs to control the false discovery rate on large scale feature selection problems.
We test our methods on problems with $p$ as large as $500,000$.
arXiv Detail & Related papers (2020-06-15T21:55:34Z) - Model-Based Reinforcement Learning with Value-Targeted Regression [48.92439657407732]
We focus on finite-horizon episodic RL where the transition model $P$ belongs to a known family of models $mathcalP$.
We derive a bound on the regret, which, in the special case of linear mixtures, the regret bound takes the form $tildemathcalO(dsqrtH3T)$.
arXiv Detail & Related papers (2020-06-01T17:47:53Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings.
In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$.
We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
arXiv Detail & Related papers (2020-02-25T19:18:36Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.