Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View

Abstract

Farhi et al. recently proposed a class of quantum algorithms, the Quantum Approximate Optimization Algorithm (QAOA), for approximately solving combinatorial optimization problems. A level-p QAOA circuit consists of p steps; in each step a classical Hamiltonian, derived from the cost function, is applied followed by a mixing Hamiltonian. The 2p times for which these two Hamiltonians are applied are the parameters of the algorithm, which are to be optimized classically for the best performance. As p increases, parameter optimization becomes inefficient due to the curse of dimensionality. The success of the QAOA approach will depend, in part, on finding effective parameter-setting strategies. Here, we analytically and numerically study parameter setting for QAOA applied to MaxCut. For level-1 QAOA, we derive an analytical expression for a general graph. In principle, expressions for higher p could be derived, but the number of terms quickly becomes prohibitive. For a special case of MaxCut, the ring of disagrees, or the 1D antiferromagnetic ring, we provide an analysis for arbitrarily high level. Using a fermionic representation, the evolution of the system under QAOA translates into quantum control of an ensemble of independent spins. This treatment enables us to obtain analytical expressions for the performance of QAOA for any p. It also greatly simplifies numerical search for the optimal values of the parameters. By exploring symmetries, we identify a lower-dimensional sub-manifold of interest; the search effort can be accordingly reduced. This analysis also explains an observed symmetry in the optimal parameter values. Further, we numerically investigate the parameter landscape and show that it is a simple one in the sense of having no local optima.

arXiv commentCorrection: A missing factor of 2 in Eq. (14) of Theorem 1 has been inserted, and a sign error in Eq. (A11) has been fixed

References in corpus (12)

• A Quantum Approximate Optimization Algorithm
• Characterizing Quantum Supremacy in Near-Term Devices
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Quantum computing and the entanglement frontier
• Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Training A Quantum Optimizer
• Singularities of Quantum Control Landscapes
• The role of controllability in optimizing quantum dynamics
• Quantum Control Landscapes Are Almost Always Trap Free

Cited by in corpus (170)

