Optimal parameter settings for application problems embedded into hardware graphs is key to practical quantum annealers (QAs). Embedding chains typically crop up as harmful Griffiths phases but can be used as a resource as we show here: to balance out singularities in the logical problem, changing its universality class. A smart choice of embedding parameters reduces annealing times for random Ising chain from $O(exp[c\sqrt{N}])$ to $O({N}^{2})$. Dramatic reduction in time-to-solution for QAs is confirmed by numerics, for which we developed a custom integrator to overcome convergence issues.
Optimal parameter settings for application problems embedded into hardware graphs is key to practical quantum annealers (QAs). Embedding chains typically crop up as harmful Griffiths phases but can be used as a resource as we show here: to balance out singularities in the logical problem, changing its universality class. A smart choice of embedding parameters reduces annealing times for random Ising chain from O(exp[cN]) to O(N2). Dramatic reduction in time-to-solution for QAs is confirmed by numerics, for which we developed a custom integrator to overcome convergence issues.
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.
In order to treat all-to-all-connected quadratic binary optimization problems (QUBOs) with hardware quantum annealers, an embedding of the original problem is required due to the sparsity of the topology of the hardware.The embedding of fully connected graphs-typically found in industrial applications-incurs a quadratic space overhead and thus a significant overhead in the time to solution.Here, we investigate this embedding penalty of established planar embedding schemes such as square-lattice embedding, embedding on a chimera lattice, and the Lechner-Hauke-Zoller scheme, using simulated quantum annealing on classical hardware.Large-scale quantum Monte Carlo simulation suggests a polynomial time-to-solution overhead.Our results demonstrate that standard analog quantum annealing hardware is at a disadvantage in comparison to classical digital annealers, as well as gate-model quantum annealers, and could also serve as a benchmark for improvements of the standard quantum annealing protocol.
Prior work showed the efficacy of pausing midanneal: such a pause improved the probability of success by orders of magnitude in a class of native problem instances and improved the time to solution in a class of embedded problem instances. A physics-based picture provides qualitative suggestions for where pausing midanneal is effective, for the interplay between annealing schedule parameters and other annealing properties and parameters such as embedding size and strength of the ferromagnetic coupling ∣JF∣, and for the conditions under which pausing can improve the time to solution. Here, through demonstrations on an updated annealing architecture that has higher connectivity than previous annealers, and on multiple embedded problem classes, we are able to confirm various aspects of this picture. We demonstrate the robustness of the optimal pause parameters across platforms and problem classes, explore how to set ∣JF∣ to optimize performance in different scenarios, and provide empirical evidence that short pauses trump longer overall annealing times in time to solution. We also identify the number of different coefficients in a problem as a predictor of problem hardness, and explore its interplay with the optimal ∣JF∣ and embedding size. Based on these results we are able to present qualitative guidelines for parameter setting in quantum annealers.
Minor embedding is essential for mapping largescale combinatorial problems onto quantum annealers, particularly in quantum machine learning and optimization. This work presents an optimized, universal minor-embedding framework that efficiently accommodates complete bipartite graphs onto the hardware topology of quantum annealers. By leveraging the inherent topographical periodicity of the physical quantum adiabatic annealer processor, our method systematically reduces qubit chain lengths, resulting in enhanced stability, computational efficiency, and scalability of quantum annealing. We benchmark our embedding framework against Minorminer, the default heuristic embedding algorithm, for the Pegasus topology, demonstrating that our approach significantly improves embedding quality. Our empirical results show a 99.98% reduction in embedding time for a 120 x 120 complete bipartite graphs. Additionally, our method eliminates long qubit chains, which primarily cause decoherence and computational errors in quantum annealing. These findings advance the scalability of quantum embeddings, particularly for quantum generative models, anomaly detection, and large-scale optimization tasks. Our results establish a foundation for integrating efficient quantum-classical hybrid solutions, paving the way for practical applications in quantum-enhanced machine learning and optimization.
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.