The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover

Abstract

The Quantum Alternating Operator Ansatz is a generalization of the Quantum Approximate Optimization Algorithm (QAOA) designed for finding approximate solutions to combinatorial optimization problems with hard constraints. In this paper, we study Maximum $k$-Vertex Cover under this ansatz due to its modest complexity, while still being more complex than the well studied problems of Max-Cut and Max E3-LIN2. Our approach includes (i) a performance comparison between easy-to-prepare classical states and Dicke states as starting states, (ii) a performance comparison between two $XY$-Hamiltonian mixing operators: the ring mixer and the complete graph mixer, (iii) an analysis of the distribution of solutions via Monte Carlo sampling, and (iv) the exploration of efficient angle selection strategies. Our results are: (i) Dicke states improve performance compared to easy-to-prepare classical states, (ii) an upper bound on the simulation of the complete graph mixer, (iii) the complete graph mixer improves performance relative to the ring mixer, (iv) numerical results indicating the standard deviation of the distribution of solutions decreases exponentially in $p$ (the number of rounds in the algorithm), requiring an exponential number of random samples to find a better solution in the next round, and (v) a correlation of angle parameters which exhibit high quality solutions that behave similarly to a discretized version of the Quantum Adiabatic Algorithm.

References in corpus (14)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• 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 Algorithm for MaxCut: A Fermionic View
• Fixed-point quantum search with an optimal number of queries
• A different kind of quantum search
• $XY$-mixers: analytical and numerical results for QAOA
• Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
• Reachability Deficits in Quantum Approximate Optimization
• Efficient quantum algorithms for $GHZ$ and $W$ states, and implementation on the IBM quantum computer
• Deterministic Preparation of Dicke States
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Efficient quantum algorithm for preparing molecular-system-like states on a quantum computer
• Finding cliques by quantum adiabatic evolution

Cited by in corpus (32)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Challenges and Opportunities in Quantum Optimization
• Quantum Algorithm Implementations for Beginners
• Benchmarking the performance of portfolio optimization with QAOA
• Quantum walk-based portfolio optimisation
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
• Constrained mixers for the quantum approximate optimization algorithm
• A Divide-and-Conquer Approach to Dicke State Preparation
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Fast-forwarding quantum evolution
• Short-Depth Circuits for Dicke State Preparation
• Constrained Optimization via Quantum Zeno Dynamics
• Comparative study of variations in quantum approximate optimization algorithms for the Traveling Salesman Problem
• Scaling Quantum Approximate Optimization on Near-term Hardware
• State preparation by shallow circuits using feed forward
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Threshold-Based Quantum Optimization
• Provable bounds for noise-free expectation values computed from noisy samples
• Simulations of Frustrated Ising Hamiltonians with Quantum Approximate Optimization
• The Quantum Alternating Operator Ansatz for Satisfiability Problems
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• Fair Sampling Error Analysis on NISQ Devices
• Parity Quantum Optimization: Encoding Constraints
• Quantum Speedup of the Dispersion and Codebook Design Problems
• Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimization
• Efficient preparation of Dicke states
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems
• Light Cone Cancellation for Variational Quantum Eigensolver in Solving Noisy Max-Cut
• Multiclass Portfolio Optimization via Variational Quantum Eigensolver with Dicke State Ansatz