Skip to content

Spin models

Overview

Classical and quantum spin systems are prototypical models for a wide range of physical phenomena including: magnetism, neuron activity, simplified models of materials and molecules, and networks. Studying the properties of spin Hamiltonians can also provide useful insights in quantum information science.

A number of scientific and industrial problems can be mapped onto finding the ground or thermal states of classical or quantum spin models, for example solving combinatorial optimization problems, training energy-based models in machine learning, and simulating low energy models of quantum chemistry [1].

Simulating the dynamics of quantum spin models is primarily of interest for quantum information science, and condensed matter physics or chemistry, for example interpreting nuclear magnetic resonance [2, 3] or related spectroscopy experiments [4, 5].

Because of the natural mapping between spin-\(1/2\) systems and qubits, as well as the locality of interactions commonly present, the resources required to simulate simple spin models using quantum algorithms can be much lower than for problems in areas like quantum chemistry or cryptography.

While our discussion will focus on quantum algorithms designed to be run on fault-tolerant quantum computers, the simple Hamiltonians of spin models are naturally realized in many physical systems. This has led to the use of analog simulators [6, 7], such as arrays of trapped ions or neutral atoms, for simulating the static and dynamic properties of interesting spin models. We will comment briefly on this below.

Actual end-to-end problem(s) solved

The most commonly studied spin models are those with pairwise interactions, referred to as \(2\)-local Hamiltonians. We note that the interactions are not necessarily geometrically local, although this will be present in many models of physical systems. Given a graph \(\mathcal{G}\) with \(N\) vertices \(\{v_i\}\) and \(L\) edges \(\{E_{ij}\}\) we associate a classical or quantum spin with each vertex, and an interaction between spins with each edge. We can also add one-body interactions acting on individual spins. The Hamiltonian can then be written as

\[\begin{equation} \label{Eq:SpinHamiltonian} H = \sum_{v_i\in V} \sum_{\alpha \in \{x,y,z\}} B_i^\alpha \sigma_\alpha^i + \sum_{E_{ij} \in E} \sum_{\alpha, \beta \in \{x,y,z\}} J_{ij}^{\alpha \beta} \sigma_\alpha^i \sigma_\beta^j \end{equation}\]

where \(\{\sigma_x^i,\sigma_y^i,\sigma_z^i\}\) denote the Pauli operators \(X_i,Y_i,Z_i\) acting on site \(i\), and \(\{B_i^\alpha\}, \{J_{ij}^{\alpha \beta}\}\) are coefficients. For classical spin Hamiltonians, the sums are restricted to \(Z\) operators. The Hamiltonian in Eq. \(\eqref{Eq:SpinHamiltonian}\) encompasses a wide range of spin models, including: the classical Ising model

\[\begin{equation} H = \sum_i B_i Z_i + \sum_{ij} J_{ij} Z_i Z_j \end{equation}\]

which also describes the Hamiltonians arising from quadratic unconstrained binary optimization (QUBO) problems, the (quantum) transverse field Ising model (TFIM)

\[\begin{equation} H = B \sum_i X_i + J \sum_{ij} Z_i Z_j\,, \end{equation}\]

and the Heisenberg model with a site-dependent magnetic field, defined in 1D with nearest-neighbor interactions by

\[\begin{equation} H = \sum_j B_j Z_j + J^x X_j X_{j+1} + J^y Y_j Y_{j+1} + J^z Z_j Z_{j+1}. \end{equation}\]

Across the different models, we can vary the dimension, locality of interactions (e.g. nearest-neighbor vs. fully connected vs. power-law), and values of the site-dependent coefficients in comparison to the interaction terms. The models can be extended beyond 2-local by considering couplings of 3 or more spins—see for example \(p\)-spin models, which are \(p\)-local [8]. The above definitions can be extended from spin-\(1/2\) systems to higher spin operators by generalizing the Pauli operators with their higher dimensional counterparts.

