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

IEEE Access

Grover Adaptive Search With Fewer Queries

Hiroaki Ominato, Takahiro Ohyama, Koichiro Yamaguchi

Published Jan 1, 2024• 4 citations
Publisher

Abstract

In binary optimization problems, where the goal is to find the input$\boldsymbol {x}$that minimizes a given objective function, Grover adaptive search (GAS) is a well-known quantum algorithm that provides quadratic speedup when compared with the brute-force approaches of classical computers. GAS calls a renowned quantum search algorithm, Grover search (GS), as a subroutine to search for inputs with function values less than the threshold value. If such an input is found, the threshold value is updated with the function value and the search targets are narrowed. To search efficiently for a solution, an appropriate number of queries must be selected to amplify the desired state of the GS in each step. This paper discusses this issue and proposes a new method for selecting the number of queries and provides proof that our method achieves quadratic speedup as well as the original GAS. Furthermore, the simulation results for 40-bit problems confirm that our method allows an optimal solution with 22% fewer queries than the standard method, thus offering the possibility of significantly reduced computation times for combinatorial optimization problems.

DOI
10.1109/access.2024.3403200

Related papers

Quantum Speedup for Multiuser Detection With Optimized Parameters in Grover Adaptive Search

Masaya Norimoto, Taku Mikuriya, Naoki Ishikawa

Maximum-likelihood multiuser detection incurs a large computational complexity, and its low-complexity detection scheme suffers from a performance loss, where this tradeoff is inevitable and inherent in a classical computer. In this paper, we use the Grover adaptive search (GAS) to break the tradeoff, which is a quantum exhaustive search algorithm guaranteed to obtain the optimal solution, achieving a quadratic speedup. Specifically, we design two specific parameters of GAS to achieve the optimal performance with a reduced complexity: the initial threshold and the number of Grover rotations. The initial threshold of GAS can be optimized using a solution of semi-definite programming, and it is possible to calculate the distribution of the number of solutions smaller than the initial threshold in advance, which depends on instantaneous channel coefficients. In addition, we analyze the number of quantum gates required for GAS and show that the gate count can be reduced by bypassing the higher-order terms in the objective function, leading to a reduced circuit runtime. Our analysis and simulation results demonstrate that the proposed approach achieves the same performance as the optimal maximum-likelihood detection while reducing the query complexity of GAS, implying that the large constant overhead of quadratic speedup can be further reduced.

IEEE Access•Jan 1, 2024•6 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•16 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 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

Grover Adaptive Search With Spin Variables

Shintaro Fujiwara, Naoki Ishikawa

This paper presents a novel approach to Grover adaptive search (GAS) for a combinatorial optimization problem whose objective function involves spin variables. While the GAS algorithm with a conventional design of a quantum dictionary subroutine handles a problem associated with an objective function with binary variables$\lbrace 0,1\rbrace$, we reformulate the problem using spin variables$\lbrace +1,-1\rbrace$to simplify the algorithm. Specifically, we introduce a novel quantum dictionary subroutine that is designed for this spin-based formulation. A key benefit of this approach is the substantial reduction in the number of CNOT gates required to construct the quantum circuit. We theoretically demonstrate that, for certain problems, our proposed approach can reduce the gate complexity from an exponential order to a polynomial order, compared to the conventional binary-based approach. This improvement has the potential to enhance the scalability and efficiency of GAS, particularly in larger quantum computations.

arXiv:2410.11633•IEEE Transactions on Quantum Engineering•Jan 1, 2025•1 citation

Grover Adaptive Search for Joint Maximum-Likelihood Detection of Power-Domain Non-Orthogonal Multiple Access

Masaya Norimoto, Naoki Ishikawa

In this paper, we address the joint maximum-likelihood detection of power-domain non-orthogonal multiple access and transform the detection problem into a binary optimization problem. Then, we solve it by a quantum algorithm, Grover adaptive search (GAS), and further accelerate the algorithm. Assuming fault-tolerant quantum computing, GAS provides a quadratic speedup for binary optimization problems in terms of query complexity. The proposed method designs the number of Grover operators using a time-invariant distribution of the number of solutions, which can be obtained in advance. Simulation results demonstrate that the proposed method is capable of reducing the query complexity in the classical domain while achieving the optimal performance.

IEEE Vehicular Technology Conference•Jun 1, 2023•2 citations
In binary optimization problems, where the goal is to find the inputx\boldsymbol {x}xthat minimizes a given objective function, Grover adaptive search (GAS) is a well-known quantum algorithm that provides quadratic speedup when compared with the brute-force approaches of classical computers. GAS calls a renowned quantum search algorithm, Grover search (GS), as a subroutine to search for inputs with function values less than the threshold value. If such an input is found, the threshold value is updated with the function value and the search targets are narrowed. To search efficiently for a solution, an appropriate number of queries must be selected to amplify the desired state of the GS in each step. This paper discusses this issue and proposes a new method for selecting the number of queries and provides proof that our method achieves quadratic speedup as well as the original GAS. Furthermore, the simulation results for 40-bit problems confirm that our method allows an optimal solution with 22% fewer queries than the standard method, thus offering the possibility of significantly reduced computation times for combinatorial optimization problems.
Maximum-likelihood multiuser detection incurs a large computational complexity, and its low-complexity detection scheme suffers from a performance loss, where this tradeoff is inevitable and inherent in a classical computer. In this paper, we use the Grover adaptive search (GAS) to break the tradeoff, which is a quantum exhaustive search algorithm guaranteed to obtain the optimal solution, achieving a quadratic speedup. Specifically, we design two specific parameters of GAS to achieve the optimal performance with a reduced complexity: the initial threshold and the number of Grover rotations. The initial threshold of GAS can be optimized using a solution of semi-definite programming, and it is possible to calculate the distribution of the number of solutions smaller than the initial threshold in advance, which depends on instantaneous channel coefficients. In addition, we analyze the number of quantum gates required for GAS and show that the gate count can be reduced by bypassing the higher-order terms in the objective function, leading to a reduced circuit runtime. Our analysis and simulation results demonstrate that the proposed approach achieves the same performance as the optimal maximum-likelihood detection while reducing the query complexity of GAS, implying that the large constant overhead of quadratic speedup can be further reduced.
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.
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.
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.
This paper presents a novel approach to Grover adaptive search (GAS) for a combinatorial optimization problem whose objective function involves spin variables. While the GAS algorithm with a conventional design of a quantum dictionary subroutine handles a problem associated with an objective function with binary variables{0,1}\lbrace 0,1\rbrace{0,1}, we reformulate the problem using spin variables{+1,−1}\lbrace +1,-1\rbrace{+1,−1}to simplify the algorithm. Specifically, we introduce a novel quantum dictionary subroutine that is designed for this spin-based formulation. A key benefit of this approach is the substantial reduction in the number of CNOT gates required to construct the quantum circuit. We theoretically demonstrate that, for certain problems, our proposed approach can reduce the gate complexity from an exponential order to a polynomial order, compared to the conventional binary-based approach. This improvement has the potential to enhance the scalability and efficiency of GAS, particularly in larger quantum computations.
In this paper, we address the joint maximum-likelihood detection of power-domain non-orthogonal multiple access and transform the detection problem into a binary optimization problem. Then, we solve it by a quantum algorithm, Grover adaptive search (GAS), and further accelerate the algorithm. Assuming fault-tolerant quantum computing, GAS provides a quadratic speedup for binary optimization problems in terms of query complexity. The proposed method designs the number of Grover operators using a time-invariant distribution of the number of solutions, which can be obtained in advance. Simulation results demonstrate that the proposed method is capable of reducing the query complexity in the classical domain while achieving the optimal performance.