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

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 $\tilde{\mathcal{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.

arXiv comment44 pages, 17 figures, formatted for Quantum

References in corpus (46)

• Surface codes: Towards practical large-scale quantum computation
• Simulated Quantum Computation of Molecular Energies
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Elucidating Reaction Mechanisms on Quantum Computers
• Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
• Toward the first quantum simulation with quantum speedup
• The Bravyi-Kitaev transformation for quantum computation of electronic structure
• Simulation of Electronic Structure Hamiltonians Using Quantum Computers
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• A random compiler for fast Hamiltonian simulation
• A new quantum ripple-carry addition circuit
• Gate count estimates for performing quantum chemistry on small quantum computers
• Halving the cost of quantum addition
• Low Depth Quantum Simulation of Electronic Structure
• Structure of Fermionic Density Matrices: Complete N-representability Conditions
• Exponential improvement in precision for simulating sparse Hamiltonians
• Magic State Distillation: Not as Costly as You Think
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Tapering off qubits to simulate fermionic Hamiltonians
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Simulating chemistry efficiently on fault-tolerant quantum computers
• Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• Application of fermionic marginal constraints to hybrid quantum algorithms
• Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization
• Exploiting locality in quantum computation for quantum chemistry
• The electronic complexity of the ground-state of the FeMo cofactor of nitrogenase as relevant to quantum simulations
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Lowering qubit requirements for quantum simulations of fermionic systems
• Auxiliary-field quantum Monte Carlo calculations of molecular systems with a Gaussian basis
• Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size
• Bravyi-Kitaev Superfast simulation of fermions on a quantum computer
• Adiabatic state preparation study of methylene
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Low overhead quantum computation using lattice surgery
• Majorana loop stabilizer codes for error correction of fermionic quantum simulations
• Hamiltonian Simulation in the Interaction Picture
• Linear and logarithmic time compositions of quantum many-body operators
• Locally restricted measurements on a multipartite quantum system: data hiding is generic

Cited by in corpus (127)

• Quantum computational chemistry
• The Variational Quantum Eigensolver: a review of methods and best practices
• Hartree-Fock on a superconducting qubit quantum computer
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• The Future of Quantum Computing with Superconducting Qubits
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Quantum computing enhanced computational catalysis
• Efficient and Noise Resilient Measurements for Quantum Chemistry on Near-Term Quantum Computers
• The prospects of quantum computing in computational molecular biology
• A perspective on the current state-of-the-art of quantum computing for drug discovery applications
• Emerging quantum computing algorithms for quantum chemistry
• Increasing the representation accuracy of quantum simulations of chemistry without extra quantum resources
• Low rank representations for quantum simulation of electronic structure
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Reliably assessing the electronic structure of cytochrome P450 on today's classical computers and tomorrow's quantum computers
• Drug design on quantum computers
• Fault-Tolerant Quantum Simulations of Chemistry in First Quantization
• Factoring 2048-bit RSA Integers in 177 Days with 13436 Qubits and a Multimode Memory
• Low-overhead fault-tolerant quantum computing using long-range connectivity
• A Jastrow-type decomposition in quantum chemistry for low-depth quantum circuits
• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size
• A randomized quantum algorithm for statistical phase estimation
• Universal quantum computing with twist-free and temporally encoded lattice surgery
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• A state-averaged orbital-optimized hybrid quantum-classical algorithm for a democratic description of ground and excited states
• Parallel window decoding enables scalable fault tolerant quantum computation
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Quantum Filter Diagonalization with Double-Factorized Hamiltonians
• Error mitigation via verified phase estimation
• NISQ Computers: A Path to Quantum Supremacy
• Resilience of quantum random access memory to generic noise
• Toward Practical Quantum Embedding Simulation of Realistic Chemical Systems on Near-term Quantum Computers
• How will quantum computers provide an industrially relevant computational advantage in quantum chemistry?
• Nearly tight Trotterization of interacting electrons
• Simulating Many-Body Systems with a Projective Quantum Eigensolver
• Near- and long-term quantum algorithmic approaches for vibrational spectroscopy
• Compilation by stochastic Hamiltonian sparsification
• Efficient quantum computation of molecular forces and other energy gradients
• Initial state preparation for quantum chemistry on quantum computers
• Reducing molecular electronic Hamiltonian simulation cost for Linear Combination of Unitaries approaches
• Block-encoding structured matrices for data input in quantum computing
• Orbital transformations to reduce the 1-norm of the electronic structure Hamiltonian for quantum computing applications
• The Impact of Hardware Specifications on Reaching Quantum Advantage in the Fault Tolerant Regime
• Fluid fermionic fragments for optimizing quantum measurements of electronic Hamiltonians in the variational quantum eigensolver
• Fault-tolerant quantum simulation of materials using Bloch orbitals
• Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
• Rapid initial state preparation for the quantum simulation of strongly correlated molecules
• Quantum Computation for Periodic Solids in Second Quantization
• Improving quantum measurements by introducing "ghost" Pauli products
• On the complexity of implementing Trotter steps
• Quantum simulation of real-space dynamics
• Data centers with quantum random access memory and quantum networks
• Simulating Effective QED on Quantum Computers
• Quantum computation of stopping power for inertial fusion target design
• Strong Error Bounds for Trotter & Strang-Splittings and Their Implications for Quantum Chemistry
• Reducing the runtime of fault-tolerant quantum simulations in chemistry through symmetry-compressed double factorization
• The Basics of Quantum Computing for Chemists
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Exponential improvements in the simulation of lattice gauge theories using near-optimal techniques
• Perturbation theory with quantum signal processing
• Quantum simulation of battery materials using ionic pseudopotentials
• Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
• Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian
• Accelerating Quantum Computations of Chemistry Through Regularized Compressed Double Factorization
• Polylogarithmic-depth controlled-NOT gates without ancilla qubits
• Expressibility of comb tensor network states (CTNS) for the P-cluster and the FeMo-cofactor of nitrogenase
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments
• Quantum Simulations of Chemistry in First Quantization with any Basis Set
• Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory
• Fault-tolerant quantum computation of molecular observables
• A stochastic quantum Krylov protocol with double factorized Hamiltonians
• Efficient Quantum Analytic Nuclear Gradients with Double Factorization
• What the foundations of quantum computer science teach us about chemistry
• Faster quantum chemistry simulations on a quantum computer with improved tensor factorization and active volume compilation
• A Perspective on Quantum Computing Applications in Quantum Chemistry using 25--100 Logical Qubits
• Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
• High ground state overlap via quantum embedding methods
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Option pricing under stochastic volatility on a quantum computer
• The phase/state duality in reversible circuit design
• Fast-forwarding quantum simulation with real-time quantum Krylov subspace algorithms
• Parallel Quantum Algorithm for Hamiltonian Simulation
• TFermion: A non-Clifford gate cost assessment library of quantum phase estimation algorithms for quantum chemistry
• Engineering analog quantum chemistry Hamiltonians using cold atoms in optical lattices
• Quantum Control Machine: The Limits of Control Flow in Quantum Programming
• Fast quantum simulation of electronic structure by spectrum amplification
• QRAM: A Survey and Critique
• Accelerating Quantum Algorithms with Precomputation
• Interleaving: Modular architectures for fault-tolerant photonic quantum computing
• Flexible layout of surface code computations using AutoCCZ states
• Saving superconducting quantum processors from qubit decay and correlated errors generated by gamma and cosmic rays
• Quantum Computation of Electronic Structure with Projector Augmented-Wave Method and Plane Wave Basis Set
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Ab initio extended Hubbard model of short polyenes for efficient quantum computing
• Analytical Ground- and Excited-State Gradients for Molecular Electronic Structure Theory from Hybrid Quantum/Classical Methods
• Roadmap for quantum simulation of the fractional quantum Hall effect
• Solving lattice gauge theories using the quantum Krylov algorithm and qubitization
• Molecular Properties from Quantum Krylov Subspace Diagonalization
• Randomized semi-quantum matrix processing
• Windowed quantum arithmetic
• Classical variational optimization of PREPARE circuit for quantum phase estimation of quantum chemistry Hamiltonians
• Solvent distribution effects on quantum chemical calculations with quantum computers
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings
• Simulating optically-active spin defects with a quantum computer
• Full-Dimensional Schrödinger Wavefunction Calculations using Tensors and Quantum Computers: the Cartesian component-separated approach
• Systematic many-fermion Hamiltonian input scheme and spectral calculations on quantum computers
• Fat-Tree QRAM: A High-Bandwidth Shared Quantum Random Access Memory for Parallel Queries
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Phase estimation with partially randomized time evolution
• Does the full configuration interaction method based on quantum phase estimation with Trotter decomposition satisfy the size consistency condition?
• Quantum resource estimates for computing binary elliptic curve discrete logarithms
• Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
• Fault-tolerant quantum simulation of generalized Hubbard models
• Low Depth Phase Oracle Using a Parallel Piecewise Circuit
• Implementation of a quantum addressable router using superconducting qubits
• Optimizing Quantum Chemistry Simulations with a Hybrid Quantization Scheme
• Unified Architecture for Quantum Lookup Tables
• Halving the cost of quantum multiplexed rotations
• Averaging gate approximation error and performance of Unitary Coupled Cluster ansatz in Pre-FTQC Era
• Offloading Quantum Computation by Superposition Masking
• Benchmarking Quantum Simulation of Chemical Hamiltonians using the Sorted-List Encoding
• Toward Density Functional Theory on Quantum Computers?
• Quantum phase estimation with optimal confidence interval using three control qubits