Obstacles to State Preparation and Variational Optimization from Symmetry Protection

Abstract

Local Hamiltonians with topological quantum order exhibit highly entangled ground states that cannot be prepared by shallow quantum circuits. Here, we show that this property may extend to all low-energy states in the presence of an on-site ${\mathbb{Z}}_2$ symmetry. This proves a version of the No Low-Energy Trivial States (NLTS) conjecture for a family of local Hamiltonians with symmetry protected topological order. A surprising consequence of this result is that the Goemans-Williamson algorithm outperforms the Quantum Approximate Optimization Algorithm (QAOA) for certain instances of MaxCut, at any constant level. We argue that the locality and symmetry of QAOA severely limits its performance. To overcome these limitations, we propose a non-local version of QAOA, and give numerical evidence that it significantly outperforms standard QAOA for frustrated Ising models on random 3-regular graphs.

16 pages

References in corpus (12)

• Fault-tolerant quantum computation by anyons
• A variational eigenvalue solver on a quantum processor
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Barren plateaus in quantum neural network training landscapes
• Entanglement spectrum of a topological phase in one dimension
• Tensor-Entanglement-Filtering Renormalization Approach and Symmetry Protected Topological Order
• Classifying quantum phases using Matrix Product States and PEPS
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Local Hamiltonians Whose Ground States are Hard to Approximate
• Classical and Quantum Bounded Depth Approximation Algorithms
• Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes

Cited by in corpus (148)

• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Warm-starting quantum optimization
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Exploiting symmetry in variational quantum machine learning
• Challenges and Opportunities in Quantum Optimization
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Quantum Algorithm Implementations for Beginners
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Parameter Concentration in Quantum Approximate Optimization
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Hybrid quantum-classical algorithms for approximate graph coloring
• The Quantum Wasserstein Distance of Order 1
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Fast quantum circuit cutting with randomized measurements
• NISQ Computers: A Path to Quantum Supremacy
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Empirical performance bounds for quantum approximate optimization
• Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• A perspective on protein structure prediction using quantum computers
• Constrained mixers for the quantum approximate optimization algorithm
• Building spatial symmetries into parameterized quantum circuits for faster training
• Graph neural network initialisation of quantum approximate optimisation
• Variational Quantum Simulation for Periodic Materials
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Quantum optimization via four-body Rydberg gates
• Low depth mechanisms for quantum optimization
• Symmetry-protected sign problem and magic in quantum phases of matter
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Symmetry enhanced variational quantum spin eigensolver
• Quantum-Informed Recursive Optimization Algorithms
• Evaluation of QAOA based on the approximation ratio of individual samples
• Assessing Quantum Computing Performance for Energy Optimization in a Prosumer Community
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• An entanglement perspective on the quantum approximate optimization algorithm
• Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• Two-dimensional ${\mathbb{Z}}_2$ lattice gauge theory on a near-term quantum simulator: variational quantum optimization, confinement, and topological order
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Quantum Approximate Optimization Algorithm pseudo-Boltzmann states
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Fast Black-Box Quantum State Preparation
• Analytical Framework for Quantum Alternating Operator Ansätze
• Quantum supremacy and random circuits
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
• Reinforcement Learning Assisted Recursive QAOA
• Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem
• An evolving objective function for improved variational quantum optimisation
• Efficient variational synthesis of quantum circuits with coherent multi-start optimization
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Exponentially tighter bounds on limitations of quantum error mitigation
• Provable bounds for noise-free expectation values computed from noisy samples
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Extending relax-and-round combinatorial optimization solvers with quantum correlations
• Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs
• Practical Verification of Quantum Properties in Quantum Approximate Optimization Runs
• Quantum Approximate Multi-Objective Optimization
• A SAT approach to the initial mapping problem in SWAP gate insertion for commuting gates
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
• Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms
• Quantum Optimization for Training Quantum Neural Networks
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• QED driven QAOA for network-flow optimization
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• Multi-Level Variational Spectroscopy using a Programmable Quantum Simulator
• Fair Sampling Error Analysis on NISQ Devices
• A Toffoli Gate Decomposition via Echoed Cross-Resonance Gates
• Multi-Objective Optimization and Network Routing with Near-Term Quantum Computers
• Sharp complexity phase transitions generated by entanglement
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• Symmetry-informed transferability of optimal parameters in the Quantum Approximate Optimization Algorithm
• Improved approximation algorithms for bounded-degree local Hamiltonians
• Automatic Depth Optimization for Quantum Approximate Optimization Algorithm
• Variational Quantum Multi-Objective Optimization
• Progress towards analytically optimal angles in quantum approximate optimisation
• Quantum-Classical Computational Molecular Design of Deuterated High-Efficiency OLED Emitters
• Approximating under the Influence of Quantum Noise and Compute Power
• Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
• Synergies Between Operations Research and Quantum Information Science
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Recursive Quantum Relaxation for Combinatorial Optimization Problems
• Improving the Performance of Digitized Counterdiabatic Quantum Optimization via Algorithm-Oriented Qubit Mapping
• Simulation of a feedback-based algorithm for quantum optimization for a realistic neutral atom system with an optimized small-angle controlled-phase gate
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Generating Target Graph Couplings for QAOA from Native Quantum Hardware Couplings
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms
• Variational quantum simulation of long-range interacting systems
• Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
• Benchmarking hybrid digitized-counterdiabatic quantum optimization
• Efficient ground state preparation in variational quantum eigensolver with symmetry-breaking layers
• Random Natural Gradient
• Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization
• Limitations of variational quantum algorithms: a quantum optimal transport approach
• Circuit lower bounds for low-energy states of quantum code Hamiltonians
• Combinatorial NLTS From the Overlap Gap Property
• A construction of Combinatorial NLTS
• Twisted hybrid algorithms for combinatorial optimization
• Hierarchical Multigrid Ansatz for Variational Quantum Algorithms
• Imaginary Hamiltonian variational ansatz for combinatorial optimization problems
• Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
• LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism
• Advancing Hybrid Quantum-Classical Algorithms via Mean-Operators
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Deep-Circuit QAOA
• Charged particle reconstruction for future high energy colliders with Quantum Approximate Optimization Algorithm
• On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA
• Limits of Short-Time Evolution of Local Hamiltonians
• Atom Cavity Encoding for NP-Complete Problems
• Path Matters: Industrial Data Meet Quantum Optimization
• Policy Gradient Approach to Compilation of Variational Quantum Circuits
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• Photonic variational quantum eigensolver for NISQ-compatible quantum technology
• Machine-learning-inspired quantum control in many-body dynamics
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Predict and Conquer: Navigating Algorithm Trade-offs with Quantum Design Automation
• Variational simulation of higher-spin systems on qubit-based quantum simulators
• Improving the Quantum Approximate Optimization Algorithm with postselection
• Efficient Large-Scale Quantum Optimization via Counterdiabatic Ansatz
• Mitigating Noise-Induced Gradient Vanishing in Variational Quantum Algorithm Training
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Q-CHOP: Quantum constrained Hamiltonian optimization
• A Quantum Constraint Generation Framework for Binary Linear Programs
• A loop Quantum Approximate Optimization Algorithm with Hamiltonian updating
• Qubit-efficient quantum combinatorial optimization solver
• Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA
• Classical algorithms for Forrelation
• Encodings of the weighted MAX k-CUT on qubit systems
• Electric Power Demand Portfolio Optimization by Fermionic QAOA with Self-Consistent Local Field Modulation
• Optimized fermionic SWAP networks with equivalent circuit averaging for QAOA