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

A guide on Grover search algorithms for solving QUBO problems

Jannes Weghake, Freyja Ullinger, Matthias Zimmermann

Published Mar 5, 2026• 0 citations
OpenAlex

Abstract

Typical industry-related optimizations, like routing, packing, or scheduling, can be reformulated as a quadratic unconstrained binary optimization (QUBO) problem [1]. In the fault-tolerant quantum computing era, a promising approach to solve these problems is the Grover Adaptive Search [2]. The Grover Adaptive Search is able to solve QUBOs with a quadratic speed-up in comparison to classical algorithms. Here different Grover runs are chained together in order to identify the optimal solution. In this poster, we present a comprehensive guide with intuitive visuals, a theoretical background and a walkthrough to help non-expert to apply the Grover Adaptive Search. In particular, we demonstrate how to parse the QUBOs into a Grover oracle - the quantum dictionary [3] - and what this implies for the different quantum registers involved. [1] G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. Lü, H. Wang, and Y. Wang, J. Comb. Optim. 28, 58 (2014). [2] W. P. Baritompa, D. W. Bulger, and G. R. Wood, SIAM J. Optim. 15, 1170 (2005). [3] A. Gilliam, C. Venci, S. Muralidharan, V. Dorum, E. May, R. Narasimhan, and C. Gonciulea, arXiv:1907.11513 (2019).

Related papers

Engineering Grover Adaptive Search: Exploring the Degrees of Freedom for Efficient QUBO Solving

Luigi Giuffrida, Deborah Volpe, Giovanni Amedeo Cirillo +2 more

Quantum computers have the potential to solve Quadratic Unconstrained Binary Optimization (QUBO) problems with lower computational complexity than classical ones. Considering the current limitations of quantum hardware, the joint use of classical and quantum paradigms could exploit both advantages. Quantum routines can make some complex tasks for classical computers feasible. For example, in the Grover Adaptive Search (GAS) procedure, the problem cost function is classically shifted iteratively, whenever a negative value is found through the quantum Grover Search (GS) algorithm, until the minimum is achieved. This quantum-classical approach is characterized by many degrees of freedom, e.g. the number of GS iterations in each call and the stop condition of the algorithm, which should be appropriately tuned for an effective and fast convergence to the optimal solution. The availability of software routines could permit the best management of the GAS parameters. This work proposes new mechanisms for GAS parameters management and compares them with the existing ones, like one available in the Qiskit framework. The proposed mechanisms can automatically arrange the parameters according to the algorithm evolution and their previous experience, thus ensuring a more frequent and faster achievement of the optimal solution. Even though these strategies can be further improved, the results are encouraging. The analysis is done to identify the best policy for different problems. It lays the foundation for designing an automatic toolchain for QUBO solving, which can obtain the best possible implementation of the GAS algorithm for each submitted problem.

IEEE Journal on Emerging and Selected Topics in Circuits and Systems•Aug 29, 2022•16 citations

Fixed-Point Grover Adaptive Search for Quadratic Binary Optimization Problems

Ákos Nagy, Jaime Park, Cindy Zhang +2 more

In this article, we study a Grover-type method for quadratic unconstrained binary optimization (QUBO) problems. For an$n$-dimensional QUBO problem with$m$nonzero terms, we construct a marker oracle for such problems with a tunable parameter,$\Lambda \in [ 1, m ] \cap \mathbb {Z}$. At$d \in \mathbb {Z}_+$precision, the oracle uses$O (n + \Lambda d)$qubits and has total depth of$O (\frac{m}{\Lambda } \log _{2} (n) + \log _{2} (d))$and a non-Clifford depth of$O (\frac{m}{\Lambda })$. Moreover, each qubit is required to be connected to at most$O (\log _{2} (\Lambda + d))$other qubits. In the case of a maximum graph cuts, as$d = 2 \left\lceil \log _{2} (n) \right\rceil$always suffices, the depth of the marker oracle can be made as shallow as$O (\log _{2} (n))$. For all values of$\Lambda$, the non-Clifford gate count of these oracles is strictly lower (at least by a factor of$\sim 2$) than previous constructions. Furthermore, we introduce a novel fixed-point Grover adaptive search for QUBO problems, using our oracle design and a hybrid fixed-point Grover search, motivated by the works of Boyer et al. (1988) and Li et al. (2019). This method has better performance guarantees than previous Grover adaptive search methods. Some of our results are novel and useful for any method based on the fixed-point Grover search. Finally, we give a heuristic argument that, with high probability and in$O (\frac{\log _{2} (n)}{\sqrt{\epsilon }})$time, this adaptive method finds a configuration that is among the best$\epsilon 2^{n}$ones.

arXiv:2311.05592•IEEE Transactions on Quantum Engineering•Jan 1, 2024•3 citations

Grover Adaptive Search for Constrained Polynomial Binary Optimization

Austin Gilliam, Stefan Woerner, Constantin Gonciulea

In this paper we discuss Grover Adaptive Search (GAS) for Constrained Polynomial Binary Optimization (CPBO) problems, and in particular, Quadratic Unconstrained Binary Optimization (QUBO) problems, as a special case. GAS can provide a quadratic speed-up for combinatorial optimization problems compared to brute force search. However, this requires the development of efficient oracles to represent problems and flag states that satisfy certain search criteria. In general, this can be achieved using quantum arithmetic, however, this is expensive in terms of Toffoli gates as well as required ancilla qubits, which can be prohibitive in the near-term. Within this work, we develop a way to construct efficient oracles to solve CPBO problems using GAS algorithms. We demonstrate this approach and the potential speed-up for the portfolio optimization problem, i.e. a QUBO, using simulation and experimental results obtained on real quantum hardware. However, our approach applies to higher-degree polynomial objective functions as well as constrained optimization problems.

arXiv:1912.04088•Quantum•Apr 8, 2021•154 citations

Practical Guide to Quantum Computing: Grover's Algorithm # 4

Mikhail Pavlov

Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.

•Mar 4, 2026•0 citations

A Review of Grover's Search Algorithm: Applications and Modifications

Ela Demirci, Emre Atlıer Olca

This study investigates the applications and adaptations of the Grover's search algorithm, an algorithm that uses quantum technologies to provide quadratic speedup while searching unsorted data. Through extensive literature review, the applications of Grover's algorithm such as database search, machine learning, cryptography, and optimization is explored in order to further understand areas open to alteration in the algorithm. Visuals are provided with the aim of enhancing the comprehension of Grover's algorithm. This study underscores how various components of Grover's search-like the oracle, diffusion operator, and iteration count-can be modified to solve complex problems more efficiently than classical search algorithms. A table generalizing aspects of modification and each of their benefits is given as an output. The growing importance of quantum technologies and the United Nations' selection of 2025 as the International Year of Quantum Science and Technology makes this research timely.

International Artificial Intelligence and Data Processing Symposium (IDAP)•Sep 6, 2025•3 citations

Leveraging qudits: high-dimensional Grover adaptive search algorithm for solving quadratic and higher-order unconstrained binary optimization problems

Sabri Gündüz, İhsan Yılmaz

Abstract The Grover Adaptive Search (GAS) is an innovative approach offering solutions to optimization problems thanks to quadratic speedup enabled by the Grover Search Algorithm. However, the need for more qubits, depending on the number of variables in optimization problems, creates problems in providing optimal solutions. The central premise of this study is the principle that d -dimension is more efficient than 2-dimension could lead to more advantageous results when the GAS algorithm is adapted to d -dimension. To that end, this study adapts the GAS algorithm to the d -dimension drawing on quantum computing in the d -dimension, allowing computing using fewer quantum resources, namely, qudits. The proposed algorithm is validated against the Quadratic and Higher-Order Unconstrained Binary Optimization (QUBO-HUBO). This study concludes the d -dimensional GAS algorithm achieves solutions using fewer qudits for these problems in the QUBO and the HUBO. This study underscores the progress achieved in the advancement of high-dimensional quantum computing.

