#  EQUAL: Improving the Fidelity of Quantum Annealers
by Injecting Controlled Perturbations

Ramin Ayanzadeh  Georgia Institute of Technology, Atlanta, GA, USA
<EMAIL_ADDRESS>Poulami Das  Georgia Institute of Technology, Atlanta,
GA, USA  Swamit S. Tannu  University of Wisconsin–Madison, Madison, WI, USA
Moinuddin Qureshi  Georgia Institute of Technology, Atlanta, GA, USA

###### Abstract

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 of 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 on 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.

The limited programmability of QAs mean that the user executes 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%).

##  1 Introduction

Quantum computing is an information processing paradigm that leverages quantum
mechanical properties of quantum bits (qubits) to store and process
information and promises significant computational advantages for many hard
problems [83, 36, 29, 53]. There exist different models for the physical
realization of this computational paradigm such as gate model quantum
computers and quantum annealers [64, 4]. Currently, prototypes of both gate
model [23, 35, 38] and annealing [42] types are available and some of them can
already outperform modern supercomputers for some tasks [7, 92, 48, 94].

Gate-based quantum computers, such as IBM and Google machines, use discrete
quantum gate operations to manipulate qubits such that the state of the qubits
evolve to produce the desired outcome as the program proceeds. Such systems
with about 50-plus qubits are already available [6, 23, 57]. To solve a
problem on a gate-based quantum computer, we map it to an efficient quantum
algorithm, map the high-level program qubits to the physical qubits of the
device, translate the instructions into a series of low-level quantum gates,
and execute them, as shown in Figure 1(a). Although these types of systems
promise significant computational advantages in the near-term, they must grow
in size for practical applications [64, 92, 77].

Unlike gate model quantum computers that can be programmed to solve different
classes of problems, _Quantum Annealers (QAs)_ are single-instruction machines
that can only solve a specific discrete optimization problem by minimizing the
energy of a physical system, called _Hamiltonian_ [24, 4]. To solve a problem
on a QA, (a) we cast it to a Hamiltonian, (b) embed it to match the topology
of the QA device, (c) obtain the resulting single _Quantum Machine Instruction
(QMI)_ , (d) execute the single QMI, and (e) repeatedly run the same QMI
multiple times [56], as shown in Figure 1(b). The outcome with the lowest
energy is deemed as the solution.

Figure 1: Steps involved in solving a problem using (a) gate-model quantum
computers and (b) quantum annealers. (c) Energy histogram of a 2000-qubit
optimization benchmark executed on D-Wave QA (in logscale). The QA can quickly
identify the region of the ground state energy (overlapping region) but the
solution is far from the global optima due to systematic bias.

As QAs can only minimize a specific objective function, any other problem must
be cast/reduced to this Hamiltonian. _Casting_ computes the coefficients of
the Hamiltonian such that the global minima of the Hamiltonian represents the
global optima of the problem of interest [54, 13, 56]. _Embedding_ maps the
problem graph to the topology of the QA. As QAs have limited connectivity
between qubits, embedding encodes a program qubit with higher connectivity by
using a chain of physical qubits. The problem of limited connectivity exists
even on most existing gate-based quantum computers and can be overcome by
inserting SWAP operations [95, 60, 88]. However, a similar approach is
impractical for QAs as they can only execute a single QMI. Unlike gate-based
systems, QAs available today with 5000-plus qubits [42, 6, 55] are much
larger, scale faster, and have the potential to power a wide range of real-
world applications—including, but not limited to, planning [80], scheduling
[91, 90], constraint satisfaction problems [16], Boolean satisfiability (SAT)
[84, 13], matrix factorization [68], cryptography [74, 39], fault detection
and system diagnosis [75], compressive sensing [14, 12], control of automated
vehicles [43], finance [27], material design [49], and protein folding [59].
Although promising, QA hardware suffers from various drawbacks such as noise,
device errors, limited programmability and low annealing time, which degrade
their reliability [4, 56, 9]. Addressing these limitations requires device-
level enhancements that may span generations of QAs. Therefore, software
techniques to improve the reliability of QAs is an important area of research
[21, 25, 33, 19, 34, 67, 41].

Despite recent hardware and software enhancements, existing QAs may fail to
find the global minima for certain problems [9]. For example, Figure 1(c)
shows the energy histogram of a 2000-qubit optimization problem on a D-Wave
QA. We can think of QA as a machine that samples from a Boltzmann distribution
such that samples with lower energy values are exponentially more likely to be
observed [93, 9]. In theory, QA can find the optimal solution with a very high
probability [65]. However, in this example, we observe that although the QA
can quickly identify the region of the global optima, the best solution from
the QA is far from the global optima. As users run only a single QMI, the
program is subjected to a similar noise profile for all trials, resulting in a
_systematic bias_. Our experiments show that running more trials or relying on
existing error-mitigation schemes cannot overcome this bias. Unfortunately,
systematic bias produce incorrect solutions far from the global optima and
limits the reliability of QAs for practical applications.

In this paper, we propose _Ensemble Quantum Annealing (EQUAL)_ , an effective
scheme for mitigating systematic bias and improving the reliability of QAs by
running an ensemble of QMIs with controlled perturbations. EQUAL is based on
the insight that running the same QMI for all trials projects QAs to a very
similar noise profile and bias. Instead, EQUAL uses an ensemble of QMIs that
subjects the system to different noise profiles and biases. Generating
effective ensembles of QMIs is non-trivial and our design focuses on
addressing it. 111The problem of systematic bias is similar to correlated
errors on gate-model quantum computers that can be addressed by mapping
programs to different sets of physical qubits on the same machine [86],
inserting different SWAP routes [86], or using different machines [71]. The
equivalent step for QAs would be to use multiple embeddings. However, this is
not viable for QA and we discuss the details in Section 6.

To generate ensembles, EQUAL creates new Hamiltonians, called _Perturbation
Hamiltonians_ , and adds them to the original problem Hamiltonian. Every
perturbation Hamiltonian adds noise to the original Hamiltonian and the QMI
obtained from this process is a perturbed variation of the original QMI. The
challenge in this step is that adding extremely small perturbations will have
no impact on the systematic bias, whereas adding large perturbations can
significantly change the landscape of the original Hamiltonian. In the worst
case, the final perturbed Hamiltonian may correspond to a problem completely
different from the one at hand. Thus, there exists a trade-off between the
ability to eliminate systematic bias and the correctness of a Hamiltonian.
Ideally, we want a perturbed Hamiltonian that can eliminate systematic bias
without altering the characteristics of the problem Hamiltonian significantly.
To address this challenge, EQUAL exploits the fact that QAs only allow a
limited precision of coefficients for a Hamiltonian due to hardware
limitations. For every ensemble, EQUAL draws the coefficients of the
corresponding perturbation Hamiltonian randomly at a range just below the
supported precision so that adding the Perturbation Hamiltonian may only shift
the coefficients of the QMI (post truncation) to one of the neighboring
quantization levels and not impose significant changes to the landscape of the
original Hamiltonian.

We also analyze existing error-mitigation approaches for QAs. Our
characterization experiments on D-Wave shows that the SQC [9] post-processing
technique is highly effective for D-Wave. We compare EQUAL with SQC and show
that the two schemes can be combined for even greater benefit. The resulting
design, _EQUAL+_ , provides significantly better fidelity than EQUAL and SQC
standalone. As the SQC post-processing relies only on classical computations,
EQUAL+ does not incur any additional trials compared to EQUAL.

Our evaluations on D-Wave’s 2041-qubit QA show that EQUAL bridges the
difference between the baseline and the ideal by an average of 14% (and up to
26%). EQUAL+ further bridges the difference between the baseline and the ideal
by an average of 55% (and up to 68%).

Overall, this paper makes the following contributions:

  1. 1.

We show that there is a systematic bias associated with each QMI, running on
QA, that deviates the annealing process from achieving the ground state of the
corresponding Hamiltonian and produces sub-optimal solutions.

  2. 2.

We propose EQUAL (Ensemble Quantum Annealing) to mitigate the bias by forming
multiple perturbed copies of a given QMI and running each for a subset of
trials.

  3. 3.

We propose an effective method to generate the perturbed copies while
retaining the structure of the problem by leveraging the hardware
imperfections from limited precision.

  4. 4.

