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.05648 · Quantum Science and Technology

Noise dynamics of quantum annealers: estimating the effective noise using idle qubits

Elijah Pelofske, Georg Hahn, Hristo N. Djidjev

Published Apr 11, 2023• 12 citations
arXivHTMLPDF

Abstract

Abstract Quantum annealing is a type of analog computation that aims to use quantum mechanical fluctuations in search of optimal solutions of QUBO (quadratic unconstrained binary optimization) or, equivalently, Ising problems. Since NP-hard problems can in general be mapped to Ising and QUBO formulations, the quantum annealing paradigm has the potential to help solve various NP-hard problems. Current quantum annealers, such as those manufactured by D-Wave Systems, Inc. have various practical limitations including the size (number of qubits) of the problem that can be solved, the qubit connectivity, and error due to the environment or system calibration, which can reduce the quality of the solutions. Typically, for an arbitrary problem instance, the corresponding QUBO (or Ising) structure will not natively embed onto the available qubit architecture on the quantum chip. Thus, in these cases, a minor embedding of the problem structure onto the device is necessary. However, minor embeddings on these devices do not always make use of the full sparse chip hardware graph, and a large portion of the available qubits stay unused during quantum annealing. In this work, we embed a disjoint random QUBO on the unused parts of the chip alongside the QUBO to be solved, which acts as an indicator of the solution quality of the device over time. Using experiments on three different D-Wave quantum annealers, we demonstrate that (i) long term trends in solution quality exist on the D-Wave device, and (ii) the unused qubits can be used to measure the current level of noise of the quantum system.

DOI
10.1088/2058-9565/accbe6

Related papers

Parallel quantum annealing

Elijah Pelofske, Georg Hahn, Hristo N. Djidjev

Quantum annealers of D-Wave Systems, Inc., offer an efficient way to compute high quality solutions of NP-hard problems. This is done by mapping a problem onto the physical qubits of the quantum chip, from which a solution is obtained after quantum annealing. However, since the connectivity of the physical qubits on the chip is limited, a minor embedding of the problem structure onto the chip is required. In this process, and especially for smaller problems, many qubits will stay unused. We propose a novel method, called parallel quantum annealing, to make better use of available qubits, wherein either the same or several independent problems are solved in the same annealing cycle of a quantum annealer, assuming enough physical qubits are available to embed more than one problem. Although the individual solution quality may be slightly decreased when solving several problems in parallel (as opposed to solving each problem separately), we demonstrate that our method may give dramatic speed-ups in terms of the Time-To-Solution (TTS) metric for solving instances of the Maximum Clique problem when compared to solving each problem sequentially on the quantum annealer. Additionally, we show that solving a single Maximum Clique problem using parallel quantum annealing reduces the TTS significantly.

arXiv:2111.05995•Scientific Reports•Mar 16, 2022•55 citations

Advanced unembedding techniques for quantum annealers

Elijah Pelofske, Georg Hahn, Hristo N. Djidjev

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.

arXiv:2009.05028•IEEE International Conference on Rebooting Computing (ICRC)•Dec 1, 2020•10 citations

Towards Quantum Computing: Solving Satisfiability Problem by Quantum Annealing

Juexiao Su