For classical spin models we seek to prepare the ground or thermal states of the model, as these may encode, for example, the solution to a combinatorial optimization problem, or a probability distribution that can be used for generative modelling. For quantum spin models, we similarly seek to compute ground or thermal states. However, because these are not classical states that can be easily extracted, we typically wish to sample observables with respect to these states. Examples include the energy, the magnetization of the system, or correlations between sites. In dynamical simulations of quantum systems, we seek to determine how observables of interest vary as a function of evolution time. Examples include the magnetization (used to infer the Hamiltonian in NMR [9] or related [10] experiments), or the growth of correlations between sites to probe thermalization. Hamiltonian simulation can efficiently access not only any feature that could be observed for simulated targets (e.g., solid-state materials of interest), but also additional features [11] which can lead to deeper understanding of the physics involved. Since studies of quench dynamics often require preparation of simple states (such as product states or the ground states of classically solvable Hamiltonians) and the measurement of local observables, propagation under the Hamiltonian typically dominates the simulation cost. For lattice systems with \(N\) spins in \(D\) dimensions, it is conventional to consider evolution times that scale as \(\Omega\left(N^{1/D}\right)\), as the system must evolve for this long for self-thermalization to take place or even for information to propagate across the system due to the Lieb–Robinson bound [12].

Dominant resource cost/complexity

For a system of \(N\) spin-\(1/2\) particles, we require \(N\) qubits to represent the state of the system. For \(N\) spin-\(S\) particles, the problem can be mapped to qubits in different ways, for example using \(N \lceil \log_2(2S+1)\rceil\) [13] qubits or using \(2NS\) qubits [5].

Quantum algorithms for preparing the ground or Gibbs states of classical spin systems are discussed in detail in the sections on combinatorial optimization, and energy-based machine learning models, respectively. We will restrict our discussion to the resources required for performing time evolution of quantum spin models. The reason for this is that quantum algorithms for preparing ground or thermal states require similar primitives for Hamiltonian access to algorithms for time evolution (e.g., block-encodings or Hamiltonian simulation itself) and use these in conjunction with either: eigenstate filtering approaches [14, 15] based on quantum singular value transformation, adiabatic state preparation, quantum phase estimation from a trial state, or quantum algorithms for thermal state preparation. More detailed discussions of these algorithms and their caveats can be found on the linked pages, as well as in the discussion of quantum algorithms for simulating molecules and materials or the Fermi–Hubbard model, where preparing (approximate) eigenstates is the primary topic of interest. All of these algorithms depend on either an overlap between the trial state and the target state, the minimum gap along an adiabatic path, or the mixing time of a Markov chain—all of which are difficult to bound in the general case.

When simulating the time evolution of spin systems, the most efficient algorithms exploit the locality of interactions in the Hamiltonian, and the resulting commutation structure. For \(2\)-local spin-\(1/2\) systems on a \(D\)-dimensional lattice with nearest-neighbor geometric locality, algorithms with almost optimal gate complexity are known for performing time evolution. Reference [16] showed that \((2k)\)th-order product formulae scale as \(\mathcal{O}\left( (Nt)^{1+1/2k} / \epsilon^{1/2k} \right)\) to simulate time evolution for time \(t\) to accuracy \(\epsilon\), using a Hamiltonian given in the Pauli access model. Note that this expression suppresses the \(5^{2k}\) constant factor present in \((2k)\)th-order Trotter. Similarly, [17] gave an algorithm with complexity \(\mathcal{O}\left( Nt \cdot \mathrm{polylog}(Nt/\epsilon) \right)\) for Hamiltonians given in the sparse access model. In contrast, note that approaches that are asymptotically optimal in the black-box setting, such as quantum signal processing, have a gate complexity of \(\mathcal{O}\left( N^2Dt + \log(1/\epsilon) \right)\) using a block-encoding based on linear combinations of unitaries (LCU).

Spin Hamiltonians with power-law interactions were studied in [18, 19], that is, where the interaction strength between spins \(i\) and \(j\) depends inversely on a power of the distance between the spins, denoted by \(\nrm{i-j}_2\). For a \(D\)-dimensional lattice with \(2\)-local interactions with interaction strengths scaling as \(1/\nrm{i-j}_2^\alpha\), \((2k)\)th-order Trotter gives a scaling of (as above, suppressing the \(5^{2k}\) constant factor present in \(2k\)th-order Trotter) [19]

