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:1902.02134 · Quantum

Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization

Dominic William Berry, Craig Gidney, Mário Motta, Jarrod R. McClean, Ryan Babbush

Published Dec 2, 2019• 223 citations
arXivHTMLPDF

Abstract

Recent work has dramatically reduced the gate complexity required to quantum simulate chemistry by using linear combinations of unitaries based methods to exploit structure in the plane wave basis Coulomb operator. Here, we show that one can achieve similar scaling even for arbitrary basis sets (which can be hundreds of times more compact than plane waves) by using qubitized quantum walks in a fashion that takes advantage of structure in the Coulomb operator, either by directly exploiting sparseness, or via a low rank tensor factorization. We provide circuits for several variants of our algorithm (which all improve over the scaling of prior methods) including one with O ~ ( N 3 / 2 λ ) T complexity, where N is number of orbitals and λ is the 1-norm of the chemistry Hamiltonian. We deploy our algorithms to simulate the FeMoco molecule (relevant to Nitrogen fixation) and obtain circuits requiring about seven hundred times less surface code spacetime volume than prior quantum algorithms for this system, despite us using a larger and more accurate active space.

DOI
10.22331/q-2019-12-02-208

Related papers

Qubitization of Arbitrary Basis Quantum Chemistry by Low Rank Factorization

Dominic William Berry, Craig Gidney, Mário Motta +2 more

Recent work has dramatically reduced the gate complexity required to quantum simulate chemistry by using linear combinations of unitaries based methods to exploit structure in the plane wave basis Coulomb operator. Here, we show that one can achieve similar scaling even for arbitrary basis sets (which can be hundreds of times more compact than plane waves) by using qubitized quantum walks in a fashion that takes advantage of structure in the Coulomb operator, either by directly exploiting sparseness, or via a low rank tensor factorization. We provide circuits for several variants of our algorithm (which all improve over the scaling of prior methods) including one with $\widetilde{\cal O}(N^{3/2} \lambda)$ T complexity, where $N$ is number of orbitals and $\lambda$ is the 1-norm of the chemistry Hamiltonian. We deploy our algorithms to simulate the FeMoco molecule (relevant to Nitrogen fixation) and obtain circuits requiring about seven hundred times less surface code spacetime volume than prior quantum algorithms for this system, despite us using a larger and more accurate active space.

•Feb 6, 2019•6 citations

Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction

Joonho Lee, Dominic William Berry, Craig Gidney +4 more

We describe quantum circuits with only O(N ) Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of N arbitrary (e.g., molecular) orbitals.With O(λ/ ) repetitions of these circuits one can use phase estimation to sample in the molecular eigenbasis, where λ is the 1-norm of Hamiltonian coefficients and is the target precision.This is the lowest complexity shown for quantum computations of chemistry within an arbitrary basis.Furthermore, up to logarithmic factors, this matches the scaling of the most efficient prior block encodings that can work only with orthogonal-basis functions diagonalizing the Coloumb operator (e.g., the plane-wave dual basis).Our key insight is to factorize the Hamiltonian using a method known as tensor hypercontraction (THC) and then to transform the Coulomb operator into an isospectral diagonal form with a nonorthogonal basis defined by the THC factors.We then use qubitization to simulate the nonorthogonal THC Hamiltonian, in a fashion that avoids most complications of the nonorthogonal basis.We also reanalyze and reduce the cost of several of the best prior algorithms for these simulations in order to facilitate a clear comparison to the present work.In addition to having lower asymptotic scaling space-time volume, compilation of our algorithm for challenging finitesized molecules such as FeMoCo reveals that our method requires the least fault-tolerant resources of any known approach.By laying out and optimizing the surface-code resources required of our approach we show that FeMoCo can be simulated using about four million physical qubits and under 4 days of runtime, assuming 1-μs cycle times and physical gate-error rates no worse than 0.1%.

arXiv:2011.03494•PRX Quantum•Jul 8, 2021•304 citations

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

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