To date, conventional computers have never been able to efficiently handle certain tasks, where the number of computation steps is likely to blow up as the problem size increases. As an emerging technology and new computing paradigm, quantum computing has a great potential to tackle those hard tasks efficiently. Among all the existing quantum computation models, quantum annealing has drawn significant attention in recent years due to the realization of the commercialized quantum annealer, sparking research interests in developing applications to solve problems that are intractable for classical computers.However, designing and implementing algorithms that manage to harness the enormous computation power from quantum annealer remains a challenging task. Generally, it requires mapping of the given optimization problem into quadratic unconstrained binary optimization(QUBO) problem and embedding the subsequent QUBO onto the physical architecture of quantum annealer. Additionally, practical quantum annealers are susceptible to errors leading to low probability of the correct solution.In this study, we focus on solving Boolean satisfiability (SAT) problem using quantum annealer while addressing practical limitations. We have proposed a mapping technique that maps SAT problem to QUBO, and we have further devised a tool flow that embeds the QUBO onto the architecture of a quantum annealing device. Additionally, We have optimized the proposed embedding flow to reduce run-time in addition to shortening the qubit chain length, leading to robust quantum annealing. To further improve the reliability of quantum annealing, we have also developed a post processing embedding technique that enlarges the energy gap between ground state and the first excited state. To demonstrate the effectiveness of proposed methods, we have conducted experiments on real quantum annealing devices manufactured by D-Wave Systems, showing compelling result of using quantum annealer to solve SAT problem.

•Jan 1, 2018•4 citations

Quantum annealing correction with minor embedding

Walter Vinci, Tameem Albash, Gerardo A. Paz-Silva +2 more

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.

arXiv:1507.02658•Physical Review A•Oct 9, 2015•97 citations

Solving larger maximum clique problems using parallel quantum annealing

Elijah Pelofske, Georg Hahn, Hristo N. Djidjev

Abstract Quantum annealing has the potential to find low energy solutions of NP-hard problems that can be expressed as quadratic unconstrained binary optimization problems. However, the hardware of the quantum annealer manufactured by D-Wave Systems, which we consider in this work, is sparsely connected and moderately sized (on the order of thousands of qubits), thus necessitating a minor-embedding of a logical problem onto the physical qubit hardware. The combination of relatively small hardware sizes and the necessity of a minor-embedding can mean that solving large optimization problems is not possible on current quantum annealers. In this research, we show that a hybrid approach combining parallel quantum annealing with graph decomposition allows one to solve larger optimization problem accurately. We apply the approach to the Maximum Clique problem on graphs with up to 120 nodes and 6395 edges.

arXiv:2205.12165•Quantum Information Processing•May 16, 2023•30 citations

An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem

Alessandro Gherardi, Alberto Leporati

Quantum annealers can be used to solve many (possibly NP-hard) combinatorial optimization problems, by formulating them as quadratic unconstrained binary optimization (QUBO) problems or, equivalently, using the Ising formulation. In this paper we analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. Due to the embedding limit of 164 nodes imposed by the anneler, we conducted a study on graph decomposition to enable instance embedding. We thus propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes. We then statistically analysed how these variables affect the quality of the solutions found by the quantum annealer. The results of our investigation include recommendations on ratio and density limits not to be exceeded, as well as a series of precautions and a priori analyses to be carried out in order to maximise the probability of obtaining a solution close to the optimum.

arXiv:2406.07587•Jun 11, 2024•0 citations
Abstract Quantum annealing is a type of analog computation that aims to use quantum mechanical fluctuations in search of optimal solutions of QUBO (quadratic unconstrained binary optimization) or, equivalently, Ising problems. Since NP-hard problems can in general be mapped to Ising and QUBO formulations, the quantum annealing paradigm has the potential to help solve various NP-hard problems. Current quantum annealers, such as those manufactured by D-Wave Systems, Inc. have various practical limitations including the size (number of qubits) of the problem that can be solved, the qubit connectivity, and error due to the environment or system calibration, which can reduce the quality of the solutions. Typically, for an arbitrary problem instance, the corresponding QUBO (or Ising) structure will not natively embed onto the available qubit architecture on the quantum chip. Thus, in these cases, a minor embedding of the problem structure onto the device is necessary. However, minor embeddings on these devices do not always make use of the full sparse chip hardware graph, and a large portion of the available qubits stay unused during quantum annealing. In this work, we embed a disjoint random QUBO on the unused parts of the chip alongside the QUBO to be solved, which acts as an indicator of the solution quality of the device over time. Using experiments on three different D-Wave quantum annealers, we demonstrate that (i) long term trends in solution quality exist on the D-Wave device, and (ii) the unused qubits can be used to measure the current level of noise of the quantum system.
Quantum annealers of D-Wave Systems, Inc., offer an efficient way to compute high quality solutions of NP-hard problems. This is done by mapping a problem onto the physical qubits of the quantum chip, from which a solution is obtained after quantum annealing. However, since the connectivity of the physical qubits on the chip is limited, a minor embedding of the problem structure onto the chip is required. In this process, and especially for smaller problems, many qubits will stay unused. We propose a novel method, called parallel quantum annealing, to make better use of available qubits, wherein either the same or several independent problems are solved in the same annealing cycle of a quantum annealer, assuming enough physical qubits are available to embed more than one problem. Although the individual solution quality may be slightly decreased when solving several problems in parallel (as opposed to solving each problem separately), we demonstrate that our method may give dramatic speed-ups in terms of the Time-To-Solution (TTS) metric for solving instances of the Maximum Clique problem when compared to solving each problem sequentially on the quantum annealer. Additionally, we show that solving a single Maximum Clique problem using parallel quantum annealing reduces the TTS significantly.
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.
To date, conventional computers have never been able to efficiently handle certain tasks, where the number of computation steps is likely to blow up as the problem size increases. As an emerging technology and new computing paradigm, quantum computing has a great potential to tackle those hard tasks efficiently. Among all the existing quantum computation models, quantum annealing has drawn significant attention in recent years due to the realization of the commercialized quantum annealer, sparking research interests in developing applications to solve problems that are intractable for classical computers.However, designing and implementing algorithms that manage to harness the enormous computation power from quantum annealer remains a challenging task. Generally, it requires mapping of the given optimization problem into quadratic unconstrained binary optimization(QUBO) problem and embedding the subsequent QUBO onto the physical architecture of quantum annealer. Additionally, practical quantum annealers are susceptible to errors leading to low probability of the correct solution.In this study, we focus on solving Boolean satisfiability (SAT) problem using quantum annealer while addressing practical limitations. We have proposed a mapping technique that maps SAT problem to QUBO, and we have further devised a tool flow that embeds the QUBO onto the architecture of a quantum annealing device. Additionally, We have optimized the proposed embedding flow to reduce run-time in addition to shortening the qubit chain length, leading to robust quantum annealing. To further improve the reliability of quantum annealing, we have also developed a post processing embedding technique that enlarges the energy gap between ground state and the first excited state. To demonstrate the effectiveness of proposed methods, we have conducted experiments on real quantum annealing devices manufactured by D-Wave Systems, showing compelling result of using quantum annealer to solve SAT problem.
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.
Abstract Quantum annealing has the potential to find low energy solutions of NP-hard problems that can be expressed as quadratic unconstrained binary optimization problems. However, the hardware of the quantum annealer manufactured by D-Wave Systems, which we consider in this work, is sparsely connected and moderately sized (on the order of thousands of qubits), thus necessitating a minor-embedding of a logical problem onto the physical qubit hardware. The combination of relatively small hardware sizes and the necessity of a minor-embedding can mean that solving large optimization problems is not possible on current quantum annealers. In this research, we show that a hybrid approach combining parallel quantum annealing with graph decomposition allows one to solve larger optimization problem accurately. We apply the approach to the Maximum Clique problem on graphs with up to 120 nodes and 6395 edges.
Quantum annealers can be used to solve many (possibly NP-hard) combinatorial optimization problems, by formulating them as quadratic unconstrained binary optimization (QUBO) problems or, equivalently, using the Ising formulation. In this paper we analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. Due to the embedding limit of 164 nodes imposed by the anneler, we conducted a study on graph decomposition to enable instance embedding. We thus propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes. We then statistically analysed how these variables affect the quality of the solutions found by the quantum annealer. The results of our investigation include recommendations on ratio and density limits not to be exceeded, as well as a series of precautions and a priori analyses to be carried out in order to maximise the probability of obtaining a solution close to the optimum.