Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2112.08167 · Entropy

Gaussian Amplitude Amplification for Quantum Pathfinding

Daniel Koch, Massimiliano Cutugno, Samuel Karlson, Saahil Patel, Laura Wessing, Paul M. Alsing

Published Jul 11, 2022• 1 citation
arXivHTMLPDF

Abstract

We study an oracle operation, along with its circuit design, which combined with the Grover diffusion operator boosts the probability of finding the minimum or maximum solutions on a weighted directed graph. We focus on the geometry of sequentially connected bipartite graphs, which naturally gives rise to solution spaces describable by Gaussian distributions. We then demonstrate how an oracle that encodes these distributions can be used to solve for the optimal path via amplitude amplification. And finally, we explore the degree to which this algorithm is capable of solving cases that are generated using randomized weights, as well as a theoretical application for solving the Traveling Salesman problem.

DOI
10.3390/e24070963

Related papers

Variational Amplitude Amplification for Solving QUBO Problems

Daniel Koch, Massimiliano Cutugno, Saahil Patel +2 more

We investigate the use of amplitude amplification on the gate-based model of quantum computing as a means for solving combinatorial optimization problems. This study focuses primarily on quadratic unconstrained binary optimization (QUBO) problems, which are well-suited for qubit superposition states. Specifically, we demonstrate circuit designs which encode QUBOs as ‘cost oracle’ operations UC, which distribute phases across the basis states proportional to a cost function. We then show that when UC is combined with the standard Grover diffusion operator Us, one can achieve high probabilities of measurement for states corresponding to optimal and near optimal solutions while still only requiring O(π42N/M) iterations. In order to achieve these probabilities, a single scalar parameter ps is required, which we show can be found through a variational quantum–classical hybrid approach and can be used for heuristic solutions.

arXiv:2301.13665•Quantum Reports•Oct 1, 2023•9 citations

Analysis and Experimental Demonstration of Amplitude Amplification for Combinatorial Optimization

Daniel Koch, Brian Pardo, Kip Nieman

Quantum Amplitude Amplification (QAA), the generalization of Grover's algorithm, is capable of yielding optimal solutions to combinatorial optimization problems with high probabilities. In this work we extend the conventional 2-dimensional representation of Grover's (orthogonal collective states) to oracles which encode cost functions such as QUBO, and show that linear cost functions are a special case whereby an exact formula exists for determining optimal oracle parameter settings. Using simulations of problem sizes up to 40 qubits we demonstrate QAA's algorithmic performance across all possible solutions, with an emphasis on the closeness in Grover-like performance for solutions near the global optimum. We conclude with experimental demonstrations of generalized QAA on both IBMQ (superconducting) and IonQ (trapped ion) qubits, showing that the observed probabilities of each basis state match our equations as a function of varying the free parameters in the oracle and diffusion operators.

quant-pharXiv:2601.10473•Jan 16, 2026•0 citations

Amplitude Amplification for Optimization via Subdivided Phase Oracle

Naphan Benchasattabuse, Takahiko Satoh, Michal Hajdušek +1 more

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:2205.00602•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•10 citations

Application of Grover’s Algorithm in Route Optimization

Vladimir Anatolievich Bogatyrev, V. S. Moskvin

Route determination and optimization is a persistent challenge in transportation networks due to combinatorial explosion of options, dynamically changing conditions, competing optimization criteria, and complexity of real-world systems. Classical algorithms struggle to efficiently solve route optimization at scale due to exponential growth of possibilities, NP-hardness, limitations of dynamic programming approaches, and inability to leverage quantum parallelism. This paper explores the potential application of Grover’s algorithm in optimizing road transportation. Grover’s quantum algorithm offers a potential solution by using an oracle function to recognize optimal routes based on constraints and objectives encoded in a quantum state representing all possible paths. Constructive interference and amplitude amplification drive the system toward optimal solutions. By utilizing Grover’s algorithm, road transportation networks can benefit from improved route planning, traffic management, and resource allocation, ultimately enhancing efficiency and reducing congestion. The transportation network must be efficiently encoded into a quantum representation. An optimization oracle tailored to routing objectives then recognizes optimal solutions, which are amplified via a diffusion operator utilizing interference. Repeated application concentrates amplitude in optimal routes, which can be measured. Key challenges include encoding the network effectively within qubit resource constraints, designing an oracle to evaluate routes based on real-world conditions and optimization criteria, and translating the optimized quantum state into actionable routing guidance. If these challenges can be met, Grover’s algorithm may enable route optimization at a scale intractable for classical techniques.