Orbital transformations to reduce the 1-norm of the electronic structure Hamiltonian for quantum computing applications

Emiel Koridon, Saad Yalouz, Bruno Senjean +3 more

Reducing the complexity of quantum algorithms to treat quantum chemistry problems is essential to demonstrate an eventual quantum advantage of noisy-intermediate scale quantum devices over their classical counterpart. Significant improvements have been made recently to simulate the time-evolution operator $U(t)={e}^{i\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{H}}t}$, where $\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{H}}$ is the electronic structure Hamiltonian, or to simulate $\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{H}}$ directly (when written as a linear combination of unitaries) by using block encoding or qubitization techniques. A fundamental measure quantifying the practical implementation complexity of these quantum algorithms is the so-called 1-norm of the qubit representation of the Hamiltonian, which can be reduced by writing the Hamiltonian in factorized or tensor-hypercontracted forms, for instance. In this paper, we investigate the effect of classical preoptimization of the electronic structure Hamiltonian representation, via single-particle basis transformation, on the 1-norm. Specifically, we employ several localization schemes and benchmark the 1-norm of several systems of different sizes (number of atoms and active space sizes). We also derive a formula for the 1-norm as a function of the electronic integrals and use this quantity as a cost function for an orbital-optimization scheme that improves over localization schemes. This paper gives more insights about the importance of the 1-norm in quantum computing for quantum chemistry and provides simple ways of decreasing its value to reduce the complexity of quantum algorithms.

arXiv:2103.14753•Physical Review Research•Aug 6, 2021•38 citations

Quantum simulations of chemistry in first quantization with any basis set

Timothy N. Georges, Marius Bothe, Christoph Sünderhauf +3 more

Quantum computation of the energy of molecules and materials is one of the most promising applications of fault-tolerant quantum computers. Practical applications require development of quantum algorithms with reduced resource requirements. Previous work has mainly focused on quantum algorithms where the Hamiltonian is represented in second quantization with compact basis sets while existing methods in first quantization are limited to a grid-based basis. In this work, we present a new method to solve the generic ground-state chemistry problem in first quantization using any basis set. We achieve asymptotic speedup in Toffoli count for molecular orbitals, and orders of magnitude improvement using dual plane waves as compared to the second quantization counterparts. In some instances, our approach provides similar or even lower resources compared to previous first quantization plane wave algorithms that, unlike our approach, avoids the loading of the classical data. The developed methodology can be applied to variety of applications, where the matrix elements of a first quantized Hamiltonian lack simple circuit representation.

