Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity

Abstract

We construct quantum circuits which exactly encode the spectra of correlated electron models up to errors from rotation synthesis. By invoking these circuits as oracles within the recently introduced "qubitization" framework, one can use quantum phase estimation to sample states in the Hamiltonian eigenbasis with optimal query complexity $O(\lambda /\epsilon )$ where $\lambda$ is an absolute sum of Hamiltonian coefficients and $\epsilon$ is target precision. For both the Hubbard model and electronic structure Hamiltonian in a second quantized basis diagonalizing the Coulomb operator, our circuits have T gate complexity $O(N+\log (1/\epsilon ))$ where $N$ is number of orbitals in the basis. This enables sampling in the eigenbasis of electronic structure Hamiltonians with T complexity $O(N^3/\epsilon +N^2\log (1/\epsilon )/\epsilon )$. Compared to prior approaches, our algorithms are asymptotically more efficient in gate complexity and require fewer T gates near the classically intractable regime. Compiling to surface code fault-tolerant gates and assuming per gate error rates of one part in a thousand reveals that one can error correct phase estimation on interesting instances of these problems beyond the current capabilities of classical methods using only about a million superconducting qubits in a matter of hours.

arXiv comment39 pages, 25 figures, 9 tables; fixed minor errors from v1

References in corpus (68)

• A variational eigenvalue solver on a quantum processor
• Surface codes: Towards practical large-scale quantum computation
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Topological quantum memory
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Simulated Quantum Computation of Molecular Energies
• Quantum random access memory
• Fault-tolerant quantum computation with high threshold in two dimensions
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Scalable Quantum Simulation of Molecular Energies
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Elucidating Reaction Mechanisms on Quantum Computers
• Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
• Towards Practical Quantum Variational Algorithms
• Synthesis of Quantum Logic Circuits
• Topological fault-tolerance in cluster state quantum computation
• Surface code quantum computing by lattice surgery
• Toward the first quantum simulation with quantum speedup
• Density matrix embedding: A simple alternative to dynamical mean-field theory
• Simulation of Electronic Structure Hamiltonians Using Quantum Computers
• Quantum measurements and the Abelian Stabilizer Problem
• Robust determination of molecular spectra on a quantum processor
• Solutions of the Two Dimensional Hubbard Model: Benchmarks and Results from a Wide Range of Numerical Algorithms
• Quantum chemistry calculations on a trapped-ion quantum simulator
• Correlation energy and spin polarization in the 2D electron gas
• Semiclassical Fourier Transform for Quantum Computation
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• Quantum codes on a lattice with boundary
• Simulating Physical Phenomena by Quantum Networks
• Architectures for a quantum random access memory
• Gate count estimates for performing quantum chemistry on small quantum computers
• Solving strongly correlated electron models on a quantum computer
• Halving the cost of quantum addition
• Low Depth Quantum Simulation of Electronic Structure
• Hybrid quantum-classical approach to correlated materials
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Adiabatic Quantum Simulation of Quantum Chemistry
• Phase Diagram of the Low-Density Two-Dimensional Homogeneous Electron Gas
• Higher Order Decompositions of Ordered Operator Exponentials
• Quantum algorithms to simulate many-body physics of correlated fermions
• On Arbitrary Phases in Quantum Amplitude Amplification
• A Full Configuration Interaction Perspective on the Homogeneous Electron Gas
• Simulating chemistry efficiently on fault-tolerant quantum computers
• Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
• Improved magic states distillation for quantum universality
• Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization
• Exploiting locality in quantum computation for quantum chemistry
• On the robustness of bucket brigade quantum RAM
• Poking holes and cutting corners to achieve Clifford gates with the surface code
• Spin Polarization of the Low Density 3D Electron Gas
• Polynomial-Time Simulation of Pairing Models on a Quantum Computer
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Investigation of the Full Configuration Interaction Quantum Monte Carlo Method Using Homogeneous Electron Gas Models
• Quantum Monte Carlo study of the three-dimensional spin-polarized homogeneous electron gas
• Exponentially More Precise Quantum Simulation of Fermions in the Configuration Interaction Representation
• Bounding the costs of quantum simulation of many-body physics in real space
• Low Loss Multi-Layer Wiring for Superconducting Microwave Devices
• A bridge to lower overhead quantum computation
• A Robust Quantum Random Access Memory
• High Coherence Plane Breaking Packaging for Superconducting Qubits
• Optimal complexity correction of correlated errors in the surface code
• Hybrid grid/basis set discretizations of the Schrödinger equation
• Representation and design of wavelets using unitary circuits
• Synthesis of Arbitrary Quantum Circuits to Topological Assembly: Systematic, Online and Compact

