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

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.00950

Sublinear-depth Quantum Simulation of Electrons with Atomic Orbitals

Jakob Günther, Aram W. Harrow

quant-phSubmitted Oct 1, 2026• Announced Oct 2, 2026• 0 citations
arXivHTMLPDF

Abstract

Discretizing electronic degrees of freedom into atomic orbitals is the default choice to accurately model electrons in molecules in a compact and flexible way. We consider the task of simulating such electronic structure models on a quantum computer for $N$ orbitals, keeping the number of orbitals per atom constant. Atomic orbitals give rise to Hamiltonians with potentially up to $\mathcal{O}(N^4)$ terms and little structure, which made it challenging to match the complexity of methods based on plane waves and real-space grids. In this work, we show that a Trotter step for atomic orbitals can be implemented in depth $\mathcal{O}(\mathrm{polylog}(N))$ without ancillas by combining a rigorous treatment of orbital localization, a hierarchical Hamiltonian decomposition based on the Fast Multipole Method, and shallow quantum Fourier arithmetic circuits. By bounding the Trotter error, we obtain sublinear simulation depth, and our total gate count $N^{5/3 + o(1)}$ matches the best scaling known for any basis.

Related papers

Low rank representations for quantum simulation of electronic structure

Mário Motta, Erika Ye, Jarrod R. McClean +4 more

Abstract The quantum simulation of quantum chemistry is a promising application of quantum computers. However, for N molecular orbitals, the $${\mathcal{O}}({N}^{4})$$ O ( N 4 ) gate complexity of performing Hamiltonian and unitary Coupled Cluster Trotter steps makes simulation based on such primitives challenging. We substantially reduce the gate complexity of such primitives through a two-step low-rank factorization of the Hamiltonian and cluster operator, accompanied by truncation of small terms. Using truncations that incur errors below chemical accuracy allow one to perform Trotter steps of the arbitrary basis electronic structure Hamiltonian with $${\mathcal{O}}({N}^{3})$$ O ( N 3 ) gate complexity in small simulations, which reduces to $${\mathcal{O}}({N}^{2})$$ O ( N 2 ) gate complexity in the asymptotic regime; and unitary Coupled Cluster Trotter steps with $${\mathcal{O}}({N}^{3})$$ O ( N 3 ) gate complexity as a function of increasing basis size for a given molecule. In the case of the Hamiltonian Trotter step, these circuits have $${\mathcal{O}}({N}^{2})$$ O ( N 2 ) depth on a linearly connected array, an improvement over the $${\mathcal{O}}({N}^{3})$$ O ( N 3 ) scaling assuming no truncation. As a practical example, we show that a chemically accurate Hamiltonian Trotter step for a 50 qubit molecular simulation can be carried out in the molecular orbital basis with as few as 4000 layers of parallel nearest-neighbor two-qubit gates, consisting of fewer than 10 5 non-Clifford rotations. We also apply our algorithm to iron–sulfur clusters relevant for elucidating the mode of action of metalloenzymes.

arXiv:1808.02625•npj Quantum Information•May 27, 2021•173 citations

Complexity of Implementing Trotter Steps

Guang Hao Low, Yuan Su, Yu Tong +1 more

Quantum dynamics can be simulated on a quantum computer by exponentiating elementary terms from the Hamiltonian in a sequential manner.However, such an implementation of Trotter steps has gate complexity depending on the total Hamiltonian term number, comparing unfavorably to algorithms using more advanced techniques.We develop methods to perform faster Trotter steps with complexity sublinear in the number of terms.We achieve this for a class of Hamiltonians whose interaction strength decays with distance according to power law.Our methods include one based on a recursive block encoding and one based on an average-cost simulation, overcoming the normalization-factor barrier of these advanced quantum simulation techniques.We also realize faster Trotter steps when certain blocks of Hamiltonian coefficients have low rank.Combining with a tighter error analysis, we show that it suffices to use η 1/3 n 1/3 + n 2/3 /η 2/3 n 1+o(1) gates to simulate uniform electron gas with n spin orbitals and η electrons in second quantization in real space, asymptotically improving over the best previous work.We obtain an analogous result when the external potential of nuclei is introduced under the Born-Oppenheimer approximation.We prove a circuit lower bound when the Hamiltonian coefficients take a continuum range of values, showing that generic n-qubit two-local Hamiltonians with commuting terms require at least (n 2 ) gates to evolve with accuracy = (1/poly(n)) for time t = ( ).Our proof is based on a gateefficient reduction from the approximate synthesis of diagonal unitaries within the Hamming weight-2 subspace, which may be of independent interest.Our result thus suggests the use of Hamiltonian structural properties as both necessary and sufficient to implement Trotter steps with lower gate complexity.

arXiv:2211.09133•PRX Quantum•May 9, 2023•29 citations

