Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2209.12166

Determination of Chain Strength induced by Embedding in D-Wave Quantum Annealer

Hunpyo Lee

Published Sep 25, 2022• 4 citations
arXivHTMLPDF

Abstract

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 $J_c$ 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 $J_c$ 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 $E_g$ is observed in many simulated annealing shots. We demonstrate that the determination of $J_c$ is increasingly sensitive with growing disorder of qubits in the combinatorial optimization problems. In addition, the values of appropriate $J_c$, where the values of $p$ are at a maximum, increase with decreasing $Δ_s$. Finally, the appropriate value of $J_c$ is shown to be observed at approximately $Δ_c/Δ_s=0.25$ and $2.1 E_g$ in the ordered and disordered qubits, respectively.

DOI
10.48550/arxiv.2209.12166

Related papers

Determination of optimal chain coupling made by embedding in D-wave quantum annealer

Hayun Park, Hunpyo Lee

The qubits in a D-wave quantum annealer (D-wave QA) are designed on a Pegasus graph that is different from the structure of a combinatorial optimization problem. This situation requires embedding with the chains connected by ferromagnetic coupling Jc between the qubits. Weak and strong Jc values induce chain breaking and enforcement of chain energy, which reduce the accuracy of quantum annealing (QA) measurements, respectively. In addition, we confirmed that even though the D-wave Ocean package provides a default coupling Jcdefault, it is not an optimal coupling Jcoptimal that maximizes the possible correct rate of QA measurements. In this paper, we present an algorithm how Jcoptimal with the maximum probability p for observing the possible lowest energy is determined. Finally, we confirm that the extracted Jcoptimal shows much better p than Jcdefault in QA measurements of various parameters of frustrated and fully connected combinatorial optimization problems. The open code is available in https://github.com/HunpyoLee/OptimizeChainStrength.

arXiv:2406.03364•AVS Quantum Science•Jul 18, 2024•3 citations

Logical qubit implementation for quantum annealing: augmented Lagrangian approach

Hristo N. Djidjev

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.

arXiv:2301.12393•Quantum Science and Technology•Apr 28, 2023•7 citations

Benchmarking Chain Strength: An Optimal Approach for Quantum Annealing

Thinh V. Le, Manh V. Nguyen, Tu N. Nguyen +3 more

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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•4 citations

Benchmarking quantum annealing with maximum cardinality matching problems

Daniel Vert, Madita Willsch, Berat Yenilen +3 more

We benchmark Quantum Annealing (QA) vs. Simulated Annealing (SA) with a focus on the impact of the embedding of problems onto the different topologies of the D-Wave quantum annealers. The series of problems we study are especially designed instances of the maximum cardinality matching problem that are easy to solve classically but difficult for SA and, as found experimentally, not easy for QA either. In addition to using several D-Wave processors, we simulate the QA process by numerically solving the time-dependent Schrödinger equation. We find that the embedded problems can be significantly more difficult than the unembedded problems, and some parameters, such as the chain strength, can be very impactful for finding the optimal solution. Thus, finding a good embedding and optimal parameter values can improve the results considerably. Interestingly, we find that although SA succeeds for the unembedded problems, the SA results obtained for the embedded version scale quite poorly in comparison with what we can achieve on the D-Wave quantum annealers.

Frontiers in Computer Science•Jun 5, 2024•7 citations

Frustrated Ising Model on D-wave Quantum Annealing Machine

Hayun Park, Hunpyo Lee

We study the frustrated Ising model on the two-dimensional $L \times L$ square lattice with ferromagnetic (FM) nearest-neighbor and antiferromagnetic diagonal-neighbor interactions using the D-wave quantum annealing machine (D-QAM) with 5000+ qubits composed on structure of the Pegasus graph. As the former Monte Carlo and mean field results, we find the FM to stripe order phase transition, through observations of the magnetization $M$, energy, magnetic susceptibility and structure factor. We also analyze probability which occurs any $M$ at a given interaction for many quantum annealing shots to estimate the shape of objective function $f$. The only one value of $M$ with specific phase is observed in the regions far from phase transition for many quantum annealing shots, while several values of $M$ with different possibilities are appeared in the regimes of phase transition. We guess that $f$ in the regimes of phase transition retains the multi-modal structure with several local minimums, due to the strong degeneracies caused by frustrations. Finally, we discuss fail of the quantum annealing simulations, through analysis of the number of the chains, defined as the same variable with $N$-qubits, as a function of $L$.

arXiv:2110.05124•Journal of the Physical Society of Japan•Jun 2, 2022•12 citations

Comparing three generations of D-Wave quantum annealers for minor embedded combinatorial optimization problems

Elijah Pelofske

Abstract Quantum annealing (QA) is a novel type of analog computation that aims to use quantum mechanical fluctuations to search for optimal solutions of Ising problems. QA in the transverse Ising model, implemented on D-Wave quantum processing units, are available as cloud computing resources. In this study we report concise benchmarks across three generations of D-Wave quantum annealers, consisting of four different devices, for the NP-hard discrete combinatorial optimization problems unweighted maximum clique and unweighted maximum cut on random graphs. The Ising, or equivalently quadratic unconstrained binary optimization, formulation of these problems do not require auxiliary variables for order reduction, and their overall structure and weights are not highly variable, which makes these problems simple test cases to understand the sampling capability of current D-Wave quantum annealers. All-to-all minor embeddings of size 52, with relatively uniform chain lengths, are used for a direct comparison across the Chimera, Pegasus, and Zephyr device topologies. A grid-search over annealing times and the minor embedding chain strengths is performed in order to determine the level of reasonable performance for each device and problem type. Experiment metrics that are reported are approximation ratios for non-broken chain samples, chain break proportions, and time-to-solution for the maximum clique problem instances. How fairly the quantum annealers sample optimal maximum cliques, for instances which contain multiple maximum cliques, is quantified using entropy of the measured ground state distributions. The newest generation of quantum annealing hardware, which has a Zephyr hardware connectivity, performed the best overall with respect to approximation ratios and chain break frequencies.

