Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods

The simulation of electron dynamics is crucial in various fields, including chemistry, physics, and materials science. Classical methods, such as Hartree-Fock and density functional theory (DFT), are widely used due to their computational efficiency. However, these methods rely on approximations, limiting their accuracy, especially when dealing with strongly correlated systems. Quantum computers, on the other hand, offer the potential for systematically improvable precision without exponential scaling, making them attractive for simulating complex quantum systems. While quantum algorithms for ground-state simulations are currently slower than classical mean-field methods, this paper explores the possibility that certain quantum algorithms for simulating dynamics could outperform even these approximate classical approaches. The research focuses on interacting fermions, systems of significant relevance across scientific disciplines. Many practically relevant ground-state problems do not exhibit strong electron correlation, making classical methods sufficient. However, even for systems well-described by mean-field theory, the authors hypothesize that quantum algorithms can offer speedup in simulating time evolution. This work specifically compares quantum algorithms to real-time time-dependent Hartree-Fock (RT-TDHF) and time-dependent density functional theory (RT-TDDFT) because of their wide usage and well-defined computational costs. The authors acknowledge limitations of comparing to linear-scaling classical methods or quantized tensor train approaches due to the uncertainties surrounding compression efficiency for dynamical and finite-temperature problems. The central question addressed is whether quantum algorithms can achieve a speedup over classical mean-field approaches for simulating the time evolution of electronic systems, even when these systems are well-approximated by mean-field theory. The paper aims to demonstrate that under certain conditions, quantum computers can indeed provide a significant advantage for simulating electron dynamics.

The use of quantum computers for simulating dynamics was initially proposed by Feynman and later proven to be universal by Lloyd et al. Early work primarily focused on quantum simulations as a means of achieving systematically improvable precision without exponential scaling. This paper, however, introduces a different perspective: that certain exact quantum algorithms for dynamics might be more efficient than classical methods employing uncontrolled approximations. The authors cite previous work on first-quantized quantum simulations applied to fermionic systems, and their development for molecular systems. Prior algorithms for simulating chemical dynamics were based on Trotterization of the time-evolution operator and the quantum Fourier transform. While these algorithms achieved a gate complexity of O(n²), the number of Trotter steps scaled poorly, leading to overall inefficient performance. Recent advancements in bounding Trotter error are leveraged in this paper to improve the efficiency of these algorithms.

The paper compares the computational costs of classical mean-field methods and quantum algorithms for simulating electron dynamics. For classical mean-field approaches, the scaling of the number of time steps required for time evolution is analyzed. The analysis considers the target precision, the total unitless time T, and the spectral norm of the Hamiltonian. The number of operations for classical mean-field time-evolution is derived, showing dependence on the basis set size (N), the number of electrons (n), the simulation time (t), and the target precision (ε). The analysis highlights that the number of time steps and, therefore, the overall computational cost, is significantly affected by the norm of the Hamiltonian, which is closely tied to the choice of basis set and the presence of the Coulomb operator. The paper then examines the space and gate complexity of quantum algorithms for simulating electron dynamics, specifically focusing on first-quantized approaches. The space complexity of first-quantized algorithms is shown to be exponentially less than that of classical mean-field methods. However, quantum algorithms require efficient gate complexity to achieve a scaling advantage. The paper reviews and tightens bounds for the most efficient known quantum algorithms, including Trotter-based approaches and interaction picture simulation schemes. These analyses consider different regimes of the relationship between the basis set size (N) and the number of basis functions (η), highlighting when different algorithms offer optimal performance. A critical aspect of quantum simulations is the measurement of observables. The authors analyze the costs associated with measuring observables in quantum algorithms, highlighting the need for sampling and its impact on the overall speedup. A novel classical shadows protocol is introduced for measuring the one-particle reduced density matrix (1-RDM) and higher-order reduced density matrices (RDMs), showing that these measurements scale poly-logarithmically with the basis set size. Finally, the paper addresses the cost of quantum state preparation, specifically for Slater determinants. A new algorithm is presented that efficiently prepares arbitrary Slater determinants using a combination of techniques from second-quantization and a novel anti-symmetrization procedure. This improved algorithm significantly reduces the gate complexity compared to previous approaches. The paper culminates in a comprehensive comparison of the computational costs for both classical mean-field methods and quantum algorithms under various conditions, including zero and finite temperature simulations. It provides detailed analysis of time evolution, measurement, and state preparation costs, offering a clear picture of where quantum speedups are most likely to occur.

