Even more efficient quantum computations of chemistry through tensor hypercontraction

Abstract

We describe quantum circuits with only $\tilde{\mathcal{O}}(N)$ Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of $N$ arbitrary (e.g., molecular) orbitals. With $\mathcal{O}(\lambda /\epsilon )$ repetitions of these circuits one can use phase estimation to sample in the molecular eigenbasis, where $\lambda$ is the 1-norm of Hamiltonian coefficients and $\epsilon$ is the target precision. This is the lowest complexity that has been 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 only work 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 non-orthogonal basis defined by the THC factors. We then use qubitization to simulate the non-orthogonal THC Hamiltonian, in a fashion that avoids most complications of the non-orthogonal 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 spacetime volume, compilation of our algorithm for challenging finite-sized 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 four days of runtime, assuming $1\mu$s cycle times and physical gate error rates no worse than $0.1\%$.

arXiv comment73 pages, fixed typos

References in corpus (48)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Surface codes: Towards practical large-scale quantum computation
• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• Simulated Quantum Computation of Molecular Energies
• Hamiltonian Simulation by Qubitization
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Elucidating Reaction Mechanisms on Quantum Computers
• 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
• Gate count estimates for performing quantum chemistry on small quantum computers
• Halving the cost of quantum addition
• Low Depth Quantum Simulation of Electronic Structure
• Efficient and Noise Resilient Measurements for Quantum Chemistry on Near-Term Quantum Computers
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Magic State Distillation: Not as Costly as You Think
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Nearly optimal lattice simulation by product formulas
• Near-optimal ground state preparation
• Quantum circuits for strongly correlated quantum systems
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization
• Regularized Orbital-Optimized Second-Order Møller-Plesset Perturbation Theory: A Reliable Fifth-Order Scaling Electron Correlation Model with Orbital Energy Dependent Regularizers
• 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
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size
• Low rank factorization of the Coulomb integrals for periodic coupled cluster theory
• Exponentially More Precise Quantum Simulation of Fermions in the Configuration Interaction Representation
• Systematically Improvable Tensor Hypercontraction: Interpolative Separable Density-Fitting for Molecules Applied to Exact Exchange, Second- and Third-Order Møller-Plesset Perturbation Theory
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Tensor-Structured Coupled Cluster Theory
• Efficient ab initio auxiliary-field quantum Monte Carlo calculations in Gaussian bases via low-rank tensor decomposition
• Bounding the costs of quantum simulation of many-body physics in real space
• Separable Resolution-of-the-Identity with All-Electron Gaussian Bases: Application to Cubic-scaling RPA
• Cubic scaling algorithms for RPA correlation using interpolative separable density fitting
• Improved Grid Optimization and Fitting in Least Squares Tensor Hypercontraction
• Hybrid grid/basis set discretizations of the Schrödinger equation

Cited by in corpus (185)

