Quantum annealing initialization of the quantum approximate optimization algorithm

Abstract

The quantum approximate optimization algorithm (QAOA) is a prospective near-term quantum algorithm due to its modest circuit depth and promising benchmarks. However, an external parameter optimization required in QAOA could become a performance bottleneck. This motivates studies of the optimization landscape and search for heuristic ways of parameter initialization. In this work we visualize the optimization landscape of the QAOA applied to the MaxCut problem on random graphs, demonstrating that random initialization of the QAOA is prone to converging to local minima with sub-optimal performance. We introduce the initialization of QAOA parameters based on the Trotterized quantum annealing (TQA) protocol, parameterized by the Trotter time step. We find that the TQA initialization allows to circumvent the issue of false minima for a broad range of time steps, yielding the same performance as the best result out of an exponentially scaling number of random initializations. Moreover, we demonstrate that the optimal value of the time step coincides with the point of proliferation of Trotter errors in quantum annealing. Our results suggest practical ways of initializing QAOA protocols on near-term quantum devices and reveals new connections between QAOA and quantum annealing.

arXiv comment10 pages, 9 figures; typos corrected, references added

References in corpus (36)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Quantum Computing in the NISQ era and beyond
• The density-matrix renormalization group in the age of matrix product states
• Quantum Annealing in the Transverse Ising Model
• Barren plateaus in quantum neural network training landscapes
• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• A Quantum Approximate Optimization Algorithm
• Adiabatic Quantum Computing
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Shortcuts to adiabaticity: concepts, methods, and applications
• The power of quantum neural networks
• Hartree-Fock on a superconducting qubit quantum computer
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Quantum Computation by Adiabatic Evolution
• Benchmarking an 11-qubit quantum computer
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Warm-starting quantum optimization
• Simulating quantum many-body dynamics on a current digital quantum computer
• Minimizing irreversible losses in quantum systems by local counter-diabatic driving
• Floquet-engineering counterdiabatic protocols in quantum many-body systems
• Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
• Quantum localization bounds Trotter errors in digital quantum simulation
• Benchmarking the Quantum Approximate Optimization Algorithm
• MAXCUT QAOA performance guarantees for p >1
• Observation of separated dynamics of charge and spin in the Fermi-Hubbard model
• Multistart Methods for Quantum Approximate Optimization
• Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Investigating Quantum Approximate Optimization Algorithms under Bang-bang Protocols

Cited by in corpus (70)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
• Avoiding barren plateaus using classical shadows
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Parameter Concentration in Quantum Approximate Optimization
• Counterdiabaticity and the quantum approximate optimization algorithm
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz
• Graph neural network initialisation of quantum approximate optimisation
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Challenges of variational quantum optimization with measurement shot noise
• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
• Lyapunov control-inspired strategies for quantum combinatorial optimization
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
• Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
• Variational counterdiabatic driving of the Hubbard model for ground-state preparation
• Fast Simulation of High-Depth QAOA Circuits
• An evolving objective function for improved variational quantum optimisation
• Provable bounds for noise-free expectation values computed from noisy samples
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• Data re-uploading with a single qudit
• PCA and t-SNE analysis in the study of QAOA entangled and non-entangled mixing operators
• Quantum Dropout: On and Over the Hardness of Quantum Approximate Optimization Algorithm
• Squeezing and quantum approximate optimization
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
• Transfer learning of optimal QAOA parameters in combinatorial optimization
• Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
• Iterative Layerwise Training for Quantum Approximate Optimization Algorithm
• Guided quantum walk
• Performance Analysis of Multi-Angle QAOA for p > 1
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Initial State Encoding via Reverse Quantum Annealing and h-gain Features
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Quantum Approximate Optimization Algorithm Parameter Prediction Using a Convolutional Neural Network
• Realization of programmable Ising models in a trapped-ion quantum simulator
• Bias-field digitized counterdiabatic quantum optimization
• JuliQAOA: Fast, Flexible QAOA Simulation
• Exploring Quantum Average-Case Distances: proofs, properties, and examples
• Improving the performance of quantum approximate optimization for preparing non-trivial quantum states without translational symmetry
• Computing Graph Edit Distance with Algorithms on Quantum Devices
• Beyond Quantum Annealing: Optimal control solutions to MaxCut problems
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Maximising Quantum-Computing Expressive Power through Randomised Circuits
• A Quantum Annealing Protocol to Solve the Nuclear Shell Model
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
• Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Adiabatic quantum computing with parameterized quantum circuits
• Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Dual Map Framework for Noise Characterization of Quantum Computers
• Digital Zero-Noise Extrapolation with Quantum Circuit Unoptimization
• Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models
• Investigating layer-selective transfer learning of QAOA parameters for Max-Cut problem
• Direct entanglement ansatz learning (DEAL) with ZNE on error-prone superconducting qubits
• Hidden local adiabatic ramp in the modulated time evolution and the quantum approximate optimization algorithm
• Light Cone Cancellation for Variational Quantum Eigensolver in Solving Noisy Max-Cut
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems
• Role of overparametrization in quantum approximate optimization
• Counting with the quantum alternating operator ansatz