Grover's Adaptative Search (GAS) algorithm combined with the High Order Binary Optimization (HOBO) oracle proposal is currently the Fault Tolerant Quantum Computer (FTQC)'s main algorithm to solve binary optimization problems. In this paper, we propose a new way to obtain the Grover's oracle needed which is costless in terms of gates and ancilla qubits. This oracle proposal also has zero additional costs linked to decimal numbers of the problem weights and a very small overcost due to high order problems with respect to the other proposals. Nevertheless, it cannot be easily adapted to constrained problems. This new oracle is based on a completely different approach, which uses Quantum Signal Processing (QSP) techniques and amplitude encoding. This method can also be described in the Quantum Singular Value Transformation (QSVT) framework as a variant of eigenstate search algorithms. Our oracle combines the benefits of both the QSVT amplitude encoding of the problem and GAS strategies to seek eigenvalues.
Grover's Adaptative Search (GAS) algorithm combined with the High Order Binary Optimization (HOBO) oracle proposal is currently the Fault Tolerant Quantum Computer (FTQC)'s main algorithm to solve binary optimization problems. In this paper, we propose a new way to obtain the Grover's oracle needed which is costless in terms of gates and ancilla qubits. This oracle proposal also has zero additional costs linked to decimal numbers of the problem weights and a very small overcost due to high order problems with respect to the other proposals. Nevertheless, it cannot be easily adapted to constrained problems. This new oracle is based on a completely different approach, which uses Quantum Signal Processing (QSP) techniques and amplitude encoding. This method can also be described in the Quantum Singular Value Transformation (QSVT) framework as a variant of eigenstate search algorithms. Our oracle combines the benefits of both the QSVT amplitude encoding of the problem and GAS strategies to seek eigenvalues.
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.
High-order binary optimization (HUBO) formulation can represent many real world problems. This mathematical approach is particularly relevant within the quantum computation domain because quantum hardware allows to directly map and solve these problems. The thesis explores the implementation of Grover Adaptive Search (GAS) by varying the different free parameters to evaluate the quality of the solution and the success rate of the algorithm, along with a possible optimization procedure. In particular, GAS is an algorithm that is compliant with HUBO and theoretically offer a quadratic speed up over classical computation. This thesis implements a quantum circuit for GAS algorithm to solve a 4-city traveling salesman problem along with two strategies to reduce the gate counts. The results include the output quality of the value of the objective function and the success rate of reaching the true minimum of 7, where the optimal configuration achieves an average value of 9.4 and a success rate of 36%. This configuration also maintains a 7% lower average value and a 10% higher success rate compared to randomly generated parameters.
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.
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).