Solving the eigenvalue problem is particularly important in almost all fields of science and engineering. With the development of quantum computers, multiple algorithms have been proposed for this purpose. However, such methods are usually only applicable to matrices of specific types, such as unitary or Hermitian matrices. The quantum annealer of the D-Wave, a quantum computer, returns the minimum value of the quadratic unconstrained binary optimization (QUBO) model. Thus, quantum annealers can be leveraged to solve arbitrary eigenvalue problems by formulating corresponding QUBO models. In this paper, we propose two higher-order unconstrained optimization (HUBO) formulations to solve eigenvalue problems involving n×n general matrices. In addition, we use a formula to reduce the order and convert the HUBO model into a QUBO model. Further, by using a quantum approximate optimization algorithm, this method can be extended to a gate-model quantum computer.
Solving the eigenvalue problem is particularly important in almost all fields of science and engineering. With the development of quantum computers, multiple algorithms have been proposed for this purpose. However, such methods are usually only applicable to matrices of specific types, such as unitary or Hermitian matrices. The quantum annealer of the D-Wave, a quantum computer, returns the minimum value of the quadratic unconstrained binary optimization (QUBO) model. Thus, quantum annealers can be leveraged to solve arbitrary eigenvalue problems by formulating corresponding QUBO models. In this paper, we propose two higher-order unconstrained optimization (HUBO) formulations to solve eigenvalue problems involving n×n general matrices. In addition, we use a formula to reduce the order and convert the HUBO model into a QUBO model. Further, by using a quantum approximate optimization algorithm, this method can be extended to a gate-model quantum computer.
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.
Quantum approaches to combinatorial optimization problems (COPs) are often limited by the resource demands of Quadratic Unconstrained Binary Optimization (QUBO) encodings, which enlarge circuits through penalty terms and increase qubit and gate counts. We show that Higher-Order Unconstrained Binary Optimization (HUBO) enables a more resource-efficient formulation. Our method systematically constructs HUBO Hamiltonians and, compared to a QUBO formulation in benchmarks on Gate Assignment (GAP), Maximum k-Colorable Subgraph (MkCS), and Integer Programming (IP) problems, significantly reduces qubit requirements and decreases total CNOT gate counts by at least 89.6% for all tested instances. These results highlight HUBO as a practical alternative for quantum optimization on near-term devices. To promote adoption, we release an open-source Python library that automates HUBO model construction, extends beyond the examples presented in this work, and broadens access to resource-efficient quantum optimization.
The security of the RSA cryptosystem is based on the difficulty of factoring a large number N into prime numbers [Formula: see text] and [Formula: see text] satisfying [Formula: see text]. This paper presents a prime factorization method using a D-Wave quantum computer that could threaten the RSA cryptosystem in the future. The starting point for this method is very simple, representing two prime numbers as qubits. Then, we set the difference between the product of the two prime numbers expressed in qubits and N as a cost function, and we find the solution when the cost function is minimized. D-Wave's quantum annealer can find the minimum value of any quadratic problem. However, the cost function must be a higher-order unconstrained optimization (HUBO) model because it contains second- or higher-order terms. We used a hybrid solver accessible via Leap, D-Wave's real-time quantum cloud service, and the dimod package provided by the D-Wave Ocean software development kit (SDK) to solve the HUBO problem. We also successfully factorized 102,454,763 with 26 logical qubits. In addition, we factorized 1,000,070,001,221 using the range-dependent Hamiltonian algorithm.
This document details the methodology and steps taken to convert Higher Order Unconstrained Binary Optimization (HUBO) models into Quadratic Unconstrained Binary Optimization (QUBO) models. The focus is primarily on prime factorization problems; a critical and computationally intensive task relevant in various domains including cryptography, optimization, and number theory. The conversion from Higher-Order Binary Optimization (HUBO) to Quadratic Unconstrained Binary Optimization (QUBO) models is crucial for harnessing the capabilities of advanced computing methodologies, particularly quantum computing and DYNEX neuromorphic computing. Quantum computing offers potential exponential speedups for specific problems through its intrinsic parallelism capabilities. Conversely, DYNEX neuromorphic computing enhances efficiency and accelerates the resolution of intricate, pattern-oriented tasks by simulating memristors in GPUs, employing a highly decentralized approach, via Blockchain technology. This transformation enables the exploitation of these cutting-edge computing paradigms to address complex optimization challenges effectively. Through detailed explanations, mathematical formulations, and algorithmic strategies, this document aims to provide a comprehensive guide to understanding and implementing the conversion process from HUBO to QUBO. It underscores the importance of such transformations in making prime factorization computationally feasible on both existing classical computers and emerging computing technologies.
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.
Density matrix electronic structure theory is used in many quantum chemistry methods to "alleviate" the computational cost that arises from directly using wave functions. Although density matrix based methods are computationally more efficient than wave function based methods, significant computational effort is involved. Because the Schrödinger equation needs to be solved as an eigenvalue problem, the time-to-solution scales cubically with the system size in mean-field type approaches such as Hartree-Fock and density functional theory and is solved as many times in order to reach charge or field self-consistency. We hereby propose and study a method to compute the density matrix by using a quadratic unconstrained binary optimization (QUBO) solver. This method could be useful to solve the problem with quantum computers and, more specifically, quantum annealers. Our proposed approach is based on a direct construction of the density matrix using a QUBO eigensolver. We explore the main parameters of the algorithm focusing on precision and efficiency. We show that, while direct construction of the density matrix using a QUBO formulation is possible, the efficiency and precision have room for improvement. Moreover, calculations performed with quantum annealing on D-Wave's new Advantage quantum computer are compared with results obtained with classical simulated annealing, further highlighting some problems of the proposed method. We also suggest alternative methods that could lead to a more efficient QUBO-based density matrix construction.