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.
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.
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.
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.
Quantum computing theory posits that a computer exploiting quantum mechanics can be strictly more powerful than classical models.Several quantum computing devices are under development, but current technology is limited by noise sensitivity.Quantum Annealing is an alternative approach that uses a noisy quantum system to solve a particular optimization problem.Problems such as SAT and MaxSAT need to be encoded to make use of quantum annealers.Encoding SAT and MaxSAT problems while respecting the constraints and limitations of current hardware is a difficult task.This thesis presents an approach to encoding SAT and MaxSAT problems that is able to encode bigger and more interesting problems for quantum annealing.A software implementation and preliminary evaluation of the method are described.
Quantum annealing (QA) uses the principles of quantum mechanics for solving unconstrained optimization problems. Since its initial proposal, there has been much interest in the search for practical problems for which QA has advantage over classical algorithms. Although it is believed that quantum computers cannot in general solve NP-complete problems efficiently, there has been evidence suggesting that effects such as quantum tunneling can bring quantum speedup over classical computation for some problems in NP. In this dissertation, we consider two problems that have both theoretical and practical importance. One is the Set Cover with Pairs problem. The other is the Factorization problem. The Set Cover with Pairs (SCP) problem is a generalization of the Set Cover problem. It requires each element in a set to be covered by at least two objects instead of one as in the Set Cover problem. The SCP problem is believed to be not only NP-hard, but also hard to approximate. In this dissertation, we explicitly construct the Ising Hamiltonians whose ground states encode the solutions of SCP instances. The resulting Ising Hamiltonian has the appealing property that the control precision required for encoding an SCP instance scales only linearly with the number of objects in the covering set. The Integer Factorization problem is of great interest in the quantum community because it is difficult to solve using classical methods and its importance in cryptography. In this dissertation, we propose a general framework for solving factorization problems using quantum annealing, by mapping the framework to an Ising Hamiltonian. We develop several methods to consider the specific requirements such as control precision, spin-spin connection in the current Ising machines. We test the methods on the latest D-Wave 2000Q machine.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.
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.