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 (3)

• Fixed-point quantum search with an optimal number of queries
• 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

Cited by in corpus (31)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Challenges and Opportunities in Quantum Optimization
• 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
• Short-Depth Circuits for Dicke State Preparation
• Fast-forwarding quantum evolution
• 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
• Parity Quantum Optimization: Encoding Constraints
• Fair Sampling Error Analysis on NISQ Devices
• 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
• Multiclass Portfolio Optimization via Variational Quantum Eigensolver with Dicke State Ansatz
• Light Cone Cancellation for Variational Quantum Eigensolver in Solving Noisy Max-Cut
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems