Threshold-Based Quantum Optimization
arXiv:2106.13860 · doi:10.1109/QCE52317.2021.00030
Abstract
We propose and study Th-QAOA (pronounced Threshold QAOA), a variation of the Quantum Alternating Operator Ansatz (QAOA) that replaces the standard phase separator operator, which encodes the objective function, with a threshold function that returns a value for solutions with an objective value above the threshold and a otherwise. We vary the threshold value to arrive at a quantum optimization algorithm. We focus on a combination with the Grover Mixer operator; the resulting GM-Th-QAOA can be viewed as a generalization of Grover's quantum search algorithm and its minimum/maximum finding cousin to approximate optimization. Our main findings include: (i) we provide intuitive arguments and show empirically that the optimum parameter values of GM-Th-QAOA (angles and threshold value) can be found with iterations of the classical outer loop, where is the number of QAOA rounds and is an upper bound on the solution value (often the number of vertices or edges in an input graph), thus eliminating the notorious outer-loop parameter finding issue of other QAOA algorithms; (ii) GM-Th-QAOA can be simulated classically with little effort up to 100 qubits through a set of tricks that cut down memory requirements; (iii) somewhat surprisingly, GM-Th-QAOA outperforms non-thresholded GM-QAOA in terms of approximation ratios achieved. This third result holds across a range of optimization problems (MaxCut, Max k-VertexCover, Max k-DensestSubgraph, MaxBisection) and various experimental design parameters, such as different input edge densities and constraint sizes.
arXiv commentV2
References in corpus (19)
- A Quantum Approximate Optimization Algorithm
- Strengths and Weaknesses of Quantum Computing
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Tight bounds on quantum searching
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Grover's quantum searching algorithm is optimal
- Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
- A Quantum Algorithm for Finding the Minimum
- Fixed-point quantum search with an optimal number of queries
- A different kind of quantum search
- -mixers: analytical and numerical results for QAOA
- Reachability Deficits in Quantum Approximate Optimization
- 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
- Deterministic Preparation of Dicke States
- Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
- Variationally Learning Grover's Quantum Search Algorithm
- The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
- Reinforcement-Learning-Based Variational Quantum Circuits Optimization for Combinatorial Problems
Cited by in corpus (6)
- A Divide-and-Conquer Approach to Dicke State Preparation
- Short-Depth Circuits for Dicke State Preparation
- Constrained Optimization via Quantum Zeno Dynamics
- Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
- The Quantum Alternating Operator Ansatz for Satisfiability Problems
- Symmetry-based quantum algorithms for open-shop scheduling with hard constraints