We propose EQUAL+ that combines EQUAL with existing SQC error-mitigation to
further improve the reliability.

##  2 Background and Motivation

###  2.1 Quantum Computing

Quantum computing is a computational paradigm that stores and processes
information using quantum bits or _qubits_. The state of a qubit $\ket{\psi}$
can be represented as a superposition of its two basis states $\ket{0}$ and
$\ket{1}$ using a vector: $\ket{\psi}=\alpha\ket{0}+\beta\ket{1}$, where
$\alpha$ and $\beta$ are complex probability amplitudes associated with the
basis states. Similarly, an $N$-qubit system exists in a superposition of
$2^{N}$ basis states. This exponential scaling in state space with a linear
increase in qubits enables quantum advantage. Currently, two types of quantum
platforms are available to users through cloud services [6, 23, 57]—gate-based
quantum computers and quantum annealers.

Gate-based Quantum Computers: A gate-based quantum computer executes a
predefined sequence of quantum gate operations to transform the initial state
of the qubits to the desired state by changing the superposition. The sequence
of quantum gates is known as a quantum circuit. Quantum computers from IBM,
Google, and others use gate-based model.

Quantum Annealers: Quantum annealing is a meta-heuristic for solving
combinatorial optimization problems that runs on classical computers [5, 30,
44, 24, 66, 65]. Quantum Annealers are single instruction machines for solving
combinatorial optimization problems. Unlike gate model quantum computers,
where we directly change the state of qubits via quantum gates, QAs control
the environment, and qubits evolve to remain in the ground state (i.e., a
configuration with the lowest energy value) of a Hamiltonian (or energy/cost
function) [24, 4]. Quantum annealers, such as the ones from D-Wave, are analog
systems that can only minimize the following energy function:

$\mathbf{H}_{p}:=f(\mathbf{z})=\sum_{i=0}^{N-1}{\mathbf{h}_{i}\mathbf{z}_{i}}+\sum_{i=0}^{N-1}{\sum_{j=i+1}^{N-1}{J_{ij}\mathbf{z}_{i}\mathbf{z}_{j}}},$
(1)

where $N$ is the number of qubits, $\mathbf{h}_{i}\in\mathbb{R}$ specifies the
linear coefficient of qubit ${i},$ $J_{i,j}\in\mathbb{R}$ represents the
coupler weight between qubits ${i}$ and ${j},$ and $\mathbf{z}_{i}$ is the
variable that can take its value from $\\{-1,+1\\}$ [56, 9, 13]. Ever since
the introduction in 2011, QAs have rapidly scaled in size up to few thousand
of qubits, as shown in Figure 2(a) and promise significant computational
advantage for a wide range of applications.

###  2.2 Operation Model of QA

To execute a program on a QA, the problem is cast to a Hamiltonian such that
its global minimum represents the optimal solution of the problem at hand.
This step computes the coefficients $\mathbf{h}$ and ${J}$, denoted in
Equation (1), corresponding to the _quantum machine instruction (QMI)_ to be
executed on the QA. Executing the QMI on a QA returns a sample
$\mathbf{z}=\\{\mathbf{z}_{0},\mathbf{z}_{1},\dots,\mathbf{z}_{N-1}\\}$ as a
potential minimum of the corresponding energy function. Unfortunately,
executing a QMI only once may not result in the ground state of the
Hamiltonian due to noise in the system [9]. Thus, in practice, the process of
executing the single QMI is repeated for thousands of trials. The sample with
the lowest energy is reported as the solution.

Figure 2:  (a) Evolution of Quantum Annealers (QAs) over time (b) A cropped
view of the D-Wave 2041-qubit QA with its connectivity graph where the nodes
denote qubits and edges represent couplers (or connectivity between two
qubits).

###  2.3 The Opportunity: Solving Large Problems with QA

Google Sycamore is a state-of-the-art 54-qubit gate-based quantum computer
that can outperform even the most powerful supercomputer for some tasks [7].
We compare the performance of the D-Wave 2041-qubit QA and Google Sycamore for
18 different Max-Cut problems. The Max-cut problems used in this evaluation
correspond to the fully-connected Sherrington-Kirkpatrick (SK) Model [81] and
uses up to 17 qubits [37, 89, 79]. These are some of the hardest benchmarks on
Sycamore as fully connected graphs require many SWAP operations to overcome
the limited connectivity. Running the same benchmarks on the D-Wave QA
requires only 102 qubits (less than 1% of the qubits). Figure 3 shows the
value of the solution obtained from both machines.

Figure 3: Comparison of 54-qubit Google Sycamore [37] and 2041-qubit D-Wave
Quantum Annealer.

We use the same weighted graphs from prior work [37] that result in negative
cut values. The performance of the D-Wave QA is comparable to Google Sycamore
and both of them are successful in finding the optimal cut at small problem
sizes. However, the performance of Google Sycamore degrades with increasing
problem size [37] due to an increase in SWAPs and circuit depth. Furthermore,
due to the limited capacity of 54-qubits, the problem size for Sycamore is
limited to no more than 54 nodes. However, as QAs are much larger (2000–5000
qubits), we can use them to solve larger problems more relevant to real-world
applications and exceed the size of near-term gate-based quantum computers.
For example, Figure 4 shows the performance of the D-Wave QA for Max-Cut
problems corresponding to the SK Model using up to 60 qubits. For each
problem, the D-Wave QA can find the optimal cut value. To determine the
optimal cut value, we evaluate all possible combinations for problems using up
to 25 qubits and use the best estimate for the larger problems.

Figure 4: Performance of D-Wave QA for larger Max-Cut problems corresponding
to the SK Model

###  2.4 The Challenge: Hardware and Software Limitations

Although QAs look promising for various applications, several challenges limit
us from solving real-world problems on them.

####  2.4.1 Hardware-Level Challenges

Limited coherence/annealing time: The probability of finding the ground state
of a Hamiltonian using a QMI increases exponentially with increasing annealing
time [4] and theoretically, many hard problems may require large annealing
time. Unfortunately, the annealing time on current QAs is in the order of
microseconds [56, 9] as qubits can retain their state only for a short span of
time. Increasing the annealing time on QA hardware causes qubits to _decohere_
and lose their state.

Noise and limited connectivity: Thermal noise and operational errors add
unwanted perturbations during annealing and prevent QAs from reaching the
ground state of a Hamiltonian [4]. QAs also suffer from sparse connectivity
between qubits, as shown in Figure 2. To address the same drawback on gate-
model quantum computers, compilers insert SWAP instructions that interchange
the state of physically adjacent qubits [88, 95, 60]. However, QAs cannot use
a similar approach as they use only one QMI. Instead, we _embed_ the problem
graph to match the target device topology where multiple physical qubits
represent a program qubit with higher connectivity. This can reduce the
effective capacity of QAs.

Limited precision and range of coefficients: Casting a problem to a
Hamiltonian and generating the corresponding QMI coefficients can require a
double-precision representation. However, large precision impacts the
performance of the digital-to-analog converters (DACs) used on the real QAs
which slows the annealing process. Therefore, existing QAs trade-off precision
to achieve lower annealing times and truncate the QMI coefficients post
casting to match the precision supported in hardware. This subjects the QMI to
quantization errors, and the reduced precision QMI actually executed on a QA
can be slightly different from the QMI that we originally intended to run,
leading to a ground state that may not represent the solution of the problem
at hand [26, 78, 9].

####  2.4.2 Software-level Challenges

Limited programmability: QA can only minimize a specific objective function
and any input problem must be _cast_ to a Hamiltonian. Unfortunately, casting
is non-trivial due to lack of standardized algorithms and often comes with
some approximations [56, 13]. Additionally, QAs can only execute a single QMI
that performs the annealing step and therefore, fine-grained optimizations at
the instruction-level are infeasible.

Limitations of Embedding: To overcome limited connectivity, a problem graph is
embedded in the QA to match the device topology. Finding the best embedding is
NP-hard [21, 25, 34, 18] and existing algorithms can take several hours
despite approximations. Also, our studies show they often fail for large
programs.

###  2.5 Impact of Trials on Energy Residual

