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.
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 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 article, we study a Grover-type method for quadratic unconstrained binary optimization (QUBO) problems. For ann-dimensional QUBO problem withmnonzero terms, we construct a marker oracle for such problems with a tunable parameter,Λ∈[1,m]∩Z. Atd∈Z+precision, the oracle usesO(n+Λd)qubits and has total depth ofO(Λmlog2(n)+log2(d))and a non-Clifford depth ofO(Λm). Moreover, each qubit is required to be connected to at mostO(log2(Λ+d))other qubits. In the case of a maximum graph cuts, asd=2⌈log2(n)⌉always suffices, the depth of the marker oracle can be made as shallow asO(log2(n)). For all values ofΛ, the non-Clifford gate count of these oracles is strictly lower (at least by a factor of∼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(ϵlog2(n))time, this adaptive method finds a configuration that is among the bestϵ2nones.
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 binary optimization problems, where the goal is to find the inputxthat 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.
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.
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.