Results in Control and Optimization

QUBO formulations for a system of linear equations

Kyungtaek Jun

Published Feb 5, 2024• 20 citations

Abstract

Abstract With the advent of quantum computers, many quantum computing algorithms are being developed. Solving linear systems is one of the most fundamental problems in almost all of science and engineering. Harrow-Hassidim-Lloyd algorithm, a monumental quantum algorithm for solving linear systems on the gate model quantum computers, was invented and several advanced variations have been developed. For a given square matrix A∈R(n×n) and a vector b∈R(n), we will find unconstrained binary optimization (QUBO) models for a vector x∈R(n) that satisfies Ax=b. To formulate QUBO models for a linear system solving problem, we make use of a linear least-square problem with binary representation of the solution. We validate those QUBO models on the D-Wave system and discuss the results. For a simple system, We provide a python code to calculate the matrix characterizing the relationship between the variables and to print the test code that can be used directly in D-Wave system.

DOI: 10.1016/j.rico.2024.100380

Related papers

QUBO formulations for numerical quantum computing

Kyungtaek Jun

With the advent of quantum computers, many quantum computing algorithms are being developed. Solving linear systems is one of the most fundamental problems in almost all science and engineering. The Harrow-Hassidim-Lloyd algorithm, a monumental quantum algorithm for solving linear systems on gate model quantum computers, was invented and several advanced variations have been developed. For a given n by n matrix A and a vector b, we will find unconstrained binary optimization (QUBO) models for a vector x that satisfies Ax=b. To formulate QUBO models for a linear system solving problem, we make use of a linear least-square problem with binary representation of the solution. We validate those QUBO models on the D-Wave system and discuss the results. For a simple system, we provide a Python code to calculate the matrix characterizing the relationship between the variables and to print the test code that can be used directly in the D-Wave system.

arXiv:2106.10819Jun 21, 20210 citations

Solving linear systems by quadratic unconstrained binary optimization on D-Wave quantum annealing device

Kyungtaek Jun, Rebecca Conley, Yecheng Huang +2 more

Many quantum computing algorithms are being developed with the advent of quantum computers. Solving linear systems is one of the most fundamental problems in almost all of science and engineering. HHL algorithm, a monumental quantum algorithm for solving linear systems on the gate model quantum computers, was invented and several advanced variations have been developed. However, HHL-based algorithms have a lot of limitations in spite of their importance. We address solving linear systems on a D-Wave quantum annealing device. To formulate a quadratic unconstrained binary optimization (QUBO) model for a linear system solving problem, we make use of a linear least-square problem with binary representation of the solution. We validate this QUBO model on the D-Wave system and discuss the results.

Apr 9, 20216 citations

Range dependent Hamiltonian Algorithm for numerical QUBO formulation

Hyunju Lee, Kyungtaek Jun

With the advent and development of quantum computers, various quantum algorithms that can solve linear equations and eigenvalues faster than classical computers have been developed. The Harrow-Hassidim-Lloyd algorithm is an algorithm that can solve linear equations in a gate model quantum computer. Still, it is constrained by the use of quantum RAM and the size limit of the matrix according to the total number of qubits in the quantum computer. Recently, Jun and Lee developed a QUBO model for solving linear systems and eigenvalue problems in the quantum computer. However, even though their model uses 2048 qubits, the number of qubits for variables that can be used for the problem is only 64. To solve this problem, we introduce an algorithm that can be used by dividing the size of the entire domain according to the number of qubits. We also form a QUBO model related to each subregion.

arXiv:2202.07692Feb 15, 20222 citations

Range dependent Hamiltonian algorithms for numerical QUBO formulation

Hyunju Lee, Kyungtaek Jun

With the advent and development of quantum computers, various quantum algorithms that can solve linear equations and eigenvalues faster than classical computers have been developed. In particular, a hybrid solver provided by D-Wave's Leap quantum cloud service can utilize up to two million variables. Using this technology, quadratic unconstrained binary optimization (QUBO) models have been proposed for linear systems, eigenvalue problems, RSA cryptosystems, and computed tomography (CT) image reconstructions. Generally, QUBO formulation is obtained through simple arithmetic operations, which offers great potential for future development with the progress of quantum computers. A common method here was to binarize the variables and match them to multiple qubits. To achieve the accuracy of 64 bits per variable, 64 logical qubits must be used. Finding the global minimum energy in quantum optimization becomes more difficult as more logical qubits are used; thus, a quantum parallel computing algorithm that can create and compute multiple QUBO models is introduced here. This new algorithm divides the entire domain each variable can have into multiple subranges to generate QUBO models. This paper demonstrates the superior performance of this new algorithm particularly when utilizing an algorithm for binary variables.

Scientific ReportsMar 14, 20251 citation

QUBO Refinement: Achieving Superior Precision through Iterative Quantum Formulation with Limited Qubits

Hyunju Lee, Kyungtaek Jun

In the era of quantum computing, the emergence of quantum computers and subsequent advancements have led to the development of various quantum algorithms capable of solving linear equations and eigenvalues, surpassing the pace of classical computers. Notably, the hybrid solver provided by the D-wave system can leverage up to two million variables. By exploiting this technology, quantum optimization models based on quadratic unconstrained binary optimization (QUBO) have been proposed for applications, such as linear systems, eigenvalue problems, RSA cryptosystems, and CT image reconstruction. The formulation of QUBO typically involves straightforward arithmetic operations, presenting significant potential for future advancements as quantum computers continue to evolve. A prevalent approach in these developments is the binarization of variables and their mapping to multiple qubits. These methods increase the required number of qubits as the range and precision of each variable increase. Determining the optimal value of a QUBO model becomes more challenging as the number of qubits increases. Furthermore, the accuracies of the existing Qiskit simulator, D-Wave system simulator, and hybrid solver are limited to two decimal places. Problems arise because the qubits yielding the optimal value for the QUBO model may not necessarily correspond to the solution of a given problem. To address these issues, we propose a new iterative algorithm. The novel algorithm sequentially progresses from the highest to the lowest exponent in binarizing each number, whereby each number is calculated using two variables, and the accuracy can be computed up to a maximum of 16 decimal places.

arXiv:2411.16138Nov 25, 20240 citations

A Tutorial on Formulating and Using QUBO Models

Fred Glover, Gary A. Kochenberger, Yu Du

The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become a subject of study in neuromorphic computing. Through these connections, QUBO models lie at the heart of experimentation carried out with quantum computers developed by D-Wave Systems and neuromorphic computers developed by IBM. Computational experience is being amassed by both the classical and the quantum computing communities that highlights not only the potential of the QUBO model but also its effectiveness as an alternative to traditional modeling and solution methodologies. This tutorial discloses the basic features of the QUBO model that give it the power and flexibility to encompass the range of applications that have thrust it onto center stage of the optimization field. We show how many different types of constraining relationships arising in practice can be embodied within the "unconstrained" QUBO formulation in a very natural manner using penalty functions, yielding exact model representations in contrast to the approximate representations produced by customary uses of penalty functions. Each step of generating such models is illustrated in detail by simple numerical examples, to highlight the convenience of using QUBO models in numerous settings. We also describe recent innovations for solving QUBO models that offer a fertile avenue for integrating classical and quantum computing and for applying these models in machine learning.

arXiv:1811.11538Nov 13, 2018164 citations