Low depth mechanisms for quantum optimization

Abstract

One of the major application areas of interest for both near-term and fault-tolerant quantum computers is the optimization of classical objective functions. In this work, we develop intuitive constructions for a large class of these algorithms based on connections to simple dynamics of quantum systems, quantum walks, and classical continuous relaxations. We focus on developing a language and tools connected with kinetic energy on a graph for understanding the physical mechanisms of success and failure to guide algorithmic improvement. This physical language, in combination with uniqueness results related to unitarity, allow us to identify some potential pitfalls from kinetic energy fundamentally opposing the goal of optimization. This is connected to effects from wavefunction confinement, phase randomization, and shadow defects lurking in the objective far away from the ideal solution. As an example, we explore the surprising deficiency of many quantum methods in solving uncoupled spin problems and how this is both predictive of performance on some more complex systems while immediately suggesting simple resolutions. Further examination of canonical problems like the Hamming ramp or bush of implications show that entanglement can be strictly detrimental to performance results from the underlying mechanism of solution in approaches like QAOA. Kinetic energy and graph Laplacian perspectives provide new insights to common initialization and optimal solutions in QAOA as well as new methods for more effective layerwise training. Connections to classical methods of continuous extensions, homotopy methods, and iterated rounding suggest new directions for research in quantum optimization. Throughout, we unveil many pitfalls and mechanisms in quantum optimization using a physical perspective, which aim to spur the development of novel quantum optimization algorithms and refinements.

References in corpus (52)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A variational eigenvalue solver on a quantum processor
• Many body localization and thermalization in quantum statistical mechanics
• Quantum Annealing in the Transverse Ising Model
• 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
• A Quantum Approximate Optimization Algorithm
• Adiabatic Quantum Computing
• Parallel Tempering: Theory, Applications, and New Perspectives
• Quantum annealing with more than one hundred qubits
• Scalable Quantum Simulation of Molecular Energies
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Spatial search by quantum walk
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Computation by Adiabatic Evolution
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• A Quantum Algorithm for Finding the Minimum
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• What is the Computational Value of Finite Range Tunneling?
• Efficient and Noise Resilient Measurements for Quantum Chemistry on Near-Term Quantum Computers
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Improving Variational Quantum Optimization using CVaR
• Quantum versus Classical Annealing of Ising Spin Glasses
• $XY$-mixers: analytical and numerical results for QAOA
• Reachability Deficits in Quantum Approximate Optimization
• A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• Quantum query complexity of some graph problems
• Nested quantum search and NP-complete problems
• Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• Learning to learn with quantum neural networks via classical neural networks
• Quantum Adiabatic Evolution Algorithms with Different Paths
• Applying quantum algorithms to constraint satisfaction problems
• Quantum speedup of branch-and-bound algorithms
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Non-ergodic delocalized states for efficient population transfer within a narrow band of the energy landscape
• Classical and Quantum Bounded Depth Approximation Algorithms
• Comparison of QAOA with Quantum and Simulated Annealing
• Submodular Functions: Extensions, Distributions, and Algorithms. A Survey
• Addressing hard classical problems with Adiabatically Assisted Variational Quantum Eigensolvers
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
• Engineering non-equilibrium quantum phase transitions via causally gapped Hamiltonians
• Efficient population transfer via non-ergodic extended states in quantum spin glass
• Self-Supervised Learning of Generative Spin-Glasses with Normalizing Flows
• Path-Integral Quantum Monte Carlo simulation with Open-Boundary Conditions
• Solving Spin Glasses with Optimized Trees of Clustered Spins

Cited by in corpus (23)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Hybrid quantum-classical algorithms for approximate graph coloring
• Neural Predictor based Quantum Architecture Search
• Biology and medicine in the landscape of quantum advantages
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• A perspective on protein structure prediction using quantum computers
• Progress toward favorable landscapes in quantum combinatorial optimization
• Constrained Optimization via Quantum Zeno Dynamics
• Quantum-Informed Recursive Optimization Algorithms
• Variational Quantum Classifiers Through the Lens of the Hessian
• Quantum approximate optimization algorithm for qudit systems
• Analytical Framework for Quantum Alternating Operator Ansätze
• Reinforcement Learning Assisted Recursive QAOA
• Quantum Optimization for Training Quantum Neural Networks
• Quantum nonequilibrium dynamics from Knizhnik-Zamolodchikov equations
• Gradients and frequency profiles of quantum re-uploading models
• Quantum optimal control in quantum technologies. Strategic report on current status, visions and goals for research in Europe
• A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Freedom of mixer rotation-axis improves performance in the quantum approximate optimization algorithm
• Improving the Quantum Approximate Optimization Algorithm with postselection
• Expanding the reach of quantum optimization with fermionic embeddings
• A loop Quantum Approximate Optimization Algorithm with Hamiltonian updating