Qubitization of Arbitrary Basis Quantum Chemistry by Low Rank Factorization

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

Abstract

Recent advancements in quantum simulation have significantly reduced the gate complexity required for chemistry by exploiting the structure of the Coulomb operator in plane wave bases. However, plane wave bases often require a large number of qubits to achieve chemical accuracy. This paper demonstrates that similar efficiency can be achieved for arbitrary basis sets—which are often hundreds of times more compact—by utilizing qubitized quantum walks. By exploiting the inherent sparsity and low-rank structure of the Coulomb operator, we present algorithms that improve upon the scaling of prior methods, including a variant with $\widetilde{\cal O}(N^{3/2} \lambda)$ T complexity. When applied to the FeMoco molecule, our methods reduce the surface code spacetime volume by a factor of approximately 700 compared to previous state-of-the-art algorithms, even while employing a larger and more accurate active space.

Introduction

Simulating the electronic structure of complex molecules is a primary objective for fault-tolerant quantum computing. A central challenge in this field is the choice of basis set. Plane wave bases offer a highly structured Coulomb operator that simplifies the Hamiltonian, but they necessitate a massive number of qubits. Conversely, arbitrary molecular bases (such as Gaussian orbitals) are highly compact but result in a Hamiltonian with $O(N^4)$ terms, where $N$ is the number of orbitals. This complexity has historically made arbitrary basis sets prohibitively expensive for quantum simulation. This work bridges that gap, providing a path to simulate chemistry in compact bases with the efficiency previously reserved for structured plane waves.

Methodology

Qubitization and Quantum Walks

The core of the proposed algorithm is "qubitization," a framework that encodes the Hamiltonian into a quantum walk. Unlike traditional Trotterization, which approximates time evolution through discrete steps, qubitization enables more efficient phase estimation with significantly lower overhead. This approach allows the simulation complexity to scale with the 1-norm of the Hamiltonian coefficients, denoted as $\lambda$.

Low-Rank Tensor Factorization

The primary bottleneck in arbitrary basis sets is the four-index Coulomb tensor $V_{pqrs}$, which describes electron-electron interactions. The authors demonstrate that this tensor is mathematically redundant and exhibits "low-rank" properties. By reshaping the tensor into a matrix and performing diagonalization, the interaction terms can be truncated. This factorization reduces the number of terms from $O(N^4)$ to $O(N^3)$ without sacrificing the precision required for chemical accuracy.

Sparsity and Algorithmic Engineering

Beyond factorization, the algorithm exploits the natural sparsity of the Hamiltonian, ignoring near-zero interaction terms. To handle the remaining data efficiently, the authors utilize an optimized version of QROM (Quantum Read-Only Memory) called "QROAM." Additionally, they introduce a novel measurement-based uncomputation technique. This method uses X-basis measurements and classically conditioned phase fixups to erase temporary data, drastically reducing the cost of Toffoli gates compared to standard reversible uncomputation.

Case Study: The FeMoco Molecule

To validate these methods, the authors simulated the Iron-Molybdenum cofactor (FeMoco), the active site of the nitrogenase enzyme. FeMoco is a critical target for quantum chemistry because understanding its catalytic mechanism for nitrogen fixation could lead to breakthroughs in industrial fertilizer production.

The study evaluated two active space models:

  • RWSWT: 108 spin-orbitals.
  • LLDUC: 152 spin-orbitals (a larger, more accurate representation).

By applying low-rank factorization and qubitization, the researchers achieved a T-gate complexity of $\tilde{O}(N^{3/2}\lambda)$. For the 152-orbital FeMoco model, the algorithm requires approximately $8 \times 10^{10}$ Toffoli gates and between 2,900 and 5,100 logical qubits.

Discussion and Results

The results represent a significant leap in feasibility for molecular simulation. The 700-fold reduction in surface code spacetime volume moves FeMoco simulation from a multi-decade computational task to one that may be viable on early-generation fault-tolerant hardware.

A key insight of the paper is the "rank deficiency of nature": the fact that pairwise Coulomb interactions are sufficiently smooth that they can be compressed significantly. This compression ensures that $\lambda$ remains manageable even as the number of orbitals increases.

Limitations and Future Outlook

Despite the massive reduction in resources, "magic state distillation"—the process of generating T-gates—remains a significant bottleneck, potentially requiring millions of qubit-weeks. Furthermore, while the algorithm scales well with $N$, the behavior of the $\lambda$ parameter in the "continuum limit" (as the basis set approaches infinite size) requires further study. Finally, for extremely large systems, the authors suggest that first-quantized methods, which track electron positions rather than orbital occupancy, may eventually surpass the efficiency of the second-quantized methods presented here.

Summary updated

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 $\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.
BibTeX
@article{berry2019qubitization,
  author = {Dominic W. Berry and Craig Gidney and Mário Motta and Jarrod R. McClean and Ryan Babbush},
  title = {{Qubitization of Arbitrary Basis Quantum Chemistry by Low Rank Factorization}},
  journal = {Quantum},
  year = {2019},
  doi = {10.22331/q-2019-12-02-208},
}

Loading related content...

Figure