Faster quantum simulation of quantum chemistry with tailored algorithms and Hamiltonians

Ian Kivlichan

With quantum computers on the horizon, it is essential to understand what problems they can be used to solve. One potential application is simulating quantum systems, in particular, systems with many interacting electrons. However, there is a disparity between the computational resources required to study these problems and the capabilities of modern experimental quantum devices. In this thesis, we make progress toward closing this gap by reducing the cost of quantum simulation of quantum chemistry on a number of fronts. In the first half, we develop three improved quantum simulation algorithms by approximating time evolution under the Hamiltonian using a truncated Taylor series rather than the Trotter-Suzuki decomposition. We do this first for the molecular electronic structure Hamiltonian in two representations, obtaining asymptotic improvements in terms of both the number of orbitals and the required precision. We also apply the truncated Taylor series paradigm to quantum simulation in real space, where we consider simulation of general wave functions discretized on a uniform grid. In the second half, by working with Hamiltonians tailored specifically to quantum algorithms, we demonstrate that Trotter steps of the electronic structure Hamiltonian can be simulated in exactly N depth and with only linear connectivity, where N is the number of spin-orbitals. This resolves the problem of non-locality in fermion-to-qubit mappings, and has wide-ranging applications for variational and phase estimation-based quantum simulation of quantum chemistry. We further study this algorithm on an error-corrected quantum computer using the surface code. Benchmarking it alongside other product formula approaches, we show that quantum simulation of scientifically important instances of the electronic structure problem that are classically intractable can be performed with only a few hundred thousand physical qubits and fewer than one billion costly fault-tolerant gates. Finally, we study the effect of using randomized Hamiltonians in iterative phase estimation, and how this allows us to reduce the costs of simulation as well as to exploit knowledge of the ground state in how we design our simulation algorithm.

•Jan 8, 2020•0 citations

Quantum simulation of chemistry with sublinear scaling in basis size

Ryan Babbush, Dominic William Berry, Jarrod R. McClean +1 more

Abstract We present a quantum algorithm for simulating quantum chemistry with gate complexity $$\tilde {\cal{O}}(N^{1/3}\eta ^{8/3})$$ O ̃ ( N 1 ∕ 3 η 8 ∕ 3 ) where η is the number of electrons and N is the number of plane wave orbitals. In comparison, the most efficient prior algorithms for simulating electronic structure using plane waves (which are at least as efficient as algorithms using any other basis) have complexity $$\tilde {\cal{O}}(N^{8/3}{\mathrm{/}}\eta ^{2/3})$$ O ̃ ( N 8 ∕ 3 ∕ η 2 ∕ 3 ) . We achieve our scaling in first quantization by performing simulation in the rotating frame of the kinetic operator using interaction picture techniques. Our algorithm is far more efficient than all prior approaches when N ≫ η , as is needed to suppress discretization error when representing molecules in the plane wave basis, or when simulating without the Born-Oppenheimer approximation.

arXiv:1807.09802•npj Quantum Information•Nov 1, 2019•104 citations

Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian

Sam McArdle, Earl T. Campbell, Yuan Su

Achieving an accurate description of fermionic systems typically requires considerably many more orbitals than fermions. Previous resource analyses of quantum chemistry simulation often failed to exploit this low fermionic number information in the implementation of Trotter-based approaches and overestimated the quantum-computer runtime as a result. They also depended on numerical procedures that are computationally too expensive to scale up to large systems of practical interest. Here we propose techniques that solve both problems by using various factorized decompositions of the electronic structure Hamiltonian. We showcase our techniques for the uniform electron gas, finding substantial (over $100\ifmmode\times\else\texttimes\fi{}$) improvements in Trotter error for low-filling fraction and pushing to much higher numbers of orbitals than is possible with existing methods. Finally, we calculate the $T$-count to perform phase estimation on Jellium. In the low-filling regime, we observe improvements in gate complexity of over $10\ifmmode\times\else\texttimes\fi{}$ compared to the best Trotter-based approach reported to date. We also report gate counts competitive with qubitization-based approaches for Wigner-Seitz values of physical interest.

arXiv:2107.07238•Physical Review A•Jan 3, 2022•17 citations

The Trotter step size required for accurate quantum simulation of quantum chemistry

David Poulin, M. B. Hastings, D. Wecker +3 more