In theory, QAs should find the global optima of a problem with high
probability [65, 4]. However, in reality, QAs often fail to find the global
optima for large problems due to noise and imperfect control. Moreover, the
limited programmability of QAs forces users to run a single QMI for thousands
of trials, resulting in a bias. As a user runs a single QMI for all trials,
the noise profile is similar throughout execution, resulting in similar
quality outcomes due to the inherent bias in the noise profile. We refer to
this bias as _Systematic Bias_.

Figure 5 shows the _Energy Residual (ER)_ [47, 46] for an optimization problem
on D-Wave QA. ER compares the gap between the energy of the solution from a
noisy QA and the global minima. The energy of the best solution from a noisy
QA remains far from the global optima even after running 1 million trials.
This non-zero ER occurs due to systematic bias, and is particularly severe for
large problems.

Figure 5: Energy Residual of an optimization problem on D-Wave QA with
increasing number of trials.

###  2.6 Goal of this Paper

Hardware and software limitations of QAs cause programs to encounter a
systematic bias during execution which cannot be bypassed by executing more
trials. Ideally, we want QAs to be free from systematic bias. In this paper,
we propose Ensemble Quantum Annealing (EQUAL) that uses an ensemble of QMIs
(with different biases) to mitigate systematic bias. We discuss the evaluation
methodology before discussing our solution.

##  3 Evaluation Methodology

We discuss the evaluation infrastructure used in this paper.

###  3.1 Quantum Platform and Baseline

For our evaluations, we use the 2041-qubit quantum annealer from D-Wave
Systems via Amazon BraKet cloud service [6]. We use the default annealing time
(i.e., 20 $\mu$seconds) and schedule recommended for this system. For the
baseline, we use 100,000 trials for each benchmark. For EQUAL, trials are
equally split between QMIs. Thus, EQUAL requires the same number of trials as
the baseline.

###  3.2 Benchmarks

We use _random weighted Max-Cut_ problems, similar to Quantum Approximate
Optimization Algorithms [28] used on gate-based quantum computers. For the
benchmarks, we draw the Hamiltonian coefficients of the QMIs from the standard
normal distribution (a mean of 0 and standard deviation of 1). This approach
is a common practice used in prior works related to benchmarking QAs [24, 78,
9, 19, 11]. To avoid the impact of embedding on our evaluations, we directly
use the connectivity graph of the D-Wave QA. Thus, the number of program
qubits in benchmarks is equal to the number of physical qubits on the QA. As
the size of benchmarks significantly exceeds the size of existing gate-model
quantum computers, we cannot compare our results with them.

###  3.3 Figure-of-Merit

We evaluate the reliability of QA using Energy Residual (ER). The best
solution from a QA is the outcome with the minimum energy. ER computes the
energy gap between the minimum energy $(E_{min})$ obtained on a QA with
respect to the global energy minimum $(E_{global})$ of the application as
follows:

$\textrm{Energy Residual (ER)}=\left|E_{min}-E_{global}\right|.$ (2)

Ideally, when the best solution obtained on a QA corresponds to the ground
state of the problem Hamiltonian, ER is zero. Thus, a lower value (closer to
zero) for ER is desirable.

The challenge in computing the ER for random large benchmarks spanning 2000+
qubits is that finding the ground state of the Hamiltonian is non-trivial. To
overcome this challenge and still enable a fair comparison, we perform
intensive classical computations using state-of-the-art tools [10] and
approximate the global optimum of our benchmark problems. Recent studies have
shown that this algorithm can estimate the ground state of Chimera based
Hamiltonians [21, 42] (such as the ones considered in our paper) with a very
high probability. 222The techniques used to derive the best estimate of the
ground state energy of a Hamiltonian requires intensive classical computing
resources and could take up-to days for problem sizes with a few thousand
qubits. We discuss more on this in Section 6

##  4 EQUAL: Ensemble Quantum Annealing

The vulnerability of a program to systematic bias results from limited
programmability and the current execution model of QAs where the same QMI is
executed for thousands of trials. This subjects each trial to a similar noise
profile on the QA and the entire execution suffers from the same inherent
bias. Our proposed solution _EQUAL_ —Ensemble Quantum Annealing—takes a
different approach. Instead of a single QMI, EQUAL generates an ensemble of
QMIs that subjects the program execution to different noise profiles and
therefore, different systematic biases. When results are aggregated, ensembles
enable us to improve the quality of solutions.

Figure 6: Overview of EQUAL. EQUAL creates an ensemble of QMIs by adding
controlled perturbations to the original QMI. It executes the original QMI as
well as the ensemble of QMIs separately on the QA hardware and returns the
outcome with the lowest energy value. EQUAL can also optionally leverage
existing post-processing error mitigation schemes (EQUAL+).

###  4.1 Challenges in Generating Ensembles in EQUAL

There is potential to generate ensembles during any one of the three phases
that a problem goes through before execution on a physical QA hardware: (1)
casting, (2) embedding, and (3) QMI generation. Generating ensembles during
casting was previously studied in the context of Boolean satisfiability (SAT)
[13] and binary compressive sensing [12] problems on QAs. Unfortunately, these
methods exploit the features of the application-specific casting algorithms.
Therefore, this approach has limited applicability and is hard to generalize
for QAs. The other alternative approach is to use an ensemble of embeddings
for a given problem. However, this approach too has its limitations. Firstly,
finding the best embedding is an NP-hard problem in itself [21, 25, 34, 18].
Secondly, current embedding schemes for QAs use several approximations and may
or may not be able to determine an ensemble of embeddings of similar quality
[21, 34, 25, 18]. Our studies show that existing embedding algorithms often
fail to find an adequate number of embeddings, particularly for problems at
scale that require 2000+ qubits. Thirdly, even if it is possible to find
multiple embeddings, they are often of inferior quality and require larger
chains of physical qubits to represent a program qubit with higher
connectivity. This makes the embedding significantly more vulnerable to noise
compared to the best embedding. Thus, generating ensembles at the embedding
step is non-trivial. Instead, EQUAL focuses on generating ensembles at the
instruction-level and produces multiple QMIs.

###  4.2 Overview of Design

Figure 6 shows an overview of EQUAL. It relies on adding controlled
perturbations to the original QMI. For each ensemble, EQUAL generates a
_Perturbation Hamiltonian_ , denoted by $\delta.$ Each of these Perturbation
Hamiltonians creates a new QMI when added to the original Hamiltonian. For
example, if EQUAL generates $m$ ensembles of QMIs, it generates $m$
perturbation Hamiltonians, namely $\delta_{1},\delta_{2},\dots,\delta_{m}.$
The ensemble QMIs—QMI1, QMI2 to QMIm—are obtained by adding the original
Hamiltonian (say $\mathbf{H})$ and the respective perturbation Hamiltonians.
In other words, the ensemble of QMIs now corresponds to the perturbed versions
of the original Hamiltonian.

###  4.3 Generating Ensembles via Controlled Perturbations

Creating an effective perturbation Hamiltonian is non-trivial. If the
perturbations add too little noise, the resulting Hamiltonian will be too
close to the problem Hamiltonian and encounter similar bias. Alternately, too
large perturbations result in a Hamiltonian significantly different from the
problem of interest and can produce infeasible results. For example, Figure
7(a) shows the landscape of an example optimization problem333Minimize
$x^{2}+y^{2}$ for $x,y\in[-2,2]$.. Figure 7(b) shows that injecting an
extremely noisy perturbation Hamiltonian significantly changes the landscape
of the original problem. Thus, there is a trade-off between the effectiveness
of a perturbation Hamiltonian to reduce bias and its ability to alter the
problem Hamiltonian. To address this challenge and generate an effective
ensemble of QMIs, EQUAL exploits the device-level characteristics of QAs.

Figure 7:  (a) Landscape of an example optimization problem. (b) The resultant
landscape differs significantly from (a) when an extremely noisy perturbation
is imposed. (This figure is for illustrative purposes only. Hamiltonians and
QAs can only deal with discrete optimization problems.)

####  4.3.1 Exploiting Hardware Characteristics of QAs