Intelligent Technologies and Electronic Devices in Vehicle and Road Transport Complex (TIRVED)•Nov 15, 2023•7 citations

Quantum DNA Sequencing using Gaussian Amplitude Amplification

Richard Marin, Carlos Baldo

In this study, we explore how quantum pathfinding algorithm called Gaussian Amplitude Amplification (GAA) can be used to solve the DNA sequencing problem. To do this, sequencing by hybridization was assumed wherein short fragments of the nucleic acids called oligonucleotides of length l were gathered and were then assembled. The process of reassembling the sequence was then abstracted into a graph problem of finding the Hamiltonian path with the least cost. The constructed directed graph was then converted into sequential bipartite graphs in order to use GAA. The results of our simulation revealed that for the case where l = 2 and spectrum size of |S| = 4, the probability of finding the optimal solution (with the least cost) is approximately 70.92% - a significant improvement compared to 4.17% when the path is chosen randomly. While this study only focused on the ideal scenario where there are no errors in the spectrum, the outcomes presented here demonstrate the plausibility of using GAA as a genome sequencing method.

arXiv:2310.20466•Oct 31, 2023•0 citations

A Quantum Framework for Combinatorial Optimization Problem over Graphs

Meng Shi, Sai Wu, Ying Li +3 more

Abstract Combinatorial optimization problems over graphs, such as the traveling salesman problem, longest path problem, and maximum independent set problem, are well-known for being computationally costly, some even NP-hard problems. In this paper, we propose a general quantum algorithm framework searching for approximate solutions to combinatorial optimization problems with linear objective functions. Our framework provides APIs (application programming interfaces) that enable developers to encode weighted graph structures onto quantum circuits and utilize variational algorithms to generate approximate solutions. One key advantage of our framework is that it allows developers to design new graph algorithms for the graph problem represented as linear combinations of edge weights without requiring expertise in quantum programming. Besides, it only uses a logarithmic level of quantum bit scale, making our framework work on quantum computers with limited physical resources. Our experimental results demonstrate that our framework can provide good approximations for the traveling salesman problem compared to current quantum algorithm.

