Skip to content

Fermi–Hubbard model

Overview

The Fermi–Hubbard model was originally introduced as a simplified model of electrons in materials [1], closely related to the tight-binding model. It displays a wide range of behaviors including metallic, insulating, and antiferromagnetic phases. The model has more recently found applicability in studying high-temperature superconductivity. The 2D Fermi–Hubbard model has a complex phase diagram that appears to reproduce universal (rather than chemical-specific) features of the phase diagram of cuprate high-temperature superconductors.

General analytic solutions are not known (beyond 1D chains or specific parameter regimes—see [2] for a recent discussion), which has motivated the use of numerical methods to understand the physics of the Fermi–Hubbard model. More recently, there has been increased interest in understanding the nonequilibrium properties of the model, for example its behavior following a quench.

Quantum simulation of Fermi–Hubbard models, based on the current estimates, requires considerably fewer resources than simulations of molecules or solving optimization problems. This makes the Fermi–Hubbard model a promising candidate for early demonstrations of quantum advantage.

Actual end-to-end problem(s) solved

The Fermi–Hubbard Hamiltonian on \(M/2\) sites is given by

\[\begin{equation} \label{hamiltonianHubbard} H= -t \sum_{\sigma \in \{\uparrow,\downarrow\}}\sum_{\langle i,j\rangle}^{M/2} (c_{i\sigma}^\dagger c_{j\sigma}+c_{j\sigma}^\dagger c_{i\sigma})+U \sum_{i}^{M/2} n_{i\uparrow} n_{i\downarrow}\,, \end{equation}\]

where \(c_{i\sigma}\) are fermionic operators and \(n_{i\sigma} \equiv c_{i\sigma}^\dagger c_{i\sigma}\) is the number operator, with \(t\) denoting the strength of the kinetic term, \(U\) the onsite interaction strength, and \(\langle i,j\rangle\) a sum over nearest-neighbor lattice sites, given a lattice geometry. It is also possible to consider longer-range hopping terms, the inclusion of site-dependent chemical potentials, or additional "orbitals" per site.

Quantum simulation provides insights into both equilibrium and nonequilibrium physics. With regards to equilibrium physics, the primary computational task is to resolve and probe the properties of the phase diagram of the Fermi–Hubbard model, as a function of: lattice geometry, parameter values \((t, U)\), doping (the expected number of fermions divided by the number of sites), and temperature. This is achieved by preparing the thermal state \(\rho \propto e^{-\beta H}\) (or at zero temperature, the ground state \(\ket{E_0}\)) for the Fermi–Hubbard Hamiltonian instantiated by the given parameters, and measuring the expectation values of a set of physical observables to error \(\epsilon\). A thorough discussion of this end-to-end problem (at zero temperature) is provided in [3], where it is shown how to

  • Prepare mean-field states in a given phase (for example a BCS superconducting ground state).
  • Adiabatically evolve from the mean-field Hamiltonian to the final Fermi–Hubbard Hamiltonian. The absence of a phase transition confirms the predicted phase.
  • Measure observables, including density correlation functions \((n_{i \uparrow} + n_{i \downarrow})(n_{j \uparrow} + n_{j \downarrow})\), pair correlation functions \(c_{i \sigma}^\dag c_{j \sigma'}^\dag c_{k \sigma'} c_{l \sigma}\), and dynamical correlation functions \(\bra{E_0} e^{iHt} A e^{-iHt}B \ket{E_0}\) (for operators \(A,B\) and ground state \(\ket{E_0}\)).

The difficulty of this problem depends on the parameter regime under consideration. The ground state in the weak coupling regime of \(U < 4t\) is well understood, but questions remain in the intermediate (\(4t \leq U \leq 6t\)) and strong (\(U > 6t\)) regimes [4]. Challenges include precisely determining the phase boundaries and understanding the nature of the superconducting phase [5]. Progress has been made on this latter question in recent years, for example showing the absence of a superconducting phase at the physically relevant parameters of \(U \sim 8t\) and \(1/8\)th doping (see [4] for a more detailed discussion). Calculations are made challenging by small energy differences between competing phases, as well as the need to extrapolate from finite simulations to the thermodynamic limit.

The simulation of nonequilibrium quantum dynamics is of interest for modeling materials driven by an external field (for example an ultrafast laser pulse or an applied voltage), or following a quench in the Hamiltonian. Classically simulating nonequilibrium quantum dynamics has so far proven challenging and is a less-well-studied problem than probing the equilibrium physics of the model. Example applications include as a model for ultrafast spintronics, whereby lasers are used to manipulate spin degrees of freedom to control and store information [6] to better understand photo-induced phase transitions [7], or to clarify the nature of thermalization in isolated quantum systems following a quench [8].

Dominant resource cost/complexity

Mapping the problem to qubits:

