The D-wave quantum annealer requires embedding with ferromagnetic (FM) chains connected by several qubits, because it cannot capture exact long-range coupling between qubits, and retains the specific architecture that depends on the hardware type. Therefore, determination of the chain strength
Jc required to sustain FM order of qubits in the chains is crucial for the accuracy of quantum annealing. In this study, we devise combinatorial optimization problems with ordered and disordered qubits for various embeddings to predict appropriate
Jc values. We analyze the energy interval
Δs and
Δc between ground and first excited states in the combinatorial optimization problems without and with chains respectively, using the exact approach. We also measure the probability
p that the exact ground energy per site
Eg is observed in many simulated annealing shots. We demonstrate that the determination of
Jc is increasingly sensitive with growing disorder of qubits in the combinatorial optimization problems. In addition, the values of appropriate
Jc, where the values of
p are at a maximum, increase with decreasing
Δs. Finally, the appropriate value of
Jc is shown to be observed at approximately
Δc/Δs=0.25 and
2.1Eg in the ordered and disordered qubits, respectively.
Abstract Solving optimization problems on quantum annealers (QA) usually requires each variable of the problem to be represented by a connected set of qubits called a logical qubit or a chain. Chain weights, in the form of ferromagnetic coupling between the chain qubits, are applied so that the physical qubits in a chain favor taking the same value in low energy samples. Assigning a good chain-strength value is crucial for the ability of QA to solve hard problems, but there are no general methods for computing such a value and, even if an optimal value is found, it may still not be suitable by being too large for accurate annealing results. In this paper, we propose an optimization-based approach for producing suitable logical qubits representations that results in smaller chain weights and show that the resulting optimization problem can be successfully solved using the augmented Lagrangian method. Experiments on the D-Wave Advantage system and the maximum clique problem on random graphs show that our approach outperforms both the default D-Wave method for chain-strength assignment as well as the quadratic penalty method.
With the current progress of quantum computing, quantum annealing is being introduced as a powerful method to solve hard computational problems. In this paper, we study the potential capability of quantum annealing in solving the phase unwrapping problem, an instance of hard computational problems. To solve the phase unwrapping problem using quantum annealing, we deploy the D-Wave Advantage machine which is currently the largest available quantum annealer. The structure of this machine, however, is not compatible with our problem graph structure. Consequently, the problem graph needs to be mapped onto the target (Pegasus) graph, and this embedding significantly affects the quality of the results. Based on our experiment and also D-Wave's reports, the lower chain lengths can result in a better performance of quantum annealing. In this paper, we propose a new embedding algorithm that has the lowest possible chain length for embedding the graph of the phase unwrapping problem onto the Pegasus graph. The obtained results using this embedding strongly outperform the results of Auto-embedding provided by D-Wave. Besides the phase unwrapping problem, this embedding can be used to embed any subset of our problem graph to the Pegasus graph.
Quantum annealing is a quantum algorithm for computing solutions to combinatorial optimization problems. This study proposes a method for minor embedding optimization problems onto sparse quantum annealing hardware graphs called 4-clique network minor embedding. This method is in contrast to the standard minor embedding technique of using a path of linearly connected qubits in order to represent a logical variable state. The 4-clique minor embedding is possible on Pegasus graph connectivity, which is the native hardware graph for some of the current D-Wave quantum annealers. The Pegasus hardware graph contains many cliques of size 4, making it possible to form a graph composed entirely of paths of connected 4-cliques on which a problem can be minor-embedded. The 4-clique chains come at the cost of additional qubit usage on the hardware graph, but they allow for stronger coupling within each chain, thereby increasing chain integrity, reducing chain breaks, and allow for greater usage of the available energy scale for programming logical problem coefficients on current quantum annealers. The 4-clique minor embedding technique is compared with the standard linear path minor embedding with experiments on two D-Wave quantum annealing processors with Pegasus hardware graphs. We show proof-of-concept experiments where the 4-clique minor embeddings can use weak chain strengths while successfully carrying out the computation of minimizing random all-to-all spin glass problem instances. Published by the American Physical Society 2024
The D-Wave quantum annealers make it possible to obtain high quality solutions of NP-hard problems by mapping a problem in a QUBO (quadratic unconstrained binary optimization) or Ising form to the physical qubit connectivity structure on the D-Wave chip. However, the latter is restricted in that only a fraction of all pairwise couplers between physical qubits exists. Modeling the connectivity structure of a given problem instance thus necessitates the computation of a minor embedding of the variables in the problem specification onto the logical qubits, which consist of several physical qubits "chained" together to act as a logical one. After annealing, it is however not guaranteed that all chained qubits get the same value (-1 or +1 for an Ising model, and 0 or 1 for a QUBO), and several approaches exist to assign a final value to each logical qubit (a process called "unembedding"). In this work, we present tailored unembedding techniques for four important NP-hard problems: the Maximum Clique, Maximum Cut, Minimum Vertex Cover, and Graph Partitioning problems. Our techniques are simple and yet make use of structural properties of the problem being solved. Using Erdös-Rényi random graphs as inputs, we compare our unembedding techniques to three popular ones (majority vote, random weighting, and minimize energy). We demonstrate that our proposed algorithms outperform the currently available ones in that they yield solutions of better quality, while being computationally equally efficient.
Quantum annealing (QA) is a promising optimization technique used to find global optimal solution of a combinatorial optimization problem by leveraging quantum fluctuations. In QA, the problem being solved is mapped onto the quantum processing unit (QPU) composed of qubits through a procedure called minor-embedding. The qubits are connected by a network of couplers, which determine the strength of the interactions between the qubits. The strength of the couplers that connect qubits within a chain is often referred to as the chain strength. The appropriate balance of chain strength is equally imperative in enabling the qubits to interact with one another in a way that is strong enough to obtain the optimal solution, but not excessively strong so as not to bias the original problem terms. To this end, we address the problem of identifying the optimal chain strength through the utilization of Path Integral Monte Carlo (PIMC) quantum simulation algorithm. The results indicate that our judicious choice of chain strength parameter facilitates enhancements in quantum annealer performance and solution quality, thereby paving the way for QA to compete with, or potentially outperform, classical optimization algorithms.