Quantum annealing is a generic solver for optimization problems that uses fictitious quantum fluctuation. The most groundbreaking progress in the research field of quantum annealing is its hardware implementation, i.e., the so-called quantum annealer, using artificial spins. However, the connectivity between the artificial spins is sparse and limited on a special network known as the chimera graph. Several embedding techniques have been proposed, but the number of logical spins, which represents the optimization problems to be solved, is drastically reduced. In particular, an optimization problem including fully or even partly connected spins suffers from low embeddable size on the chimera graph. In the present study, we propose an alternative approach to solve a large-scale optimization problem on the chimera graph via a well-known method in statistical mechanics called the Hubbard-Stratonovich transformation or its variants. The proposed method can be used to deal with a fully connected Ising model without embedding on the chimera graph and leads to nontrivial results of the optimization problem. We tested the proposed method with a number of partition problems involving solving linear equations and the traffic flow optimization problem in Sendai and Kyoto cities in Japan.
Quantum annealing is a generic solver for optimization problems that uses fictitious quantum fluctuation. The most groundbreaking progress in the research field of quantum annealing is its hardware implementation, i.e., the so-called quantum annealer, using artificial spins. However, the connectivity between the artificial spins is sparse and limited on a special network known as the chimera graph. Several embedding techniques have been proposed, but the number of logical spins, which represents the optimization problems to be solved, is drastically reduced. In particular, an optimization problem including fully or even partly connected spins suffers from low embeddable size on the chimera graph. In the present study, we propose an alternative approach to solve a large-scale optimization problem on the chimera graph via a well-known method in statistical mechanics called the Hubbard-Stratonovich transformation or its variants. The proposed method can be used to deal with a fully connected Ising model without embedding on the chimera graph and leads to nontrivial results of the optimization problem. We tested the proposed method with a number of partition problems involving solving linear equations and the traffic flow optimization problem in Sendai and Kyoto cities in Japan.
Quantum annealing is a generic solver for combinatorial optimization problems that utilizes quantum fluctuations. Recently, there has been extensive research applying quantum annealers, which are hardware implementations of quantum annealing. Since quantum annealers can only handle quadratic unconstrained binary optimization problems, to solve constrained combinatorial optimization problems using quantum annealers, the constraints must be incorporated into the objective function. One such technique is the Ohzeki method, which employs a Hubbard-Stratonovich transformation to relax equality constraints, and its effectiveness for large-scale problems has been demonstrated numerically. This study applies the Ohzeki method to combinatorial optimization problems with inequality constraints. We show that inequality constraints can be relaxed into a similar objective function through statistical mechanics calculations similar to those for equality constraints. In addition, we evaluate the performance of this method in a typical inequality-constrained combinatorial optimization problem, the quadratic knapsack problem.
This paper investigates the possibility of using an analog quantum computer as commercialized by D-Wave to solve large QUBO problems by means of a single invocation of the quantum annealer. Indeed this machine solves a spin glass problem with programmable coefficients but subject to quite strong topology restrictions on the set of non-zero coefficients. Rather than mapping problem variables onto multiple qbits, an approach which requires many invocations of the annealer to solve small size problems, it is tempting to investigate the existence of sparse relaxations compliant with the qbits interconnection topology of the machine, hence solvable in one invocation of the annealing oracle, but still providing good-quality solutions to the original problem. This paper provides an experimental setup which aims to determine whether or not such convenient relaxations do exist or, rather, are easy to find. Our experiments suggest that it is not the case and, therefore, that solving even moderate size arbitrary problems with a single call to a quantum annealer is not possible at least within the constraints of the so-called Chimera topology. We conclude the paper with a number of perspectives that this results imply on the design of heuristics taking profit of a quantum annealing oracle to solve large scale problems.
Quantum annealing is a promising algorithm for solving combinatorial optimization problems. However, various hardware restrictions significantly impede its efficient performance. Size-reduction methods provide an effective approach to addressing large-scale problems but often introduce additional difficulties. A notable hardware restriction is that quantum annealing can handle only a limited number of decision variables, compared to the size of the problem. Moreover, when employing size-reduction methods, the interactions and local magnetic fields in the Ising model — used to represent the combinatorial optimization problem — can become excessively large, making them difficult to implement on hardware. Although prior studies suggest that energy rescaling impacts the performance of quantum annealing, its interplay with size-reduction methods remains unexplored. This study examines the relationship between fixing spins, a promising size-reduction method, and the effects of energy rescaling. Numerical simulations and experiments conducted on a quantum annealer demonstrate that the fixing spins method enhances quantum annealing performance while preserving the spin-chain embedding for a homogeneous, fully connected ferromagnetic Ising model.
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.
Quantum annealing is a promising approach to solving a diversity of classical optimization problems across different fields, but real-world problems are often represented by densely connected graphs, which cannot be directly implemented in hardware in a scalable way. This work overcomes this limitation by presenting a very sparse architecture that results in effective dense connectivities. This result will have an impact on the engineering challenge of building large-scale quantum annealing devices that can solve practical optimization problems in several industry sectors, such as logistics, energy, or finance.
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.