Quantum Physics
[Submitted on 2 May 2022]
Title:Amplitude Amplification for Optimization via Subdivided Phase Oracle
View PDFAbstract: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.
Submission history
From: Naphan Benchasattabuse [view email][v1] Mon, 2 May 2022 01:14:27 UTC (1,479 KB)
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
Connected Papers (What is Connected Papers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.