\[\begin{equation} \widetilde{\mathcal{O}}\left( \begin{array}{rcl} N^{3-\frac{\alpha}{D}(1+1/2k)+1/k} t^{1+1/2k}\epsilon^{-1/2k} & & \text{for } 0 \leq \alpha < D, \\ N^{2+1/2k} t^{1+1/2k}\epsilon^{-1/2k} & & \alpha \geq D\end{array} \right). \end{equation}\]

Focusing on the \(D=1\) case, if one were to directly apply quantum signal processing based on a block-encoding via the LCU approach, the scaling would be

\[\begin{equation} \widetilde{\mathcal{O}}\left( N^2 t + \log(1/\epsilon) \right) \end{equation}\]

These asymptotic complexities are complemented by the constant factor analyses discussed in the following section.

For estimating expectation values of observables to precision \(\epsilon\), one can either consider directly sampling and then re-preparing the state of interest (scaling as \(\mathcal{O}\left( 1/\epsilon^2 \right)\)), or coherent approaches based on amplitude estimation scaling as \(\mathcal{O}\left( 1/\epsilon \right)\), but requiring a longer coherent circuit depth. Measurements of simple observables, such as the magnetization, can be obtained through the computational basis measurements on single qubits. For more complicated observables, one can consider the approaches in [20, 21, 22], discussed in more detail in the section on quantum chemistry.

Existing error corrected resource estimates

A number of fault-tolerant resource estimates for simulating the dynamics of spin systems, or for finding their ground states via quantum phase estimation have been reported in the literature. In such calculations it is necessary to optimize the constant factor contributions from implementing the algorithmic primitives used. A detailed comparative study on simulating the dynamics of a 1D nearest-neighbor Heisenberg model was reported in [23], comparing the logical qubit and \(T\) gate counts of product formulae, Taylor series, and quantum signal processing. The two most efficient approaches are shown in the first two rows of Table 1.

Problem Method # Spins # \(T\) gates Logical qubits Parameters
1D Heisenberg dyn. QSP \(50\) \(2.4\times 10^9\) \(67\) \(\begin{gathered}B_j \in [-1,1], J^x=J^y=J^z=1,\\t=N, \epsilon=10^{-3}\end{gathered}\)  [23]
1D Heisenberg dyn. Trotter (6th order) \(50\) \(1.8\times 10^8\) \(50\) \(\begin{gathered}B_j \in [-1,1], J^x=J^y=J^z=1,\\t=N, \epsilon=10^{-3}\end{gathered}\) [23]
2D NN TFIM1 dyn. Trotter (4th order) \(100\) \(1.7\times 10^5\) \(100\) \(t=10/J, B=J, \epsilon=10^{-2}\) [24, 25]
2D \(1/r^2\) TFIM dyn. Trotter (4th order) \(100\) \(1.5\times 10^7\) \(100\) \(t=10/J, B=J, \epsilon=10^{-2}\) [24]
2D Heisenberg ground state with nearest- and next-nearest-neighbor interactions Qubitized QPE \(100\) \(10^8\) N.C.2 \(\epsilon=10^{-2}, J_1=1, J_2=0.5, B_j=0\)         [26]

Table 1: Fault-tolerant resource estimates for quantum phase estimation (QPE) and dynamics simulation (dyn.) applied to different spin models. The presented gate counts are for a single run of the circuit. The results presented in rows 1 and 2 can be compared to each other, and both target an error of \(\epsilon=10^{-3}\) in the operator norm distance between the ideal and implemented time evolution unitary. While [23] presents both analytic and empirical Trotter error bounds, the gate count presented in the table is that resulting from the empirical bound, though we remark that more recent analytic bounds are close to matching the empirical bounds [19]. The results presented in rows 3 and 4 can be compared to each other, and determine the number of Trotter steps used empirically by targeting an error of \(\epsilon=10^{-2}\) in a particular spatially averaged local observable, and then extrapolating this behavior to larger system sizes.

