Suitable Ising problems for quantum annealers need to be formulated such that they respect the specific hardware restrictions and at the same time represent the original problems which shall actually be solved. This requires to find an embedding into the hardware graph and choose the parameters of the embedded Ising problem in accordance with the precision of the machine. We have developed a method to provide provably equivalent embedded Ising problems with optimal parameters for a given arbitrary Ising problem and a corresponding embedding. The thus formulated optimal embedded Ising problems are compared to the state-of-the-art embedding transformation implemented in the D-Wave API. We investigate the Ising formulations in different scenarios to evaluate the performance of both methods. Meanwhile, we study the influence of the gap parameter of the optimality method. Although in theory, any positive value for this gap parameter suffices for the equivalence of the original and the embedded problem, i.e., for separating the feasible embedded solutions from the infeasible ones, the effective gap for practical setups differs. We show that our method provides better embedded Ising problems for certain constellations in terms of a better coefficient structure of the embedded Ising problem and of a larger success probability in finding the optimal solution of the original problem. The latter is the key factor from the users' point of view for using quantum annealers to solve their problems.
Suitable Ising problems for quantum annealers need to be formulated such that they respect the specific hardware restrictions and at the same time represent the original problems which shall actually be solved. This requires to find an embedding into the hardware graph and choose the parameters of the embedded Ising problem in accordance with the precision of the machine. We have developed a method to provide provably equivalent embedded Ising problems with optimal parameters for a given arbitrary Ising problem and a corresponding embedding. The thus formulated optimal embedded Ising problems are compared to the state-of-the-art embedding transformation implemented in the D-Wave API. We investigate the Ising formulations in different scenarios to evaluate the performance of both methods. Meanwhile, we study the influence of the gap parameter of the optimality method. Although in theory, any positive value for this gap parameter suffices for the equivalence of the original and the embedded problem, i.e., for separating the feasible embedded solutions from the infeasible ones, the effective gap for practical setups differs. We show that our method provides better embedded Ising problems for certain constellations in terms of a better coefficient structure of the embedded Ising problem and of a larger success probability in finding the optimal solution of the original problem. The latter is the key factor from the users' point of view for using quantum annealers to solve their problems.
Abstract One of the central applications for quantum annealers is to find the solutions of Ising problems. Suitable Ising problems, however, need to be formulated such that they, on the one hand, respect the specific restrictions of the hardware and, on the other hand, represent the original problems which shall actually be solved. We evaluate sufficient requirements on such an embedded Ising problem analytically and transform them into a linear optimization problem. With an objective function aiming to minimize the maximal absolute problem parameter, the precision issues of the annealers are addressed. Due to the redundancy of several constraints, we can show that the formally exponentially large optimization problem can be reduced and finally solved in polynomial time for the standard embedding setting where the embedded vertices induce trees. This allows to formulate provably equivalent embedded Ising problems in a practical setup.
Abstract Quantum annealing is a type of analog computation that aims to use quantum mechanical fluctuations in search of optimal solutions of QUBO (quadratic unconstrained binary optimization) or, equivalently, Ising problems. Since NP-hard problems can in general be mapped to Ising and QUBO formulations, the quantum annealing paradigm has the potential to help solve various NP-hard problems. Current quantum annealers, such as those manufactured by D-Wave Systems, Inc. have various practical limitations including the size (number of qubits) of the problem that can be solved, the qubit connectivity, and error due to the environment or system calibration, which can reduce the quality of the solutions. Typically, for an arbitrary problem instance, the corresponding QUBO (or Ising) structure will not natively embed onto the available qubit architecture on the quantum chip. Thus, in these cases, a minor embedding of the problem structure onto the device is necessary. However, minor embeddings on these devices do not always make use of the full sparse chip hardware graph, and a large portion of the available qubits stay unused during quantum annealing. In this work, we embed a disjoint random QUBO on the unused parts of the chip alongside the QUBO to be solved, which acts as an indicator of the solution quality of the device over time. Using experiments on three different D-Wave quantum annealers, we demonstrate that (i) long term trends in solution quality exist on the D-Wave device, and (ii) the unused qubits can be used to measure the current level of noise of the quantum system.
Combinatorial optimization problems with a large solution space are difficult to solve just using von Neumann computers. Ising machines or annealing machines have been developed to tackle these problems as a promising Non-von Neumann computer. In order to use these annealing machines, every combinatorial optimization problem is mapped onto the physical Ising model, which consists of spins, interactions between them, and their external magnetic fields. Then the annealing machines operate so as to search the ground state of the physical Ising model, which corresponds to the optimal solution of the original combinatorial optimization problem. A combinatorial optimization problem can be firstly described by an ideal fully-connected Ising model but it is very hard to embed it onto the physical Ising model topology of a particular annealing machine, which causes one of the largest issues in annealing machines. In this paper, we propose a fully-connected Ising model embedding method targeting for CMOS annealing machine. The key idea is that the proposed method replicates every logical spin in a fully-connected Ising model and embeds each logical spin onto the physical spins with the same chain length. Experimental results through an actual combinatorial problem show that the proposed method obtains spin embeddings superior to the conventional de facto standard method, in terms of the embedding time and the probability of obtaining a feasible solution.
This study addresses the minor-embedding problem, which involves mapping the variables of an Ising model onto a quantum annealing processor. The primary motivation stems from the observed performance disparity of quantum annealers when solving problems suited to the processor's architecture versus those with non-hardware-native topologies. Our research has two main objectives: i) to analyze the impact of embedding quality on the performance of D-Wave Systems quantum annealers, and ii) to evaluate the quality of the embeddings generated by Minorminer, the standard minor-embedding technique in the quantum annealing literature, provided by D-Wave. Regarding the first objective, our experiments reveal a clear correlation between the average chain length of embeddings and the relative errors of the solutions sampled. This underscores the critical influence of embedding quality on quantum annealing performance. For the second objective, we evaluate Minorminer's embedding capabilities, the quality and robustness of its embeddings, and its execution-time performance on Erdös-Rényi graphs. We also compare its performance with Clique Embedding, another algorithm developed by D-Wave, which is deterministic and designed to embed fully connected Ising models into quantum annealing processors, serving as a worst-case scenario. The results demonstrate that there is significant room for improvement for Minorminer, suggesting that more effective embedding strategies could lead to meaningful gains in quantum annealing performance.
Quantum annealing is a heuristic algorithm that solves combinatorial optimization problems, and D-Wave Systems Inc. has developed hardware implementation of this algorithm. However, in general, we cannot embed all the logical variables of a large-scale problem, since the number of available qubits is limited. In order to handle a large problem, qbsolv has been proposed as a method for partitioning the original large problem into subproblems that are embeddable in the D-Wave quantum annealer, and it then iteratively optimizes the subproblems using the quantum annealer. Multiple logical variables in the subproblem are simultaneously updated in this iterative solver, and using this approach we expect to obtain better solutions than can be obtained by conventional local search algorithms. Although embedding of large subproblems is essential for improving the accuracy of solutions in this scheme, the size of the subproblems are small in qbsolv since the subproblems are basically embedded by using an embedding of a complete graph even for sparse problem graphs. This means that the resource of the D-Wave quantum annealer is not exploited efficiently. In this paper, we propose a fast algorithm for embedding larger subproblems, and we show that better solutions are obtained efficiently by embedding larger subproblems.
Quantum annealing provides a promising route for the development of quantum optimization devices, but the usefulness of such devices will be limited in part by the range of implementable problems as dictated by hardware constraints. To overcome constraints imposed by restricted connectivity between qubits, a larger set of interactions can be approximated using minor embedding techniques whereby several physical qubits are used to represent a single logical qubit. However, minor embedding introduces new types of errors due to its approximate nature. We introduce and study quantum annealing correction schemes designed to improve the performance of quantum annealers in conjunction with minor embedding, thus leading to a hybrid scheme defined over an encoded graph. We argue that this scheme can be efficiently decoded using an energy minimization technique provided the density of errors does not exceed the per-site percolation threshold of the encoded graph. We test the hybrid scheme using a D-Wave Two processor on problems for which the encoded graph is a two-level grid and the Ising model is known to be NP-hard. The problems we consider are frustrated Ising model problem instances with ``planted'' (a priori known) solutions. Applied in conjunction with optimized energy penalties and decoding techniques, we find that this approach enables the quantum annealer to solve minor embedded instances with significantly higher success probability than it would without error correction. Our work demonstrates that quantum annealing correction can and should be used to improve the robustness of quantum annealing not only for natively embeddable problems but also when minor embedding is used to extend the connectivity of physical devices.