The simulation of molecules is a widely anticipated application of quantum computers. However, recent studies [1, 2] have cast a shadow on this hope by revealing that the complexity in gate count of such simulations increases with the number of spin orbitals N as N8 , which becomes prohibitive even for molecules of modest size N ∼ 100. This study was partly based on a scaling analysis of the Trotter step required for an ensemble of random artificial molecules. Here, we revisit this analysis and find instead that the scaling is closer to N6 in worst case for real model molecules we have studied, indicating that the random ensemble fails to accurately capture the statistical properties of real world molecules. Actual scaling may be significantly better than this due to averaging effects. We then present an alternative simulation scheme and show that it can sometimes outperform existing schemes, but that this possibility depends crucially on the details of the simulated molecule. We obtain further improvements using a version of the coalescing scheme of [1]; this scheme is based on using different Trotter steps for different terms. The method we use to bound the complexity of simulating a given molecule is efficient, in contrast to the approach of [1, 2] which relied on exponentially costly classical exact simulation.

Quantum Information and Computation•Apr 1, 2015•159 citations
Discretizing electronic degrees of freedom into atomic orbitals is the default choice to accurately model electrons in molecules in a compact and flexible way. We consider the task of simulating such electronic structure models on a quantum computer for NNN orbitals, keeping the number of orbitals per atom constant. Atomic orbitals give rise to Hamiltonians with potentially up to O(N4)\mathcal{O}(N^4)O(N4) terms and little structure, which made it challenging to match the complexity of methods based on plane waves and real-space grids. In this work, we show that a Trotter step for atomic orbitals can be implemented in depth O(polylog(N))\mathcal{O}(\mathrm{polylog}(N))O(polylog(N)) without ancillas by combining a rigorous treatment of orbital localization, a hierarchical Hamiltonian decomposition based on the Fast Multipole Method, and shallow quantum Fourier arithmetic circuits. By bounding the Trotter error, we obtain sublinear simulation depth, and our total gate count N5/3+o(1)N^{5/3 + o(1)}N5/3+o(1) matches the best scaling known for any basis.
Abstract The quantum simulation of quantum chemistry is a promising application of quantum computers. However, for N molecular orbitals, the O(N4){\mathcal{O}}({N}^{4})O(N4) O ( N 4 ) gate complexity of performing Hamiltonian and unitary Coupled Cluster Trotter steps makes simulation based on such primitives challenging. We substantially reduce the gate complexity of such primitives through a two-step low-rank factorization of the Hamiltonian and cluster operator, accompanied by truncation of small terms. Using truncations that incur errors below chemical accuracy allow one to perform Trotter steps of the arbitrary basis electronic structure Hamiltonian with O(N3){\mathcal{O}}({N}^{3})O(N3) O ( N 3 ) gate complexity in small simulations, which reduces to O(N2){\mathcal{O}}({N}^{2})O(N2) O ( N 2 ) gate complexity in the asymptotic regime; and unitary Coupled Cluster Trotter steps with O(N3){\mathcal{O}}({N}^{3})O(N3) O ( N 3 ) gate complexity as a function of increasing basis size for a given molecule. In the case of the Hamiltonian Trotter step, these circuits have O(N2){\mathcal{O}}({N}^{2})O(N2) O ( N 2 ) depth on a linearly connected array, an improvement over the O(N3){\mathcal{O}}({N}^{3})O(N3) O ( N 3 ) scaling assuming no truncation. As a practical example, we show that a chemically accurate Hamiltonian Trotter step for a 50 qubit molecular simulation can be carried out in the molecular orbital basis with as few as 4000 layers of parallel nearest-neighbor two-qubit gates, consisting of fewer than 10 5 non-Clifford rotations. We also apply our algorithm to iron–sulfur clusters relevant for elucidating the mode of action of metalloenzymes.
Quantum dynamics can be simulated on a quantum computer by exponentiating elementary terms from the Hamiltonian in a sequential manner.However, such an implementation of Trotter steps has gate complexity depending on the total Hamiltonian term number, comparing unfavorably to algorithms using more advanced techniques.We develop methods to perform faster Trotter steps with complexity sublinear in the number of terms.We achieve this for a class of Hamiltonians whose interaction strength decays with distance according to power law.Our methods include one based on a recursive block encoding and one based on an average-cost simulation, overcoming the normalization-factor barrier of these advanced quantum simulation techniques.We also realize faster Trotter steps when certain blocks of Hamiltonian coefficients have low rank.Combining with a tighter error analysis, we show that it suffices to use η 1/3 n 1/3 + n 2/3 /η 2/3 n 1+o(1) gates to simulate uniform electron gas with n spin orbitals and η electrons in second quantization in real space, asymptotically improving over the best previous work.We obtain an analogous result when the external potential of nuclei is introduced under the Born-Oppenheimer approximation.We prove a circuit lower bound when the Hamiltonian coefficients take a continuum range of values, showing that generic n-qubit two-local Hamiltonians with commuting terms require at least (n 2 ) gates to evolve with accuracy = (1/poly(n)) for time t = ( ).Our proof is based on a gateefficient reduction from the approximate synthesis of diagonal unitaries within the Hamming weight-2 subspace, which may be of independent interest.Our result thus suggests the use of Hamiltonian structural properties as both necessary and sufficient to implement Trotter steps with lower gate complexity.
With quantum computers on the horizon, it is essential to understand what problems they can be used to solve. One potential application is simulating quantum systems, in particular, systems with many interacting electrons. However, there is a disparity between the computational resources required to study these problems and the capabilities of modern experimental quantum devices. In this thesis, we make progress toward closing this gap by reducing the cost of quantum simulation of quantum chemistry on a number of fronts. In the first half, we develop three improved quantum simulation algorithms by approximating time evolution under the Hamiltonian using a truncated Taylor series rather than the Trotter-Suzuki decomposition. We do this first for the molecular electronic structure Hamiltonian in two representations, obtaining asymptotic improvements in terms of both the number of orbitals and the required precision. We also apply the truncated Taylor series paradigm to quantum simulation in real space, where we consider simulation of general wave functions discretized on a uniform grid. In the second half, by working with Hamiltonians tailored specifically to quantum algorithms, we demonstrate that Trotter steps of the electronic structure Hamiltonian can be simulated in exactly N depth and with only linear connectivity, where N is the number of spin-orbitals. This resolves the problem of non-locality in fermion-to-qubit mappings, and has wide-ranging applications for variational and phase estimation-based quantum simulation of quantum chemistry. We further study this algorithm on an error-corrected quantum computer using the surface code. Benchmarking it alongside other product formula approaches, we show that quantum simulation of scientifically important instances of the electronic structure problem that are classically intractable can be performed with only a few hundred thousand physical qubits and fewer than one billion costly fault-tolerant gates. Finally, we study the effect of using randomized Hamiltonians in iterative phase estimation, and how this allows us to reduce the costs of simulation as well as to exploit knowledge of the ground state in how we design our simulation algorithm.
Abstract We present a quantum algorithm for simulating quantum chemistry with gate complexity O~(N1/3η8/3)\tilde {\cal{O}}(N^{1/3}\eta ^{8/3})O~(N1/3η8/3) O ̃ ( N 1 ∕ 3 η 8 ∕ 3 ) where η is the number of electrons and N is the number of plane wave orbitals. In comparison, the most efficient prior algorithms for simulating electronic structure using plane waves (which are at least as efficient as algorithms using any other basis) have complexity O~(N8/3/η2/3)\tilde {\cal{O}}(N^{8/3}{\mathrm{/}}\eta ^{2/3})O~(N8/3/η2/3) O ̃ ( N 8 ∕ 3 ∕ η 2 ∕ 3 ) . We achieve our scaling in first quantization by performing simulation in the rotating frame of the kinetic operator using interaction picture techniques. Our algorithm is far more efficient than all prior approaches when N ≫ η , as is needed to suppress discretization error when representing molecules in the plane wave basis, or when simulating without the Born-Oppenheimer approximation.
Achieving an accurate description of fermionic systems typically requires considerably many more orbitals than fermions. Previous resource analyses of quantum chemistry simulation often failed to exploit this low fermionic number information in the implementation of Trotter-based approaches and overestimated the quantum-computer runtime as a result. They also depended on numerical procedures that are computationally too expensive to scale up to large systems of practical interest. Here we propose techniques that solve both problems by using various factorized decompositions of the electronic structure Hamiltonian. We showcase our techniques for the uniform electron gas, finding substantial (over $100\ifmmode\times\else\texttimes\fi{}$) improvements in Trotter error for low-filling fraction and pushing to much higher numbers of orbitals than is possible with existing methods. Finally, we calculate the TTT-count to perform phase estimation on Jellium. In the low-filling regime, we observe improvements in gate complexity of over $10\ifmmode\times\else\texttimes\fi{}$ compared to the best Trotter-based approach reported to date. We also report gate counts competitive with qubitization-based approaches for Wigner-Seitz values of physical interest.
The simulation of molecules is a widely anticipated application of quantum computers. However, recent studies [1, 2] have cast a shadow on this hope by revealing that the complexity in gate count of such simulations increases with the number of spin orbitals N as N8 , which becomes prohibitive even for molecules of modest size N ∼ 100. This study was partly based on a scaling analysis of the Trotter step required for an ensemble of random artificial molecules. Here, we revisit this analysis and find instead that the scaling is closer to N6 in worst case for real model molecules we have studied, indicating that the random ensemble fails to accurately capture the statistical properties of real world molecules. Actual scaling may be significantly better than this due to averaging effects. We then present an alternative simulation scheme and show that it can sometimes outperform existing schemes, but that this possibility depends crucially on the details of the simulated molecule. We obtain further improvements using a version of the coalescing scheme of [1]; this scheme is based on using different Trotter steps for different terms. The method we use to bound the complexity of simulating a given molecule is efficient, in contrast to the approach of [1, 2] which relied on exponentially costly classical exact simulation.