On a fault-tolerant quantum computer arbitrary angle rotation gates must be synthesized using a larger number of \(T\) and Clifford gates [27]. The number of \(T\) gates to synthesize a group of parallel rotation gates can be reduced if they share the same angle [28, 29]. This technique can be exploited in fault-tolerant compilations of algorithms simulating physical spin systems, which often exhibit features such as translational invariance.

In addition to the entries given in Table 1, fault-tolerant approaches to simulating NMR [3] and muon spectroscopy [5] experiments, which are effectively spin model simulations, have been considered.

Caveats

The decision forms of the ground state problem for 2-local classical and quantum spin models are NP–complete [30, 31] and QMA–complete [32], respectively. As such, we do not expect quantum algorithms to provide efficient solutions to these problems in the general case. Nevertheless, given the success of classical heuristics for these problems, one may hope to observe a similar benefit from quantum heuristic algorithms, such as Monte Carlo–style Gibbs sampling algorithms.

In contrast, simulating the dynamics of spin models is a BQP-complete problem [33], and is likely one of the most simple beyond-classical calculations that could be performed on a future fault-tolerant quantum computer. While such a computation would be of great scientific interest, providing new insights in quantum information and many-body physics, it is currently unclear whether dynamics simulations of large systems will have a direct impact on industrially relevant applications.

Comparable classical complexity and challenging instance sizes

Exact classical simulations of quantum spin models are exponentially costly in system size. Exact simulations that consider a time evolution long enough for information to propagate across the system (as per the Lieb–Robinson bound) are thus limited to around 50 spins using the largest classical supercomputers [34, 23].

Approximate classical algorithms for studying quantum spin systems include tensor network approaches and quantum Monte Carlo methods. These methods provide empirically accurate results for computing the ground states of physically motivated spin systems, in particular those with local interactions, in low dimensions. For example, the ground states of local, gapped 1D Hamiltonians have area law entanglement, and so can be efficiently represented by matrix product states. Similar statements can be made in 2D, using e.g. projected entangled pair states (PEPS).

In contrast, these methods are less accurate when performing simulations of quantum spin dynamics [35, 36]. In these systems the entanglement entropy grows linearly with time [37], resulting in a cost that grows exponentially with time for tensor network approaches targeting fixed accuracy. For example, it was claimed in [24] that simulations of the dynamics of the 2D TFIM for \(N=100\) spins would be far beyond the current capabilities of tensor network methods [24].

Many physical systems are subject to strong interactions with their environment which limits their coherence times. In these cases, the behavior of the system can often be reproduced by simulating a smaller number of spins (e.g. \(\leq 30\)) and accounting for the interactions with the environment through physically motivated heuristics [38]. Such simulations (accessible via open source software libraries) are used to analyze NMR [9] and muon spectroscopy experiments [10].

Speedup

The speedup for computing the ground states of quantum spin Hamiltonians over classical approximate methods (such as tensor networks or quantum Monte Carlo) is currently an open research question. A large speedup appears to require the availability of good initial states for quantum algorithms, without also being able to efficiently solve the problem classically [39].

The simulation of quantum spin dynamics appears to be exponentially costly using all known classical methods. As such, quantum algorithms for Hamiltonian simulation would provide an exponential speedup for this task. This would likely provide insights in quantum information and many–body physics. As an example, such systems could study the competition and interplay between thermalization and many–body localization in quantum systems.

NISQ implementations

Quantum spin models are commonly used as benchmark systems for NISQ algorithms—e.g. finding ground states [40], simulating dynamics [41], or probing thermalization [42].

The Hamiltonians of spin models are also naturally realized in a wide range of physical systems, including trapped ions or neutral atoms [6, 7]. For example, recent experiments in neutral atom systems have studied the dynamics of \(\mathcal{O}\left( 200 \right)\) spins, which went beyond the capabilities of classical simulation via matrix product state approaches [43, 44]. Analog simulators are already an important tool providing new scientific insights, and they set a high bar for the future performance of fault-tolerant approaches to simulating spin systems.