Recollect that casting a problem to a Hamiltonian can require double-precision
representation of the Hamiltonian coefficients. Unfortunately, real QAs can
only support a small range and precision of coefficients due to the
limitations imposed by the digital to analog converters (DACs) used on QAs. If
the precision of the coefficients are too large, the DACs are too slow which
eventually slows the controlling modules of QAs and is not desirable. To
bridge this gap, post the casting step, the coefficients of the QMI are
truncated to match the precision supported by the hardware. While this is a
limitation on QAs, EQUAL leverages it to its advantage and draws the
coefficients of the perturbation Hamiltonian randomly at a range that is below
the supported precision so that adding the perturbation Hamiltonian only
shifts the coefficients of the QMI (post truncation) to one of the neighboring
quantization levels and thus, does not significantly alter the problem
landscape. More specifically, let $b$ be the number of bits used for
representing coefficients of a physical QA. For every ensemble, EQUAL draws a
uniform random number $r\in\left[{\frac{1}{2^{b+1}},\frac{1}{2^{b}}}\right]$
and set all coefficients of the Perturbation Hamiltonian to be $r$.

Figure 8: Trends in Energy Residual for the baseline and EQUAL for all the
benchmarks.

####  4.3.2 Profiling QAs to estimate Hardware Precision

Unfortunately, the precision of the coefficients supported on real devices is
unavailable to programmers. Determining this precision is vital for the
performance of EQUAL. Drawing the perturbation Hamiltonian coefficients far
below the supported precision introduces large noise and may alter the
Hamiltonian landscape significantly. Alternately, drawing them far above the
supported range may not have any effect post truncation. To tackle this
challenge, EQUAL profiles the QA using random benchmarks to estimate the
precision supported by QAs. In this experiment, we truncate all coefficients
of the benchmark for $2,3,\dots,16$ bits precision and execute the
corresponding QMIs. Figure 9 shows the relative Energy Residual of the
truncated QMIs with respect to the original problem (without truncation). Our
profiling experiments with multiple benchmarks show that the hardware is
likely limited by 7–8 bits of precision. Thus, EQUAL generates coefficients of
ensembles in $\left[\frac{1}{2^{9}},\frac{1}{2^{8}}\right].$

Figure 9:  Relative Energy Residual of QMIs with truncated coefficients with
respect to the original problem QMI for bits values of precision. (Lower is
better)

###  4.4 Execution on QA Hardware

EQUAL splits the trials between the ensemble of QMIs equally, including the
original QMI (without perturbation), and executes them separately on the QA
hardware. Our default design uses 10 ensembles of QMIs, and allocates 10,000
trials for every ensemble. We do a more rigorous sensitivity analysis for the
number of trials and ensembles in Section 5.8.

By default, the outcome with lowest energy is deemed as the solution for
problems executed on QAs. In the baseline, this corresponds to the outcome
with the lowest energy obtained by executing the original QMI. As EQUAL
executes multiple QMIs, the outcome with the lowest energy among all the QMIs
is returned as the solution. Also, as EQUAL runs the ensemble of perturbed
QMIs in addition to the original program QMI, the final solution is guaranteed
not to perform worse than the baseline, assuming there are no sampling errors.
Note that the solution with the minimum energy corresponds to an outcome that
may come from a single QMI. For the baseline this corresponds to the original
QMI, whereas for EQUAL it comes from one or more of the QMIs in the ensemble.
However, which QMI corresponds to the best solution is not known a-priori and
EQUAL must execute the entire ensemble.

Figure 10:  Histogram of energy values from the outcomes on the QA for
benchmark B1 using the Baseline and EQUAL. The solution from EQUAL is closer
to the ideal solution compared to the baseline solution ($d_{2}<d_{1}$). The
histograms for the baseline and EQUAL largely overlaps which indicates that
EQUAL does not significantly alter the problem Hamiltonian.

###  4.5 Results for Energy Residual

Energy Residual (ER) computes the gap between the energy obtained from the
best outcome on a QA with the global optima. Figure 8 compares the ER of the
individual benchmarks for baseline and EQUAL. We observe that the ER quickly
saturates in the baseline for all benchmarks, whereas improves for EQUAL as
more QMIs are executed. As the QMIs are generated using random controlled
perturbations, some of them may result in higher ER compared to the baseline
due to a different noise profile at run time. However, the ensemble overall
enables EQUAL to reach a better solution. In the worst case, EQUAL performs
similar to baseline as the original program QMI is executed too. We observe
that the fidelity of the baseline saturates with more trials, whereas the
diversity of EQUAL helps it keep on improving with additional trials.

Figure 11 shows the ER of EQUAL for our benchmarks executed on D-Wave
2041-qubit QA relative to the baseline. We observe that EQUAL bridges the
difference between the baseline and the ideal by an average of 14% (and up to
26%). QAs deal with industry-scale optimization problems where even a
minuscule improvement has a tremendous impact in terms of practical advantage
such as saving millions of dollars [1, 22, 27] in the context of scheduling
and planning applications or finding better candidates for drug discovery [59]
and material science [49]. Thus, the quality of solutions is of utmost
importance.

Figure 11: Energy Residual of six random benchmarks on D-Wave QA hardware
using EQUAL relative to the baseline.

###  4.6 Case-Study: How EQUAL Reduces Systematic Bias

Figure 10 shows the histograms of the energy values obtained by running
benchmark B1 for the baseline and EQUAL. The goal of QAs is to obtain the
outcome corresponding to the ground state energy. We observe that the optimal
solution is at a distance $d_{1}$ from the ground state and EQUAL produces a
solution at distance $d_{2}$ that is closer to the ground state energy
($d_{2}<d_{1}$) by minimizing the impact of bias. We also observe that
distributions for both the baseline and EQUAL overlap largely, indicating that
the ensemble of QMIs do not largely alter the original Hamiltonian
corresponding to our problem. We make similar observations for other
benchmarks.

An ideal QA is a machine that samples from the Boltzmann distribution, whereas
the distribution obtained from a real QA hardware is different due to noise.
The best solution obtained by a QA depends on the overlapping region between
the ideal and the noisy distributions. From Figure 10, we observe two
potential approaches to get closer to the global optima. First, by
_flattening_ the energy histogram of the Hamiltonian such that it covers a
broader search space. Second, by _shifting_ the energy histogram towards the
ideal solution. Note that both of these techniques must ensure that the
properties of the original program Hamiltonian remain unaltered. EQUAL uses
the first approach. The performance of EQUAL can be improved further if we
could shift the histogram closer to the ideal solution. We explore combining
EQUAL with existing error mitigation schemes to obtain the advantage of both
flattening the histogram and shifting the histogram towards the ground state.

##  5 Combining EQUAL with Error-Mitigation

Ensembles are generated by only adding controlled perturbations to the problem
Hamiltonian. Therefore, they have limited capability to shift the noisy
distribution from a QA towards the ideal distribution even if a large number
of ensembles are used. Alternately, large perturbations may significantly
change the landscape of the problem. Instead, we take an orthogonal approach
and explore existing error-mitigation schemes that introduce a shift in the
energy histogram.

###  5.1 Primer on Error-Mitigation Schemes for QA

Error-mitigation schemes for QAs can be classified into (1) software and (2)
hardware schemes. Software schemes refer to optimizations performed during the
casting and embedding steps (pre-processing techniques) or modifications on
the outcomes obtained from QAs (post-processing techniques). On the other
hand, hardware-based schemes control the device-level parameters on QAs to
reduce the impact of errors.

We characterize the impact of these error-mitigation techniques individually
and combined with each other to understand their effectiveness in (1)
eliminating systematic bias on their own and (2) shifting the noisy
distribution of the QA towards the ideal distribution. For our analysis, we
choose (a) spin reversal transform, (b) longer inter-sample delay, and (c)
single-qubit correction. Spin-reversal transform is a representative candidate
for a software pre-processing technique. On the other hand, inter-sample delay
is a device-level control available to programmers to reduce the correlation
between consecutive trials on a QA. Lastly, Single-Qubit Correction (SQC) [9]
is a post-processing technique which leverages the insight that for a given
QMI, QAs can quickly recognize the neighborhood of the ground state even if
they fail to get to the ground state [9]. We perform characterization studies
for these three error mitigation schemes (see Appendix A) and found that SQC
is the most effective scheme, and therefore we use SQC as the error mitigation
scheme for our study.

Figure 12: Single Qubit Correction Post-Processing [9]

###  5.2 Overview of SQC Post-Processing

