Abstract Recent access to commercially available quantum computing capabilities offers the potential for testing a host of new algorithms that take advantage of fundamentally different processing approaches. One such computing resource is D-Wave’s quantum annealing computer, which employs an energy minimization-based computing mechanism to find solutions to problems stated in an Ising formulation. These solutions, however, must be interpreted in terms of Monte Carlo-style probabilistic occurrences and histograms of candidate solutions that presume the underlying statistics of the qubits are “fair.” This paper quantifies the underlying fairness of individual qubits on a single D-Wave machine, showing that there is a measurable bias in the resulting solution as a function of which qubits are used in the calculation. Further, an example problem is demonstrated, whereby the same problem formulation yields distinctly different solution probabilities by changing which physical qubits are employed.
Abstract Recent access to commercially available quantum computing capabilities offers the potential for testing a host of new algorithms that take advantage of fundamentally different processing approaches. One such computing resource is D-Wave’s quantum annealing computer, which employs an energy minimization-based computing mechanism to find solutions to problems stated in an Ising formulation. These solutions, however, must be interpreted in terms of Monte Carlo-style probabilistic occurrences and histograms of candidate solutions that presume the underlying statistics of the qubits are “fair.” This paper quantifies the underlying fairness of individual qubits on a single D-Wave machine, showing that there is a measurable bias in the resulting solution as a function of which qubits are used in the calculation. Further, an example problem is demonstrated, whereby the same problem formulation yields distinctly different solution probabilities by changing which physical qubits are employed.
Quantum computers use quantum resources to carry out computational tasks and may outperform classical computers in solving certain computational problems. Special-purpose quantum computers such as quantum annealers employ quantum adiabatic theorem to solve combinatorial optimization problems. In this paper, we compare classical annealings such as simulated annealing and quantum annealings that are done by the D-Wave machines both theoretically and numerically. We show that if the classical and quantum annealing are characterized by equivalent Ising models, then solving an optimization problem, i.e., finding the minimal energy of each Ising model, by the two annealing procedures, are mathematically identical. For quantum annealing, we also derive the probability lower-bound on successfully solving an optimization problem by measuring the system at the end of the annealing procedure. Moreover, we present the Markov chain Monte Carlo (MCMC) method to realize quantum annealing by classical computers and investigate its statistical properties. In the numerical section, we discuss the discrepancies between the MCMC based annealing approaches and the quantum annealing approach in solving optimization problems.
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.
Abstract Quantum annealers like those manufactured by D-Wave Systems are designed to find high quality solutions to optimization problems that are typically hard for classical computers. They utilize quantum effects like tunneling to evolve toward low-energy states representing solutions to optimization problems. However, their analog nature and limited control functionalities present challenges to correcting or mitigating hardware errors. As quantum computing advances towards applications, effective error suppression is an important research goal. We propose a new approach called replication based mitigation (RBM) based on parallel quantum annealing (QA). In RBM, physical qubits representing the same logical qubit are dispersed across different copies of the problem embedded in the hardware. This mitigates hardware biases, is compatible with limited qubit connectivity in current annealers, and is well-suited for currently available noisy intermediate-scale quantum annealers. Our experimental analysis shows that RBM provides solution quality on par with previous methods while being more flexible and compatible with a wider range of hardware connectivity patterns. In comparisons against standard QA without error mitigation on larger problem instances that could not be handled by previous methods, RBM consistently gets better energies and ground state probabilities across parameterized problem sets.
Programmable quantum annealers are used for optimization, probabilistic sampling, and simulation, but their performance is commonly reported without the energy exchanged during computation. Here we characterize the D-Wave quantum annealer as a closed thermodynamic cycle. From initial and final Ising energies and an effective temperature fitted to the output distribution, we obtain lower bounds on entropy production, environment energy exchange, work, and power. By varying the prepared distribution and the reverse annealing turning point, we map heater-, accelerator-, refrigerator-, and engine-compatible regimes in one dimensional chains and higher connectivity instances, and apply the same analysis to Advantage and Advantage2 hardware. For an encoded optimization problem, the measured processor energy change states whether final candidates improve or worsen the programmed objective on average. For sampling, the fitted temperature provides an operational measure of how strongly probability is concentrated among low energy configurations. The thermodynamic mode therefore adds information absent from solution quality or runtime alone: it distinguishes driven refinement, net heating, and heat pumping while quantifying their energetic consequences. This framework connects quantum optimization, probabilistic computing, statistical physics simulation, hardware diagnostics, and energy-aware assessment without assuming that a thermodynamic label alone determines computational performance.
Quantum computing is an information processing paradigm that uses quantum-mechanical properties to speedup computationally hard problems. Gate-based quantum computers and Quantum Annealers (QAs) are two commercially available hardware platforms that are accessible to users today. Although promising, existing gate-based quantum computers consist of only a few dozen qubits and are not large enough for most applications. On the other hand, existing QAs with few thousand qubits have the potential to solve some domain-specific optimization problems. QAs are single instruction machines and to execute a program, the problem is cast to a Hamiltonian, embedded in the hardware, and a single quantum machine instruction (QMI) is run. Unfortunately, noise and imperfections in hardware result in sub-optimal solutions on QAs even if the QMI is run for thousands of trials.Due to the limited programmability of QAs users execute the same QMI for all trials. This subjects all trials to a similar noise profile throughout the execution, resulting in a systematic bias. We observe that systematic bias leads to sub-optimal solutions and cannot be alleviated by executing more trials or using existing error-mitigation schemes. To address this challenge, we propose EQUAL (Ensemble QUantum AnneaLing). EQUAL generates an ensemble of QMIs by adding controlled perturbations to the program QMI. When executed on the QA, the ensemble of QMIs steers the program away from encountering the same bias during all trials and thus, improves the quality of solutions. Our evaluations using the 2041-qubit D-Wave QA show that EQUAL bridges the difference between the baseline and the ideal by an average of 14% (and up to 26%) without requiring any additional trials. EQUAL can be combined with existing error mitigation schemes to further bridge the difference between the baseline and ideal by an average of 55% (and up to 68%).
This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. The main disadvantage of calculations on quantum computers is their non-determinism. For optimization problems, of course, it is possible to get surprisingly good results but without a guarantee of the actual optimality of the result, i.e, an assurance that there exists no better solution which could potentially be found by the quantum machine. In this paper, we propose an novel approach that provides such a guarantee of optimality. We generate a solution that is optimal in the strict mathematical sense, without probabilistic considerations. To accomplish this, we use the D-Wave quantum machine working as a sampler implementing quantum annealing -- an approach considered a hardware metaheuristic -- to obtain upper and lower bounds on the value of the objective function of the problem under consideration. Then, we use the Branch and Bound scheme controlled by quantum annealing. This allows us to obtain very quickly -- in constant time -- the boundaries of the considered subproblems. Our approach is a combination of calculations realized on a quantum machine controlled by procedures implemented on a classical computer, allowing us to generate optimal solutions to the NP-hard problems of task scheduling on a single machine with a total weighted tardiness criterion. The proposed quantum algorithm shows a significant advantage over the classical CPU approach both in terms of calculation time and the number of generated solution tree nodes.