arXiv:2408.03145•npj Quantum Information•Apr 1, 2025•19 citations
Recent work has dramatically reduced the gate complexity required to quantum simulate chemistry by using linear combinations of unitaries based methods to exploit structure in the plane wave basis Coulomb operator. Here, we show that one can achieve similar scaling even for arbitrary basis sets (which can be hundreds of times more compact than plane waves) by using qubitized quantum walks in a fashion that takes advantage of structure in the Coulomb operator, either by directly exploiting sparseness, or via a low rank tensor factorization. We provide circuits for several variants of our algorithm (which all improve over the scaling of prior methods) including one with O ~ ( N 3 / 2 λ ) T complexity, where N is number of orbitals and λ is the 1-norm of the chemistry Hamiltonian. We deploy our algorithms to simulate the FeMoco molecule (relevant to Nitrogen fixation) and obtain circuits requiring about seven hundred times less surface code spacetime volume than prior quantum algorithms for this system, despite us using a larger and more accurate active space.
Recent work has dramatically reduced the gate complexity required to quantum simulate chemistry by using linear combinations of unitaries based methods to exploit structure in the plane wave basis Coulomb operator. Here, we show that one can achieve similar scaling even for arbitrary basis sets (which can be hundreds of times more compact than plane waves) by using qubitized quantum walks in a fashion that takes advantage of structure in the Coulomb operator, either by directly exploiting sparseness, or via a low rank tensor factorization. We provide circuits for several variants of our algorithm (which all improve over the scaling of prior methods) including one with O~(N3/2λ)\widetilde{\cal O}(N^{3/2} \lambda)O(N3/2λ) T complexity, where NNN is number of orbitals and λ\lambdaλ is the 1-norm of the chemistry Hamiltonian. We deploy our algorithms to simulate the FeMoco molecule (relevant to Nitrogen fixation) and obtain circuits requiring about seven hundred times less surface code spacetime volume than prior quantum algorithms for this system, despite us using a larger and more accurate active space.
We describe quantum circuits with only O(N ) Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of N arbitrary (e.g., molecular) orbitals.With O(λ/ ) repetitions of these circuits one can use phase estimation to sample in the molecular eigenbasis, where λ is the 1-norm of Hamiltonian coefficients and is the target precision.This is the lowest complexity shown for quantum computations of chemistry within an arbitrary basis.Furthermore, up to logarithmic factors, this matches the scaling of the most efficient prior block encodings that can work only with orthogonal-basis functions diagonalizing the Coloumb operator (e.g., the plane-wave dual basis).Our key insight is to factorize the Hamiltonian using a method known as tensor hypercontraction (THC) and then to transform the Coulomb operator into an isospectral diagonal form with a nonorthogonal basis defined by the THC factors.We then use qubitization to simulate the nonorthogonal THC Hamiltonian, in a fashion that avoids most complications of the nonorthogonal basis.We also reanalyze and reduce the cost of several of the best prior algorithms for these simulations in order to facilitate a clear comparison to the present work.In addition to having lower asymptotic scaling space-time volume, compilation of our algorithm for challenging finitesized molecules such as FeMoCo reveals that our method requires the least fault-tolerant resources of any known approach.By laying out and optimizing the surface-code resources required of our approach we show that FeMoCo can be simulated using about four million physical qubits and under 4 days of runtime, assuming 1-μs cycle times and physical gate-error rates no worse than 0.1%.
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.
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.
Reducing the complexity of quantum algorithms to treat quantum chemistry problems is essential to demonstrate an eventual quantum advantage of noisy-intermediate scale quantum devices over their classical counterpart. Significant improvements have been made recently to simulate the time-evolution operator $U(t)={e}^{i\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{H}}t}$, where $\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{H}}$ is the electronic structure Hamiltonian, or to simulate $\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{H}}$ directly (when written as a linear combination of unitaries) by using block encoding or qubitization techniques. A fundamental measure quantifying the practical implementation complexity of these quantum algorithms is the so-called 1-norm of the qubit representation of the Hamiltonian, which can be reduced by writing the Hamiltonian in factorized or tensor-hypercontracted forms, for instance. In this paper, we investigate the effect of classical preoptimization of the electronic structure Hamiltonian representation, via single-particle basis transformation, on the 1-norm. Specifically, we employ several localization schemes and benchmark the 1-norm of several systems of different sizes (number of atoms and active space sizes). We also derive a formula for the 1-norm as a function of the electronic integrals and use this quantity as a cost function for an orbital-optimization scheme that improves over localization schemes. This paper gives more insights about the importance of the 1-norm in quantum computing for quantum chemistry and provides simple ways of decreasing its value to reduce the complexity of quantum algorithms.
Quantum computation of the energy of molecules and materials is one of the most promising applications of fault-tolerant quantum computers. Practical applications require development of quantum algorithms with reduced resource requirements. Previous work has mainly focused on quantum algorithms where the Hamiltonian is represented in second quantization with compact basis sets while existing methods in first quantization are limited to a grid-based basis. In this work, we present a new method to solve the generic ground-state chemistry problem in first quantization using any basis set. We achieve asymptotic speedup in Toffoli count for molecular orbitals, and orders of magnitude improvement using dual plane waves as compared to the second quantization counterparts. In some instances, our approach provides similar or even lower resources compared to previous first quantization plane wave algorithms that, unlike our approach, avoids the loading of the classical data. The developed methodology can be applied to variety of applications, where the matrix elements of a first quantized Hamiltonian lack simple circuit representation.