SQC is analogous to the gradient descent scheme but only applicable to
discrete optimization problems. Instead of computing the gradient for
determining the direction of the move in every iteration, SQC uses a greedy
approach and moves to a neighbor (i.e., an outcome that is one Hamming
distance away from the current solution) with the lowest energy value. Figure
12 illustrates the overview of an iteration of SQC. For each candidate outcome
generated by executing the QMI, SQC finds the one Hamming distance away
neighbors and computes their energy values. If any neighbors can obtain a
lower energy value than the candidate itself, the neighbor is retained and the
current solution is discarded. When multiple neighbors obtain lower energy
values, the best neighbor is retained. The process is repeatedly executed
until we cannot find any new neighbor that has better quality.

###  5.3 EQUAL+: Combining EQUAL and SQC

Figure 13 shows an overview of EQUAL+. EQUAL+ applies SQC on the outcomes of
each QMI and obtains the best outcome for each QMI. The process is performed
for each QMI in parallel. Once applying SQC on each QMI converges, the final
output of EQUAL+ is picked as the candidate with the lowest energy among all
the individual best candidates from the QMIs. The time to converge depends on
several factors such as the size of the problem, number of outcomes, quality
of the outcomes. However, our evaluations show that EQUAL+ converges within a
few seconds even for large benchmarks such as the ones used in our
evaluations.

Figure 13: Overview of EQUAL+ design. It applies the SQC post-processing
algorithm on the outcomes from each QMI in parallel. Finally, it selects the
best outcome from all the QMIs as the output solution.

Using this greedy approach helps locate neighbors from current outcomes that
were not produced by the QA originally. With each neighbor located, EQUAL+
shifts the outcome distribution towards the ideal solution (global optima).
Note that although SQC is effective on its own, the diversity of EQUAL+ is
essential to improve its search space. The capability of SQC alone to
introduce new outcomes is limited by the quality of outcomes from the QMI. In
EQUAL+, the ensembles enable us to explore a much larger neighborhood compared
to applying SQC alone. In the end, EQUAL+ may discover a solution from one of
the weakest outcomes corresponding to one of the weakest QMIs (sub-optimal
outcome that did not correspond to the best solution in any of the QMIs).

Note that EQUAL+ is versatile, and any other post-processing candidate that
introduces the desired shifting property in the energy distribution may be
used. We use SQC for its performance and low time complexity.

Figure 14: Histogram of energy values from the outcomes on the QA for
benchmark B1 using EQUAL and EQUAL+.

###  5.4 Analysis of Overheads

We discuss the overheads for both EQUAL and EQUAL+. EQUAL generates the
ensemble of QMIs prior to execution on the QA. As the perturbed Hamiltonian
only adjusts the coefficients of the original problem QMI, the ensemble does
not need to re-perform the casting or embedding step. Although embedding can
take up to several hours and may fail for certain Hamiltonians, this overhead
and limitation is entirely avoided by EQUAL. EQUAL also requires the
programmer to estimate the precision of the hardware using a set of profiling
experiments. However, profiling need not be done for each application. As the
precision supported is only device-specific, profiling once for each QA
hardware is enough and the same information can be re-used for multiple
applications. For execution on the QA, EQUAL requires the same number of
trials as the baseline and therefore, does not incur any overhead of
additional trials.

EQUAL+ incurs some additional overheads for the post-processing step as it
applies the SQC heuristic algorithm on all the outcomes obtained from all the
QMIs. The space complexity of the post-processing phase in EQUAL+ is linear
with the number of qubits [9]. As SQC is iteratively applied on every outcome
of a QMI, the time complexity depends on the number of outcomes which is equal
to the number of trials in the worst-case (assuming each trial generates a
unique outcome). The post-processing for each QMI is done in parallel. Our
studies show that EQUAL+ converges within a few iterations and the post-
processing step for EQUAL+ only takes a few seconds. Therefore, the overheads
are acceptable.

###  5.5 Results for Energy Residual

Figure 15 shows the Energy Residual of EQUAL+ relative to the baseline. We
also compare against EQUAL and SQC standalone. We observe that EQUAL+ improves
the ER by 0.45 compared to the baseline on average and by up to 0.32. In other
words, EQUAL+ improves the quality of solutions by 55% on average and up to
68%.

Figure 15: Energy Residual using EQUAL+ relative to the baseline. We also
compare with EQUAL and SQC standalone.

###  5.6 Results for Validation of Precision Selection

We draw the perturbation Hamiltonian coefficients in the range
$\left[\frac{1}{2^{9}},\frac{1}{2^{8}}\right]$ based on profiling across a
wide range of values. We confirm that this approach is robust by conducting
additional studies at application level. Figure 16 shows the ER of some
benchmarks relative to baseline when the precision range is varied. We confirm
that 8 to 9 bits of precision is more robust compared to others and on average
outperforms the others.

Figure 16: Energy Residual of random benchmarks on D-Wave QA hardware using
EQUAL relative to the baseline for different values of bit precision used for
generating QMIs.

###  5.7 Case-Study: How EQUAL+ reduces Systematic Bias

Figure 14 shows the histograms of energy values of benchmark B1 for EQUAL and
EQUAL+. We observe that the optimal solution is at a distance $d_{1}$ from the
ground state energy in EQUAL. EQUAL+ exploits the shifting property of SQC to
obtain a solution at distance $d_{2}$ and is closer to the ground state energy
($d_{2}<d_{1}$). Note that EQUAL+ shifts the overall histogram towards the
ideal solution and achieves the intended goal. As EQUAL+ applies post-
processing on the outcomes from the QMIs, the introduced shift in the
histogram does not alter the original problem Hamiltonian.

###  5.8 Impact of Number of Ensembles

We study the impact of the number of ensembles on the effectiveness of EQUAL
using a single benchmark problem. For a given trial budget of 100K trials, we
choose two modes for EQUAL. In the first instance, we use 10 QMIs and run each
of them for 10K trials each. In the second instance, we use 100 QMIs and run
each of them for 1K trials each. Figure 17 shows the ER for the baseline and
these two instances of EQUAL. Note that we access the QA device through cloud
services and a more rigorous sensitivity analysis in terms of QMIs and trials
is challenging. We observe that executing more QMIs introduces more randomness
and makes them vulnerable to sampling errors. EQUAL with 10 QMIs achieve a
sweet spot between the baseline and EQUAL with a large number of ensembles
such that we have both diversity as well as sufficient trials for each QMI to
reduce sampling errors.

Figure 17: Energy Residual for benchmark (B1). The baseline executes a single
QMI for all 100K trials. EQUAL has 10 QMIs for 10K trials each or 100 QMIs
executed for 1K trials each.

##  6 Related Work

Both gate-model quantum computers and QAs promise significant advantages for a
wide range of applications [7, 28, 76, 45, 17, 80, 91, 90, 16, 84, 13, 68, 74,
39, 75, 14, 12, 43, 27, 49, 59]. Thus, developing error-mitigation policies is
an active area of research for both QAs and gate-model quantum computers. We
discuss prior works and compare against schemes that use ensembles.

###  6.1 Priors works using Ensembles

The potential of ensembles has been explored for both gate-model quantum
computers and QAs.

Ensemble policies for Gate-model quantum computers: Systematic bias in QAs is
similar to correlated errors on gate-based quantum computers. To tackle these
errors on gate-model quantum computers, recent studies propose the use of
ensemble of mappings that maps a program to different sets of physical qubits
and SWAP routes on the same [86] or different machines [71]. This process
produces functionally identical copies of the same program but are only
executed differently. Leveraging a similar approach for EQUAL is non-trivial
due to the complexities involved in the embedding process, particularly for
problems at scale. Obtaining alternate embeddings is non-trivial, may fail or
result in inferior quality. Instead, EQUAL uses an ensemble of QMIs by
introducing controlled perturbations while minimizing the alterations in the
functionality of the original problem Hamiltonian.

Ensemble policies for QAs: Using ensembles in QAs have been investigated at
the casting level for two different applications. However, as each application
uses its own casting algorithm, this approach cannot be generalized. EQUAL on
the other hand, avoids such application-specific assumptions and is applicable
irrespective of the problem at hand. In another study, Mohseni et al. proposed
a multi-level embedding scheme that uses a diverse encoding of qubits to
generate ensembles [58]. However, this approach reduces the capacity of the QA
significantly. It is also not scalable as it introduces overheads to the
embedding step, which already takes several hours for current systems.
Moreover, our studies show that finding alternate embeddings frequently fail
or result in embeddings of inferior quality for large problems. EQUAL avoids
these overheads by introducing diversity post embedding.