Data Science and Engineering•Jan 24, 2025•4 citations
We study an oracle operation, along with its circuit design, which combined with the Grover diffusion operator boosts the probability of finding the minimum or maximum solutions on a weighted directed graph. We focus on the geometry of sequentially connected bipartite graphs, which naturally gives rise to solution spaces describable by Gaussian distributions. We then demonstrate how an oracle that encodes these distributions can be used to solve for the optimal path via amplitude amplification. And finally, we explore the degree to which this algorithm is capable of solving cases that are generated using randomized weights, as well as a theoretical application for solving the Traveling Salesman problem.
We investigate the use of amplitude amplification on the gate-based model of quantum computing as a means for solving combinatorial optimization problems. This study focuses primarily on quadratic unconstrained binary optimization (QUBO) problems, which are well-suited for qubit superposition states. Specifically, we demonstrate circuit designs which encode QUBOs as ‘cost oracle’ operations UC, which distribute phases across the basis states proportional to a cost function. We then show that when UC is combined with the standard Grover diffusion operator Us, one can achieve high probabilities of measurement for states corresponding to optimal and near optimal solutions while still only requiring O(π42N/M) iterations. In order to achieve these probabilities, a single scalar parameter ps is required, which we show can be found through a variational quantum–classical hybrid approach and can be used for heuristic solutions.
Quantum Amplitude Amplification (QAA), the generalization of Grover's algorithm, is capable of yielding optimal solutions to combinatorial optimization problems with high probabilities. In this work we extend the conventional 2-dimensional representation of Grover's (orthogonal collective states) to oracles which encode cost functions such as QUBO, and show that linear cost functions are a special case whereby an exact formula exists for determining optimal oracle parameter settings. Using simulations of problem sizes up to 40 qubits we demonstrate QAA's algorithmic performance across all possible solutions, with an emphasis on the closeness in Grover-like performance for solutions near the global optimum. We conclude with experimental demonstrations of generalized QAA on both IBMQ (superconducting) and IonQ (trapped ion) qubits, showing that the observed probabilities of each basis state match our equations as a function of varying the free parameters in the oracle and diffusion operators.
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.
Route determination and optimization is a persistent challenge in transportation networks due to combinatorial explosion of options, dynamically changing conditions, competing optimization criteria, and complexity of real-world systems. Classical algorithms struggle to efficiently solve route optimization at scale due to exponential growth of possibilities, NP-hardness, limitations of dynamic programming approaches, and inability to leverage quantum parallelism. This paper explores the potential application of Grover’s algorithm in optimizing road transportation. Grover’s quantum algorithm offers a potential solution by using an oracle function to recognize optimal routes based on constraints and objectives encoded in a quantum state representing all possible paths. Constructive interference and amplitude amplification drive the system toward optimal solutions. By utilizing Grover’s algorithm, road transportation networks can benefit from improved route planning, traffic management, and resource allocation, ultimately enhancing efficiency and reducing congestion. The transportation network must be efficiently encoded into a quantum representation. An optimization oracle tailored to routing objectives then recognizes optimal solutions, which are amplified via a diffusion operator utilizing interference. Repeated application concentrates amplitude in optimal routes, which can be measured. Key challenges include encoding the network effectively within qubit resource constraints, designing an oracle to evaluate routes based on real-world conditions and optimization criteria, and translating the optimized quantum state into actionable routing guidance. If these challenges can be met, Grover’s algorithm may enable route optimization at a scale intractable for classical techniques.
In this study, we explore how quantum pathfinding algorithm called Gaussian Amplitude Amplification (GAA) can be used to solve the DNA sequencing problem. To do this, sequencing by hybridization was assumed wherein short fragments of the nucleic acids called oligonucleotides of length l were gathered and were then assembled. The process of reassembling the sequence was then abstracted into a graph problem of finding the Hamiltonian path with the least cost. The constructed directed graph was then converted into sequential bipartite graphs in order to use GAA. The results of our simulation revealed that for the case where l = 2 and spectrum size of |S| = 4, the probability of finding the optimal solution (with the least cost) is approximately 70.92% - a significant improvement compared to 4.17% when the path is chosen randomly. While this study only focused on the ideal scenario where there are no errors in the spectrum, the outcomes presented here demonstrate the plausibility of using GAA as a genome sequencing method.
Abstract Combinatorial optimization problems over graphs, such as the traveling salesman problem, longest path problem, and maximum independent set problem, are well-known for being computationally costly, some even NP-hard problems. In this paper, we propose a general quantum algorithm framework searching for approximate solutions to combinatorial optimization problems with linear objective functions. Our framework provides APIs (application programming interfaces) that enable developers to encode weighted graph structures onto quantum circuits and utilize variational algorithms to generate approximate solutions. One key advantage of our framework is that it allows developers to design new graph algorithms for the graph problem represented as linear combinations of edge weights without requiring expertise in quantum programming. Besides, it only uses a logarithmic level of quantum bit scale, making our framework work on quantum computers with limited physical resources. Our experimental results demonstrate that our framework can provide good approximations for the traveling salesman problem compared to current quantum algorithm.