arXiv:2301.03009•Quantum Science and Technology•Jan 30, 2025•28 citations
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 JcJ_cJc​ 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 JcJ_cJc​ values. We analyze the energy interval ΔsΔ_sΔs​ and ΔcΔ_cΔ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 ppp that the exact ground energy per site EgE_gEg​ is observed in many simulated annealing shots. We demonstrate that the determination of JcJ_cJc​ is increasingly sensitive with growing disorder of qubits in the combinatorial optimization problems. In addition, the values of appropriate JcJ_cJc​, where the values of ppp are at a maximum, increase with decreasing ΔsΔ_sΔs​. Finally, the appropriate value of JcJ_cJc​ is shown to be observed at approximately Δc/Δs=0.25Δ_c/Δ_s=0.25Δc​/Δs​=0.25 and 2.1Eg2.1 E_g2.1Eg​ in the ordered and disordered qubits, respectively.
The qubits in a D-wave quantum annealer (D-wave QA) are designed on a Pegasus graph that is different from the structure of a combinatorial optimization problem. This situation requires embedding with the chains connected by ferromagnetic coupling Jc between the qubits. Weak and strong Jc values induce chain breaking and enforcement of chain energy, which reduce the accuracy of quantum annealing (QA) measurements, respectively. In addition, we confirmed that even though the D-wave Ocean package provides a default coupling Jcdefault, it is not an optimal coupling Jcoptimal that maximizes the possible correct rate of QA measurements. In this paper, we present an algorithm how Jcoptimal with the maximum probability p for observing the possible lowest energy is determined. Finally, we confirm that the extracted Jcoptimal shows much better p than Jcdefault in QA measurements of various parameters of frustrated and fully connected combinatorial optimization problems. The open code is available in https://github.com/HunpyoLee/OptimizeChainStrength.
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.
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.
We benchmark Quantum Annealing (QA) vs. Simulated Annealing (SA) with a focus on the impact of the embedding of problems onto the different topologies of the D-Wave quantum annealers. The series of problems we study are especially designed instances of the maximum cardinality matching problem that are easy to solve classically but difficult for SA and, as found experimentally, not easy for QA either. In addition to using several D-Wave processors, we simulate the QA process by numerically solving the time-dependent Schrödinger equation. We find that the embedded problems can be significantly more difficult than the unembedded problems, and some parameters, such as the chain strength, can be very impactful for finding the optimal solution. Thus, finding a good embedding and optimal parameter values can improve the results considerably. Interestingly, we find that although SA succeeds for the unembedded problems, the SA results obtained for the embedded version scale quite poorly in comparison with what we can achieve on the D-Wave quantum annealers.
We study the frustrated Ising model on the two-dimensional L×LL \times LL×L square lattice with ferromagnetic (FM) nearest-neighbor and antiferromagnetic diagonal-neighbor interactions using the D-wave quantum annealing machine (D-QAM) with 5000+ qubits composed on structure of the Pegasus graph. As the former Monte Carlo and mean field results, we find the FM to stripe order phase transition, through observations of the magnetization MMM, energy, magnetic susceptibility and structure factor. We also analyze probability which occurs any MMM at a given interaction for many quantum annealing shots to estimate the shape of objective function fff. The only one value of MMM with specific phase is observed in the regions far from phase transition for many quantum annealing shots, while several values of MMM with different possibilities are appeared in the regimes of phase transition. We guess that fff in the regimes of phase transition retains the multi-modal structure with several local minimums, due to the strong degeneracies caused by frustrations. Finally, we discuss fail of the quantum annealing simulations, through analysis of the number of the chains, defined as the same variable with NNN-qubits, as a function of LLL.
Abstract Quantum annealing (QA) is a novel type of analog computation that aims to use quantum mechanical fluctuations to search for optimal solutions of Ising problems. QA in the transverse Ising model, implemented on D-Wave quantum processing units, are available as cloud computing resources. In this study we report concise benchmarks across three generations of D-Wave quantum annealers, consisting of four different devices, for the NP-hard discrete combinatorial optimization problems unweighted maximum clique and unweighted maximum cut on random graphs. The Ising, or equivalently quadratic unconstrained binary optimization, formulation of these problems do not require auxiliary variables for order reduction, and their overall structure and weights are not highly variable, which makes these problems simple test cases to understand the sampling capability of current D-Wave quantum annealers. All-to-all minor embeddings of size 52, with relatively uniform chain lengths, are used for a direct comparison across the Chimera, Pegasus, and Zephyr device topologies. A grid-search over annealing times and the minor embedding chain strengths is performed in order to determine the level of reasonable performance for each device and problem type. Experiment metrics that are reported are approximation ratios for non-broken chain samples, chain break proportions, and time-to-solution for the maximum clique problem instances. How fairly the quantum annealers sample optimal maximum cliques, for instances which contain multiple maximum cliques, is quantified using entropy of the measured ground state distributions. The newest generation of quantum annealing hardware, which has a Zephyr hardware connectivity, performed the best overall with respect to approximation ratios and chain break frequencies.