Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation

Abstract

We propose GM-QAOA, a variation of the Quantum Alternating Operator Ansatz (QAOA) that uses Grover-like selective phase shift mixing operators. GM-QAOA works on any NP optimization problem for which it is possible to efficiently prepare an equal superposition of all feasible solutions; it is designed to perform particularly well for constraint optimization problems, where not all possible variable assignments are feasible solutions. GM-QAOA has the following features: (i) It is not susceptible to Hamiltonian Simulation error (such as Trotterization errors) as its operators can be implemented exactly using standard gate sets and (ii) Solutions with the same objective value are always sampled with the same amplitude. We illustrate the potential of GM-QAOA on several optimization problem classes: for permutation-based optimization problems such as the Traveling Salesperson Problem, we present an efficient algorithm to prepare a superposition of all possible permutations of $n$ numbers, defined on $O(n^2)$ qubits; for the hard constraint $k$-Vertex-Cover problem, and for an application to Discrete Portfolio Rebalancing, we show that GM-QAOA outperforms existing QAOA approaches.

References in corpus (4)

• Simulating Hamiltonian dynamics with a truncated Taylor series
• Fixed-point quantum search with an optimal number of queries
• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• Ground-state statistics from annealing algorithms: Quantum vs classical approaches

Cited by in corpus (56)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Warm-starting quantum optimization
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Barren Plateaus in Variational Quantum Computing
• Challenges and Opportunities in Quantum Optimization
• 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
• A Divide-and-Conquer Approach to Dicke State Preparation
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• 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
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Scaling Quantum Approximate Optimization on Near-term Hardware
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Sampling on NISQ Devices: "Who's the Fairest One of All?"
• 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
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• PCA and t-SNE analysis in the study of QAOA entangled and non-entangled mixing operators
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• The Quantum Alternating Operator Ansatz for Satisfiability Problems
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Fair Sampling Error Analysis on NISQ Devices
• Performance Analysis of Multi-Angle QAOA for p > 1
• Combinatorial Optimization with Quantum Computers
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• Quantum Speedup of the Dispersion and Codebook Design Problems
• Approximating under the Influence of Quantum Noise and Compute Power
• JuliQAOA: Fast, Flexible QAOA Simulation
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
• Amplitude Amplification for Optimization via Subdivided Phase Oracle
• Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions
• Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
• Quantum Approximate Optimization Algorithm with Sparsified Phase Operator
• Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization
• LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism
• Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Complement Grover's Search Algorithm: An Amplitude Suppression Implementation
• Quick design of feasible tensor networks for constrained combinatorial optimization
• Predict and Conquer: Navigating Algorithm Trade-offs with Quantum Design Automation
• A quantum search method for quadratic and multidimensional knapsack problems
• Counting with the quantum alternating operator ansatz
• Feed-Forward Probabilistic Error Cancellation with Noisy Recovery Gates
• Quantum tree generator improves QAOA state-of-the-art for the knapsack problem
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems
• Multiclass Portfolio Optimization via Variational Quantum Eigensolver with Dicke State Ansatz