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.
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.
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.
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.
In this paper, we propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization (HUBO) problem. This algorithm is based on the Grover adaptive search that originally supported HUBO with integer coefficients. Next, as an application example, we formulate multiple-input multiple-output maximum likelihood detection as a HUBO problem with real-valued coefficients, where we use the Gray-coded bit-to-symbol mapping specified in the 5G standard. The proposed approach allows us to construct an efficient quantum circuit for the detection problem and to analyze specific numbers of required qubits and quantum gates, whereas other conventional studies have assumed that such a circuit is feasible as a quantum oracle. To further accelerate the quantum algorithm, we also derive a probability distribution of the objective function value and determine a unique threshold to sample better states. Assuming a future fault-tolerant quantum computing, our proposed algorithm has the potential for significantly reducing query complexity in the classical domain and providing a quadratic speedup in the quantum domain.
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.
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 this paper, we propose a novel method of formulating an NP-hard wireless channel assignment problem as a higher-order unconstrained binary optimization (HUBO), where the Grover adaptive search (GAS) is used to provide a quadratic speedup for solving the problem. The conventional method relies on a one-hot encoding of the channel indices, resulting in a quadratic formulation. By contrast, we conceive ascending and descending binary encodings of the channel indices, construct a specific quantum circuit, and derive the exact numbers of qubits and gates required by GAS. Our analysis clarifies that the proposed HUBO formulation significantly reduces the number of qubits and the query complexity compared with the conventional quadratic formulation. This advantage is achieved at the cost of an increased number of quantum gates, which we demonstrate can be reduced by our proposed descending binary encoding.