Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization

Abstract

Here we explore which heuristic quantum algorithms for combinatorial optimization might be most practical to try out on a small fault-tolerant quantum computer. We compile circuits for several variants of quantum accelerated simulated annealing including those using qubitization or Szegedy walks to quantize classical Markov chains and those simulating spectral gap amplified Hamiltonians encoding a Gibbs state. We also optimize fault-tolerant realizations of the adiabatic algorithm, quantum enhanced population transfer, the quantum approximate optimization algorithm, and other approaches. Many of these methods are bottlenecked by calls to the same subroutines; thus, optimized circuits for those primitives should be of interest regardless of which heuristic is most effective in practice. We compile these bottlenecks for several families of optimization problems and report for how long and for what size systems one can perform these heuristics in the surface code given a range of resource budgets. Our results discourage the notion that any quantum optimization heuristic realizing only a quadratic speedup will achieve an advantage over classical algorithms on modest superconducting qubit surface code processors without significant improvements in the implementation of the surface code. For instance, under quantum-favorable assumptions (e.g., that the quantum algorithm requires exactly quadratically fewer steps), our analysis suggests that quantum accelerated simulated annealing would require roughly a day and a million physical qubits to optimize spin glasses that could be solved by classical simulated annealing in about four CPU-minutes.

arXiv comment77 pages, 19 figures, 9 tables. v2 contains new appendix on in-place binary to unary conversion

References in corpus (40)

• Fault-tolerant quantum computation by anyons
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Surface codes: Towards practical large-scale quantum computation
• Quantum Annealing in the Transverse Ising Model
• 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
• Fault-tolerant quantum computation with high threshold in two dimensions
• Hamiltonian Simulation by Qubitization
• Quantum annealing with more than one hundred qubits
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Quantum speedup of Monte Carlo methods
• Halving the cost of quantum addition
• Fixed-point quantum search with an optimal number of queries
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Quantum Simulations of Classical Annealing Processes
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Higher Order Decompositions of Ordered Operator Exponentials
• Optimized simulated annealing for Ising spin glasses
• Simulating chemistry efficiently on fault-tolerant quantum computers
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Efficient synthesis of universal Repeat-Until-Success circuits
• Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• Black-box quantum state preparation without arithmetic
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Improved Error-Scaling for Adiabatic Quantum State Transfer
• Applying quantum algorithms to constraint satisfaction problems
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• Quantum speedup of branch-and-bound algorithms
• Distilling one-qubit magic states into Toffoli states
• Non-ergodic delocalized states for efficient population transfer within a narrow band of the energy landscape
• Low Autocorrelation Binary Sequences
• A note on the switching adiabatic theorem
• Fast Quantum Methods for Optimization
• On The Power Of Coherently Controlled Quantum Adiabatic Evolutions
• Improved Bounds for Eigenpath Traversal

Cited by in corpus (64)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Quantum computing for finance
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Fault-Tolerant Quantum Simulations of Chemistry in First Quantization
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Factoring 2048-bit RSA Integers in 177 Days with 13436 Qubits and a Multimode Memory
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Low-overhead fault-tolerant quantum computing using long-range connectivity
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• A case study of variational quantum algorithms for a job shop scheduling problem
• Early fault-tolerant simulations of the Hubbard model
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Benchmarking quantum computers
• Exponential quantum speedup in simulating coupled classical oscillators
• Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation
• Hybridized Methods for Quantum Simulation in the Interaction Picture
• Grid-based methods for chemistry simulations on a quantum computer
• Block-encoding structured matrices for data input in quantum computing
• Constrained Optimization via Quantum Zeno Dynamics
• Quantifying nonlocality: how outperforming local quantum codes is expensive
• A scalable and fast artificial neural network syndrome decoder for surface codes
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• Preparing Bethe Ansatz Eigenstates on a Quantum Computer
• Fault-tolerant quantum simulation of materials using Bloch orbitals
• Rapid initial state preparation for the quantum simulation of strongly correlated molecules
• An efficient quantum algorithm for preparation of uniform quantum superposition states
• Quantum algorithm for time-dependent differential equations using Dyson series
• Quantum computation of stopping power for inertial fusion target design
• High-Fidelity Magic-State Preparation with a Biased-Noise Architecture
• Explainable AI using expressive Boolean formulas
• Extending relax-and-round combinatorial optimization solvers with quantum correlations
• 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
• Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations
• Quantum Simulation of Realistic Materials in First Quantization Using Non-local Pseudopotentials
• 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 computing through the lens of control: A tutorial introduction
• Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
• On proving the robustness of algorithms for early fault-tolerant quantum computers
• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• Fast quantum simulation of electronic structure by spectrum amplification
• Accelerating Quantum Algorithms with Precomputation
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• End-to-end complexity for simulating the Schwinger model on quantum computers
• The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver
• Quantum Extremal Learning
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• The First Hardware Demonstration of a Universal Programmable RRAM-based Probabilistic Computer for Molecular Docking
• Quantum eigenvalue processing
• Quantum state preparation via piecewise QSVT
• Low Depth Phase Oracle Using a Parallel Piecewise Circuit
• Fault-tolerant quantum simulation of generalized Hubbard models
• No ((n, k, d < 127)) code can violate the quantum Hamming bound
• Phase estimation with partially randomized time evolution
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
• Approximate real-time evolution operator for potential with one ancillary qubit and application to first-quantized Hamiltonian simulation
• Quantum Simulation of Nuclear Dynamics in First Quantization
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs