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

An Improved GAS Algorithm and it's application on the Credit Card Scoring Problem

Zhijian Wang, Yuchen He, Yong Long, Tian Luan

Published Dec 17, 2024• 0 citations
Publisher

Abstract

Abstract This paper introduces an improved Grover Adaptive Search(GAS) algorithm. The GAS algorithm has been prove to achieve quadratic acceleration in the Constrained Polynomial Binary Optimization (CPBO) problem. Nevertheless, the acceleration effect of the GAS algorithm can be decreased by the poor threshold selection. This article uses the Quantum Approximate Optimization Algorithm(QAOA) to improve the initial threshold selection, thereby accelerating the convergence speed of the original GAS algorithm. The acceleration effect of the improved GAS algorithm is presented by the application on the Max-cut problem and the credit card scoring problem.

DOI
10.21203/rs.3.rs-5437472/v1

Related papers

An Improved GAS Algorithm

Zhijian Wang, Yuchen He, Tian Luan +1 more

This paper introduces an improved Grover Adaptive Search (GAS) algorithm. The GAS algorithm has been prove to achieve quadratic acceleration in the Constrained Polynomial Binary Optimization (CPBO) problem. Nevertheless, the acceleration effect of the GAS algorithm can be decreased by the poor threshold selection. This article uses the Quantum Approximate Optimization Algorithm (QAOA) to improve the initial threshold selection, thereby accelerating the convergence speed of the original GAS algorithm. The acceleration effect of the improved GAS algorithm is presented by the Max-Cut problem and the CPBO problem.

Entropy•Feb 26, 2025•1 citation

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

Quantum-Accelerated Self-Consistent Field: A Hybrid Algorithm

Alexis Ralli, Tim Weaving, Thomas M. Bickley +2 more

We present the Grover adaptive search self-consistent field (GAS-SCF) algorithm. GAS-SCF leverages quantum arithmetic to construct an efficient oracle that marks target states (Fock states) which improve upon some initial classical energy estimate. Amplitude amplification then increases the probability of measuring these states. This approach offers a theoretical quadratic speed-up for the optimization problem encountered in SCF quantum chemistry and establishes a baseline against which structured optimization algorithms, such as QAOA and DQI may be compared. In this work, we classically simulate three examples as proofs of concept of the algorithm, the largest consisting of 26 qubits. We then extend our analysis to two larger systems, with O3 representing the largest case at 330 qubits. These examples are chosen to probe classically challenging SCF regimes. Achieving chemically relevant applications of GAS-SCF will require large-scale, fault-tolerant quantum hardware.

quant-pharXiv:2606.20176•Jun 19, 2026•0 citations

Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies With Higher Order Formulations

Yuki Sano, Kosuke Mitarai, Naoki Yamamoto +1 more

Grover adaptive search (GAS) is a quantum exhaustive search algorithm designed to solve binary optimization problems. In this article, we propose higher order binary formulations that can simultaneously reduce the numbers of qubits and gates required for GAS. Specifically, we consider two novel strategies: one that reduces the number of gates through polynomial factorization, and the other that halves the order of the objective function, subsequently decreasing circuit runtime and implementation cost. Our analysis demonstrates that the proposed higher order formulations improve the convergence performance of GAS by reducing both the search space size and the number of quantum gates. Our strategies are also beneficial for general combinatorial optimization problems using one-hot encoding.

arXiv:2308.01572•IEEE Transactions on Quantum Engineering•Jan 1, 2024•17 citations

Grover Adaptive Search With Fewer Queries

Hiroaki Ominato, Takahiro Ohyama, Koichiro Yamaguchi

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.

IEEE Access•Jan 1, 2024•4 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
Abstract This paper introduces an improved Grover Adaptive Search(GAS) algorithm. The GAS algorithm has been prove to achieve quadratic acceleration in the Constrained Polynomial Binary Optimization (CPBO) problem. Nevertheless, the acceleration effect of the GAS algorithm can be decreased by the poor threshold selection. This article uses the Quantum Approximate Optimization Algorithm(QAOA) to improve the initial threshold selection, thereby accelerating the convergence speed of the original GAS algorithm. The acceleration effect of the improved GAS algorithm is presented by the application on the Max-cut problem and the credit card scoring problem.
This paper introduces an improved Grover Adaptive Search (GAS) algorithm. The GAS algorithm has been prove to achieve quadratic acceleration in the Constrained Polynomial Binary Optimization (CPBO) problem. Nevertheless, the acceleration effect of the GAS algorithm can be decreased by the poor threshold selection. This article uses the Quantum Approximate Optimization Algorithm (QAOA) to improve the initial threshold selection, thereby accelerating the convergence speed of the original GAS algorithm. The acceleration effect of the improved GAS algorithm is presented by the Max-Cut problem and the CPBO problem.
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.
We present the Grover adaptive search self-consistent field (GAS-SCF) algorithm. GAS-SCF leverages quantum arithmetic to construct an efficient oracle that marks target states (Fock states) which improve upon some initial classical energy estimate. Amplitude amplification then increases the probability of measuring these states. This approach offers a theoretical quadratic speed-up for the optimization problem encountered in SCF quantum chemistry and establishes a baseline against which structured optimization algorithms, such as QAOA and DQI may be compared. In this work, we classically simulate three examples as proofs of concept of the algorithm, the largest consisting of 26 qubits. We then extend our analysis to two larger systems, with O3 representing the largest case at 330 qubits. These examples are chosen to probe classically challenging SCF regimes. Achieving chemically relevant applications of GAS-SCF will require large-scale, fault-tolerant quantum hardware.
Grover adaptive search (GAS) is a quantum exhaustive search algorithm designed to solve binary optimization problems. In this article, we propose higher order binary formulations that can simultaneously reduce the numbers of qubits and gates required for GAS. Specifically, we consider two novel strategies: one that reduces the number of gates through polynomial factorization, and the other that halves the order of the objective function, subsequently decreasing circuit runtime and implementation cost. Our analysis demonstrates that the proposed higher order formulations improve the convergence performance of GAS by reducing both the search space size and the number of quantum gates. Our strategies are also beneficial for general combinatorial optimization problems using one-hot encoding.
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.
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.