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.
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.
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.
The emergence of quantum annealers has catalyzed the development of quantum optimization algorithms across various fields. The formulation of a quadratic unconstrained binary optimization (QUBO) model for quantum linear systems suggests that quantum optimization algorithms can play an important role in science and engineering. Recently, a QUBO model was developed by applying a quantum linear system to computed tomography (CT) image reconstruction to clearly show the internal structure of the sample. To date, ultra-clear CT images have not been reconstructed using quantum optimization algorithms owing to limitations in logical qubits. However, the quantum CT image reconstruction algorithm using a quantum linear system provides confidence in the accuracy of the CT image by leveraging the difference between the global and theoretical minimum energies. In this paper, we propose an algorithm that can use two or more QUBO models for CT image reconstruction. The proposed algorithm formulates several QUBO models from CT image reconstruction and verifies them using the hybrid solver of the D-Wave system. The proposed algorithm suggests that quantum-optimized CT algorithms can make greater progress in the future.
Quantum optimization shows significant potential in tackling complex combinatorial challenges, prompting our research exploration into the domain of quantum computing to address the Bin Packing Problem (BPP) through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work-in-progress paper outlines our proposal for a thorough study that encompasses classical bin packing formulations, initiating with the Mixed Integer Linear Program, followed by a comparative analysis of the corresponding QUBO representations, and adopting a structured approach of Quantum Annealing on the D-Wave machine. While our work is still in progress, continuous comparative analyses are being conducted to evaluate various QUBO formulations, derived from diverse classical bin packing models, aiming to identify the most efficient QUBO for addressing the BPP. On another front, efforts are dedicated to refining the solution process further, with a focus on enhancing the precision of the selected QUBO formulation.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
A Quadratic Unconstrained Binary Optimization (QUBO) model is defined by a quadratic objective function comprising binary variables, each taking values of 0 or 1. The objective of the QUBO problem is to determine the optimal assignment of these binary variables to minimize the QUBO model. QUBO models are instrumental in solving various combinatorial optimization problems, leading to extensive research on solver development, as many combinatorial optimization problems can be reformulated as QUBO problems. Notably, D-Wave Systems, a company specializing in quantum technologies, has developed quantum annealers which are programmable QUBO solvers that utilize quantum mechanics. SHA-1 is a cryptographic hash function that generates a 160-bit hash value from a message of an arbitrary length. This hash value makes it difficult to compute the original message within a practical timeframe. A pre-image attack, which aims to compute the original message from a hash value, is important in cryptographic hash functions. Previous research has shown that a QUBO can be designed to simulate SHA-1, facilitating the execution of a pre-image attack. In this paper, we present a novel QUBO model with fewer bits, linear terms, and quadratic terms than previous QUBO models for simulating hash values and pre-image calculations in SHA-1. While the previous QUBO model requires 34,016 bits, 32,584 linear terms, and 168,188 quadratic terms, our new model requires only 32,096 bits, 26,600 linear terms, and 157,308 quadratic terms. This approach can efficiently execute pre-image attacks using a quantum annealer, providing valuable insights for evaluating the robustness of cryptographic security systems.
The quantum annealing devices, which encode the solution to a computational problem in the ground state of a quantum Hamiltonian, are implemented in D-Wave systems with more than 2,000 qubits. However, quantum annealing can solve only a classical combinatorial optimization problem such as an Ising model, or equivalently, a quadratic unconstrained binary optimization (QUBO) problem. In this paper, we formulate the QUBO model to solve elliptic problems with Dirichlet and Neumann boundary conditions using the finite element method. In this formulation, we develop the objective function of quadratic binary variables represented by qubits and the system finds the binary string combination minimizing the objective function globally. Based on the QUBO formulation, we introduce an iterative algorithm to solve the elliptic problems. We discuss the validation of the modeling on the D-Wave quantum annealing system.