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.

10 pages, 9 figures; typos corrected, references added

References in corpus (10)

• The density-matrix renormalization group in the age of matrix product states
• A Quantum Approximate Optimization Algorithm
• The power of quantum neural networks
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Warm-starting quantum optimization
• MAXCUT QAOA performance guarantees for p >1
• Observation of separated dynamics of charge and spin in the Fermi-Hubbard model
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• 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 (69)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• 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
• Fast Simulation of High-Depth QAOA Circuits
• An evolving objective function for improved variational quantum optimisation
• Variational counterdiabatic driving of the Hubbard model for ground-state preparation
• Provable bounds for noise-free expectation values computed from noisy samples
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• 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
• Data re-uploading with a single qudit
• 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
• Guided quantum walk
• Iterative Layerwise Training for Quantum Approximate Optimization Algorithm
• Performance Analysis of Multi-Angle QAOA for p > 1
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm Parameter Prediction Using a Convolutional Neural Network
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Initial State Encoding via Reverse Quantum Annealing and h-gain Features
• 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
• Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
• A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
• Adiabatic quantum computing with parameterized quantum circuits
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
• Dual Map Framework for Noise Characterization of Quantum Computers
• Digital Zero-Noise Extrapolation with Quantum Circuit Unoptimization
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Light Cone Cancellation for Variational Quantum Eigensolver in Solving Noisy Max-Cut
• Direct entanglement ansatz learning (DEAL) with ZNE on error-prone superconducting qubits
• Role of overparametrization in quantum approximate optimization
• Hidden local adiabatic ramp in the modulated time evolution and the quantum approximate optimization algorithm
• Counting with the quantum alternating operator ansatz
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems
• Investigating layer-selective transfer learning of QAOA parameters for Max-Cut problem