Simulation of the Fermi–Hubbard model is most naturally performed in the second-quantized representation, as the regime of interest is usually close to half-filling (c.f. simulation of molecules). The Jordan–Wigner mapping between fermions and qubits is typically used (it has not yet been established if other mappings [9, 10], which preserve locality, provide concrete advantages in the fault-tolerant setting). For an \(L \times L\) lattice, we require \(M = 2L^2\) qubits to simulate the spinful Fermi–Hubbard model using the Jordan–Wigner mapping.

Accessing the Hamiltonian:

Quantum algorithms for simulating the Fermi–Hubbard model require access to the Hamiltonian. This is typically provided by block-encoding or Hamiltonian simulation. The structure in the Fermi–Hubbard Hamiltonian reduces the costs of these subroutines. For example, performing a block-encoding using the linear combinations of unitaries technique requires access to a PREPARE unitary and a SELECT unitary. The PREPARE unitary requires preparing a quantum state from classical data. Because the Fermi–Hubbard Hamiltonian has a small number of unique coefficients, the cost of this unitary can be reduced. Combining the results of [11, 12, 13] one can implement an \((M(2t+U/8), \mathcal{O}\left( \log(M) \right), \epsilon)\)-block-encoding of the Fermi–Hubbard Hamiltonian using

\[\begin{equation} \mathcal{O}\left( M + \log(M/\epsilon) \right) \end{equation}\]

non-Clifford gates.

As another example, the costs of Trotter approaches for Hamiltonian simulation can exploit the fact that many terms in the Fermi–Hubbard Hamiltonian commute, due to their locality. We will explicitly discuss these costs below.

State preparation:

  • Eigenstate preparation: There exist quantum algorithms that can prepare energy eigenstates using QSVT-based eigenstate filtering [14] (cost scales as \(1/\gamma\) with \(\gamma\) the overlap of the initial state with the desired eigenstate) or adiabatic state preparation (scaling depends on the gap between energy levels along the adiabatic path). Adiabatic state preparation was proposed as a method of classifying the phase diagram of the Fermi–Hubbard model [3]. A discrete version of the adiabatic approach, based on qubitization, was numerically investigated in the context of preparing ground states of the Fermi–Hubbard model [15], and showed promising results for the small system sizes considered (see also [16]).
  • Thermal states: A number of algorithms have been developed for preparation of thermal states. The most promising of these algorithms depend on the mixing time of a Markov chain (as in classical Monte Carlo approaches for preparing Gibbs states), which is currently undetermined for the Fermi–Hubbard model.
  • Time evolution: As discussed above, Trotter approaches for Hamiltonian simulation can exploit beneficial features of the Fermi–Hubbard Hamiltonian, such as locality, fixed particle number, and commutativity of the terms [17, 18, 19]. For a Fermi–Hubbard model with \(\eta\) fermions on \(M\) spin-lattice-sites, \(p\)th-order Trotter methods can simulate time evolution for time \(\tau\) up to error \(\epsilon\) using
    \[\begin{equation} \mathcal{O}\left( \frac{5^p M \eta^{1/p} \tau^{1+1/p}}{\epsilon^{1/p}} \right) \end{equation}\]

    gates. Explicit gate counts for Trotterization can be obtained from [20, 18, 13, 21], which have focused on constant factors for low-order formulae, rather than the asymptotic scaling. Post-Trotter methods, such as [22], using quantum signal processing as a building block, can achieve similar scaling in \(M\) and \(t\). A suboptimal approach (i.e., not using the method of [22]) briefly discussed in [23] has a gate complexity of approximately

    \[\begin{equation} 44 M^2 (2t + 3U/8)\tau \end{equation}\]

    \(T\) gates to simulate time evolution for time \(\tau\) using quantum signal processing, neglecting logarithmic dependence on the error of the simulation.1