Cited by in corpus (231)

• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• 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
• A Theory of Trotter Error
• Generalized Unitary Coupled Cluster Wavefunctions for Quantum Computation
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• A random compiler for fast Hamiltonian simulation
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Halving the cost of quantum addition
• Quantum computing enhanced computational catalysis
• Error-mitigated digital quantum simulation
• Microwave Quantum Link between Superconducting Circuits Housed in Spatially Separated Cryogenic Systems
• Quantum Computer Systems for Scientific Discovery
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Magic State Distillation: Not as Costly as You Think
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• A perspective on the current state-of-the-art of quantum computing for drug discovery applications
• Strategies for solving the Fermi-Hubbard model on near-term quantum computers
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Increasing the representation accuracy of quantum simulations of chemistry without extra quantum resources
• Hardware-efficient quantum random access memory with hybrid quantum acoustic systems
• Low rank representations for quantum simulation of electronic structure
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• Circuit-Based Quantum Random Access Memory for Classical Data
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• Reliably assessing the electronic structure of cytochrome P450 on today's classical computers and tomorrow's quantum computers
• Quantum error mitigation as a universal error-minimization technique: applications from NISQ to FTQC eras
• Digital Quantum Simulation of the Schwinger Model and Symmetry Protection with Trapped Ions
• Decoding quantum errors with subspace expansions
• Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation
• Measurement reduction in variational quantum algorithms
• Fault-Tolerant Quantum Simulations of Chemistry in First Quantization
• Black-box quantum state preparation without arithmetic
• Factoring 2048-bit RSA Integers in 177 Days with 13436 Qubits and a Multimode Memory
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Quantum Simulation of Quantum Field Theory in the Light-Front Formulation
• 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
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Downfolding of many-body Hamiltonians using active-space models: extension of the sub-system embedding sub-algebras approach to unitary coupled cluster formalisms
• Quantum Computing for Neutrino-nucleus Scattering
• Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size
• A randomized quantum algorithm for statistical phase estimation
• Fault tolerant resource estimation of quantum random-access memories
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Early fault-tolerant simulations of the Hubbard model
• Orbital-optimized pair-correlated electron simulations on trapped-ion quantum computers
• Minimizing estimation runtime on noisy quantum computers
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Resilience of quantum random access memory to generic noise
• Benchmarking quantum computers
• How will quantum computers provide an industrially relevant computational advantage in quantum chemistry?
• Applying quantum algorithms to constraint satisfaction problems
• Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series
• Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
• Quantum codes for quantum simulation of Fermions on a square lattice of qubits
• Evaluating energy differences on a quantum computer with robust phase estimation
• Linear-depth quantum circuits for multiqubit controlled gates
• Fast multi-qubit gates through simultaneous two-qubit gates
• Near- and long-term quantum algorithmic approaches for vibrational spectroscopy
• Simulating key properties of lithium-ion batteries with a fault-tolerant quantum computer
• Efficient quantum computation of molecular forces and other energy gradients
• Compilation by stochastic Hamiltonian sparsification
• Boundaries of quantum supremacy via random circuit sampling
• Quantum unary approach to option pricing
• Hybridized Methods for Quantum Simulation in the Interaction Picture
• Initial state preparation for quantum chemistry on quantum computers
• Block-encoding structured matrices for data input in quantum computing
• No-go theorems for quantum resource purification II: new approach and channel theory
• Subsystem codes with high thresholds by gauge fixing and reduced qubit overhead
• Low cost quantum circuits for classically intractable instances of the Hamiltonian dynamics simulation problem
• Extensive characterization of a family of efficient three-qubit gates at the coherence limit
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• Preparing Bethe Ansatz Eigenstates on a Quantum Computer
• Parallelising the Queries in Bucket Brigade Quantum RAM
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Fault-tolerant quantum simulation of materials using Bloch orbitals
• Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer
• Rapid initial state preparation for the quantum simulation of strongly correlated molecules
• Quantum Computation for Periodic Solids in Second Quantization
• Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
• Fault-tolerant qubit from a constant number of components
• Local variational quantum compilation of a large-scale Hamiltonian dynamics
• Seeking a quantum advantage with trapped-ion quantum simulations of condensed-phase chemical dynamics
• Multi-sliced Gausslet Basis Sets for Electronic Structure
• A Sparse Model of Quantum Holography
• Simulating Effective QED on Quantum Computers
• Data centers with quantum random access memory and quantum networks
• Quantum computation of stopping power for inertial fusion target design
• Statistical phase estimation and error mitigation on a superconducting quantum processor
• Systems Architecture for Quantum Random Access Memory
• Looped Pipelines Enabling Effective 3D Qubit Lattices in a Strictly 2D Device
• Error-resilient Monte Carlo quantum simulation of imaginary time
• Reducing the runtime of fault-tolerant quantum simulations in chemistry through symmetry-compressed double factorization
• Hamiltonian simulation for hyperbolic partial differential equations by scalable quantum circuits
• Efficient Deterministic Preparation of Quantum States Using Decision Diagrams
• Nearly-optimal state preparation for quantum simulations of lattice gauge theories
• High-Fidelity Magic-State Preparation with a Biased-Noise Architecture
• LDPC-cat codes for low-overhead quantum computing in 2D
• Constraints on magic state protocols from the statistical mechanics of Wigner negativity
• Creating and manipulating a Laughlin-type $\nu =1/3$ fractional quantum Hall state on a quantum computer with linear depth circuits
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Perturbation theory with quantum signal processing
• Exponential improvements in the simulation of lattice gauge theories using near-optimal techniques
• Quantum simulation of battery materials using ionic pseudopotentials
• Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
• Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation
• Implementation of Measurement Reduction for the Variational Quantum Eigensolver
• Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian
• Accelerating Quantum Computations of Chemistry Through Regularized Compressed Double Factorization
• Towards early fault tolerance on a 2$\times$N array of qubits equipped with shuttling
• Importance sampling for stochastic quantum simulations
• Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
• Doubling Efficiency of Hamiltonian Simulation via Generalized Quantum Signal Processing
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Variational dynamics as a ground-state problem on a quantum computer
• 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
• Quantum algorithms for scientific computing
• Fault-tolerant quantum computation of molecular observables
• Accurate and Efficient Quantum Computations of Molecular Properties Using Daubechies Wavelet Molecular Orbitals: A Benchmark Study against Experimental Data
• Quantum Simulation of Realistic Materials in First Quantization Using Non-local Pseudopotentials
• Faster quantum chemistry simulations on a quantum computer with improved tensor factorization and active volume compilation
• Optimal Hamiltonian simulation for time-periodic systems
• Overhead-constrained circuit knitting for variational quantum dynamics
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians
• The prospects of Monte Carlo antibody loop modelling on a fault-tolerant quantum computer
• Rise of conditionally clean ancillae for efficient quantum circuit constructions
• Quantum error mitigation for Fourier moment computation
• Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
• Dancing the Quantum Waltz: Compiling Three-Qubit Gates on Four Level Architectures
• Power-optimal, stabilized entangling gate between trapped-ion qubits
• A controllable two-qubit swapping gate using superconducting circuits
• Quantifying $T$-gate-count improvements for ground-state-energy estimation with near-optimal state preparation
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Tangling schedules eases hardware connectivity requirements for quantum error correction
• Measurement-efficient quantum Krylov subspace diagonalisation
• Jet Discrimination with Quantum Complete Graph Neural Network
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Quantum state preparation for multivariate functions
• Unitary Partitioning and the Contextual Subspace Variational Quantum Eigensolver
• Universal quantum computing with thermal state bosonic systems
• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• Low-overhead quantum computing with the color code
• Black-Box Quantum State Preparation with Inverse Coefficients
• Quantifying fermionic nonlinearity of quantum circuits
• TFermion: A non-Clifford gate cost assessment library of quantum phase estimation algorithms for quantum chemistry
• Selection and improvement of product formulae for best performance of quantum simulation
• Quantum Control Machine: The Limits of Control Flow in Quantum Programming
• Fast quantum simulation of electronic structure by spectrum amplification
• SurfBraid: A concept tool for preparing and resource estimating quantum circuits protected by the surface code
• QRAM: A Survey and Critique
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Cycle Index Polynomials and Generalized Quantum Separability Tests
• Time-Efficient Logical Operations on Quantum Low-Density Parity Check Codes
• Anderson impurity solver integrating tensor network methods with quantum computing
• Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
• Flexible layout of surface code computations using AutoCCZ states
• Block encoding bosons by signal processing
• Entanglement-assisted phase estimation algorithm for calculating dynamical response functions
• Calculating the energy profile of an enzymatic reaction on a quantum computer
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Quantum random access memory with transmon-controlled phonon routing
• Quantum simulation costs for Suzuki-Trotter decomposition of quantum many-body lattice models
• Roadmap for quantum simulation of the fractional quantum Hall effect
• Molecular Properties from Quantum Krylov Subspace Diagonalization
• Resource-optimized fault-tolerant simulation of the Fermi-Hubbard model and high-temperature superconductor models
• Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian
• Windowed quantum arithmetic
• Classical variational optimization of PREPARE circuit for quantum phase estimation of quantum chemistry Hamiltonians
• Quantum phase estimation based filtering: performance analysis and application to low-energy spectral calculation
• Ladder Operator Block-Encoding
• LSQCA: Resource-Efficient Load/Store Architecture for Limited-Scale Fault-Tolerant Quantum Computing
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• Simulating optically-active spin defects with a quantum computer
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Refining resource estimation for the quantum computation of vibrational molecular spectra through Trotter error analysis
• Efficient multi-qubit subspace rotations via topological quantum walks
• Learning from physics experiments, with quantum computers: Applications in muon spectroscopy
• Quantum simulation by qubitization without Toffoli gates
• Heisenberg-limited adaptive gradient estimation for multiple observables
• Some Error Analysis for the Quantum Phase Estimation Algorithms
• Unification of Finite Symmetries in Simulation of Many-body Systems on Quantum Computers
• Nonlinear Spectroscopy via Generalized Quantum Phase Estimation
• Hybrid Quantum-Classical Algorithm For Robust Optimization via Stochastic-Gradient Online Learning
• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
• Implementation of a quantum addressable router using superconducting qubits
• Discontinuous Galerkin discretization for quantum simulation of chemistry
• Does the full configuration interaction method based on quantum phase estimation with Trotter decomposition satisfy the size consistency condition?
• Exponential distillation of dominant eigenproperties
• Prospects for NMR Spectral Prediction on Fault-Tolerant Quantum Computers
• Superconducting qubits in the millions: the potential and limitations of modularity
• Approximate real-time evolution operator for potential with one ancillary qubit and application to first-quantized Hamiltonian simulation
• Time versus Hardware: Reducing Qubit Counts with a (Surface Code) Data Bus
• Low Depth Phase Oracle Using a Parallel Piecewise Circuit
• Fault-tolerant quantum simulation of generalized Hubbard models
• Quantum resource estimates for computing binary elliptic curve discrete logarithms
• Averting multi-qubit burst errors in surface code magic state factories
• A Q# Implementation of a Quantum Lookup Table for Quantum Arithmetic Functions
• Symmetric channel verification for purifying noisy quantum channels
• Averaging gate approximation error and performance of Unitary Coupled Cluster ansatz in Pre-FTQC Era
• Error Crafting in Mixed Quantum Gate Synthesis
• Unified Architecture for Quantum Lookup Tables
• Type-Based Verification of Connectivity Constraints in Lattice Surgery
• Four-body coupler for superconducting qubits based on Josephson parametric oscillators
• Correcting and extending Trotterized quantum many-body dynamics
• Refined Criteria for QRAM Error Suppression via Efficient Large-Scale QRAM Simulator
• 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
• Phase Estimation with Compressed Controlled Time Evolution
• A Jordan-Wigner gadget that reduces T count by more than 6x for quantum chemistry applications
• Really Small Shoe Boxes - On Realistic Quantum Resource Estimation
• Faster Quantum Algorithm for Multiple Observables Estimation in Fermionic Problems
• Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation
• Quantum Heaviside Eigen Solver
• Quantum Error Source and Channel Coding
• Quantum phase estimation with optimal confidence interval using three control qubits
• Block Encoding of Sparse Matrices via Coherent Permutation
• Quantum Arithmetic Algorithms: Implementation, Resource Estimation, and Comparison
• Fast-forwardability of Qubit-mapped Fermion models based on Cartan decomposition
• qSIEVE: Efficient qLDPC Memory via Systolic Movement in Atom Arrays
• Benchmarking Quantum Simulation of Chemical Hamiltonians using the Sorted-List Encoding
• Network Requirements for Distributed Quantum Computation
• Quantum Merlin-Arthur proof systems for synthesizing quantum states
• Benincasa-Dowker-Glaser causal set actions by quantum counting