Amplitude Amplification for Optimization via Subdivided Phase Oracle
arXiv:2205.00602 · doi:10.1109/QCE53715.2022.00020
Abstract
We propose an algorithm using a modified variant of amplitude amplification to solve combinatorial optimization problems via the use of a subdivided phase oracle. Instead of dividing input states into two groups and shifting the phase equally for all states within the same group, the subdivided phase oracle changes the phase of each input state uniquely in proportion to their objective value. We provide visualization of how amplitudes change after each iteration of applying the subdivided phase oracle followed by conventional Grover diffusion in the complex plane. We then show via numerical simulation that for normal, skew normal, and exponential distribution of objective values, the algorithm can be used to amplify the probability of measuring the optimal solution to a significant degree independent of the search space size. In the case of skew normal and exponential distributions, this probability can be amplified to be close to unity, making our algorithm near deterministic. We then modify our algorithm in order to demonstrate how it can be extended to a broader set of objective value distributions. Finally, we discuss the speedup compared to classical schemes using the query complexity model, and show that our algorithm offers a significant advantage over these classical approaches.
arXiv comment9 pages, 7 figures, comments welcome
References in corpus (23)
- Variational Quantum Algorithms
- Ising formulations of many NP problems
- A Quantum Approximate Optimization Algorithm
- Strengths and Weaknesses of Quantum Computing
- Quantum Amplitude Amplification and Estimation
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Tight bounds on quantum searching
- Spatial search by quantum walk
- Grover Algorithm with zero theoretical failure rate
- A Quantum Algorithm for Finding the Minimum
- Fixed-point quantum search with an optimal number of queries
- A different kind of quantum search
- On Arbitrary Phases in Quantum Amplitude Amplification
- Grover Adaptive Search for Constrained Polynomial Binary Optimization
- Phase matching in quantum searching
- Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution
- Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
- Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations
- Arbitrary phase rotation of the marked state can not be used for Grover's quantum search algorithm
- Variationally Learning Grover's Quantum Search Algorithm
- Subdivided Phase Oracle for NISQ Search Algorithms
- Quantum Amplitude Amplification Operators
- Quantum Algorithms with Fixed Points: The Case of Database Search