Measuring observables:

  • Energies: Quantum phase estimation can be used to measure the energy eigenvalues of the Fermi–Hubbard Hamiltonian, given access to an initial state \(\ket{\psi}\) that has sufficient overlap \(\gamma = |\braket{\psi}{E_j}|\) with the target eigenstate \(\ket{E_j}\). We require \(\mathcal{O}\left( \gamma^{-2} \epsilon^{-1} \right)\) calls to a unitary \(U\) encoding the spectrum of the Hamiltonian to measure the energy to precision \(\epsilon\).2 Successfully applying QPE projects the initial state into the target eigenstate, which enables the measurement of other observables with respect to the target eigenstate. Using \(U \approx e^{iHt}\) implemented via second-order product formulae (the approximation error must be balanced against the error from QPE) results in a \(T\) gate count of \(\mathcal{O}\left( M^{3/2}/\Delta E^{3/2} \right)\) to resolve the energy of the Fermi–Hubbard model to precision \(\Delta E\), neglecting the cost of initial state preparation [20, 13]. Performing QPE on a quantum walk operator \(W\) which acts like \(e^{i\arccos{H}}\) and can be implemented via qubitization [24, 25] results in a \(T\) gate scaling of \(\mathcal{O}\left( M^2/\Delta E \right)\), also neglecting the cost of initial state preparation [11].
  • Other observables: There have been few studies considering the costs of measuring observables other than the ground state energy using fault-tolerant quantum algorithms. In general, it is important to minimize the number of calls to the unitary \(U_\psi\) that prepares the desired state, as this is typically considered the dominant cost. Reference [3] discussed methods for measuring density correlation functions \((n_{i \uparrow} + n_{i \downarrow})(n_{j \uparrow} + n_{j \downarrow})\), pair correlation functions \(\smash{c_{i \sigma}^\dag c_{j \sigma'}^\dag c_{k \sigma'} c_{l \sigma}}\), and dynamical correlation functions \(\smash{\bra{E_0} e^{iHt} A e^{-iHt}B \ket{E_0}}\) (for operators \(A,B\) and ground state \(\ket{E_0}\)), including approaches for nondestructively measuring some of these observables. Some of these approaches can now be reframed as performing amplitude estimation [26] on \(U_O\), a unitary block-encoding of the observable \(O\) with subnormalization factor \(\alpha_O\) [27]. A recent approach [28, 29] based on the quantum gradient estimation algorithm of [30] simultaneously computes the value of \(M\) (noncommuting) observables \(O_j\). The algorithm makes \(\widetilde{\mathcal{O}}\left( M^{1/2}/\epsilon \right)\) calls to \(U_\psi, U_\psi^\dag\) (or \(R_\psi = I - 2 \ket{\psi}\bra{\psi}\)) and either \(\widetilde{\mathcal{O}}\left( M^{3/2}/\epsilon \right)\) calls to gates of the form \(e^{i x O_j}\) [28] or \(\widetilde{\mathcal{O}}\left( M/\epsilon \right)\) calls to a block-encoding of the observables [29]. The algorithm also requires \(\mathcal{O}\left( M \log(1/\epsilon) \right)\) additional qubits. This approach has been considered in the context of measuring fermionic reduced density matrices and dynamic correlation functions [28].

Existing error corrected resource estimates

There have been a number of fault-tolerant resource estimates for algorithms targeting both static and dynamic properties of the Fermi–Hubbard model. In Table 1, we present approximate resource estimates for simulations of the 2D \(10\times 10\) spinful Fermi–Hubbard model. The table presents the number of logical qubits and gates required to run the algorithm; these can be converted into physical resource estimates via methods for fault-tolerant quantum computation.

References [11, 12] applied qubitization-based quantum phase estimation to calculate the ground state energy to constant additive error. For a lattice with \(M\) spin orbitals, using the compilation of [11], the number of \(T\) gates scales as roughly [11, Eq. (61)]