###  6.2 Software error mitigation policies

These techniques are either applied prior to the execution of the QMI (pre-
processing) or after the QMI is executed (post-processing). Pre-processing
schemes transform the problem QMI at the casting or embedding level such that
it is less vulnerable to errors during execution time [73, 9, 13, 12]. Pre-
processing schemes are analogous to compiler-level optimizations on gate-model
quantum computers [85, 62, 69, 52, 3, 61, 61, 70, 82, 95, 15, 50, 31, 86, 60,
2, 63, 71, 87, 88, 51, 32]. Unlike QAs, gate-model quantum computers have
higher programmability and allow programmers to leverage fine-grained
optimizations at the instruction scheduling level. Post-processing schemes for
QAs exploit the fact that even if a QA cannot generate the solution with the
lowest energy, it quickly locates the neighborhood where the optimal solution
might reside. By modifying the outcome obtained from the QA using classical
heuristic algorithms, post-processing schemes can significantly improve the
quality of solutions [9, 19, 33]. One of the most promising post-processing
schemes is Multi-Qubit Correction (MQC) [9]. We use this scheme to obtain the
best known estimate of the ground state energy in our evaluations. However,
this algorithm requires significant classical computational overheads and may
take up to days to obtain a better quality solution. Nonetheless, the
performance of MQC depends on the quality of the outcomes obtained from the QA
and both EQUAL and EQUAL+ can benefit from it. Post-processing algorithms can
significantly improve the application fidelity even for gate-based quantum
computers [40, 20, 71, 72].

###  6.3 Hardware-level error mitigation

Recent studies have proposed improvements to the annealing process itself [65,
4] but implementing them requires fabricating newer QAs. Few other schemes
reduce the impact of noise on the annealing process. Examples include
controlling the delay between two consecutive trials and qubit preparation
times [41]. Exposing the hardware characteristics and enabling device-level
controls to the programmer has been shown to be effective even for gate-model
systems [8].

##  7 Conclusion

Quantum Annealers (QAs) have thousands of qubits and are promising for a wide
range of applications. Unfortunately, QA suffers from both hardware and
software limitations. Therefore, there is increasing interest in developing
software policies to tackle these limitations. However, our studies show that
executing a program on a QA makes it vulnerable to a systematic bias that
cannot be overcome by increasing the number of trials or relying on existing
error-mitigation schemes.

This paper proposes EQUAL—Ensemble Quantum Annealing—a software framework that
creates multiple perturbed copies of an input problem by injecting controlled
perturbations to the original problem Hamiltonian. By executing an ensemble of
quantum machine instructions (QMIs), EQUAL projects the program to different
noise profiles and therefore, different biases. 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. We also propose EQUAL+ that exploits the properties of
existing error mitigation schemes for enhanced performance. EQUAL+ bridges the
difference between the baseline and the ideal by an average of 55% (and up to
68%).

##  Appendix A Appendix: Characterizing Error Mitigation

While designing EQUAL+, we have various options regarding how to combine
existing error-mitigation schemes. To understand suitable candidates, we
perform several characterization experiments whose results are described next.

###  A.1 Spin-Reversal vs. Single Qubit Correction

Spin-Reversal Transform (SRT) is a pre-processing which flips randomly
selected qubits to mitigate analog errors of QAs [73]. Figure 19 shows the
Energy Residual of a benchmark executed on D-Wave QA when spin reversal
transform is applied standalone and in the presence of SQC. We observe that
both spin reversal and SQC reduces the ER, and the performance of SQC is
comparable to spin-reversal transform.

Figure 18: Energy Residual of a random benchmark with Spin Reversal Transform
and Single Qubit Correction.

###  A.2 Inter-Sample Delay vs. Single Qubit Correction

Increasing the Inter-Sample-Delay (ISD) which increases the delay between
successive QA reads to reduce the inter-sample correlations. Figure 19 shows
the ER of a benchmark executed on D-Wave QA under default ISD and when the ISD
is increased. We also study the performance in the presence of SQC. We observe
that similar to spin-reversal transform, while longer ISD reduces the ER, SQC
outperforms and can be combined for further benefits.

Figure 19: Energy Residual of a random benchmark with longer ISD and Single
Qubit Correction.

We leverage the insights from this study to investigate if EQUAL can benefit
from post-processing too. The additional advantage of relying on post-
processing schemes is that it does not add any overheads in the casting or
embedding step.

## Acknowledgements

Ramin Ayanzadeh was supported by the NSF Computing Innovation Fellows (CI-
Fellows) program. Poulami Das was supported by the Microsoft Research PhD
fellowship. This research was partially supported by the Office of the Vice
Chancellor for Research and Graduate Education at the University of
Wisconsin–Madison with funding from the Wisconsin Alumni Research Foundation.

