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\%$.

73 pages, fixed typos

References in corpus (9)

• Surface codes: Towards practical large-scale quantum computation
• Simulated Quantum Computation of Molecular Energies
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Quantum circuits for strongly correlated quantum systems
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Systematically Improvable Tensor Hypercontraction: Interpolative Separable Density-Fitting for Molecules Applied to Exact Exchange, Second- and Third-Order Møller-Plesset Perturbation Theory
• Separable Resolution-of-the-Identity with All-Electron Gaussian Bases: Application to Cubic-scaling RPA
• Hybrid grid/basis set discretizations of the Schrödinger equation

Cited by in corpus (183)

• 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
• 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
• Optimized Low-Depth Quantum Circuits for Molecular Electronic Structure using a Separable Pair Approximation
• Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values
• 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
• 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
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• Fluid fermionic fragments for optimizing quantum measurements of electronic Hamiltonians in the variational quantum eigensolver
• Fault-tolerant quantum simulation of materials using Bloch orbitals
• Rapid initial state preparation for the quantum simulation of strongly correlated molecules
• Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
• Quantum Computation for Periodic Solids in Second Quantization
• On the complexity of implementing Trotter steps
• Hybrid quantum-classical algorithm for computing imaginary-time correlation functions
• Scalable Networking of Neutral-Atom Qubits: Nanofiber-Based Approach for Multiprocessor Fault-Tolerant Quantum Computer
• Quantum simulation of real-space dynamics
• 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
• qSWIFT: High-order randomized compiler for Hamiltonian simulation
• Tensorized Pauli decomposition algorithm
• Error-resilient Monte Carlo quantum simulation of imaginary time
• The Cost of Improving the Precision of the Variational Quantum Eigensolver for Quantum Chemistry
• Statistical phase estimation and error mitigation on a superconducting quantum processor
• 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
• Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation
• Quantum simulation of battery materials using ionic pseudopotentials
• Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian
• HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
• Accelerating Quantum Computations of Chemistry Through Regularized Compressed Double Factorization
• Handbook for Quantifying Robustness of Magic
• Polylogarithmic-depth controlled-NOT gates without ancilla qubits
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• Platinum-based Catalysts for Oxygen Reduction Reaction simulated with a Quantum Computer
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Quantum Equation of Motion with Orbital Optimization for Computing Molecular Properties in Near-Term Quantum Computing
• Quantum Simulations of Chemistry in First Quantization with any Basis Set
• Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments
• Quantum algorithms for scientific computing
• 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
• Fault-tolerant quantum computation of molecular observables
• Average-case Speedup for Product Formulas
• A Perspective on Quantum Computing Applications in Quantum Chemistry using 25--100 Logical Qubits
• Quantum Simulation of Realistic Materials in First Quantization Using Non-local Pseudopotentials
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Faster quantum chemistry simulations on a quantum computer with improved tensor factorization and active volume compilation
• Contextual Subspace Variational Quantum Eigensolver Calculation of the Dissociation Curve of Molecular Nitrogen on a Superconducting Quantum Computer
• Rise of conditionally clean ancillae for efficient quantum circuit constructions
• Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
• 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
• Measurement-efficient quantum Krylov subspace diagonalisation
• Compilation of a simple chemistry application to quantum error correction primitives
• Option pricing under stochastic volatility on a quantum computer
• Fast-forwarding quantum simulation with real-time quantum Krylov subspace algorithms
• Scatter-Gather DMA Performance Analysis within an SoC-based Control System for Trapped-Ion Quantum Computing
• LILLIPUT: A Lightweight Low-Latency Lookup-Table Based Decoder for Near-term Quantum Error Correction
• Distributed Quantum Computing with QMPI
• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
• Improved Parameter Targeting in 3D-Integrated Superconducting Circuits through a Polymer Spacer Process
• 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
• Mitigating Errors on Superconducting Quantum Processors through Fuzzy Clustering
• Interleaving: Modular architectures for fault-tolerant photonic quantum computing
• More quantum chemistry with fewer qubits
• Simulating open-system molecular dynamics on analog quantum computers
• 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
• Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
• Unlocking early fault-tolerant quantum computing with mitigated magic dilution
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Quantum Computation of Electronic Structure with Projector Augmented-Wave Method and Plane Wave Basis Set
• Sparse random Hamiltonians are quantumly easy
• Concatenate codes, save qubits
• LUCI in the Surface Code with Dropouts
• Practicality of quantum adiabatic algorithm for chemistry applications
• Efficient ground-state energy estimation and certification on early fault-tolerant quantum computers
• Ab initio extended Hubbard model of short polyenes for efficient quantum computing
• Dimension reduction and redundancy removal through successive Schmidt decompositions
• Differentiable quantum computational chemistry with PennyLane
• TE-PAI: Exact Time Evolution by Sampling Random Circuits
• Resource-optimized fault-tolerant simulation of the Fermi-Hubbard model and high-temperature superconductor models
• Molecular Properties from Quantum Krylov Subspace Diagonalization
• The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts
• Near-term quantum algorithm for computing molecular and materials properties based on recursive variational series methods
• Randomized semi-quantum matrix processing
• Quantifying Grover speed-ups beyond asymptotic analysis
• Quantum Computing in Pharma: A Multilayer Embedding Approach for Near Future Applications
• LSQCA: Resource-Efficient Load/Store Architecture for Limited-Scale Fault-Tolerant Quantum Computing
• Simulating optically-active spin defects with a quantum computer
• Faster computation of nonstabilizerness
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Classical variational optimization of PREPARE circuit for quantum phase estimation of quantum chemistry Hamiltonians
• Solvent distribution effects on quantum chemical calculations with quantum computers
• Ladder Operator Block-Encoding
• Distributed quantum error correction based on hyperbolic Floquet codes
• The Electronic Structure of the Hydrogen Molecule: A Tutorial Exercise in Classical and Quantum Computation
• Comparative study on compact quantum circuits of hybrid quantum-classical algorithms for quantum impurity models
• Quantum eigenvalue processing
• Capturing the Page Curve and Entanglement Dynamics of Black Holes in Quantum Computers
• Prospects for NMR Spectral Prediction on Fault-Tolerant Quantum Computers
• Does the full configuration interaction method based on quantum phase estimation with Trotter decomposition satisfy the size consistency condition?
• Practical limitations of quantum data propagation on noisy quantum processors
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Low Depth Phase Oracle Using a Parallel Piecewise Circuit
• Fault-tolerant quantum simulation of generalized Hubbard models
• Superconducting qubits in the millions: the potential and limitations of modularity
• 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
• Halving the cost of quantum multiplexed rotations
• Quantum linear system algorithm with optimal queries to initial state preparation
• Type-Based Verification of Connectivity Constraints in Lattice Surgery
• 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
• Error Crafting in Mixed Quantum Gate Synthesis
• Quantum Utility in Simulating the Real-time Dynamics of the Fermi-Hubbard Model using Superconducting Quantum Computers
• Hybrid quantum gap estimation algorithm using a filtered time series
• Fault-tolerant interfaces for modular quantum computing on diverse qubit platforms
• Averaging gate approximation error and performance of Unitary Coupled Cluster ansatz in Pre-FTQC Era
• Moments-based quantum computation of the electric dipole moment of molecular systems
• Fault-tolerant Quantum Error Correction Using a Linear Array of Emitters
• Enhanced Krylov Methods for Molecular Hamiltonians: Reduced Memory Cost and Complexity Scaling via Tensor Hypercontraction
• 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
• Faster Quantum Algorithm for Multiple Observables Estimation in Fermionic Problems
• 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
• Quantum Simulation of Nuclear Dynamics in First Quantization
• Toward Density Functional Theory on Quantum Computers?
• Towards Compact Wavefunctions from Quantum-Selected Configuration Interaction
• Numerical investigation of the quantum inverse algorithm on small molecules