The European Physical Journal Plus•Apr 2, 2026•0 citations
Typical industry-related optimizations, like routing, packing, or scheduling, can be reformulated as a quadratic unconstrained binary optimization (QUBO) problem [1]. In the fault-tolerant quantum computing era, a promising approach to solve these problems is the Grover Adaptive Search [2]. The Grover Adaptive Search is able to solve QUBOs with a quadratic speed-up in comparison to classical algorithms. Here different Grover runs are chained together in order to identify the optimal solution. In this poster, we present a comprehensive guide with intuitive visuals, a theoretical background and a walkthrough to help non-expert to apply the Grover Adaptive Search. In particular, we demonstrate how to parse the QUBOs into a Grover oracle - the quantum dictionary [3] - and what this implies for the different quantum registers involved. [1] G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. Lü, H. Wang, and Y. Wang, J. Comb. Optim. 28, 58 (2014). [2] W. P. Baritompa, D. W. Bulger, and G. R. Wood, SIAM J. Optim. 15, 1170 (2005). [3] A. Gilliam, C. Venci, S. Muralidharan, V. Dorum, E. May, R. Narasimhan, and C. Gonciulea, arXiv:1907.11513 (2019).
Quantum computers have the potential to solve Quadratic Unconstrained Binary Optimization (QUBO) problems with lower computational complexity than classical ones. Considering the current limitations of quantum hardware, the joint use of classical and quantum paradigms could exploit both advantages. Quantum routines can make some complex tasks for classical computers feasible. For example, in the Grover Adaptive Search (GAS) procedure, the problem cost function is classically shifted iteratively, whenever a negative value is found through the quantum Grover Search (GS) algorithm, until the minimum is achieved. This quantum-classical approach is characterized by many degrees of freedom, e.g. the number of GS iterations in each call and the stop condition of the algorithm, which should be appropriately tuned for an effective and fast convergence to the optimal solution. The availability of software routines could permit the best management of the GAS parameters. This work proposes new mechanisms for GAS parameters management and compares them with the existing ones, like one available in the Qiskit framework. The proposed mechanisms can automatically arrange the parameters according to the algorithm evolution and their previous experience, thus ensuring a more frequent and faster achievement of the optimal solution. Even though these strategies can be further improved, the results are encouraging. The analysis is done to identify the best policy for different problems. It lays the foundation for designing an automatic toolchain for QUBO solving, which can obtain the best possible implementation of the GAS algorithm for each submitted problem.
In this article, we study a Grover-type method for quadratic unconstrained binary optimization (QUBO) problems. For annnn-dimensional QUBO problem withmmmnonzero terms, we construct a marker oracle for such problems with a tunable parameter,Λ∈[1,m]∩Z\Lambda \in [ 1, m ] \cap \mathbb {Z}Λ∈[1,m]∩Z. Atd∈Z+d \in \mathbb {Z}_+d∈Z+​precision, the oracle usesO(n+Λd)O (n + \Lambda d)O(n+Λd)qubits and has total depth ofO(mΛlog⁡2(n)+log⁡2(d))O (\frac{m}{\Lambda } \log _{2} (n) + \log _{2} (d))O(Λm​log2​(n)+log2​(d))and a non-Clifford depth ofO(mΛ)O (\frac{m}{\Lambda })O(Λm​). Moreover, each qubit is required to be connected to at mostO(log⁡2(Λ+d))O (\log _{2} (\Lambda + d))O(log2​(Λ+d))other qubits. In the case of a maximum graph cuts, asd=2⌈log⁡2(n)⌉d = 2 \left\lceil \log _{2} (n) \right\rceild=2⌈log2​(n)⌉always suffices, the depth of the marker oracle can be made as shallow asO(log⁡2(n))O (\log _{2} (n))O(log2​(n)). For all values ofΛ\LambdaΛ, the non-Clifford gate count of these oracles is strictly lower (at least by a factor of∼2\sim 2∼2) than previous constructions. Furthermore, we introduce a novel fixed-point Grover adaptive search for QUBO problems, using our oracle design and a hybrid fixed-point Grover search, motivated by the works of Boyer et al. (1988) and Li et al. (2019). This method has better performance guarantees than previous Grover adaptive search methods. Some of our results are novel and useful for any method based on the fixed-point Grover search. Finally, we give a heuristic argument that, with high probability and inO(log⁡2(n)ϵ)O (\frac{\log _{2} (n)}{\sqrt{\epsilon }})O(ϵ​log2​(n)​)time, this adaptive method finds a configuration that is among the bestϵ2n\epsilon 2^{n}ϵ2nones.
In this paper we discuss Grover Adaptive Search (GAS) for Constrained Polynomial Binary Optimization (CPBO) problems, and in particular, Quadratic Unconstrained Binary Optimization (QUBO) problems, as a special case. GAS can provide a quadratic speed-up for combinatorial optimization problems compared to brute force search. However, this requires the development of efficient oracles to represent problems and flag states that satisfy certain search criteria. In general, this can be achieved using quantum arithmetic, however, this is expensive in terms of Toffoli gates as well as required ancilla qubits, which can be prohibitive in the near-term. Within this work, we develop a way to construct efficient oracles to solve CPBO problems using GAS algorithms. We demonstrate this approach and the potential speed-up for the portfolio optimization problem, i.e. a QUBO, using simulation and experimental results obtained on real quantum hardware. However, our approach applies to higher-degree polynomial objective functions as well as constrained optimization problems.
Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.
This study investigates the applications and adaptations of the Grover's search algorithm, an algorithm that uses quantum technologies to provide quadratic speedup while searching unsorted data. Through extensive literature review, the applications of Grover's algorithm such as database search, machine learning, cryptography, and optimization is explored in order to further understand areas open to alteration in the algorithm. Visuals are provided with the aim of enhancing the comprehension of Grover's algorithm. This study underscores how various components of Grover's search-like the oracle, diffusion operator, and iteration count-can be modified to solve complex problems more efficiently than classical search algorithms. A table generalizing aspects of modification and each of their benefits is given as an output. The growing importance of quantum technologies and the United Nations' selection of 2025 as the International Year of Quantum Science and Technology makes this research timely.
Abstract The Grover Adaptive Search (GAS) is an innovative approach offering solutions to optimization problems thanks to quadratic speedup enabled by the Grover Search Algorithm. However, the need for more qubits, depending on the number of variables in optimization problems, creates problems in providing optimal solutions. The central premise of this study is the principle that d -dimension is more efficient than 2-dimension could lead to more advantageous results when the GAS algorithm is adapted to d -dimension. To that end, this study adapts the GAS algorithm to the d -dimension drawing on quantum computing in the d -dimension, allowing computing using fewer quantum resources, namely, qudits. The proposed algorithm is validated against the Quadratic and Higher-Order Unconstrained Binary Optimization (QUBO-HUBO). This study concludes the d -dimensional GAS algorithm achieves solutions using fewer qudits for these problems in the QUBO and the HUBO. This study underscores the progress achieved in the advancement of high-dimensional quantum computing.