• Variational Quantum Algorithms
• Barren plateaus in quantum neural network training landscapes
• Noisy intermediate-scale quantum (NISQ) algorithms
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Layerwise learning for quantum neural networks
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• General parameter-shift rules for quantum gradients
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Warm-starting quantum optimization
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Variational Quantum Linear Solver
• $XY$-mixers: analytical and numerical results for QAOA
• A Tutorial on Formulating and Using QUBO Models
• Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer
• Reachability Deficits in Quantum Approximate Optimization
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
• Variational Thermal Quantum Simulation via Thermofield Double States
• Efficient variational simulation of non-trivial quantum states
• Quantum Algorithm Implementations for Beginners
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Benchmarking the Quantum Approximate Optimization Algorithm
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• MAXCUT QAOA performance guarantees for p >1
• Implementation of the XY interaction family with calibration of a single pulse
• From pulses to circuits and back again: A quantum optimal control perspective on variational quantum algorithms
• Classical Optimizers for Noisy Intermediate-Scale Quantum Devices
• Hybrid quantum-classical algorithms for approximate graph coloring
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Multistart Methods for Quantum Approximate Optimization
• Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
• On the Universality of the Quantum Approximate Optimization Algorithm
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Implementation of quantum imaginary-time evolution method on NISQ devices: Nonlocal approximation
• Minimizing estimation runtime on noisy quantum computers
• Fast quantum circuit cutting with randomized measurements
• Reinforcement Learning assisted Quantum Optimization
• Learning quantum data with the quantum Earth Mover's distance
• Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Empirical performance bounds for quantum approximate optimization
• Network Community Detection On Small Quantum Computers
• Variationally Learning Grover's Quantum Search Algorithm
• Multilevel Combinatorial Optimization Across Quantum Architectures
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• Noise-Resilient Variational Hybrid Quantum-Classical Optimization
• Robust resource-efficient quantum variational ansatz through evolutionary algorithm
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Low depth mechanisms for quantum optimization
• Evaluating Quantum Approximate Optimization Algorithm: A Case Study
• Can Error Mitigation Improve Trainability of Noisy Variational Quantum Algorithms?
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• Evaluation of QAOA based on the approximation ratio of individual samples
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
• Making Trotters Sprint: A Variational Imaginary Time Ansatz for Quantum Many-body Systems
• Scaling Quantum Approximate Optimization on Near-term Hardware
• An entanglement perspective on the quantum approximate optimization algorithm
• Probing many-body localization by excited-state VQE
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Comparison of QAOA with Quantum and Simulated Annealing
• Analytical Framework for Quantum Alternating Operator Ansätze
• Probing Geometric Excitations of Fractional Quantum Hall States on Quantum Computers
• Designing calibration and expressivity-efficient instruction sets for quantum computing
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• On Circuit Depth Scaling For Quantum Approximate Optimization
• Reachability Deficits in Quantum Approximate Optimization of Graph Problems
• An evolving objective function for improved variational quantum optimisation
• Quantifying the efficiency of state preparation via quantum variational eigensolvers
• Improving Quantum Computation by Optimized Qubit Routing
• Approaches to Constrained Quantum Approximate Optimization
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture
• Evaluation of Parameterized Quantum Circuits with Cross-Resonance Pulse-Driven Entanglers
• Threshold-Based Quantum Optimization
• Entanglement Production and Convergence Properties of the Variational Quantum Eigensolver
• Calibrating the role of entanglement in variational quantum circuits
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• Optimizing Ansatz Design in QAOA for Max-cut
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Extending relax-and-round combinatorial optimization solvers with quantum correlations
• Quantum Dropout: On and Over the Hardness of Quantum Approximate Optimization Algorithm
• Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs
• PCA and t-SNE analysis in the study of QAOA entangled and non-entangled mixing operators
• Practical Verification of Quantum Properties in Quantum Approximate Optimization Runs
• Many-body localization enables iterative quantum optimization
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
• Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design
• Knapsack Problem variants of QAOA for battery revenue optimisation
• What do QAOA energies reveal about graphs?
• Variational quantum Gibbs state preparation with a truncated Taylor series
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth
• Beyond unital noise in variational quantum algorithms: noise-induced barren plateaus and limit sets
• Dynamic-ADAPT-QAOA: An algorithm with shallow and noise-resilient circuits
• Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem
• Performance Analysis of Multi-Angle QAOA for p > 1
• Quantum computing through the lens of control: A tutorial introduction
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Variational quantum eigensolver with linear depth problem-inspired ansatz for solving portfolio optimization in finance
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• Symmetry-informed transferability of optimal parameters in the Quantum Approximate Optimization Algorithm
• Reinforcement-Learning-Based Variational Quantum Circuits Optimization for Combinatorial Problems
• Automatic Depth Optimization for Quantum Approximate Optimization Algorithm
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Adaptive projected variational quantum dynamics
• Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size
• Collective dynamics of phase-repulsive oscillators solves graph coloring problem
• Characterization of variational quantum algorithms using free fermions
• Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimization
• Quantum Error Mitigation via Quantum-Noise-Effect Circuit Groups
• Towards Optimizations of Quantum Circuit Simulation for Solving Max-Cut Problems with QAOA
• Recursive Quantum Relaxation for Combinatorial Optimization Problems
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Ion native variational ansatz for quantum approximate optimization
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Hybrid quantum-classical unsupervised data clustering based on the self-organizing feature map
• Forbidden subspaces for level-1 QAOA and IQP circuits
• Graph Cut Segmentation Methods Revisited with a Quantum Algorithm
• Rapid quantum approaches for combinatorial optimisation inspired by optimal state-transfer
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Maximising Quantum-Computing Expressive Power through Randomised Circuits
• Quantum approximate optimization algorithm with random and subgraph phase operators
• Random Natural Gradient
• Red-QAOA: Efficient Variational Optimization through Circuit Reduction
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Quantum circuit compilation with quantum computers
• Diagrammatic Analysis for Parameterized Quantum Circuits
• Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization
• A framework for optimal quantum spatial search using alternating phase-walks
• Optimally Stopped Variational Quantum Algorithms
• HybridQ: A Hybrid Simulator for Quantum Circuits
• QForte: an efficient state simulator and quantum algorithms library for molecular electronic structure
• An explicit vector algorithm for high-girth MaxCut
• A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
• A Novel Noise-Aware Classical Optimizer for Variational Quantum Algorithms
• Crosstalk-Based Parameterized Quantum Circuit Approximation
• Adiabatic quantum computing with parameterized quantum circuits
• Quantum Approximation for Wireless Scheduling
• On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA
• Evolved Quantum Boltzmann Machines
• Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers
• Quantum Scheduling for Millimeter-Wave Observation Satellite Constellation
• Lower Bounds on Circuit Depth of the Quantum Approximate Optimization Algorithm
• Variational quantum algorithms with invariant probabilistic error cancellation on noisy quantum processors
• Digital Zero-Noise Extrapolation with Quantum Circuit Unoptimization
• A Noise-Aware Scalable Subspace Classical Optimizer for the Quantum Approximate Optimization Algorithm
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles
• Mitigating Noise-Induced Gradient Vanishing in Variational Quantum Algorithm Training
• Simulating Quantum Circuits with Tree Tensor Networks using Density-Matrix Renormalization Group Algorithm
• Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem
• Exploring Entanglement and Parameter Sensitivity in QAOA through Quantum Fisher Information
• Interference and Measurement: Changing amplitude phase information to amplitude magnitude information
• An Analysis of the Quantum Approximation Optimisation Algorithm
• Role of overparametrization in quantum approximate optimization
• Investigating layer-selective transfer learning of QAOA parameters for Max-Cut problem
• A Quantum Genetic Algorithm with application to Cosmological Parameters Estimation
• Classical algorithms for Forrelation