\[\begin{equation} \# T \propto \frac{(4t + U)M^2}{\Delta E} \end{equation}\]

and the number of logical qubits scales as approximately [11, Eq. (62)]

\[\begin{equation} \# \mathrm{Qubits} \sim M + \log\left( \frac{(2t + 0.5U)M^4}{\Delta E} \right). \end{equation}\]

References [20, 13] applied second-order Trotter-based quantum phase estimation to calculate the ground state energy, targeting relative error. Relative errors are appropriate when energy densities in the thermodynamic limit are of interest, and are better suited to the poorer error scaling of Trotter methods (compared to post-Trotter methods like qubitization). In both references, rigorous but potentially loose upper bounds on the Trotter error are computed. For a lattice with \(M\) spin orbitals, using the compilation of [13], the number of \(T\) gates scales as roughly [13, Eqs. (C3), (D6), (D10), (E17), (F10)]

\[\begin{equation} \# T \propto t\sqrt{t+U} \left(\frac{M}{\Delta E}\right)^{3/2} \end{equation}\]

and the number of logical qubits scales as approximately [13, Table II]

\[\begin{equation} \# \mathrm{Qubits} \sim (1 + \kappa)M \end{equation}\]

where \(\kappa\) is a free parameter that controls the number of ancilla qubits used for a compilation technique known as Hamming weight phasing (which reduces the cost of applying identical arbitrary angle rotation gates in parallel) [31, 20], set to \(\kappa=0.25\) in [13] and in our Table 1.

Problem and method #T gates qubits Parameters
via qubitized QPE [11, 12] \(\sim 10^8\) \(\sim 236\) \(U/t=4\) and \(\Delta E = 0.01t\)
via Trotterized QPE  [13, 20] \(\sim 5 \times 10^6\) \(\sim 250\) \(U/t = 8\) and \(\Delta E = 0.005 E_{\rm tot}\)
via fourth-order Trotter [23] \(4.6\times 10^5\) \(200\) \(T=10/t\), \(U=t\), and \(\epsilon \leq 1\%\)

Table 1: Fault-tolerant resource estimates for quantum phase estimation (QPE) and dynamics simulation applied to a 2D \(10\times 10\) Fermi–Hubbard model. The QPE circuits target an energy error of \(\Delta E\). In the second row, \(E_{\rm tot}\) denotes the ground state energy. The dynamics simulation runs for time \(T\), and targets an error of less than \(1\%\) in a spatially averaged intensive observable, with Trotter errors bounded numerically via extrapolated small-scale simulations. The presented gate counts are for a single run of the circuit. For QPE, the number of required runs depends on the overlap between the initial state and the ground state. For dynamics simulations, the number of circuit repetitions depends on the precision to which one wants to estimate a given observable. The parameters for each problem vary between different rows of the table, and so cannot be directly compared (although the different methods for the same problem, e.g., ground state energy estimation, could be compared by changing the analyses in the original papers to the desired matching parameter values).

The methods described above for encoding the Hamiltonian spectra (qubitization and Trotter) can also be used to simulate the dynamics of the Fermi–Hubbard model. Trotter methods can be applied directly, while qubitization can be combined with quantum signal processing (QSP) to perform Hamiltonian simulation. In [23], a comparison was made between fourth-order Trotterization and qubitization\(+\)QSP for simulating time evolution of a \(10 \times 10\) Fermi–Hubbard model. Trotter was determined to be the more efficient method, although this conclusion hinges on a Trotter decomposition with large steps (justified via numerical simulations). We note that the Trotter decompositions and analyses in [13, 23] are different, which hampers an immediate comparison. It may also be fruitful to compare with Hamiltonian simulation algorithms designed explicitly for simulating local Hamiltonians [22] (see discussion in [11]).

Caveats

In general, preparing the ground state of the Fermi–Hubbard model is known to be a hard problem, even for a quantum computer. This task has been proven QMA-hard for the Fermi–Hubbard model with a site dependent magnetic field [32] and for the Fermi–Hubbard model with a site-dependent \(t \rightarrow t_{ij}\) [33]. While the complexity class of the canonical Fermi–Hubbard model is not yet known, when preparing the ground state via quantum phase estimation or eigenstate filtering methods, it is necessary to prepare an initial state with an overlap that decays no worse than polynomially with system size; otherwise, the overall complexity will be superpolynomial. While numerical simulations on small system sizes have shown encouraging results [16, 15], it is still an open question as to whether this property holds for sufficiently large system sizes to enable extrapolation to the thermodynamic limit.

It is also important to note that this extrapolation of measured properties, computed at a range of finite system sizes, to the thermodynamic limit, has been observed to contribute a significant proportion of the uncertainty and errors in classical methods [34], and will also afflict quantum simulations.

Finally, it will be necessary to repeat simulations a large number of times. In order to measure a single observable to precision \(\epsilon\) we require \(\mathcal{O}\left( 1/\epsilon^2 \right)\) incoherent repetitions of the simulation, or \(\mathcal{O}\left( 1/\epsilon \right)\) using methods based on amplitude estimation. To map out and compute properties of the phase diagram or extract the phase following a quench, we may need to measure a large number of observables. In some cases, it may be necessary to re-prepare the initial state for each observable.

Comparable classical complexity and challenging instance sizes

The Fermi–Hubbard model has been a fertile environment for the development and testing of classical numerical methods for both static and dynamical properties. State-of-the-art methods for computing the phase diagram include: quantum Monte Carlo methods (determinantal QMC, diagrammatic MC, auxiliary-field QMC, diffusion MC), density matrix renormalization group (DMRG), coupled cluster methods, impurity methods (dynamical mean-field theory, density matrix embedding theory), among others. These methods typically have an approximation parameter (e.g., the excitation degree in coupled cluster or the bond dimension in DMRG) which influences the scaling of the algorithm and the accuracy of the simulation. Modern numerical studies of the Fermi–Hubbard model typically cross-validate using a number of simulation methods [34, 35]. For example, [34] benchmarked a range of methods and performed sufficiently large and accurate simulations for extrapolation to the thermodynamic limit. That work concluded that "the ground-state properties of a substantial part of the Hubbard model phase space are now under numerical control," but that some uncertainties still remain for \(4t \leq U \leq 8\) and dopings near half-filling. For a recent review of numerical simulations of the Fermi–Hubbard model, we refer the reader to [4].

The simulation of dynamics of the Fermi–Hubbard model appears to be more challenging for classical methods. For example, [36, 23] concluded that simulating the dynamics of a \(10 \times 10\) lattice would be infeasible for tensor network techniques. Other classical approaches for simulating time evolution of the Fermi–Hubbard model include nonequilibrium extensions of dynamical mean-field theory [37] or Floquet methods [7].

Speedup

The speedup of quantum algorithms for computing static properties, such as the ground state energy, of the Fermi–Hubbard model is difficult to determine. In general, we know that closely related models are QMA-hard (see Caveats) and so should be exponentially difficult for both classical and quantum computers. Assuming an initial state that has overlap with the target eigenstate that decays no faster than polynomially, then quantum phase estimation can be used to efficiently measure the eigenenergy and project into the desired eigenstate. It does so with cost \(\mathcal{O}\left( M^2/\Delta E \right)\) or \(\mathcal{O}((M/\Delta E)^{3/2})\), depending on the quantum algorithm used. Exact classical methods such as exact diagonalization have a cost that scales exponentially with \(M\) or \(1/\Delta E\). Approximate classical methods scale with an approximation parameter (e.g., bond dimension, number of excitations) which will depend on both \(M\) and \(\Delta E\). For example, [38, Fig. 4] shows the convergence of a tensor network (PEPS) calculation for the 2D Fermi–Hubbard model as a function of bond dimension and system size. For the small systems studied (up to \(16 \times 4\) sites) the plots are consistent with the bond dimension scaling polynomially in \(1/\Delta E\), with a weak dependence on the system size. If this holds for larger system sizes and across a range of system parameters, this would suggest that quantum algorithms provide only a polynomial speedup for computing the ground state energy.

Simulating the dynamics of the Fermi–Hubbard Hamiltonian requires polynomial resources using quantum algorithms, scaling almost linearly in \(M\) and \(\tau\). In contrast, all known classical methods appear to scale exponentially in system size and simulation accuracy. For example, [23] used tensor network (matrix product state) approaches for simulating the dynamics of the Fermi–Hubbard model following a quench. When truncating the bond dimension to facilitate efficient classical simulation, they found that errors in the observables grew exponentially with time. While this supports the conclusion of an exponential quantum speedup, we note that classical approaches will likely continue to improve and be applied to increasingly large system sizes. By using carefully engineered interactions (e.g., deviating significantly from a square lattice) it can be shown that simulating the dynamics of the Fermi–Hubbard model on a planar graph is a BQP-complete problem, and so is expected to be hard for classical computers, in the worst case [39].

NISQ implementations

There have been a number of proposals (and experimental demonstrations) of simulating the Fermi–Hubbard model on NISQ hardware. Ground state calculations can be performed using the variational quantum eigensolver (VQE) [40, 41, 42, 43, 44], and experimental demonstrations have been carried out on lattices of size \(1 \times 8\) and \(2 \times 4\) using 16 superconducting qubits, yielding qualitative agreement with theoretical expectation [45].

Dynamics can be simulated using Hamiltonian simulation (typically Trotter methods) [18] and have been demonstrated for an \(8 \times 1\) lattice on 16 superconducting qubits [46].

The simple Hamiltonian of the Fermi–Hubbard model makes it well suited to realization in analog quantum simulators, including ultracold atoms in optical lattices, trapped ions, and neutral atom arrays. It has been argued that some local observables can be robust to errors in the simulation [47, 23], enabling analog simulations to already surpass classical methods for simulating dynamics. We refer the reader to [36, 48] for additional discussion on analog simulation.

Outlook

The Fermi–Hubbard model provides a longstanding and physically relevant computational challenge. The low gate counts and modest number of logical qubits required to compute ground state energies could make quantum algorithms competitive with leading classical approaches in challenging regimes. We note that further research is required to ascertain the costs for initial state preparation for these calculations. For the less-well-studied task of simulating the dynamics of the Fermi–Hubbard model, quantum algorithms currently provide an exponential speedup over known classical algorithms. Nevertheless, as the Fermi–Hubbard Hamiltonian is sufficiently simple to be realized in many controlled physical systems, future fault-tolerant quantum computers will also have to compete against analog quantum simulators.

Bibliography

  1. J. Hubbard and Brian Hilton Flowers. Electron correlations in narrow energy bands. Proceedings of the Royal Society A, 276(1365):238–257, 1963. URL: https://royalsocietypublishing.org/doi/abs/10.1098/rspa.1963.0204, arXiv:https://royalsocietypublishing.org/doi/pdf/10.1098/rspa.1963.0204, doi:10.1098/rspa.1963.0204.

  2. Daniel P. Arovas, Erez Berg, Steven A. Kivelson, and Srinivas Raghu. The hubbard model. Annual Review of Condensed Matter Physics, 13:239–274, 2022. arXiv: https://arxiv.org/abs/2103.12097. arXiv:2103.12097, doi:10.1146/annurev-conmatphys-031620-102024.

  3. Dave Wecker, Matthew B. Hastings, Nathan Wiebe, Bryan K. Clark, Chetan Nayak, and Matthias Troyer. Solving strongly correlated electron models on a quantum computer. Physical Review A, 92:062318, 12 2015. arXiv: https://arxiv.org/abs/1506.05135. URL: https://link.aps.org/doi/10.1103/PhysRevA.92.062318, doi:10.1103/PhysRevA.92.062318.

  4. Mingpu Qin, Thomas Schafer, Sabine Andergassen, Philippe Corboz, and Emanuel Gull. The hubbard model: a computational perspective. Annual Review of Condensed Matter Physics, 13:275–302, 2022. arXiv: https://arxiv.org/abs/2104.00064. arXiv:2104.00064, doi:10.1146/annurev-conmatphys-090921-033948.

  5. Eduardo Fradkin, Steven A. Kivelson, and John M. Tranquada. Colloquium: theory of intertwined orders in high temperature superconductors. Reviews of Modern Physics, 87:457–482, 5 2015. arXiv: https://arxiv.org/abs/1407.4480. URL: https://link.aps.org/doi/10.1103/RevModPhys.87.457, doi:10.1103/RevModPhys.87.457.

  6. Igor Žutić, Jaroslav Fabian, and S. Das Sarma. Spintronics: fundamentals and applications. Reviews of Modern Physics, 76:323–410, 4 2004. arXiv: https://arxiv.org/abs/cond-mat/0405528. URL: https://link.aps.org/doi/10.1103/RevModPhys.76.323, doi:10.1103/RevModPhys.76.323.

  7. Takashi Oka and Sota Kitamura. Floquet engineering of quantum materials. Annual Review of Condensed Matter Physics, 10(1):387–408, 2019. arXiv: https://arxiv.org/abs/1804.03212. URL: https://doi.org/10.1146/annurev-conmatphys-031218-013423, arXiv:https://doi.org/10.1146/annurev-conmatphys-031218-013423, doi:10.1146/annurev-conmatphys-031218-013423.

  8. Anatoli Polkovnikov, Krishnendu Sengupta, Alessandro Silva, and Mukund Vengalattore. Colloquium: nonequilibrium dynamics of closed interacting quantum systems. Reviews of Modern Physics, 83:863–883, 8 2011. arXiv: https://arxiv.org/abs/1007.5331. URL: https://link.aps.org/doi/10.1103/RevModPhys.83.863, doi:10.1103/RevModPhys.83.863.

  9. Frank Verstraete and J Ignacio Cirac. Mapping local hamiltonians of fermions to local hamiltonians of spins. Journal of Statistical Mechanics: Theory and Experiment, 2005(09):P09012, 2005. arXiv: https://arxiv.org/abs/cond-mat/0508353.

  10. Charles Derby, Joel Klassen, Johannes Bausch, and Toby Cubitt. Compact fermion to qubit mappings. Physical Review B, 104:035118, 7 2021. URL: https://link.aps.org/doi/10.1103/PhysRevB.104.035118, doi:10.1103/PhysRevB.104.035118.

  11. Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear t complexity. Physical Review X, 8(4):041015, 2018. arXiv: https://arxiv.org/abs/1805.03662. doi:10.1103/PhysRevX.8.041015.

  12. 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.

  13. 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.

  14. 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.

  15. Jessica Lemieux, Guillaume Duclos-Cianci, David Sénéchal, and David Poulin. Resource estimate for quantum many-body ground-state preparation on a quantum computer. Physical Review A, 103(5):052408, 2021. arXiv: https://arxiv.org/abs/2006.04650. arXiv:2006.04650, doi:10.1103/PhysRevA.103.052408.

  16. Norm M. Tubman, Carlos Mejuto-Zaera, Jeffrey M. Epstein, Diptarka Hait, Daniel S. Levine, William Huggins, Zhang Jiang, Jarrod R. McClean, Ryan Babbush, Martin Head-Gordon, and K. Birgitta Whaley. Postponing the orthogonality catastrophe: efficient state preparation for electronic structure simulations on quantum devices. arXiv: https://arxiv.org/abs/1809.05523, 2018.

  17. 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.

  18. Laura Clinton, Johannes Bausch, and Toby Cubitt. Hamiltonian simulation algorithms for near-term quantum hardware. Nature Communications, 12(1):4989, 8 2021. arXiv: https://arxiv.org/abs/2003.06886. URL: https://doi.org/10.1038/s41467-021-25196-0, doi:10.1038/s41467-021-25196-0.

  19. Yuan Su, Hsin Yuan Huang, and Earl T. Campbell. Nearly tight trotterization of interacting electrons. Quantum, 5(1):1–58, 2021. arXiv: https://arxiv.org/abs/2012.09194. arXiv:2012.09194, doi:10.22331/Q-2021-07-05-495.

  20. Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, and Ryan Babbush. Improved fault-tolerant quantum simulation of condensed-phase correlated electrons via trotterization. Quantum, 4:296, 7 2020. arXiv: https://arxiv.org/abs/1902.10673. URL: https://doi.org/10.22331/q-2020-07-16-296, doi:10.22331/q-2020-07-16-296.

  21. Ansgar Schubert and Christian B Mendl. Trotter error with commutator scaling for the fermi–hubbard model. arXiv: https://arxiv.org/abs/2306.10603, 2023.

  22. 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.

  23. 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.

  24. David Poulin, Alexei Kitaev, Damian S. Steiger, Matthew B. Hastings, and Matthias Troyer. Quantum algorithm for spectral measurement with a lower gate count. Physical Review Letters, 121:010501, 7 2018. arXiv: https://arxiv.org/abs/1711.11025. URL: https://link.aps.org/doi/10.1103/PhysRevLett.121.010501, doi:10.1103/PhysRevLett.121.010501.

  25. Dominic W. Berry, Mária Kieferová, Artur Scherer, Yuval R. Sanders, Guang Hao Low, Nathan Wiebe, Craig Gidney, and Ryan Babbush. Improved techniques for preparing eigenstates of fermionic hamiltonians. npj Quantum Information, 4(1):22, 5 2018. arXiv: https://arxiv.org/abs/1711.10460. URL: https://doi.org/10.1038/s41534-018-0071-5, doi:10.1038/s41534-018-0071-5.

  26. Emanuel Knill, Gerardo Ortiz, and Rolando D. Somma. Optimal quantum measurements of expectation values of observables. Physical Review A, 75:012328, 1 2007. arXiv: https://arxiv.org/abs/quant-ph/0607019. URL: https://link.aps.org/doi/10.1103/PhysRevA.75.012328, doi:10.1103/PhysRevA.75.012328.

  27. 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.

  28. 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.

  29. 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.

  30. András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe. Optimizing quantum optimization algorithms via faster quantum gradient computation. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1425–1444. 2019. arXiv: https://arxiv.org/abs/1711.00465. doi:10.1137/1.9781611975482.87.

  31. 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.

  32. Norbert Schuch and Frank Verstraete. Computational complexity of interacting electrons and fundamental limitations of density functionaltheory. Nature Physics, 5(10):732–735, 2009. arXiv: https://arxiv.org/abs/0712.0483. arXiv:0712.0483, doi:10.1038/nphys1370.

  33. Bryan O'Gorman, Sandy Irani, James Whitfield, and Bill Fefferman. Intractability of electronic structure in a fixed basis. PRX Quantum, 3:020322, 5 2022. arXiv: https://arxiv.org/abs/2103.08215. URL: https://link.aps.org/doi/10.1103/PRXQuantum.3.020322, doi:10.1103/PRXQuantum.3.020322.

  34. J. P. F. LeBlanc, Andrey E. Antipov, Federico Becca, Ireneusz W. Bulik, Garnet Kin-Lic Chan, Chia-Min Chung, Youjin Deng, Michel Ferrero, Thomas M. Henderson, Carlos A. Jiménez-Hoyos, E. Kozik, Xuan-Wen Liu, Andrew J. Millis, N. V. Prokof'ev, Mingpu Qin, Gustavo E. Scuseria, Hao Shi, B. V. Svistunov, Luca F. Tocchio, I. S. Tupitsyn, Steven R. White, Shiwei Zhang, Bo-Xiao Zheng, Zhenyue Zhu, and Emanuel Gull. Solutions of the two-dimensional hubbard model: benchmarks and results from a wide range of numerical algorithms. Physical Review X, 5:041041, 12 2015. arXiv: https://arxiv.org/abs/1505.02290. URL: https://link.aps.org/doi/10.1103/PhysRevX.5.041041, doi:10.1103/PhysRevX.5.041041.

  35. Thomas Schäfer, Nils Wentzell, Fedor Šimkovic, Yuan-Yao He, Cornelia Hille, Marcel Klett, Christian J. Eckhardt, Behnam Arzhang, Viktor Harkov, Fran ç çois-Marie Le Régent, Alfred Kirsch, Yan Wang, Aaram J. Kim, Evgeny Kozik, Evgeny A. Stepanov, Anna Kauch, Sabine Andergassen, Philipp Hansmann, Daniel Rohe, Yuri M. Vilk, James P. F. LeBlanc, Shiwei Zhang, A.-M. S. Tremblay, Michel Ferrero, Olivier Parcollet, and Antoine Georges. Tracking the footprints of spin fluctuations: a multimethod, multimessenger study of the two-dimensional hubbard model. Physical Review X, 11:011058, 3 2021. arXiv: https://arxiv.org/abs/2006.10769. URL: https://link.aps.org/doi/10.1103/PhysRevX.11.011058, doi:10.1103/PhysRevX.11.011058.

  36. Andrew J. Daley, Immanuel Bloch, Christian Kokail, Stuart Flannigan, Natalie Pearson, Matthias Troyer, and Peter Zoller. Practical quantum advantage in quantum simulation. Nature, 607(7920):667–676, 2022. doi:10.1038/s41586-022-04940-6.

  37. Hideo Aoki, Naoto Tsuji, Martin Eckstein, Marcus Kollar, Takashi Oka, and Philipp Werner. Nonequilibrium dynamical mean-field theory and its applications. Reviews of Modern Physics, 86:779–837, 6 2014. arXiv: https://arxiv.org/abs/1310.5329. URL: https://link.aps.org/doi/10.1103/RevModPhys.86.779, doi:10.1103/RevModPhys.86.779.

  38. 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.

  39. Ning Bao, Patrick Hayden, Grant Salton, and Nathaniel Thomas. Universal quantum computation by scattering in the fermi–hubbard model. New Journal of Physics, 17(9):093028, 2015. arXiv: https://arxiv.org/abs/1409.3585.

  40. Zhang Jiang, Kevin J. Sung, Kostyantyn Kechedzhi, Vadim N. Smelyanskiy, and Sergio Boixo. Quantum algorithms to simulate many-body physics of correlated fermions. Physical Review Applied, 9(4):44036, 2018. arXiv: https://arxiv.org/abs/1711.05395. URL: https://doi.org/10.1103/PhysRevApplied.9.044036, arXiv:1711.05395, doi:10.1103/PhysRevApplied.9.044036.

  41. Jan Michael Reiner, Sebastian Zanker, Iris Schwenk, Juha Leppakangas, Frank Wilhelm-Mauch, Gerd Schön, and Michael Marthaler. Effects of gate errors in digital quantum simulations of fermionic systems. Quantum Science and Technology, 2018. arXiv: https://arxiv.org/abs/1804.06668. arXiv:1804.06668, doi:10.1088/2058-9565/aad5ba.

  42. Jan Michael Reiner, Frank Wilhelm-Mauch, Gerd Schön, and Michael Marthaler. Finding the ground state of the hubbard model by variational methods on a quantum computer with gate errors. Quantum Science and Technology, 2019. arXiv: https://arxiv.org/abs/1811.04476. arXiv:1811.04476, doi:10.1088/2058-9565/ab1e85.

  43. Zhenyu Cai. Resource estimation for quantum variational simulations of the hubbard model. Physical Review Applied, 14(1):1, 2020. arXiv: https://arxiv.org/abs/1910.02719. URL: https://doi.org/10.1103/PhysRevApplied.14.014059, arXiv:1910.02719, doi:10.1103/PhysRevApplied.14.014059.

  44. Chris Cade, Lana Mineh, Ashley Montanaro, and Stasja Stanisic. Strategies for solving the fermi–hubbard model on near-term quantum computers. Physical Review B, 102:235122, 12 2020. arXiv: https://arxiv.org/abs/1912.06007. URL: https://link.aps.org/doi/10.1103/PhysRevB.102.235122, doi:10.1103/PhysRevB.102.235122.

  45. Stasja Stanisic, Jan Lukas Bosse, Filippo Maria Gambetta, Raul A. Santos, Wojciech Mruczkiewicz, Thomas E. O'Brien, Eric Ostby, and Ashley Montanaro. Observing ground-state properties of the fermi–hubbard model using a scalable algorithm on a quantum computer. Nature Communications, 13(1):5743, 2022. arXiv: https://arxiv.org/abs/2112.02025. URL: https://doi.org/10.1038/s41467-022-33335-4, doi:10.1038/s41467-022-33335-4.

  46. Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Andreas Bengtsson, Sergio Boixo, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Yu-An Chen, Ben Chiaro, Roberto Collins, Stephen J. Cotton, William Courtney, Sean Demura, Alan Derk, Andrew Dunsworth, Daniel Eppens, Thomas Eckl, Catherine Erickson, Edward Farhi, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Jonathan A. Gross, Steve Habegger, Matthew P. Harrigan, Alan Ho, Sabrina Hong, Trent Huang, William Huggins, Lev B. Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V. Klimov, Alexander N. Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Erik Lucero, Michael Marthaler, Orion Martin, John M. Martinis, Anika Marusczyk, Sam McArdle, Jarrod R. McClean, Trevor McCourt, Matt McEwen, Anthony Megrant, Carlos Mejuto-Zaera, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Hartmut Neven, Michael Newman, Murphy Yuezhen Niu, Thomas E. O'Brien, Eric Ostby, Bálint Pató, Andre Petukhov, Harald Putterman, Chris Quintana, Jan-Michael Reiner, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Doug Strain, Kevin J. Sung, Peter Schmitteckert, Marco Szalay, Norm M. Tubman, Amit Vainsencher, Theodore White, Nicolas Vogt, Z. Jamie Yao, Ping Yeh, Adam Zalcman, and Sebastian Zanker. Observation of separated dynamics of charge and spin in the fermi–hubbard model. arXiv: https://arxiv.org/abs/2010.07965, 2020. URL: http://arxiv.org/abs/2010.07965.

  47. Pablo M. Poggi. Analysis of lower bounds for quantum control times and their relation to the quantum speed limit. arXiv: https://arxiv.org/abs/2002.11147, 2020. URL: http://arxiv.org/abs/2002.11147, arXiv:2002.11147.

  48. Christian Gross and Immanuel Bloch. Quantum simulations with ultracold atoms in optical lattices. Science, 357(6355):995–1001, 2017. doi:10.1126/science.aal3837.

  1. Note that in [23], \(M\) is defined as the number of lattice sites, and so corresponds to \(M/2\) here. ↩

  2. It is possible to improve the complexity to \(\mathcal{O}\left( \gamma^{-1} \epsilon^{-1} \right)\) using amplitude amplification if a sufficiently precise estimate of the eigenvalue is known, or to \(\mathcal{O}\left( \gamma^{-2} \Delta^{-1} + \epsilon^{-1} \right)\) by exploiting knowledge of the gap \(\Delta\) between the energy eigenstates to perform rejection sampling [25]. ↩