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:2311.05592 · IEEE Transactions on Quantum Engineering

Fixed-Point Grover Adaptive Search for Quadratic Binary Optimization Problems

Ákos Nagy, Jaime Park, Cindy Zhang, Atithi Acharya, Alex Khan

Published Jan 1, 2024• 9 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tqe.2024.3484650

Related papers

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•187 citations

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•19 citations

A guide on Grover search algorithms for solving QUBO problems

Jannes Weghake, Freyja Ullinger, Matthias Zimmermann

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).

•Mar 5, 2026•0 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

Grover Adaptive Search for the Higher-Order Formulation of Quadratic Assignment Problems

Taku Mikuriya, Shintaro Fujiwara, Kein Yukiyoshi +2 more

We demonstrate that the search space of the quadratic assignment problem (QAP), known as an NP-hard combinatorial optimization problem, can be reduced using Grover adaptive search (GAS) with permutation preparation operator (PPO). To that end, we first revise the traditional quadratic unconstrained binary optimization (QUBO) formulation of the QAP into a higher-order unconstrained binary optimization (HUBO) formulation, introducing a binary encoding method. Algebraic analyses in terms of the number of qubits, quantum gates, circuit depth, and query complexity are performed, which indicate that our proposed approach significantly reduces the search space size, improving convergence performance to the optimal solution compared to the conventional one. Furthermore, although the PPO for HUBO has a greater circuit depth than the PPO for QUBO, when the analysis is extended to the entire state preparation operator, both HUBO and QUBO exhibit comparable depths. Therefore, owing to its smaller number of variables, HUBO can be concluded to be more effective.

arXiv:2410.12181•Oct 16, 2024•3 citations

Quantum Grover Adaptive Search for Discrete Simulation Optimization

Mingjie Hu, Jian-qiang Hu, Enlu Zhou

Quantum computing has advanced rapidly in recent years and has shown advantages in a variety of domains. In this paper, we investigate its potential for discrete simulation optimization in the fixed-confidence setting, a fundamental problem in the simulation literature. We first introduce a quantum simulation oracle that prepares a coherent superposition over all candidate solutions and provides the foundation for quantum algorithm design. Based on this oracle, we develop the first Grover-search-based quantum algorithm for discrete simulation optimization, called SOGAS. In particular, SOGAS uses a binary-search framework to progressively eliminate suboptimal solutions while carefully controlling the error probability, and eventually identifies a set of near-optimal solutions. We prove that SOGAS returns a near-optimal solution with probability at least the prescribed confidence level and achieves a quadratic speedup in the dependence of query complexity on the number of candidate solutions. Numerical experiments further show that SOGAS substantially outperforms classical benchmarks and provide empirical evidence for quantum advantage in discrete simulation optimization.

quant-pharXiv:2604.26277•Apr 30, 2026•3 citations
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.
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.
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).
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.
We demonstrate that the search space of the quadratic assignment problem (QAP), known as an NP-hard combinatorial optimization problem, can be reduced using Grover adaptive search (GAS) with permutation preparation operator (PPO). To that end, we first revise the traditional quadratic unconstrained binary optimization (QUBO) formulation of the QAP into a higher-order unconstrained binary optimization (HUBO) formulation, introducing a binary encoding method. Algebraic analyses in terms of the number of qubits, quantum gates, circuit depth, and query complexity are performed, which indicate that our proposed approach significantly reduces the search space size, improving convergence performance to the optimal solution compared to the conventional one. Furthermore, although the PPO for HUBO has a greater circuit depth than the PPO for QUBO, when the analysis is extended to the entire state preparation operator, both HUBO and QUBO exhibit comparable depths. Therefore, owing to its smaller number of variables, HUBO can be concluded to be more effective.
Quantum computing has advanced rapidly in recent years and has shown advantages in a variety of domains. In this paper, we investigate its potential for discrete simulation optimization in the fixed-confidence setting, a fundamental problem in the simulation literature. We first introduce a quantum simulation oracle that prepares a coherent superposition over all candidate solutions and provides the foundation for quantum algorithm design. Based on this oracle, we develop the first Grover-search-based quantum algorithm for discrete simulation optimization, called SOGAS. In particular, SOGAS uses a binary-search framework to progressively eliminate suboptimal solutions while carefully controlling the error probability, and eventually identifies a set of near-optimal solutions. We prove that SOGAS returns a near-optimal solution with probability at least the prescribed confidence level and achieves a quadratic speedup in the dependence of query complexity on the number of candidate solutions. Numerical experiments further show that SOGAS substantially outperforms classical benchmarks and provide empirical evidence for quantum advantage in discrete simulation optimization.