arXiv:2502.01008 · Journal of the Physical Society of Japan

Impact of Fixing Spins in a Quantum Annealer with Energy Rescaling

T Hattori, Hirotaka Irie, Tadashi Kadowaki, Shu Tanaka

Published Jun 11, 2025• 3 citations

Abstract

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.

DOI: 10.7566/jpsj.94.074001

Related papers

Advantages of Fixing Spins in Quantum Annealing

T Hattori, Hirotaka Irie, Tadashi Kadowaki +1 more

Quantum annealing can efficiently obtain solutions to combinatorial optimization problems. Size-reduction methods are used to treat large-scale combinatorial optimization problems that cannot be input directly into a quantum annealer because of its size limitation. Various size-reduction methods using fixing spins have been proposed as quantum-classical hybrid methods to obtain solutions. However, the high performance of these hybrid methods is yet to be clearly elucidated. In this study, we adopted a parameterized fixing spins method to verify the effects of fixing spins. The results revealed that setting the appropriate number of spins of the subproblem is crucial for obtaining a satisfactory solution, and the energy gap expansion is confirmed after fixing spins.

arXiv:2410.21924Journal of the Physical Society of JapanDec 20, 20244 citations

Spin-Variable Reduction Method for Handling Linear Equality Constraints in Ising Machines

Tatsuhiko Shirai, Nozomu Togawa

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.

IEEE Transactions on ComputersJan 24, 202311 citations

Effectiveness of Hybrid Optimization Method for Quantum Annealing Machines

Shuta Kikuchi, Nozomu Togawa, Shu Tanaka

To enhance the performance of quantum annealing machines, several methods have been proposed to reduce the number of spins by fixing spin values through preprocessing. We proposed a hybrid optimization method that combines a simulated annealing (SA)-based non-quantum-type Ising machine with a quantum annealing machine. However, its applicability remains unclear. Therefore, we evaluated the performance of the hybrid method on large-size Ising models and analyzed its characteristics. The results indicate that the hybrid method improves upon solutions obtained by the preprocessing SA, even if the Ising models cannot be embedded in the quantum annealing machine. We analyzed the method from three perspectives: preprocessing, spin-fixed sub-Ising model generation method, and the accuracy of the quantum annealing machine. From the viewpoint of the minimum energy gap, we found that solving the sub-Ising model with a quantum annealing machine results in a higher solution accuracy than solving the original Ising model. Additionally, we demonstrated that the number of fixed spins and the accuracy of the quantum annealing machine affect the dependency of the solution accuracy on the sub-Ising model size.

arXiv:2507.15544Jul 21, 20250 citations

Physical Properties of Error Reduction Algorithms for Ising Machines

Kanta Hino, Shu Tanaka

Ising machines are expected to be dedicated computers that are capable of efficiently searching for good solutions to combinatorial optimization problems. When solving combinatorial optimization problems with an Ising machine, the objective function and constraints of the combinatorial optimization problems are expressed using the Ising model. Then, the low-energy states of the Ising model are searched by the internal algorithms of Ising machines. Typical internal algorithms are Simulated Annealing (SA) and Quantum Annealing (QA). Both algorithms exhibit stochastic behavior, so the final solution may contain errors. Therefore, it is an essential issue in the field of Ising machines to reduce errors as much as possible. A previous study proposed an error reduction method for QA machines, namely the Quantum Annealing Correction (QAC) model. This method reduces error by introducing penalty interaction and performing a specific decoding method. Building on these valuable insights, we proposed an alternative error reduction method, the stacked model. To verify the effectiveness, we examined on the relationship between the penalty interaction and the success probability of the QAC model and the stacked model on SA. The obtained results differ from the facts observed in QA. In summary, a decoding method different from the one considered effective in QA was found to be effective in SA. This result suggests that when considering an appropriate error reduction method, it is necessary to consider the internal algorithm of the Ising machine.

IEEE International Conference on Quantum Computing and Engineering (QCE)Sep 15, 20242 citations

Hybrid Optimization Method Using Simulated-Annealing-Based Ising Machine and Quantum Annealer

Shuta Kikuchi, Nozomu Togawa, Shu Tanaka

Ising machines have the potential to realize fast and highly accurate solvers for combinatorial optimization problems. They are classified based on their internal algorithms. Examples include simulated-annealing-based Ising machines (non-quantum-type Ising machines) and quantum-annealing-based Ising machines (quantum annealers). Herein we propose a hybrid optimization method, which utilizes the advantages of both types. In this hybrid optimization method, the preprocessing step is performed by solving the non-quantum-annealing Ising machine multiple times. Then sub-Ising models with a reduced size by spin fixing are solved using a quantum annealer. The performance of the hybrid optimization method is evaluated via simulations using Simulated Annealing (SA) as a non-quantum-type Ising machine and D-Wave Advantage as a quantum annealer. Additionally, we investigate the parameter dependence of the proposed hybrid optimization method. The hybrid optimization method outperforms the preprocessing SA and the quantum annealing machine alone in fully connected random Ising models.

arXiv:2306.06589Journal of the Physical Society of JapanNov 10, 20238 citations

Quantum Annealing for Combinatorial Optimization: Foundations, Architectures, Benchmarks, and Emerging Directions

Rudraksh Sharma, Ravi Katukam, Arjun Nagulapally

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.

quant-pharXiv:2602.03101Feb 4, 20260 citations