## References

  * [1] Ravindra K Ahuja, Claudio B Cunha, and Güvenç Şahin.  Network models in railroad planning and scheduling.  In Emerging theory, methods, and applications, pages 54–101. INFORMS, 2005.
  * [2] Mahabubul Alam, Abdullah Ash-Saki, and Swaroop Ghosh.  Circuit compilation methodologies for quantum approximate optimization algorithm.  In 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 215–228. IEEE, 2020.
  * [3] Mahabubul Alam, Abdullah Ash-Saki, and Swaroop Ghosh.  An efficient circuit compilation flow for quantum approximate optimization algorithm.  In 2020 57th ACM/IEEE Design Automation Conference (DAC), pages 1–6. IEEE, 2020.
  * [4] Tameem Albash and Daniel A Lidar.  Adiabatic quantum computation.  Reviews of Modern Physics, 90(1):015002, 2018.
  * [5] Patricia Amara, D Hsu, and John E Straub.  Global energy minimum searches using an approximate solution of the imaginary time schrödinger equation.  The Journal of Physical Chemistry, 97(25):6715–6721, 1993.
  * [6] Amazon.  Amazon Braket - Explore and experiment with quantum computing:.  https://aws.amazon.com/braket/, 2022.  [Online; accessed 22-July-2021].
  * [7] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * [8] Abe Asfaw, Thomas Alexander, Paul Nation, and Jay Gambetta.  Get to the heart of real quantum hardware.  https://www.ibm.com/blogs/research/2019/12/qiskit-openpulse/, 2019\.  [Online; accessed 08-August-2022].
  * [9] Ramin Ayanzadeh, John Dorband, Milton Halem, and Tim Finin.  Multi-qubit correction for quantum annealers.  Scientific Reports, 11, 2021.
  * [10] Ramin Ayanzadeh, John Dorband, Milton Halem, and Tim Finin.  Multi qubit correction (mqc) for quantum annealers, 2021.  Python implementation of MQC.
  * [11] Ramin Ayanzadeh, Milton Halem, John Dorband, and Tim Finin.  Quantum-assisted greedy algorithms.  arXiv preprint arXiv:1912.02362, 2019.
  * [12] Ramin Ayanzadeh, Milton Halem, and Tim Finin.  An ensemble approach for compressive sensing with quantum annealers.  In IGARSS 2020-2020 IEEE International Geoscience and Remote Sensing Symposium, pages 3517–3520. IEEE, 2020.
  * [13] Ramin Ayanzadeh, Milton Halem, and Tim Finin.  Reinforcement quantum annealing: A hybrid quantum learning automata.  Scientific Reports, 10(1):1–11, 2020.
  * [14] Ramin Ayanzadeh, Seyedahmad Mousavi, Milton Halem, and Tim Finin.  Quantum annealing based binary compressive sensing with matrix uncertainty.  arXiv preprint arXiv:1901.00088, 2019.
  * [15] George S Barron and Christopher J Wood.  Measurement error mitigation for variational quantum algorithms.  arXiv preprint arXiv:2010.08520, 2020.
  * [16] Zhengbing Bian, Fabian Chudak, Robert Brian Israel, Brad Lackey, William G Macready, and Aidan Roy.  Mapping constrained optimization problems to quantum annealing with application to fault diagnosis.  Frontiers in ICT, 3:14, 2016.
  * [17] Rupak Biswas, Zhang Jiang, Kostya Kechezhi, Sergey Knysh, Salvatore Mandra, Bryan O’Gorman, Alejandro Perdomo-Ortiz, Andre Petukhov, John Realpe-Gómez, Eleanor Rieffel, et al.  A nasa perspective on quantum computing: Opportunities and challenges.  Parallel Computing, 64:81–98, 2017.
  * [18] Tomas Boothby, Andrew D King, and Aidan Roy.  Fast clique minor generation in chimera qubit connectivity graphs.  Quantum Information Processing, 15(1):495–508, 2016.
  * [19] Ajinkya Borle and Josh McCarter.  On post-processing the results of quantum optimizers.  In International Conference on Theory and Practice of Natural Computing, pages 222–233. Springer, 2019.
  * [20] Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C Mckay, and Jay M Gambetta.  Mitigating measurement errors in multi-qubit experiments.  arXiv preprint arXiv:2006.14044, 2020.
  * [21] Jun Cai, William G Macready, and Aidan Roy.  A practical heuristic for finding graph minors.  arXiv preprint arXiv:1406.2741, 2014.
  * [22] Brian Carlson, Yonghong Chen, Mingguo Hong, Roy Jones, Kevin Larson, Xingwang Ma, Peter Nieuwesteeg, Haili Song, Kimberly Sperry, Matthew Tackett, et al.  Miso unlocks billions in savings through the application of operations research for energy and ancillary services markets.  Interfaces, 42(1):58–73, 2012.
  * [23] International Business Machines Corporation.  Universal Quantum Computer Development at IBM:.  http://research.ibm.com/ibm-q/research/, 2021.  [Online; accessed 22-July-2021].
  * [24] Arnab Das and Bikas K Chakrabarti.  Colloquium: Quantum annealing and analog quantum computation.  Reviews of Modern Physics, 80(3):1061, 2008.
  * [25] Prasanna Date, Robert Patton, Catherine Schuman, and Thomas Potok.  Efficiently embedding qubo problems on adiabatic quantum computers.  Quantum Information Processing, 18(4):1–31, 2019.
  * [26] John E Dorband.  Extending the d-wave with support for higher precision coefficients.  arXiv preprint arXiv:1807.05244, 2018.
  * [27] Nada Elsokkary, Faisal Shah Khan, Davide La Torre, Travis S Humble, and Joel Gottlieb.  Financial portfolio management using d-wave quantum optimizer: The case of abu dhabi securities exchange.  Technical report, Oak Ridge National Lab.(ORNL), Oak Ridge, TN (United States), 2017.
  * [28] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  A quantum approximate optimization algorithm.  arXiv preprint arXiv:1411.4028, 2014.
  * [29] RP Feynman.  Simulating physics with computers.  International Journal of Theoretical Physics, 21(6), 1982.
  * [30] AB Finnila, MA Gomez, C Sebenik, C Stenson, and JD Doll.  Quantum annealing: a new method for minimizing multidimensional functions.  Chemical physics letters, 219(5-6):343–348, 1994.
  * [31] Pranav Gokhale, Yongshan Ding, Thomas Propson, Christopher Winkler, Nelson Leung, Yunong Shi, David I Schuster, Henry Hoffmann, and Frederic T Chong.  Partial Compilation of Variational Algorithms for Noisy Intermediate-Scale Quantum Machines.  In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, pages 266–278. ACM, 2019.
  * [32] Pranav Gokhale, Ali Javadi-Abhari, Nathan Earnest, Yunong Shi, and Frederic T Chong.  Optimized Quantum Compilation for Near-Term Algorithms with OpenPulse.  arXiv preprint arXiv:2004.11205, 2020.
  * [33] John K Golden and Daniel O’Malley.  Pre-and post-processing in quantum-computational hydrologic inverse analysis.  Quantum Information Processing, 20(5):1–18, 2021.
  * [34] Timothy D Goodrich, Blair D Sullivan, and Travis S Humble.  Optimizing adiabatic quantum program compilation using a graph-theoretic framework.  Quantum Information Processing, 17(5):1–26, 2018.
  * [35] Google.  Google Quantum AI.  https://quantumai.google/, 2022.  [Online; accessed 22-July-2021].
  * [36] Lov K Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996.
  * [37] Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, et al.  Quantum approximate optimization of non-planar graph problems on a planar superconducting processor.  Nature Physics, 17(3):332–336, 2021.
  * [38] Honeywell.  Honeywell Quantum Solutions.  https://www.honeywell.com/us/en/company/quantum, 2021.  [Online; accessed 22-July-2021].
  * [39] Feng Hu, Lucas Lamata, Mikel Sanz, Xi Chen, Xingyuan Chen, Chao Wang, and Enrique Solano.  Quantum computing cryptography: Finding cryptographic boolean functions with quantum annealing by a 2000 qubit d-wave quantum computer.  Physics Letters A, 384(10):126214, 2020.
  * [40] IBM.  Measurement Error Mitigation.  https://qiskit.org/textbook/ch-quantum-hardware/measurement-error-mitigation.html, 2010\.  [Online; accessed 26-July-2020].
  * [41] D-Wave Systems Inc.  D-wave ocean software documentation.  https://docs.ocean.dwavesys.com/en/stable/, 2022.  [Online; accessed 22-July-2021].
  * [42] D-Wave Systems Inc.  The first and only quantum computer built for business.  https://www.dwavesys.com/, 2022.  [Online; accessed 22-July-2021].
  * [43] Daisuke Inoue, Akihisa Okada, Tadayoshi Matsumori, Kazuyuki Aihara, and Hiroaki Yoshida.  Traffic signal optimization on a square lattice with quantum annealing.  Scientific reports, 11(1):1–12, 2021.
  * [44] Tadashi Kadowaki and Hidetoshi Nishimori.  Quantum annealing in the transverse ising model.  Physical Review E, 58(5):5355, 1998.
  * [45] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta.  Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets.  Nature, 549(7671):242–246, 2017.
  * [46] Hamed Karimi and Gili Rosenberg.  Boosting quantum annealer performance via sample persistence.  Quantum Information Processing, 16(7):166, 2017.
  * [47] Hamed Karimi, Gili Rosenberg, and Helmut G Katzgraber.  Effective optimization using sample persistence: A case study on quantum annealers and various monte carlo optimization methods.  Physical Review E, 96(4):043312, 2017.
  * [48] Andrew D King, Jack Raymond, Trevor Lanting, Sergei V Isakov, Masoud Mohseni, Gabriel Poulin-Lamarre, Sara Ejtemaee, William Bernoudy, Isil Ozfidan, Anatoly Yu Smirnov, et al.  Scaling advantage over path-integral monte carlo in quantum simulation of geometrically frustrated magnets.  Nature communications, 12(1):1–6, 2021.
  * [49] Koki Kitai, Jiang Guo, Shenghong Ju, Shu Tanaka, Koji Tsuda, Junichiro Shiomi, and Ryo Tamura.  Designing metamaterials with quantum annealing and factorization machines.  Physical Review Research, 2(1):013319, 2020.
  * [50] Hyeokjea Kwon and Joonwoo Bae.  A hybrid quantum-classical approach to mitigating measurement errors.  arXiv preprint arXiv:2003.12314, 2020.
  * [51] Gushu Li, Yufei Ding, and Yuan Xie.  Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices.  arXiv preprint arXiv:1809.02573, 2018.
  * [52] Junde Li, Mahabubul Alam, and Swaroop Ghosh.  Large-scale quantum approximate optimization via divide-and-conquer.  arXiv preprint arXiv:2102.13288, 2021.
  * [53] Seth Lloyd.  Universal quantum simulators.  Science, pages 1073–1078, 1996.
  * [54] Andrew Lucas.  Ising formulations of many np problems.  Frontiers in physics, 2:5, 2014.
  * [55] C McGeoch and P Farre.  The d-wave advantage system: An overview.  Technical report, Tech. Rep. (D-Wave Systems Inc, Burnaby, BC, Canada, 2020).
  * [56] Catherine C McGeoch.  Theory versus practice in annealing-based quantum computing.  Theoretical Computer Science, 2020.
  * [57] Microsoft.  Azure Quantum - Quantum Service | Microsoft Azure.  https://azure.microsoft.com/en-us/services/quantum/#product-overview, 2022\.  [Online; accessed 22-July-2021].
  * [58] Naeimeh Mohseni, Marek Narozniak, Alexey N Pyrkov, Valentin Ivannikov, Jonathan P Dowling, and Tim Byrnes.  Error suppression in adiabatic quantum computing with qubit ensembles.  npj Quantum Information, 7(1):1–10, 2021.
  * [59] Vikram Khipple Mulligan, Hans Melo, Haley Irene Merritt, Stewart Slocum, Brian D Weitzner, Andrew M Watkins, P Douglas Renfrew, Craig Pelissier, Paramjit S Arora, and Richard Bonneau.  Designing peptides on a quantum computer.  bioRxiv, page 752485, 2020.
  * [60] Prakash Murali, Jonathan M Baker, Ali Javadi-Abhari, Frederic T Chong, and Margaret Martonosi.  Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers.  In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1015–1029, 2019.
  * [61] Prakash Murali, Norbert M Linke, Margaret Martonosi, Ali Javadi Abhari, Nhung Hong Nguyen, and Cinthia Huerta Alderete.  Architecting noisy intermediate-scale quantum computers: a real-system study.  IEEE Micro, 40(3):73–80, 2020.
  * [62] Prakash Murali, Norbert Matthias Linke, Margaret Martonosi, Ali Javadi Abhari, Nhung Hong Nguyen, and Cinthia Huerta Alderete.  Full-stack, real-system quantum computer studies: Architectural comparisons and design insights.  In 2019 ACM/IEEE 46th Annual International Symposium on Computer Architecture (ISCA), pages 527–540. IEEE, 2019.
  * [63] Prakash Murali, David C McKay, Margaret Martonosi, and Ali Javadi-Abhari.  Software Mitigation of Crosstalk on Noisy Intermediate-Scale Quantum Computers.  arXiv preprint arXiv:2001.02826, 2020.
  * [64] Michael A Nielsen and Isaac L Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, 2010.
  * [65] Hidetoshi Nishimori and Kabuki Takada.  Exponential enhancement of the efficiency of quantum annealing by non-stoquastic hamiltonians.  Frontiers in ICT, 4:2, 2017.
  * [66] Masayuki Ohzeki and Hidetoshi Nishimori.  Quantum annealing: An introduction and new developments.  Journal of Computational and Theoretical Nanoscience, 8(6):963–971, 2011.
  * [67] Shuntaro Okada, Masayuki Ohzeki, Masayoshi Terabe, and Shinichiro Taguchi.  Improving solutions by embedding larger subproblems in a d-wave quantum annealer.  Scientific reports, 9(1):1–10, 2019.
  * [68] Daniel O’Malley, Velimir V Vesselinov, Boian S Alexandrov, and Ludmil B Alexandrov.  Nonnegative/binary matrix factorization with a d-wave quantum annealer.  PloS one, 13(12):e0206653, 2018.
  * [69] Tirthak Patel, Baolin Li, Rohan Basu Roy, and Devesh Tiwari.  $\\{$UREQA$\\}$: Leveraging operation-aware error rates for effective quantum circuit mapping on nisq-era quantum computers.  In 2020 $\\{$USENIX$\\}$ Annual Technical Conference ($\\{$USENIX$\\}$$\\{$ATC$\\}$ 20), pages 705–711, 2020.
  * [70] Tirthak Patel and Devesh Tiwari.  Disq: a novel quantum output state classification method on ibm quantum computers using openpulse.  In Proceedings of the 39th International Conference on Computer-Aided Design, pages 1–9, 2020.
  * [71] Tirthak Patel and Devesh Tiwari.  Veritas: accurately estimating the correct output on noisy intermediate-scale quantum computers.  In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–16. IEEE, 2020.
  * [72] Tirthak Patel and Devesh Tiwari.  Qraft: reverse your quantum circuit and know the correct program output.  In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 443–455, 2021.
  * [73] Elijah Pelofske, Georg Hahn, and Hristo Djidjev.  Optimizing the spin reversal transform on the d-wave 2000q.  arXiv preprint arXiv:1906.10955, 2019.
  * [74] WangChun Peng, BaoNan Wang, Feng Hu, YunJiang Wang, XianJin Fang, XingYuan Chen, and Chao Wang.  Factoring larger integers with fewer qubits via quantum annealing with optimized parameters.  SCIENCE CHINA Physics, Mechanics & Astronomy, 62(6):60311, 2019\.
  * [75] Alejandro Perdomo-Ortiz, Joseph Fluegemann, Sriram Narasimhan, Rupak Biswas, and Vadim N Smelyanskiy.  A quantum annealing approach for fault detection and diagnosis of graph-based systems.  The European Physical Journal Special Topics, 224(1):131–148, 2015\.
  * [76] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alan Aspuru-Guzik, and Jeremy L O’brien.  A variational eigenvalue solver on a photonic quantum processor.  Nature communications, 5(1):1–7, 2014.
  * [77] John Preskill.  Quantum computing in the nisq era and beyond.  arXiv preprint arXiv:1801.00862, 2018.
  * [78] Kristen L Pudenz, Tameem Albash, and Daniel A Lidar.  Quantum annealing correction for random ising problems.  Physical Review A, 91(4):042302, 2015.
  * [79] Google AI Quantum and Collaborators.  Sycamore qaoa experimental data.  7 2020.
  * [80] Eleanor G Rieffel, Davide Venturelli, Bryan O’Gorman, Minh B Do, Elicia M Prystay, and Vadim N Smelyanskiy.  A case study in programming a quantum annealer for hard operational planning problems.  Quantum Information Processing, 14(1):1–36, 2015.
  * [81] David Sherrington and Scott Kirkpatrick.  Solvable model of a spin-glass.  Physical review letters, 35(26):1792, 1975.
  * [82] Yunong Shi, Nelson Leung, Pranav Gokhale, Zane Rossi, David I Schuster, Henry Hoffmann, and Frederic T Chong.  Optimized compilation of aggregated instructions for realistic quantum computers.  In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1031–1044, 2019.
  * [83] Peter W Shor.  Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.  SIAM review, 41(2):303–332, 1999.
  * [84] Juexiao Su, Tianheng Tu, and Lei He.  A quantum annealing approach for boolean satisfiability problem.  In Proceedings of the 53rd Annual Design Automation Conference, page 148. ACM, 2016.
  * [85] Wei Tang, Teague Tomesh, Martin Suchara, Jeffrey Larson, and Margaret Martonosi.  Cutqc: using small quantum computers for large quantum circuit evaluations.  In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 473–486, 2021.
  * [86] Swamit S Tannu and Moinuddin Qureshi.  Ensemble of diverse mappings: Improving reliability of quantum computers by orchestrating dissimilar mistakes.  In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, pages 253–265, 2019.
  * [87] Swamit S Tannu and Moinuddin K Qureshi.  Mitigating measurement errors in quantum computers by exploiting state-dependent bias.  In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, pages 279–290, 2019.
  * [88] Swamit S Tannu and Moinuddin K Qureshi.  Not all qubits are created equal: a case for variability-aware policies for nisq-era quantum computers.  In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 987–999, 2019.
  * [89] Quantum AI team and collaborators.  Recirq, October 2020.
  * [90] Tony T Tran, Minh Do, Eleanor G Rieffel, Jeremy Frank, Zhihui Wang, Bryan O’Gorman, Davide Venturelli, and J Christopher Beck.  A hybrid quantum-classical approach to solving scheduling problems.  In Ninth annual symposium on combinatorial search, 2016.
  * [91] Davide Venturelli, Dominic JJ Marchand, and Galo Rojo.  Quantum annealing implementation of job-shop scheduling.  arXiv preprint arXiv:1506.08479, 2015.
  * [92] Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S Humble, Rupak Biswas, Eleanor G Rieffel, Alan Ho, and Salvatore Mandrà.  Establishing the quantum supremacy frontier with a 281 pflop/s simulation.  Quantum Science and Technology, 5(3):034003, 2020.
  * [93] Walter Vinci, Tameem Albash, and Daniel A Lidar.  Nested quantum annealing correction.  npj Quantum Information, 2(1):1–6, 2016.
  * [94] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, et al.  Strong quantum computational advantage using a superconducting quantum processor.  arXiv preprint arXiv:2106.14734, 2021.
  * [95] Alwin Zulehner, Alexandru Paler, and Robert Wille.  An efficient methodology for mapping quantum circuits to the ibm qx architectures.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 38(7):1226–1236, 2018.