Ising models minimizing a quadratic objective function with spin variables of either −1 or +1 are instrumental in tackling combinatorial optimization problems by programmable Quantum Annealers. This paper introduces unit Ising models, where non-zero coefficients are restricted to −1 or +1. Due to the limited resolution of quantum annealers, unit Ising models are more suitable for quantum annealers. A fixed unit Ising model for logic circuits could lead to Application-Specific Unit Quantum Annealers (ASUQAs) for inverse function computation, similar to ASICs. Our findings suggest a powerful new method for compromising the RSA cryptosystem by leveraging ASUQAs for factorization.
Ising models minimizing a quadratic objective function with spin variables of either −1 or +1 are instrumental in tackling combinatorial optimization problems by programmable Quantum Annealers. This paper introduces unit Ising models, where non-zero coefficients are restricted to −1 or +1. Due to the limited resolution of quantum annealers, unit Ising models are more suitable for quantum annealers. A fixed unit Ising model for logic circuits could lead to Application-Specific Unit Quantum Annealers (ASUQAs) for inverse function computation, similar to ASICs. Our findings suggest a powerful new method for compromising the RSA cryptosystem by leveraging ASUQAs for factorization.
Ising Models, defined by quadratic objective functions (or Hamiltonians), enable to use quantum annealers to search for optimal or near-optimal solutions of satisfiability problems. However, current quantum annealers have limited resolution, meaning that small or closely-valued coefficients in the Hamiltonian may be obscured by flux noise, leading to a degradation in the performance of quantum annealing. In this paper, we propose a novel design methodology for encoding satisfiability problems into Ising models via Integer Linear Programming. Experimental results show that our method can effectively reduce the resolution requirements for quantum annealers.
ABSTRACT An Ising model is a mathematical model defined by an objective function comprising a quadratic formula of multiple spin variables, each taking values of either or . The task of determining a spin value assignment to these variables that minimizes the resulting value of an Ising model is a challenging optimization problem. Recently, quantum annealers, consisting of qubit cells interconnected according to principles of quantum mechanics, have emerged as a solution for tackling such problems. Ising models characterized by fewer quadratic terms are preferable as they reduce the resource requirements of quantum annealers. Additionally, it is advantageous for the absolute values of coefficients associated with linear and quadratic terms to be small to facilitate the discovery of good solutions, given the inherent limitations in the resolution of quantum annealers. The primary contribution of this article lies in presenting Ising models tailored for solving the ‐Queens puzzle. The conventional Ising model for this puzzle involves quadratic terms, with the maximum absolute value of coefficients being . Our novel Ising model significantly reduces the number of quadratic terms to only , with a maximum absolute coefficient of 6. Furthermore, we provide embedding results for a quantum annealer D‐Wave Advantage utilizing a Pegasus graph . We succeeded in embedding our novel Ising model for up to the 21‐Queens puzzle, while the conventional Ising model can be embedded only for up to the 14‐Queens puzzle.
Integer factorization, a fundamental problem in computational mathematics, holds critical significance for modern cryptography, particularly in RSA encryption. Traditional approaches such as the number field sieve face exponential complexity limitations, while Shor’s quantum algorithm remains impractical due to hardware constraints. This study proposes a universal algorithm for integer factorization based on Ising machines by transforming the problem into a Quadratic Unconstrained Binary Optimization (QUBO) formulation. The algorithm introduces an optimal reduction formula to optimize the parameter ranges of local field coefficients ( h ) and coupling coefficients ( J ) in the Ising model. Additionally, a non-uniform column grouping method is employed to resolve the conflict between coefficient ranges and carry auxiliary quantum bits(qubits), minimizing the number of auxiliary qubits with minimal compromise on coefficient ranges. Using this approach, we successfully factorized the 22-bit integer 2,093,809 with only 118 qubits. Extrapolating to existing photonic Ising machines with 100,000 qubits, our method demonstrates the potential to factorize 631-bit integers, highlighting its promise for efficient large-scale integer factorization. All results presented in this paper are obtained from simulations on Fixstars Amplify and D-Wave simulators.
Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.
We have developed a framework to convert an arbitrary integer factorization problem to an executable Ising model by first writing it as an optimization function then transforming the k-bit coupling (k ≥ 3) terms to quadratic terms using ancillary variables. Our resource-efficient method uses [Formula: see text] binary variables (qubits) for finding the factors of an integer N. We present how to factorize 15, 143, 59989, and 376289 using 4, 12, 59, and 94 logical qubits, respectively. This method was tested using the D-Wave 2000Q for finding an embedding and determining the prime factors for a given composite number. The method is general and could be used to factor larger integers as the number of available qubits increases, or combined with other ad hoc methods to achieve better performances for specific numbers.
We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph κ-partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.