Outlook

Simulating the behavior of spin systems is arguably one of the most natural tasks for quantum computers, and is exponentially costly using all known classical methods. Such simulations can provide important insights into questions in quantum information and many-body physics, as well as acting as models for more complex systems in condensed matter physics and chemistry.

Fault-tolerant resource estimates for quantum algorithms simulating spin systems are among the lowest known for beyond-classical tasks. Nevertheless, analog quantum simulators are already able to natively simulate the dynamics of hundreds of spins. In order to surpass these capabilities, digital approaches may need to consider more complex observables, or target accuracies not available with error correction.

In addition, for many systems of scientific interest in related fields, such as chemistry or condensed matter physics, decoherence–inducing interactions with the environment often limit the required simulation sizes. Identifying applications requiring accurate simulation of the dynamics of large spin models would increase the impact and applicability of quantum algorithms in this area.

Bibliography

  1. Ruslan N. Tazhigulov, Shi-Ning Sun, Reza Haghshenas, Huanchen Zhai, Adrian T.K. Tan, Nicholas C. Rubin, Ryan Babbush, Austin J. Minnich, and Garnet Kin-Lic Chan. Simulating models of challenging correlated molecules and materials on the sycamore quantum processor. PRX Quantum, 3:040318, 11 2022. arXiv: https://arxiv.org/abs/2203.15291. URL: https://link.aps.org/doi/10.1103/PRXQuantum.3.040318, doi:10.1103/PRXQuantum.3.040318.

  2. Dries Sels, Hesam Dashti, Samia Mora, Olga Demler, and Eugene Demler. Quantum approximate bayesian computation for nmr model inference. Nature Machine Intelligence, 2(7):396–402, 7 2020. arXiv: https://arxiv.org/abs/1910.14221. URL: https://doi.org/10.1038/s42256-020-0198-x, doi:10.1038/s42256-020-0198-x.

  3. Thomas E. O'Brien, Lev B. Ioffe, Yuan Su, David Fushman, Hartmut Neven, Ryan Babbush, and Vadim Smelyanskiy. Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments. PRX Quantum, 3:030345, 9 2022. arXiv: https://arxiv.org/abs/2109.02163. URL: https://link.aps.org/doi/10.1103/PRXQuantum.3.030345, doi:10.1103/PRXQuantum.3.030345.

  4. A. Chiesa, F. Tacchino, M. Grossi, P. Santini, I. Tavernelli, D. Gerace, and S. Carretta. Quantum hardware simulating four-dimensional inelastic neutron scattering. Nature Physics, 15(5):455–459, 5 2019. arXiv: https://arxiv.org/abs/1809.07974. URL: https://doi.org/10.1038/s41567-019-0437-4, doi:10.1038/s41567-019-0437-4.

  5. Sam McArdle. Learning from physics experiments with quantum computers: applications in muon spectroscopy. PRX Quantum, 2:020349, 6 2021. arXiv: https://arxiv.org/abs/2012.06602. URL: https://link.aps.org/doi/10.1103/PRXQuantum.2.020349, doi:10.1103/PRXQuantum.2.020349.

  6. Immanuel Bloch, Jean Dalibard, and Sylvain Nascimbène. Quantum simulations with ultracold quantum gases. Nature Physics, 8(4):267–276, 4 2012. URL: http://www.nature.com/doifinder/10.1038/nphys2259, arXiv:nphys2259, doi:10.1038/nphys2259.

  7. I. M. Georgescu, S. Ashhab, and Franco Nori. Quantum simulation. Reviews of Modern Physics, 86(1):153–185, 2014. arXiv: https://arxiv.org/abs/1308.6253. arXiv:1308.6253, doi:10.1103/RevModPhys.86.153.

  8. B. Derrida. Random-energy model: limit of a family of disordered models. Physical Review Letters, 45:79–82, 7 1980. URL: https://link.aps.org/doi/10.1103/PhysRevLett.45.79, doi:10.1103/PhysRevLett.45.79.

  9. H.J. Hogben, M. Krzystyniak, G.T.P. Charnock, P.J. Hore, and Ilya Kuprov. Spinach – a software library for simulation of spin dynamics in large spin systems. Journal of Magnetic Resonance, 208(2):179–194, 2011. URL: https://www.sciencedirect.com/science/article/pii/S1090780710003575, doi:https://doi.org/10.1016/j.jmr.2010.11.008.

  10. Pietro Bonfà, Jonathan Frassineti, Muhammad Maikudi Isah, Ifeanyi John Onuorah, and Samuele Sanna. Undi: an open-source library to simulate muon-nuclear interactions in solids. Computer Physics Communications, 260:107719, 2021. URL: https://www.sciencedirect.com/science/article/pii/S0010465520303556, doi:https://doi.org/10.1016/j.cpc.2020.107719.

  11. Joana Fraxanet, Tymoteusz Salamon, and Maciej Lewenstein. The Coming Decades of Quantum Simulation, pages 85–125. Springer International Publishing, Cham, 2023, arXiv: https://arxiv.org/abs/2204.08905. URL: https://doi.org/10.1007/978-3-031-32469-7\_4, doi:10.1007/978-3-031-32469-7\_4.

  12. Chi-Fang Chen, Andrew Lucas, and Chao Yin. Speed limits and locality in many-body quantum dynamics. arXiv: https://arxiv.org/abs/2303.07386, 2023.

  13. Nicolas PD Sawaya, Tim Menke, Thi Ha Kyaw, Sonika Johri, Alán Aspuru-Guzik, and Gian Giacomo Guerreschi. Resource-efficient digital quantum simulation of d-level systems for photonic, vibrational, and spin-s hamiltonians. npj Quantum Information, 6(1):1–13, 2020. arXiv: https://arxiv.org/abs/1909.12847. doi:https://doi.org/10.1038/s41534-020-0278-0.

  14. Lin Lin and Yu Tong. Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4:361, 2020. arXiv: https://arxiv.org/abs/1910.14596. doi:10.22331/q-2020-11-11-361.

  15. Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum, 4:372, 2020. arXiv: https://arxiv.org/abs/2002.12508. doi:10.22331/q-2020-12-14-372.

  16. Andrew M Childs and Yuan Su. Nearly optimal lattice simulation by product formulas. Physical Review Letters, 123(5):050503, 2019. arXiv: https://arxiv.org/abs/1901.00564. arXiv:1901.00564, doi:10.1103/PhysRevLett.123.050503.

  17. Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low. Quantum algorithm for simulating real time evolution of lattice hamiltonians. In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS), 350–360. 2018. arXiv: https://arxiv.org/abs/1801.03922. doi:10.1109/FOCS.2018.00041.

  18. Minh C. Tran, Andrew Y. Guo, Yuan Su, James R. Garrison, Zachary Eldredge, Michael Foss-Feig, Andrew M. Childs, and Alexey V. Gorshkov. Locality and digital quantum simulation of power-law interactions. Physical Review X, 9:031006, 7 2019. arXiv: https://arxiv.org/abs/1808.05225. URL: https://link.aps.org/doi/10.1103/PhysRevX.9.031006, doi:10.1103/PhysRevX.9.031006.

  19. Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. Theory of trotter error with commutator scaling. Physical Review X, 2 2021. arXiv: https://arxiv.org/abs/1912.08854. doi:10.1103/physrevx.11.011020.

  20. Patrick Rall. Quantum algorithms for estimating physical quantities using block encodings. Physical Review A, 102:022408, 8 2020. arXiv: https://arxiv.org/abs/2004.06832. URL: https://link.aps.org/doi/10.1103/PhysRevA.102.022408, doi:10.1103/PhysRevA.102.022408.

  21. William J. Huggins, Kianna Wan, Jarrod McClean, Thomas E. O'Brien, Nathan Wiebe, and Ryan Babbush. Nearly optimal quantum algorithm for estimating multiple expectation values. Physical Review Letters, 129:240501, 12 2022. arXiv: https://arxiv.org/abs/2111.09283. URL: https://link.aps.org/doi/10.1103/PhysRevLett.129.240501, doi:10.1103/PhysRevLett.129.240501.

  22. Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, and Giacomo Nannicini. Quantum tomography using state-preparation unitaries. In Proceedings of the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1265–1318. 2023. arXiv: https://arxiv.org/abs/2207.08800. doi:10.1137/1.9781611977554.ch47.

  23. Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences, 115(38):9456–9461, 2018. arXiv: https://arxiv.org/abs/1711.10980. doi:10.1073/pnas.1801723115.

  24. S Flannigan, N Pearson, G H Low, A Buyskikh, I Bloch, P Zoller, M Troyer, and A J Daley. Propagation of errors and quantitative quantum simulation with quantum advantage. Quantum Science and Technology, 7(4):045025, 8 2022. arXiv: https://arxiv.org/abs/2204.13644. URL: https://dx.doi.org/10.1088/2058-9565/ac88f5, doi:10.1088/2058-9565/ac88f5.

  25. Michael E. Beverland, Prakash Murali, Matthias Troyer, Krysta M. Svore, Torsten Hoeffler, Vadym Kliuchnikov, Guang Hao Low, Mathias Soeken, Aarthi Sundaram, and Alexander Vaschillo. Assessing requirements to scale to practical quantum advantage. arXiv: https://arxiv.org/abs/2211.07629, 2022. URL: http://arxiv.org/abs/2211.07629.

  26. Nobuyuki Yoshioka, Tsuyoshi Okubo, Yasunari Suzuki, Yuki Koizumi, and Wataru Mizukami. Hunting for quantum-classical crossover in condensed matter problems. arXiv: https://arxiv.org/abs/2210.14109, 2022.

  27. A Yu Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191, 1997. doi:10.1070/RM1997v052n06ABEH002155.

  28. Craig Gidney. Halving the cost of quantum addition. Quantum, 2:74, 2018. arXiv: https://arxiv.org/abs/1709.06648. arXiv:1709.06648, doi:10.22331/q-2018-06-18-74.

  29. Earl T Campbell. Early fault-tolerant simulations of the hubbard model. Quantum Science and Technology, 7(1):015007, 11 2021. arXiv: https://arxiv.org/abs/2012.09238. URL: https://dx.doi.org/10.1088/2058-9565/ac3110, doi:10.1088/2058-9565/ac3110.

  30. F Barahona. On the computational complexity of ising spin glass models. Journal of Physics A: Mathematical and Theoretical, 15(10):3241–3253, 10 1982. URL: https://doi.org/10.1088/0305-4470/15/10/028, doi:10.1088/0305-4470/15/10/028.

  31. Andrew Lucas. Ising formulations of many np problems. Frontiers in Physics, 2014. arXiv: https://arxiv.org/abs/1302.5843. URL: https://www.frontiersin.org/articles/10.3389/fphy.2014.00005, doi:10.3389/fphy.2014.00005.

  32. Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local hamiltonian problem. SIAM Journal on Computing, 35(5):1070–1097, 2006. Earlier version in FSTTCS'04. arXiv: https://arxiv.org/abs/quant-ph/0406180. doi:10.1137/S009753970444522.

  33. Seth Lloyd. Universal quantum simulators. Science, 273(5278):1073–1078, 1996. doi:10.1126/science.273.5278.1073.

  34. Thomas Häner and Damian S Steiger. 0.5 petabyte simulation of a 45-qubit quantum circuit. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. New York, NY, USA, 2017. Association for Computing Machinery. arXiv: https://arxiv.org/abs/1704.01127. URL: https://doi.org/10.1145/3126908.3126947, doi:10.1145/3126908.3126947.

  35. Norbert Schuch, Michael M. Wolf, Frank Verstraete, and J. Ignacio Cirac. Entropy scaling and simulability by matrix product states. Physical Review Letters, 100(3):030504, 2008. arXiv: https://arxiv.org/abs/0705.0292. doi:10.1103/PhysRevLett.100.030504.

  36. Ulrich Schollwöck. The density-matrix renormalization group in the age of matrix product states. Annals of Physics, 326(1):96–192, 2011. arXiv: https://arxiv.org/abs/1008.3477. arXiv:1008.3477, doi:10.1016/j.aop.2010.09.012.

  37. Pasquale Calabrese and John Cardy. Evolution of entanglement entropy in one-dimensional systems. Journal of Statistical Mechanics: Theory and Experiment, pages 04010, 2005. arXiv: https://arxiv.org/abs/cond-mat/0503393. arXiv:0503393, doi:10.1088/1742-5468/2005/04/P04010.

  38. J. M. Wilkinson and S. J. Blundell. Information and decoherence in a muon-fluorine coupled system. Physical Review Letters, 125:087201, 8 2020. arXiv: https://arxiv.org/abs/2003.02762. URL: https://link.aps.org/doi/10.1103/PhysRevLett.125.087201, doi:10.1103/PhysRevLett.125.087201.

  39. Seunghoon Lee, Joonho Lee, Huanchen Zhai, Yu Tong, Alexander M. Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi-Hao Cui, Wenyuan Liu, Michael Kastoryano, Ryan Babbush, John Preskill, David R. Reichman, Earl T. Campbell, Edward F. Valeev, Lin Lin, and Garnet Kin-Lic Chan. Evaluating the evidence for exponential quantum advantage in ground-state quantum chemistry. Nature Communications, 14(1):1952, 2023. arXiv: https://arxiv.org/abs/2208.02199. URL: https://doi.org/10.1038/s41467-023-37587-6, doi:10.1038/s41467-023-37587-6.

  40. Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549(7671):242–246, 9 2017. arXiv: https://arxiv.org/abs/1704.05018. URL: https://doi.org/10.1038/nature23879, doi:10.1038/nature23879.

  41. Eliott Rosenberg, Trond Andersen, Rhine Samajdar, Andre Petukhov, Jesse Hoke, Dmitry Abanin, Andreas Bengtsson, Ilya Drozdov, Catherine Erickson, Paul Klimov, and others. Dynamics of magnetization at infinite temperature in a heisenberg spin chain. arXiv: https://arxiv.org/abs/2306.09333, 2023.

  42. X Mi, AA Michailidis, S Shabani, KC Miao, PV Klimov, J Lloyd, E Rosenberg, R Acharya, I Aleiner, TI Andersen, and others. Stable quantum-correlated many body states via engineered dissipation. arXiv: https://arxiv.org/abs/2304.13878, 2023.

  43. Sepehr Ebadi, Tout T. Wang, Harry Levine, Alexander Keesling, Giulia Semeghini, Ahmed Omran, Dolev Bluvstein, Rhine Samajdar, Hannes Pichler, Wen Wei Ho, Soonwon Choi, Subir Sachdev, Markus Greiner, Vladan Vuletic, and Mikhail D. Lukin. Quantum phases of matter on a 256-atom programmable quantum simulator. Nature, 595:227, 2021. arXiv: https://arxiv.org/abs/2012.12281. URL: http://arxiv.org/abs/2012.12281, arXiv:2012.12281, doi:10.1038/s41586-021-03582-4.

  44. Pascal Scholl, Michael Schuler, Hannah J. Williams, Alexander A. Eberharter, Daniel Barredo, Kai Niklas Schymik, Vincent Lienhard, Louis Paul Henry, Thomas C. Lang, Thierry Lahaye, Andreas M. Läuchli, and Antoine Browaeys. Quantum simulation of 2d antiferromagnets with hundreds of rydberg atoms. Nature, 595(7866):233–238, 2021. arXiv: https://arxiv.org/abs/2012.12268. doi:10.1038/s41586-021-03585-1.

  1. 2D nearest-neighbor transverse field Ising model. ↩

  2. Not computed, scales as \(\mathcal{O}\left( N+ \log(N) + \log(N/\epsilon) \right)\). ↩