Quantum Simulation of Chemistry with Sublinear Scaling to the Continuum

Ryan Babbush, Dominic W. Berry, Jarrod R. McClean, Hartmut NevenarXiv 2018

TL;DR

This paper introduces a novel quantum algorithm for simulating quantum chemistry that achieves sublinear scaling with respect to the number of basis functions. This breakthrough significantly reduces the computational resources required, potentially enabling more accurate and complex molecular simulations on future quantum computers.

What Problem Does This Paper Address?

Simulating the electronic structure of molecules is a cornerstone of chemistry and materials science, crucial for understanding chemical reactions, designing new drugs, and discovering novel materials. Quantum computers hold immense promise for tackling these simulations, as they can naturally represent quantum mechanical systems. However, existing quantum algorithms for chemistry simulations face a significant hurdle: their computational cost scales poorly with the size of the system, particularly with the number of basis functions used to represent the molecular orbitals.

Previous approaches often used Gaussian orbitals, which are compact but lead to complex Hamiltonians. While more recent methods employing plane waves offer better structure, they still require a vast number of basis functions (N) to achieve sufficient accuracy, especially for molecules where electron density is localized. This leads to algorithms with gate complexities like O(N⁸/³ / η²/³), where η is the number of electrons. The need for a large N to suppress discretization errors, coupled with the high computational cost, has limited the practical applicability of these methods for realistic molecular simulations. This paper aims to break this scaling barrier by developing an algorithm with sublinear dependence on N.

Methods

The core innovation of this paper lies in a novel quantum algorithm that leverages first quantization and the interaction picture to achieve sublinear scaling in the number of basis functions (N).

Here's a breakdown of the key techniques:

  • First Quantization: Instead of the typical second quantization approach where operators encode fermionic anticommutation relations, this method directly encodes the wavefunction of n particles in N orbitals. This means the wavefunction itself must explicitly satisfy antisymmetry.
  • Plane Wave Basis: The simulation uses a plane wave basis, which is standard for periodic systems and offers good properties for representing electron wavefunctions.
  • Interaction Picture Simulation: The algorithm borrows from the interaction picture technique, which is particularly effective when the Hamiltonian can be split into two parts with vastly different norms (e.g., H = A + B, where ||A|| >> ||B||). By simulating in the rotating frame of the larger norm operator (A), its large norm doesn't dominate the complexity. In this work, the kinetic energy operator (T) is chosen as A, and the potential energy operator (U+V) as B.
  • Momentum Space Representation: The potential energy operator is simulated in momentum space, which is crucial for the interaction picture approach.
  • Novel State Preparation: A significant portion of the paper is dedicated to developing an efficient algorithm for preparing the necessary quantum state, which is identified as a bottleneck in previous approaches. This involves a clever method of preparing a superposition of momentum states using nested cubes and amplitude amplification.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and does not present experimental results or benchmarks on specific datasets.

Key Insights and Ideas

  • Sublinear Scaling is Achievable: The most significant insight is demonstrating that quantum chemistry simulations can achieve gate complexity that scales better than linearly with the number of basis functions (N). This is a major step towards making quantum simulations of complex molecules feasible.
  • First Quantization Advantage: Explicitly enforcing antisymmetry in the wavefunction (first quantization) rather than in the operators (second quantization) is key to unlocking this improved scaling.
  • Interaction Picture for Kinetic Energy: Choosing the kinetic energy operator as the "large" part of the Hamiltonian for the interaction picture simulation is a critical strategic choice that leads to the sublinear scaling in N.
  • State Preparation Bottleneck Solved: The paper presents a surprisingly efficient algorithm for preparing the required momentum state, which was a major obstacle for previous methods. This algorithm's complexity is logarithmic in N, making it negligible compared to other parts of the simulation.
  • Bridging the Gap to Real-World Problems: The authors argue that this improved scaling could allow for simulations of systems like FeMoco (a complex biological molecule) with significantly fewer qubits than previously thought possible, potentially surpassing classical methods in accuracy and resource requirements.

Key Results

The paper presents a quantum algorithm for simulating quantum chemistry with a gate complexity of Õ(N¹/³ η⁸/³), where η is the number of electrons and N is the number of plane wave orbitals. This is a substantial improvement over prior algorithms, such as those with complexity O(N⁸/³ / η²/³).

Specifically, the authors highlight:

  • Improved Gate Complexity: The algorithm achieves Õ(N¹/³ η⁸/³) gate complexity, a significant reduction compared to previous state-of-the-art methods.
  • Sublinear Dependence on Basis Size: The dependence on N is sublinear (N¹/³), meaning that increasing the number of basis functions has a much smaller impact on the computational cost than in previous algorithms.
  • Efficient State Preparation: The proposed state preparation algorithm has a complexity of O(log N), effectively removing a major bottleneck.
  • Potential for Realistic Simulations: The authors estimate that for a molecule like FeMoco, their algorithm could require significantly fewer qubits and T gates compared to previous methods, potentially enabling simulations with higher accuracy than previously feasible.

Limitations and Future Work

  • Constant Factors: While the asymptotic scaling is greatly improved, the paper acknowledges that actual gate counts will depend on constant factors, which require further detailed analysis.
  • Qubitization Alternative: The authors briefly mention that sublinear scaling in basis size could also be achieved without the interaction picture, using qubitization, potentially leading to a slightly different scaling (Õ(n⁸/³N¹/³t + n⁴/³N²/³t)). This suggests avenues for further optimization.
  • Fault Tolerance: The algorithm is presented in the context of fault-tolerant quantum computing. Adapting it for near-term, noisy intermediate-scale quantum (NISQ) devices would be a significant future challenge.
  • Explicit Nuclear Treatment: The algorithm's ability to support simulations with explicit quantum treatment of nuclei is highlighted as a promising future direction, moving beyond the Born-Oppenheimer approximation.
  • FeMoco Simulation: The paper uses the FeMoco calculation as a motivating example, suggesting that further work is needed to fully realize such simulations and compare them rigorously with classical approaches.

Summary updated

BibTeX
@misc{babbush2018quantum,
  author = {Ryan Babbush and Dominic W. Berry and Jarrod R. McClean and Hartmut Neven},
  title = {{Quantum Simulation of Chemistry with Sublinear Scaling to the Continuum}},
  year = {2018},
}
Figure