• The Variational Quantum Eigensolver: a review of methods and best practices
• Quantum Error Mitigation
• Exponential suppression of bit or phase flip errors with repetitive error correction
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• A perspective on the current state-of-the-art of quantum computing for drug discovery applications
• Emerging quantum computing algorithms for quantum chemistry
• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Reliably assessing the electronic structure of cytochrome P450 on today's classical computers and tomorrow's quantum computers
• Digital Quantum Simulation of the Schwinger Model and Symmetry Protection with Trapped Ions
• Drug design on quantum computers
• Measurements as a roadblock to near-term practical quantum advantage in chemistry: resource analysis
• 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
• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
• A randomized quantum algorithm for statistical phase estimation
• Chemistry Beyond the Scale of Exact Diagonalization on a Quantum-Centric Supercomputer
• A Fault-Tolerant Honeycomb Memory
• Universal quantum computing with twist-free and temporally encoded lattice surgery
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Orbital-optimized pair-correlated electron simulations on trapped-ion quantum computers
• Parallel window decoding enables scalable fault tolerant quantum computation
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Prospects of Quantum Computing for Molecular Sciences
• NISQ Computers: A Path to Quantum Supremacy
• Purification-based quantum error mitigation of pair-correlated electron simulations
• Concentration for random product formulas
• Toward Practical Quantum Embedding Simulation of Realistic Chemical Systems on Near-term Quantum Computers
• Benchmarking quantum computers
• A high-fidelity quantum matter-link between ion-trap microchip modules
• Towards near-term quantum simulation of materials
• Simulating Many-Body Systems with a Projective Quantum Eigensolver
• Efficient Fully-Coherent Quantum Signal Processing Algorithms for Real-Time Dynamics Simulation
• Simulating key properties of lithium-ion batteries with a fault-tolerant quantum computer
• Efficient quantum computation of molecular forces and other energy gradients
• Initial state preparation for quantum chemistry on quantum computers
• Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values
• Optimized Low-Depth Quantum Circuits for Molecular Electronic Structure using a Separable Pair Approximation
• Block-encoding structured matrices for data input in quantum computing
• Reducing molecular electronic Hamiltonian simulation cost for Linear Combination of Unitaries approaches
• Hunting for quantum-classical crossover in condensed matter problems
• A scalable and fast artificial neural network syndrome decoder for surface codes
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• 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
• Quantum Computation for Periodic Solids in Second Quantization
• Rapid initial state preparation for the quantum simulation of strongly correlated molecules
• On the complexity of implementing Trotter steps
• Hybrid quantum-classical algorithm for computing imaginary-time correlation functions
• Quantum simulation of real-space dynamics
• Scalable Networking of Neutral-Atom Qubits: Nanofiber-Based Approach for Multiprocessor Fault-Tolerant Quantum Computer
• Enhancing quantum utility: simulating large-scale quantum spin chains on superconducting quantum computers
• Simulating Effective QED on Quantum Computers
• Quantum computation of stopping power for inertial fusion target design
• Tensorized Pauli decomposition algorithm
• qSWIFT: High-order randomized compiler for Hamiltonian simulation
• Statistical phase estimation and error mitigation on a superconducting quantum processor
• Error-resilient Monte Carlo quantum simulation of imaginary time
• The Cost of Improving the Precision of the Variational Quantum Eigensolver for Quantum Chemistry
• Reducing the runtime of fault-tolerant quantum simulations in chemistry through symmetry-compressed double factorization
• Strong Error Bounds for Trotter & Strang-Splittings and Their Implications for Quantum Chemistry
• 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
• Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation
• Quantum simulation of battery materials using ionic pseudopotentials
• HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
• Accelerating Quantum Computations of Chemistry Through Regularized Compressed Double Factorization
• Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian
• Handbook for Quantifying Robustness of Magic
• Polylogarithmic-depth controlled-NOT gates without ancilla qubits
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Platinum-based Catalysts for Oxygen Reduction Reaction simulated with a Quantum Computer
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• Quantum algorithms for scientific computing
• Quantum Simulations of Chemistry in First Quantization with any Basis Set
• Quantum Equation of Motion with Orbital Optimization for Computing Molecular Properties in Near-Term Quantum Computing
• Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments
• Fault-tolerant quantum computation of molecular observables
• Assessment of various Hamiltonian partitionings for the electronic structure problem on a quantum computer using the Trotter approximation
• What the foundations of quantum computer science teach us about chemistry
• Average-case Speedup for Product Formulas
• A Perspective on Quantum Computing Applications in Quantum Chemistry using 25--100 Logical Qubits
• Faster quantum chemistry simulations on a quantum computer with improved tensor factorization and active volume compilation
• Quantum Simulation of Realistic Materials in First Quantization Using Non-local Pseudopotentials
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Rise of conditionally clean ancillae for efficient quantum circuit constructions
• Contextual Subspace Variational Quantum Eigensolver Calculation of the Dissociation Curve of Molecular Nitrogen on a Superconducting Quantum Computer
• Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
• Power-optimal, stabilized entangling gate between trapped-ion qubits
• High ground state overlap via quantum embedding methods
• ERASER: Towards Adaptive Leakage Suppression for Fault-Tolerant Quantum Computing
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Quantifying $T$-gate-count improvements for ground-state-energy estimation with near-optimal state preparation
• Tangling schedules eases hardware connectivity requirements for quantum error correction
• Option pricing under stochastic volatility on a quantum computer
• Measurement-efficient quantum Krylov subspace diagonalisation
• Compilation of a simple chemistry application to quantum error correction primitives
• Distributed Quantum Computing with QMPI
• LILLIPUT: A Lightweight Low-Latency Lookup-Table Based Decoder for Near-term Quantum Error Correction
• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• Scatter-Gather DMA Performance Analysis within an SoC-based Control System for Trapped-Ion Quantum Computing
• Fast-forwarding quantum simulation with real-time quantum Krylov subspace algorithms
• TFermion: A non-Clifford gate cost assessment library of quantum phase estimation algorithms for quantum chemistry
• Fast quantum simulation of electronic structure by spectrum amplification
• Improved Parameter Targeting in 3D-Integrated Superconducting Circuits through a Polymer Spacer Process
• Mitigating Errors on Superconducting Quantum Processors through Fuzzy Clustering
• Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
• More quantum chemistry with fewer qubits
• Interleaving: Modular architectures for fault-tolerant photonic quantum computing
• Local Clustering Decoder as a fast and adaptive hardware decoder for the surface code
• Code switching revisited: Low-overhead magic state preparation using color codes
• Simulating open-system molecular dynamics on analog quantum computers
• Quantum Computation of Electronic Structure with Projector Augmented-Wave Method and Plane Wave Basis Set
• Practicality of quantum adiabatic algorithm for chemistry applications
• Concatenate codes, save qubits
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Unlocking early fault-tolerant quantum computing with mitigated magic dilution
• LUCI in the Surface Code with Dropouts
• Sparse random Hamiltonians are quantumly easy
• Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
• Differentiable quantum computational chemistry with PennyLane
• Ab initio extended Hubbard model of short polyenes for efficient quantum computing
• Efficient ground-state energy estimation and certification on early fault-tolerant quantum computers
• TE-PAI: Exact Time Evolution by Sampling Random Circuits
• Dimension reduction and redundancy removal through successive Schmidt decompositions
• The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts
• Randomized semi-quantum matrix processing
• Resource-optimized fault-tolerant simulation of the Fermi-Hubbard model and high-temperature superconductor models
• Near-term quantum algorithm for computing molecular and materials properties based on recursive variational series methods
• Molecular Properties from Quantum Krylov Subspace Diagonalization
• Quantifying Grover speed-ups beyond asymptotic analysis
• Solvent distribution effects on quantum chemical calculations with quantum computers
• Ladder Operator Block-Encoding
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Quantum Computing in Pharma: A Multilayer Embedding Approach for Near Future Applications
• Faster computation of nonstabilizerness
• LSQCA: Resource-Efficient Load/Store Architecture for Limited-Scale Fault-Tolerant Quantum Computing
• Simulating optically-active spin defects with a quantum computer
• Classical variational optimization of PREPARE circuit for quantum phase estimation of quantum chemistry Hamiltonians
• Comparative study on compact quantum circuits of hybrid quantum-classical algorithms for quantum impurity models
• The Electronic Structure of the Hydrogen Molecule: A Tutorial Exercise in Classical and Quantum Computation
• Capturing the Page Curve and Entanglement Dynamics of Black Holes in Quantum Computers
• Distributed quantum error correction based on hyperbolic Floquet codes
• Quantum eigenvalue processing
• Low Depth Phase Oracle Using a Parallel Piecewise Circuit
• Superconducting qubits in the millions: the potential and limitations of modularity
• Prospects for NMR Spectral Prediction on Fault-Tolerant Quantum Computers
• Practical limitations of quantum data propagation on noisy quantum processors
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Quantum-computing within a bosonic context: Assessing finite basis effects on prototypical vibrational Hamiltonian spectra
• Phase estimation with partially randomized time evolution
• Fat-Tree QRAM: A High-Bandwidth Shared Quantum Random Access Memory for Parallel Queries
• Fault-tolerant quantum simulation of generalized Hubbard models
• Does the full configuration interaction method based on quantum phase estimation with Trotter decomposition satisfy the size consistency condition?
• Fault-tolerant interfaces for modular quantum computing on diverse qubit platforms
• Quantum linear system algorithm with optimal queries to initial state preparation
• Hybrid quantum gap estimation algorithm using a filtered time series
• Averaging gate approximation error and performance of Unitary Coupled Cluster ansatz in Pre-FTQC Era
• Type-Based Verification of Connectivity Constraints in Lattice Surgery
• Halving the cost of quantum multiplexed rotations
• Online Job Scheduler for Fault-tolerant Quantum Multiprogramming
• Quantum algorithm for solving generalized eigenvalue problems with application to the Schrödinger equation
• Quantum-Classical Auxiliary Field Quantum Monte Carlo with Matchgate Shadows on Trapped Ion Quantum Computers
• Optimizing Quantum Chemistry Simulations with a Hybrid Quantization Scheme
• Quantum Utility in Simulating the Real-time Dynamics of the Fermi-Hubbard Model using Superconducting Quantum Computers
• Error Crafting in Mixed Quantum Gate Synthesis
• Towards Compact Wavefunctions from Quantum-Selected Configuration Interaction
• Benchmarking Quantum Simulation of Chemical Hamiltonians using the Sorted-List Encoding
• Dense packing of the surface code: code deformation procedures and hook-error-avoiding gate scheduling
• Quantum phase estimation with optimal confidence interval using three control qubits
• Efficient Auxiliary-Field Quantum Monte Carlo using Isometric Tensor Hypercontraction
• QAISim: A Toolkit for Modeling and Simulation of AI in Quantum Cloud Computing Environments
• Fault-tolerant Quantum Error Correction Using a Linear Array of Emitters
• Numerical investigation of the quantum inverse algorithm on small molecules
• Toward Density Functional Theory on Quantum Computers?
• Quantum Simulation of Nuclear Dynamics in First Quantization
• Faster Quantum Algorithm for Multiple Observables Estimation in Fermionic Problems
• Enhanced Krylov Methods for Molecular Hamiltonians: Reduced Memory Cost and Complexity Scaling via Tensor Hypercontraction
• Moments-based quantum computation of the electric dipole moment of molecular systems