The core finding is that under certain conditions, quantum algorithms for simulating the time evolution of electronic systems can be significantly more efficient than classical mean-field methods, even when the systems are well-approximated by mean-field theory. Specifically: 1. **Exponential Space Advantage:** First-quantized quantum algorithms require exponentially less space (O(n log N)) compared to classical mean-field methods (O(Nⁿ log(1/ε))). 2. **Polynomial Time Advantage:** In certain regimes (e.g., when N < O(η³)), optimized quantum algorithms exhibit polynomial speedups over classical mean-field algorithms for simulating time evolution. The degree of speedup varies based on the relationship between N and η and can reach a quintic speedup in N with quadratic slowdown in η when N > O(η⁴). 3. **Efficient Measurement:** A new classical shadows protocol is presented for efficiently estimating the k-particle RDMs, with the number of samples scaling only poly-logarithmically with basis set size. 4. **Improved State Preparation:** A novel algorithm for preparing Slater determinants in first-quantization is presented, significantly reducing the gate complexity from O(Nn²) to O(Nn) gates. 5. **Finite Temperature Advantage:** The quantum speedup is significantly more pronounced at finite temperatures because the need for sampling in quantum algorithms does not increase meaningfully, while classically it introduces a multiplicative O(1/ε²) sampling cost. The paper presents detailed scaling analysis and numerical comparisons demonstrating these advantages under various conditions, including different regimes of N and η, different observables, and at zero and finite temperatures. The most significant speedups are observed when the number of basis functions is substantially larger than the number of electrons. A detailed table (Table 1) summarizes the costs for both classical and quantum approaches, clearly highlighting these differences. Figure 1 shows the quantum speedup ratio over classical methods, demonstrating substantial speedups under various assumptions about the relationship between N and η.

The findings of this study demonstrate that quantum algorithms have the potential to outperform classical mean-field methods for simulating electron dynamics, even in regimes where mean-field theory provides a reasonably good approximation. The significant space advantage of first-quantized methods is notable. However, the overall speedup depends on the interplay between basis set size, number of electrons, simulation time, desired precision, and the choice of observables. While the quantum algorithms show a clear advantage in certain parameter regimes, the requirement of sampling to estimate observables introduces a cost that affects the overall speedup. The advantage is particularly striking at finite temperatures, which opens up exciting applications for simulating warm dense matter and hot dense matter. The results underscore the importance of considering the specific application and the relevant observables when assessing the potential advantages of quantum computation. The development of the new state preparation and measurement algorithms is also a significant contribution, showcasing advancements in quantum algorithm design.

This paper provides compelling evidence that quantum algorithms can offer significant advantages for simulating electron dynamics, particularly at finite temperatures. The refined bounds on the computational cost of quantum algorithms, combined with the introduction of more efficient methods for state preparation and measurement, demonstrate the potential for achieving substantial speedups over classical mean-field methods. Future research directions include further optimization of quantum algorithms, exploration of the trade-offs between accuracy and efficiency in different parameter regimes, and application to specific problems in materials science, chemistry, and astrophysics, especially those involving warm and hot dense matter. The development and implementation of error mitigation and correction strategies will be critical for realizing these quantum advantages on near-term devices.

While this paper provides a rigorous comparison of scaling complexities, it doesn't fully account for constant factors in both classical and quantum algorithms. This means the actual speedup in practice could differ from the theoretical predictions, especially for smaller system sizes. The analysis relies on upper bounds, and tighter bounds derived for restricted inputs might further refine the comparison. Moreover, the analysis focuses on specific quantum algorithms and does not exhaustively explore all possible quantum approaches. The effect of quantum error correction on the overall speedup is also not explicitly addressed, although the magnitude of the speedups suggested hints that even with overhead, a quantum advantage may be possible. Finally, the accessibility and scalability of implementing these quantum algorithms on existing or near-term quantum hardware are not explicitly addressed.