# Test Case Minimization with Quantum Annealers

Xinyi Wang
Simula Research Laboratory
Oslo, Norway
<EMAIL_ADDRESS>
&Asmar Muqeet
Simula Research Laboratory
University of Oslo
Oslo, Norway
<EMAIL_ADDRESS>
&Tao Yue
Simula Research Laboratory
Oslo, Norway
<EMAIL_ADDRESS>
&Shaukat Ali
Simula Research Laboratory and
Oslo Metropolitan University
Oslo, Norway
<EMAIL_ADDRESS>
&Paolo Arcaini
National Institute of Informatics
Tokyo, Japan
<EMAIL_ADDRESS>

###### Abstract

Quantum annealers are specialized quantum computers for solving combinatorial
optimization problems using special characteristics of quantum computing (QC),
such as superposition, entanglement, and quantum tunneling. Theoretically,
quantum annealers can outperform classical computers. However, the currently
available quantum annealers are small-scale, i.e., they have limited quantum
bits (qubits); hence, they currently cannot demonstrate the quantum advantage.
Nonetheless, research is warranted to develop novel mechanisms to formulate
combinatorial optimization problems for quantum annealing (QA). However,
solving combinatorial problems with QA in software engineering remains
unexplored. Toward this end, we propose BootQA, the very first effort at
solving the test case minimization (TCM) problem with QA. In BootQA, we
provide a novel formulation of TCM for QA, followed by devising a mechanism to
incorporate bootstrap sampling to QA to optimize the use of qubits. We also
implemented our TCM formulation in three other optimization processes:
classical simulated annealing (SA), QA without problem decomposition, and QA
with an existing D-Wave problem decomposition strategy, and conducted an
empirical evaluation with three real-world TCM datasets. Results show that
BootQA outperforms QA without problem decomposition and QA with the existing
decomposition strategy in terms of effectiveness. Moreover, BootQA’s
effectiveness is similar to SA. Finally, BootQA has higher efficiency in terms
of time when solving large TCM problems than the other three optimization
processes.

_K_ eywords quantum annealer $\cdot$ test case minimization $\cdot$ D-Wave
$\cdot$ quantum computing

##  1 Introduction

Quantum Computing (QC) is pledging to unravel complex computational problems
more efficiently than classical computing [1]. One particular application of
QC in the near future is solving combinatorial optimization problems. To this
end, quantum annealers – a special kind of quantum computers have been used to
demonstrate solving combinatorial optimization problems with quantum annealing
(QA) [2, 3, 4]. To this end, D-Wave Systems Inc.111https://www.dwavesys.com/
has commercialized quantum annealers and continuously increases the number of
quantum bits (qubits). Currently, the most powerful system from D-Wave is the
Advantage system with more than 5,000 qubits. Theoretically, QA can solve
optimization problems faster than state-of-the-art algorithms on classical
computers [5]. However, due to the small scale of currently available quantum
annealers, demonstrating their quantum advantage over the classical is
practically impossible. Current research challenges include devising novel
problem encoding mechanisms and optimally utilizing the limited number of
available qubits. With this purpose, some research has already experimentally
demonstrated the potential of using QA for solving combinatorial optimization
problems [2, 3, 4]. However, QA has not been investigated for solving
optimization problems in software engineering, including test optimization.
Test optimization aims to improve the cost-effectiveness of software testing.
Particularly, in the context of regression testing, test optimization can be
applied to select and prioritize a subset of test cases for testing a new
software version from the test suite used for testing previous software
versions. Test optimization can involve various optimization objectives, such
as minimizing the number of test cases to select to improve the test
efficiency and maximizing the fault detection rate of the selected test cases
to enhance the test effectiveness. In the literature, a range of test
optimization solutions have been proposed [6, 7], and search algorithms (e.g.,
NSGA-II [8]) have been commonly used for cost-effectively solving various test
optimization problems [9, 10, 11].

In this paper, we aim to address the test case minimization (TCM) problem with
QA, which aims to find a minimum number of test cases for execution [7].
However, two main research challenges exist. First, considering that QA solves
an optimization problem by formulating it as an Ising Model or a Quadratic
Unconstrained Binary Optimization (QUBO) model, we, hence, need a novel
formulation for TCM. Second, current quantum annealers have a limited number
of qubits. Therefore, they cannot be directly employed to solve complex TCM
problems with large numbers of test cases, and new methods are needed to
optimize the use of qubits.

In this paper, we propose BootQA to address the above two challenges. In
particular, first, we propose a novel and generic QUBO formulation for TCM
problems. Second, to optimize the use of qubits to solve large TCM problems,
we introduce bootstrap sampling [12] to the QA process. To investigate the
cost-effectiveness of BootQA, we also implemented our QUBO formulation in
three other optimization processes: classical Simulated Annealing (SA), QA
without sub-problem decomposing, and QA with an existing decomposing strategy
of D-Wave. We perform an empirical evaluation on three real-world datasets and
evaluate the four optimization processes regarding their effectiveness and
time efficiency in solving the three TCM problems. Results show that BootQA
exhibits similar effectiveness with SA and outperforms the other two Quantum
Processing Unit (QPU) based processes. Moreover, BootQA shows the highest time
efficiency among all, especially for large-scale TCM problems. We provide the
experiment results and implementations in the online repository:
https://github.com/AsmarMuqeet/BootQA.

In the rest of the paper, Sect. 2 introduces the background, and Sect. 3
discusses the related work. Sect. 4 presents the proposed test case
minimization approach with QA. Sect. 5 presents the empirical evaluation, and
Sect. 6 presents the evaluation results, followed by discussions in Sect. 7.
We conclude the paper in Sect. 8.

##  2 Background

QA is based on the adiabatic theorem [13, 14], stating that if a quantum
system is initialized in a _ground state_ (i.e., the lowest energy state) and
the _Hamiltonian_ 222In quantum mechanics, the Hamiltonian of a quantum system
specifies its total energy [5], i.e., the sum of both the kinetic and
potential energy of the system. of the system changes sufficiently slowly, the
quantum system will remain in the ground state during the system evolution.
The adiabatic theorem can solve optimization problems by preparing a quantum
system in a ground state of an easy-to-implement initial Hamiltonian and
slowly evolving the initial Hamiltonian to the final Hamiltonian, whose ground
state encodes solutions that solve the optimization problem. Below, we
introduce the three main steps of solving an optimization problem with QA on a
D-Wave QPU as described in [15].

Step 1: Objective function and QUBO formalization. A minimization objective
function is defined as a mathematical expression representing the energy of
the quantum system, which is converted into an Ising [16] or QUBO model to be
implemented on QA hardware. For D-Wave QA, QUBO is the standard model, which
is a quadratic formulation with binary variables and formatted as a real-
valued upper-diagonal weight matrix $Q$ with its dimensions defined by the
number of binary variables [17], defined as follows:

$\min
f(\boldsymbol{x})=\boldsymbol{x}^{\mathrm{T}}Q\boldsymbol{x}=\sum_{i}Q_{i,i}x_{i}+\sum_{i<j}Q_{i,j}x_{i}x_{j}$
(1)

where $\boldsymbol{x}$ is the vector of binary decision variables, and
$\boldsymbol{x}^{\mathrm{T}}$ is the transpose of $\boldsymbol{x}$. Diagonal
terms $Q_{i,i}$ in $Q$ are the linear coefficients, and off-diagonal terms
$Q_{i,j}$ are quadratic coefficients. For example, for a three-variable
$(x_{0},x_{1},x_{2})$ problem, the generic QUBO formulation is as follows:

$\min
f(\boldsymbol{x})=\begin{bmatrix}x_{0}\,x_{1}\,x_{2}\end{bmatrix}\begin{bmatrix}Q_{00}&Q_{01}&Q_{02}\\\
0&Q_{11}&Q_{12}\\\ 0&0&Q_{22}\end{bmatrix}\begin{bmatrix}x_{0}\\\ x_{1}\\\
x_{2}\end{bmatrix}$

With Eq. 1, we convert an optimization problem into a _QUBO graph_ where each
variable is represented as a node, and each non-zero off-diagonal term is
represented as an edge between a pair of nodes connecting the corresponding
variables, as shown, for example, in Fig. 1(a).

(a) QUBO graph

(b) Working graph

Figure 1: QUBO formalization for a three-variable problem

Step 2: Minor-embedding. We map a QUBO graph into a working graph describing
how physical qubits are organized and connected in the QA hardware. The
process is called minor-embedding, e.g., Chimera topology for the D-Wave 2000Q
system and Pegasus for the Advantage system [18, 19]. In a working graph
(e.g., Fig. 1(b)), each node represents a physical qubit, and each edge
connecting a pair of nodes (i.e., physical qubits) denotes a coupler. Ideally,
each node in the QUBO graph (e.g., Fig. 1(a)) should be mapped to a physical
qubit, and each edge should be mapped to a coupler. However, since the working
graph might not be fully connected, not all QUBO problems can be perfectly
embedded into QA. For instance, to directly map the full-connected QUBO graph
in Fig. 1(a) onto the working graph in Fig. 1(b), direct physical connections
between any two pairs of three qubits representing three variables are needed,
which is not the case for this working graph. To handle this, D-Wave
introduced chain, which groups multiple physically connected qubits that can
represent a node together (a variable in the QUBO formulation) of the QUBO
graph. All the physical qubits in one chain act together as a single logical
qubit to solve the optimization problem. In this example, $x_{1}$ from the
QUBO graph (Fig. 1(a)) is mapped to two physical qubits in the working graph,
i.e., a chain. As a result, each pair of variables is now connected in the
working graph using this chain.

Minor embedding is time-consuming and requires specific algorithms to find
suitable solutions [20]. A significant quantity of qubits and couplers is
needed to embed some large and densely connected QUBO graphs. In this paper,
we used the algorithms implemented by D-Wave for minor embedding.

Step 3: Programming, initialization, and sampling. In the programming process,
coefficients of the defined QUBO model are involved in defining the final
Hamiltonian of the quantum system. Each linear coefficient is applied as
weight qubit bias, while each quadratic coefficient is mapped as coupler
strength in the QA hardware. After programming, all qubits are initialized in
equal superposition as the initial Hamiltonian of the system.

QA is a heuristic algorithm. As a result, it cannot guarantee finding the
optimal solution, i.e., reaching the system’s ground state. Thus, multiple
sampling processes are required to generate multiple candidate solutions in an
execution. The number of sampling processes is determined by the number of
reads parameter in D-Wave QPU-API. Each sampling process has an annealing
process and a read-out process. In the annealing process, the quantum system
evolves from the initial to the final Hamiltonian in a time-dependent manner
according to the Schrödinger equation. When the system reaches the final
Hamiltonian’s ground state, all qubits are read out, and the values represent
a candidate solution. Generally, we consider the solution with the lowest
energy as the optimal solution generated by QA.

##  3 Related Work

Quantum annealing for optimization. Several QA applications in various domains
have emerged recently, such as portfolio problem [21], machine learning [22,
23, 24], routing problems (e.g., traveling salesman [25, 26], vehicle routing
[27], control of traffic signal [28, 29], process job scheduling [30, 31]),
and logistical network design [32]. Though QA has shown promising results in
solving optimization problems in these domains, the potential for test case
optimization remains unexplored, which is the focus of this paper.

Test case optimization for classical software. Test case optimization is often
classified into test case prioritization and TCM [33]. Test case
prioritization aims to identify the most optimal ordering of test cases for
execution, while TCM revolves around selecting a minimum subset of test cases
that minimizes the overall test execution cost while maximizing the overall
fault detection capability, etc. Test case optimization has been extensively
studied in the literature [34, 35, 36]. For instance, the authors of the
survey in [6] identified and studied 90 test case optimization approaches and
concluded that search-based (evolutionary algorithms, search algorithms) and
clustering techniques are the most commonly used techniques. Another survey
[7] analyzes 29 TCM and prioritization approaches with machine learning
applied. The survey concludes that these approaches mainly employ supervised
learning, reinforcement learning, and natural language processing-based
methods. Current machine learning-based approaches in software development
pipelines with continuous integration are unsuitable since they require the
reconstruction of machine learning models from scratch from time to time. In
contrast to existing works in the literature, we focus on using quantum
annealers for TCM. Thus, our work is the first work on using quantum computers
for solving TCM problems.

Quantum software testing. In quantum software engineering [37, 38], quantum
software testing [39, 40, 41] is an active research sub-area. Several quantum
software testing approaches have been proposed, such as based on search
algorithms [42, 43, 44], mutation testing [45, 46, 47, 48], fuzzing [44],
metamorphic testing [49, 50], and combinatorial testing [51], which all focus
on generating test cases for testing quantum programs. In contrast, in this
paper, we propose BootQA to minimize test suites for testing classical
software with quantum computers.

##  4 Quantum annealing for test case minimization

Figure 2: Overview of BootQA

This section, first, introduces the overview of the BootQA (Sect. 4.1).
Second, we define the generic QUBO formulation (Sect. 4.2) and illustrate it
with the running example.

###  4.1 Overview of BootQA

A QUBO formulation can be represented as a QUBO graph (see Sect. 2). If a QUBO
graph has many nodes and connections among them, a substantial amount of
qubits and couplers in the hardware are needed to embed the whole problem,
which is not be supported by today’s QA hardware. To circumvent this issue, we
use a bootstrap sampling strategy (Fig. 2, left side) to decompose the
original TCM problem into smaller sub-problems. Generally, bootstrap sampling
creates small sub-problems by sampling subsets of test cases from the entire
test suite to ensure that each sub-problem is solvable on the QA hardware.
Note that each subset is created from the entire test suite; hence each test
case may appear in different subsets, and all subsets are independent.

Specifically, given a test suite $\mathit{TS}$, we decompose the original test
suite into $M$ smaller test suites of size $N$ as shown in Figure 2. $N$ is
given by considering the maximum number of qubits and couplers supported by a
given QA hardware. We randomly sample $M$ subsets of $\mathit{TS}$ of size
$N$, i.e., $Subset_{0}$, $Subset_{1}$, …, $Subset_{M-1}$, repeatedly until a
certain percentage of $\mathit{TS}$ is covered. This coverage percentage is a
hyper-parameter $\beta$ of BootQA. These subsets are used as the input to
formulate the sub-problems according to the QUBO formulation (Sect. 4.2). Each
sub-problem is solved individually with QA, and as a result, a corresponding
sub-solution is produced.

For each sub-problem (Fig. 2, right side), we construct an overall objective
function based on test cases and their properties in the sub-problem, which is
an instance of the generic QUBO formulation introduced in Sect. 4.2. We first
extract the properties of test cases in each subset as optimization
objectives. Second, we combine them into the overall objective function as a
QUBO formulation (Step 1). With the QUBO graph converted from the formulation,
we embed it into the hardware working graph (Step 2: minor-embedding). After
the process of programming, initialization and sampling (Step 3), among all
candidate solutions, we choose the solution with the lowest energy as the sub-
solution of the sub-problem (see details in Sect. 2).

Eventually, for $M$ sub-problems, we obtain $M$ sub-solutions, each of which
is a subset of the original test suite. Each selected test case in each sub-
problem is considered as a selected test case in the final solution for the
whole problem. In other words, we merge all the unique test cases selected in
all sub-solutions to form the final solution for the whole problem.

###  4.2 QUBO Formulation for Test Case Minimization

TCM selects the smallest possible subset of test cases out of the total set of
test cases available, for the software under test (SUT), while satisfying all
testing objectives as much as possible. Examples of objectives include
minimizing the overall test execution time and maximizing the fault detection
rate of the selected subset of test cases, whose corresponding values can be
obtained based on the history executions. For TCM, the selection of each test
case is represented as a binary variable $t_{i}$. If $t_{i}$ takes the value
of 1, it means that the $i$-th test case is selected and 0 otherwise.
Consequently, we represent the vector of $s$ variables in the QUBO as
$\boldsymbol{t}=[t_{0},$ $t_{1},$ $\ldots,$ $t_{s-1}]$.

Each test case is characterized with $r$ properties. Each property is
associated with one testing objective. We represent the set of $r$ properties
as $P=\\{p_{0},$ $p_{1},$ $\ldots,$ $p_{r-1}\\}$.

######  Example 1.

To explain our approach, we use a small-scale running example composed of two
test cases, shown in Table 1.

Table 1: Running Example

Test Case ID | Execution Time $\mathtt{et}$ (s) | Failure Rate $\mathtt{fr}$ (%)
---|---|---
$t_{0}$ | 10 | 80%
$t_{1}$ | 20 | 40%

Each test case has two properties: execution time ($\mathtt{et}$) and failure
rate ($\mathtt{fr}$), shown as two columns in Table 1. The values of these two
properties are based on the history of test executions. The test case
execution time is the average time a test case takes across all its
executions. The failure rate is the percentage of times a test case failed out
of the total number of executions during the history executions. For example,
test case $t_{0}$ has execution time of 10 seconds and failure rate of 80%.
$\lhd$

For the $h$-th property, the vector of the values of all test cases is
represented as $\boldsymbol{v}^{p_{h}}=$ $[v_{0}^{p_{h}},$ $v_{1}^{p_{h}},$
$\ldots,$ $v_{s-1}^{p_{h}}]$, where $v_{i}^{p_{h}}$ represents the $h$-th
property value of $t_{i}$. A TCM approach maximizes the overall effectiveness
while minimizing the overall cost with the selected test cases. To this end,
some properties shall be maximized (e.g., failure rate in our running
example), and others shall be minimized (e.g., execution time in our running
example). To treat all objectives equally in the overall objective function,
we do the min-max normalization for properties whose ranges are not between 0
and 1.

For a property $p_{h}$, we aim to optimize the cumulative sum of property
values for the selected test cases. Specifically, we maximize the sum of
property values for all the selected test cases if $p_{h}$ is an
_effectiveness property_ , and conversely, we minimize the sum if $p_{h}$ is
_cost property_. To do this, we define the objective function
$\mathcal{O}_{p_{h}}$ (to be minimized) that computes the distance between the
sum of values of the property for all selected test cases and the
corresponding property’s theoretical limit $L^{p_{h}}$ with the Euclidean
distance; $L^{p_{h}}$ is the upper limit for an effectiveness property, and
the lower limit for a cost property. Formally:

$\mathcal{O}_{p_{h}}(\boldsymbol{t})={(\boldsymbol{v}^{p_{h}}}\cdot{\boldsymbol{t}}^{\mathrm{T}}-L^{p_{h}})^{2}$

where the sum of values of the property is calculated with matrix
multiplication $\boldsymbol{v}^{p_{h}}\cdot{\boldsymbol{t}}^{\mathrm{T}}$,
with ${\boldsymbol{t}}^{\mathrm{T}}$ being the transpose of $\boldsymbol{t}$.
For an effectiveness property $p_{h}$, we calculate the theoretical limit as
the sum of values of all the test cases for $p_{h}$. For a cost property, one
possible theoretical limit is 0. However, depending on the context, other
limits could be used. Since for each variable $t_{i}\in\\{0,1\\}$, it holds
that $t_{i}^{2}=t_{i}$, the above formula can then be expanded as below:

$\mathcal{O}_{p_{h}}(\boldsymbol{t})=\sum_{i=0}^{s-1}({v_{i}^{p_{h}}}^{2}-2v_{p_{i}{h}}^{p_{h}})t_{i}+2\sum^{s-1}_{i<j}v_{i}^{p_{h}}v_{j}^{p_{h}}\cdot
t_{i}t_{j}+{(L^{p_{h}})}^{2}$

######  Example 2.

For the objective of failure rate (i.e., the property $\mathtt{fr}$) of our
running example, we represent the vector of values as
$\boldsymbol{v}^{\mathtt{fr}}=[v_{0}^{\mathtt{fr}},v_{1}^{\mathtt{fr}}]$. The
vector of two test cases is represented as $\boldsymbol{t}=[t_{0},t_{1}]$. The
upper theoretical limit is $L^{\mathtt{fr}}$. The objective formulation turns
out to be:

$\begin{array}[]{ll}\mathcal{O}_{\mathtt{fr}}(\boldsymbol{t})&=(\boldsymbol{v}^{\mathtt{fr}}\cdot{\boldsymbol{t}}^{\mathrm{T}}-L^{\mathtt{fr}})^{2}=(v_{0}^{\mathtt{fr}}t_{0}+v_{1}^{\mathtt{fr}}t_{1}-L^{\mathtt{fr}})^{2}\\\
&=({v_{0}^{\mathtt{fr}}}^{2}-2L^{\mathtt{fr}}v_{0}^{\mathtt{fr}})t_{0}+({v_{1}^{\mathtt{fr}}}^{2}-2L^{\mathtt{fr}}v_{1}^{\mathtt{fr}})t_{1}\\\
&+2v_{0}^{\mathtt{fr}}v_{1}^{\mathtt{fr}}t_{0}t_{1}+({L^{\mathtt{fr}}})^{2}\end{array}$

Since $\boldsymbol{v}^{\mathtt{fr}}=$ $[0.8,$ $0.4]$ and
$L^{\mathtt{fr}}=1.2$, the formula above is instantiated as:

$\mathcal{O}_{\mathtt{fr}}(\boldsymbol{t})=-1.28t_{0}-0.8t_{1}+0.64t_{0}t_{1}+1.44$

Similarly, for the objective of $\mathtt{et}$, we first do normalization for
the property values. Then we get the vector
$\boldsymbol{v}^{\mathtt{et}}=[v_{0}^{\mathtt{et}},v_{1}^{\mathtt{et}}]=[0.5,1]$
and $L^{\mathtt{et}}=0$. The objective function becomes:

$\mathcal{O}_{\mathtt{et}}(\boldsymbol{t})=0.25t_{0}+t_{1}+t_{0}t_{1}$

$\lhd$

A key objective of TCM is to minimize the number of test cases selected (we
name it as $\mathtt{num}$), i.e., the size of the selected test suite should
be as small as possible. We add up the variable values in $\boldsymbol{t}$
($t_{i}\in\\{0,1\\}$ and $t_{i}=1$ denoting that $t_{i}$ is selected) to
calculate $\mathtt{num}$. To be consistent with the formalization of the other
two properties, we represent the total number of test cases selected as a
matrix multiplication:
$\boldsymbol{v}^{\mathtt{num}}\cdot{\boldsymbol{t}}^{\mathrm{T}}$, where all
values in $\boldsymbol{v}^{\mathtt{num}}$ are 1. Since we want to minimize the
number of selected test cases, we consider its lower theoretical limit
$L^{\mathtt{num}}=0$. Consequently, the objective is represented as follows:

$\mathcal{O}_{\mathtt{num}}(\boldsymbol{t})=(\boldsymbol{v}^{\mathtt{num}}\cdot\boldsymbol{t}^{\mathrm{T}}-L^{\mathtt{num}})^{2}=\sum_{i=0}^{s-1}t_{i}+2\sum_{i<j}^{s-1}t_{i}t_{j}$

######  Example 3.

In the running example, the objective function for $\mathtt{num}$ becomes
$\mathcal{O}_{\mathtt{num}}(\boldsymbol{t})=t_{0}+t_{1}+2t_{0}t_{1}$. $\lhd$

The overall objective function $\mathcal{O}_{\mathit{all}}$ can then be
calculated based on the objectives corresponding to the properties and the
objective of the number of selected test cases. We integrate all the
objectives with the weighted-sum approach, where each objective is first
normalized and then multiplied with a specific weight ($w_{\mathtt{num}}$ or
$w_{p_{h}}$) to reflect its priority in the TCM. For clarity, we do not show
normalization in the rest of the calculation. The formulation is shown below:

$\mathcal{O}_{\mathit{all}}(\boldsymbol{t})=w_{\mathtt{num}}\cdot\mathcal{O}_{\mathtt{num}}(\boldsymbol{t})+\sum_{p_{h}\in
P}w_{p_{h}}\cdot\mathcal{O}_{p_{h}}(\boldsymbol{t})$

######  Example 4.

In our running example, the overall objective is defined as follows:

$\begin{array}[]{l}\mathcal{O}_{\mathit{all}}(\boldsymbol{t})=w_{\mathtt{num}}\mathcal{O}_{\mathtt{num}}(\boldsymbol{t})+w_{\mathtt{et}}\mathcal{O}_{\mathtt{et}}(\boldsymbol{t})+w_{\mathtt{fr}}\mathcal{O}_{\mathtt{fr}}(\boldsymbol{t})\end{array}$

$\lhd$

We then transfer the overall objective function into a QUBO model. Since all
constant terms are combined to represent the offset of the energy system, and
it doesn’t affect the optimization process, we do not need to consider it in
the QUBO formulation. The general objective function is shown below: (See Eq.
1):

$\displaystyle\min\mathcal{O}_{\mathit{all}}(\boldsymbol{t})=$
$\displaystyle\sum_{i=0}^{s-1}\left(w_{\mathtt{num}}+\sum_{p_{h}\in
P}w_{p_{h}}\left({{v_{i}^{p_{h}}}^{2}}-2L^{p_{h}}\right)\right)\cdot t_{i}$
$\displaystyle+\sum^{s-1}_{i<j}\left(2w_{\mathtt{num}}+2\sum_{p_{h}\in
P}w_{p_{h}}v_{i}^{p_{h}}v_{j}^{p_{h}}\right)\cdot t_{i}t_{j}$

where $w_{\mathtt{num}}+\sum_{p_{h}\in
P}w_{p_{h}}({v_{i}^{p_{h}}}^{2}-2L^{p_{h}})$ represents the linear
coefficients (the diagonal terms in the weight matrix $Q$) and
$2w_{\mathtt{num}}+2\sum_{p_{h}\in P}w_{p_{h}}v_{i}^{p_{h}}v_{j}^{p_{h}}$
represents the quadratic coefficients (off-diagonal terms in $Q$).

######  Example 5.

With the property set $P=\\{\mathtt{fr},\mathtt{et}\\}$, the expanded
objective function without the constant term is

$\displaystyle\mathcal{O}_{\mathit{all}}(\boldsymbol{t})$
$\displaystyle=\left(w_{\mathtt{num}}+\sum_{p_{h}\in
P}w_{p_{h}}({v_{0}^{p_{h}}}^{2}-2L^{\mathtt{et}}v_{0}^{\mathtt{et}})\right)t_{0}$
$\displaystyle+\left(w_{\mathtt{num}}+\sum_{p_{h}\in
P}w_{p_{h}}({v_{1}^{p_{h}}}^{2}-2L^{\mathtt{et}}v_{1}^{\mathtt{et}})\right)t_{1}$
$\displaystyle+2\left(w_{\mathtt{num}}+\sum_{p_{h}\in
P}w_{p_{h}}v_{0}^{p_{h}}v_{1}^{p_{h}}\right)t_{0}t_{1}$

We set all three weight values as $0.33$, and we obtain:

$\displaystyle\mathcal{O}_{\mathit{all}}(\boldsymbol{t})=-0.0099t_{0}+0.396t_{1}+0.5412t_{0}t_{1}$

The objective function of the format with the $Q$ matrix is:

$\mathcal{O}_{\mathit{all}}(\boldsymbol{t})=\boldsymbol{t}Q{\boldsymbol{t}}^{\mathrm{T}}=\begin{bmatrix}t_{0}\,t_{1}\end{bmatrix}\begin{bmatrix}-0.0099&0.5412\\\
0&0.396\\\ \end{bmatrix}\begin{bmatrix}t_{0}\\\ t_{1}\end{bmatrix}$

$\lhd$

##  5 Experiment Design

We first present the research questions in Sect. 5.1, followed by the
experimental setup in Sect. 5.2, and evaluation metrics and statistical tests
in Sect. 5.3.

###  5.1 Research Questions

  * RQ1

Does the proposed QUBO formulation solve TCM problems effectively? This RQ
examines whether our QUBO formulation is effective for TCM by checking the
results of SA. If yes, we can use the same QUBO formulation for QA. This check
is necessary as we want to avoid any factor that may influence QA
effectiveness that is not due to the formulation, such as hardware noise.
Next, we compare BootQA with SA to determine if it performs similarly to SA in
solving TCM to justify its use.

  * RQ2

How is the effectiveness of BootQA compared with the QA process of not
employing any sub-problem decomposition? This RQ checks if QA with bootstrap
sampling can outperform QA without decomposing in solving a small-scale TCM
problem. Note that solving large problems with it is practically infeasible.

  * RQ3

How does BootQA compare with an existing QA algorithm with a D-Wave built-in
sub-problem decomposing? This RQ checks whether BootQA’s bootstrapping
sampling strategy helps it to perform better than an existing QA algorithm
from D-Wave with its own sub-problem decomposing process.

  * RQ4

How is the time efficiency of BootQA compared with the other three approaches?
This RQ aims to check the time cost of all approaches to obtain a
comprehensive view of their overall time efficiency.

###  5.2 Experimental Setup and Execution

Datasets. We selected three real-world datasets to evaluate BootQA:
PaintControl and IOF/ROL from ABB Robotics
Norway333http://new.abb.com/products/robotics from [52], and GSDTSR
444https://code.google.com/archive/p/google-shared-dataset-of-test-suite-
results/wikis/DataFields.wiki from Google. Each test case in these datasets
has property values related to “execution time” and “failure rate”. Since we
need test cases in the original test suite $\mathit{TS}$ that have the
possibility to trigger failures, we filtered out test cases whose failure
rates are 0. Eventually, we employed 89, 287, and 1663 test cases from
PaintControl, GSDTSR, IOF/ROL, respectively, and formed the three datasets for
our experiment.

Baselines To evaluate BootQA, we also implement our TCM formulation in QA in
the following three optimization processes and hence form three baselines. (1)
Simulated Annealing (SA). We use the dwave-neal framework from D-Wave as the
SA baseline. It uses the QUBO formulation for optimization but with classical
SA. (2) Vanilla QPU (VQ). We directly solve the TCM problems by running QA
directly on D-Wave’s QA hardware without decomposing. (3) EIDQ. We implement
EIDQ as our baseline approach, which is tailored from the default hybrid QA
algorithm from D-wave, Kerberos. This algorithm runs two classical branches
(i.e., tabu search and (SA)) and a QPU branch in parallel and searches for an
optimal solution by taking the best one from those produced by the three
branches iteratively. The number of iterations is a hyper-parameter. In our
experiment, we disabled the classical branches and we already have SA for
comparison. The QPU branch of Kerberos is interesting as it also combines a
classical decomposing technique, i.e., Energy Impact Decomposer [53], which
forms a good comparison baseline. For convenience, we name the modified
Kerberos as EIDQ. The decomposing technique applies search to find a sub-
problem of a certain size that maximally contribute to the overall objective
[53].

Parameters. Each test case in each dataset has two properties: execution time
and failure rate. For failure rate, we calculated the upper limit
($L^{\mathtt{fr}}$) as the sum of the failure rates of all test cases in one
dataset or one subset of it for BootQA since we aim to maximize the failure
rate of the test suite. For execution time, we set the lowest limit (i.e.,
$L^{\mathtt{et}}$) to 0 since we aim to minimize the execution time of the
test suite. We use equal weights in $\mathcal{O}_{\mathit{all}}$. Moreover, we
used the default settings in the D-Wave framework for hardware execution. For
the three QPU-based approaches (i.e., BootQA, EIDQ and VQ), we set the number
of reads (see Sect. 2) as 100 in each execution. For SA, we set the number of
iterations as 100. The coverage rate $\beta$ in our experiment is 90%.

We employed a range of sub-problem sizes $N$ (defining the number of test
cases in each sub-problem, see Sect. 4.2) to conduct a series of experiments
with BootQA. For GSDTSR and IOF/ROL, we went from 10 to 160 with an increment
of 10 to identify the best $N$. We stopped at 160 since our pilot study
results show that the current QA hardware was unstable in finding embeddings
for more than 160 variables. For PaintControl, the total size of the dataset
is 89; therefore, we use $N$ from 10 to 80, with an increment of 10. For a
fair comparison, we used the same number of variables (as for BootQA) as the
maximum sub-problem size of EIDQ in all iterations. We repeat experiments on
each dataset 10 times for each sub-problem size in BootQA and EIDQ. For SA and
VQ, since there is no decomposing, we repeat experiments 10 times.

Execution Environment. We used the D-Wave Advantage system [54] as the QPU,
and the classical part of the experiment was run on one CPU node in the
Ex3555EX3 is a national, experimental, heterogeneous computational cluster for
researchers conducting experiments. cluster with Intel(R) Xeon(R) Platinum
8168 CPU @ 2.70GHz.

###  5.3 Evaluation Metrics and Statistical Tests

####  5.3.1 Evaluation Metrics

We evaluate the approaches’ effectiveness with the $\mathit{FV}$ metric (the
lower, the better), which is related to the calculated objective function
values. For BootQA and EIDQ, for each sub-problem size, $\mathit{FV}$ for a
TCM problem is calculated by taking the average value of the objective
function ($\mathcal{O}_{\mathit{all}}$) values of the 10 optimal solutions
found in 10 repetitions. For SA and VQ, as there are no sub-problems,
$\mathit{FV}$ is calculated by taking the average value of the objective
function ($\mathcal{O}_{\mathit{all}}$) values of the 10 optimal solutions
found for 10 repetitions. In addition, to compare BootQA with SA (RQ1) and VQ
(RQ2), we evaluate their effectiveness with the $\mathit{FV}$ metric for each
sub-problem size and also with the best sub-problem size. BootQA and EIDQ are
compared (RQ3) by various sub-problem sizes’ effectiveness measured with
$\mathit{FV}$. In RQ4, we evaluate the efficiency of BootQA in terms of the
optimization time exTime. For SA and VQ, we calculate exTime as the sum of the
classical CPU time for SA and QPU time for VQ. For BootQA and EIDQ, exTime is
the sum of the decomposing time and the QPU time. For BootQA (or EIDQ), we
calculate the bootstrap sampling time (or the decomposing time) and cumulative
QPU portion time for all sub-problems. We used the best sub-problem sizes for
both BootQA and EIDQ to evaluate the total time cost and the number of qubits
when comparing with SA and VQ.

####  5.3.2 Statistical Tests

Following the guideline from [55], to establish the statistical significance
of the results, we compare BootQA and EIDQ with the $\mathit{FV}$ metrics (see
Section 5.3.1) for all sub-problem sizes for each dataset using the Mann-
Whitney U test and Vargha and Delaney’s $\hat{A}_{12}$ effect size. We set the
significance level as 0.05. The null hypothesis is that there is no
significant difference between the two approaches. If the null hypothesis is
not rejected, we consider the effectiveness of the two approaches to be equal.
Otherwise, if the null hypothesis is rejected, we utilize Vargha and Delaney’s
$\hat{A}_{12}$ statistic as the effect size measure to quantify the magnitude
of the difference between the two groups. If $\hat{A}_{12}$ is 0.5, the result
is achieved by chance. If $\hat{A}_{12}$ is smaller than 0.5, then BootQA
obtains lower values than EIDQ with a high probability and vice versa. For
$\hat{A}_{12}$ statistics, the effect size in the range $(0.34,0.44]$ and
$[0.56,0.64)$ are interpreted as _Small_ , $(0.29,0.34]$ and $[0.64,0.71)$ are
interpreted as _Medium_ , and $[0,0.29]$ and $[0.71,1]$ are interpreted as
_Large_.

##  6 Experiment Results

In this section, we discuss experimental results to answer each RQ. The
implementation of BootQA and all experiment results are provided in the online
repository: https://github.com/AsmarMuqeet/BootQA.

###  6.1 RQ1: Effectiveness of QUBO formulation

We implement our QUBO formulation in SA to evaluate its effectiveness in
solving three TCM problems of the three datasets. We obtain $\mathit{FV}$
values of $1.19\text{e-}2$, $1.74\text{e-}4$, and $2.40\text{e-}2$ for
PaintControl, GSDTSR, and IOF/ROL, respectively, which are all very close to 0
(smaller is better), implying that our QUBO formulation effectively guides SA
to find optimal solutions for all three TCM problems.

Encouraged by this, we then solve the TCM problems with BootQA with various
sub-problem sizes (see Sect. 5.2). We calculated the $\mathit{FV}$ value for
each sub-problem size and observed that for all three datasets, the
$\mathit{FV}$ values obtained by BootQA with all sub-problem sizes are close
to those produced by SA; the average $\mathit{FV}$ value differences are
$2.71\text{e-}3$, $2.63\text{e-}3$ and $1.10\text{e-}2$, for PaintControl,
GSDTSR and IOF/ROL, respectively. When comparing BootQA configured with the
best sub-problem sizes (30, 20, and 30 for PaintControl, GSDTSR, and IOF/ROL,
respectively) with SA, the average $\mathit{FV}$ differences are even more
minor: $3.09\text{e-}4$, $8.21\text{e-}6$, and $7.04\text{e-}4$ for
PaintControl, GSDTSR, and IOF/ROL, respectively. Thus, we can conclude that
the effectiveness of BootQA is practically similar to SA.

###  6.2 RQ2: Effectiveness of BootQA compared to VQ

Large TCM problems cannot be directly solved on QA due to the limited number
of qubits and couplers possible on the current QA hardware. For example, the
overall QUBO graph scale of the two larger datasets (i.e., GSDTSR and IOF/ROL)
exceeds the capacity of the current hardware. Thus, decomposing strategies are
needed to fit a large TCM problem into the QA hardware.

To assess the effectiveness of using the bootstrap sampling strategy in QA to
solve TCM problems, we compare the effectiveness of BootQA and VQ for solving
a small TCM problem with PaintControl. Recall from Sect. 5 that we conduct
experiments on BootQA configured with 8 different sub-problem sizes for
PaintControl. We used Mann-Whitney U statistical test and Vargha and Delaney’s
$\hat{A}_{12}$ statistics to compare $\mathcal{O}_{\mathit{all}}$values
produced by BootQA configured with each sub-problem size with those produced
by VQ in 10 repetitions. Results show that when BootQA is configured with 5
out of the 8 sub-problem sizes (i.e., 10, 20, 30 (the best sub-problem size),
40, and 50), the p-values are less than 0.05 with a large magnitude in favor
of BootQA. No significant difference can be observed when BootQA has the 60
and 70 sub-problem sizes. For the sub-problem size 80, VQ significantly
outperforms BootQA with a large magnitude. Thus, we can conclude that BootQA’s
bootstrapping strategy with the best sub-problem size can potentially solve
large TCM problems compared with implementing QA without decomposition.

###  6.3 RQ3: Effectiveness of BootQA comparing to EIDQ

Considering that both BootQA and EIDQ solve a TCM problem by splitting it into
sub-problems, their sizes (i.e., the number of test cases in each sub-problem)
might impact their performance. According to Sect. 5.2, we employ a range of
sub-problem sizes for both BootQA and EIDQ. To compare them, for each sub-
problem size, we analyze the objective function ($\mathcal{O}_{\mathit{all}}$)
values of the optimal solutions produced by BootQA and EIDQ in 10 repetitions.
Results are shown in Fig. 3.

(a) GSDTSR

(b) PaintControl

(c) IOF/ROL

Figure 3: RQ3 – Objective function ($\mathcal{O}_{\mathit{all}}$) values
produced by BootQA and EIDQ for each sub-problem

Comparing the three datasets, we can see that, in most cases, the objective
function values of BootQA are lower than that of EIDQ, except for the cases
with the 70 and 80 sub-problem sizes in PaintControl. Moreover, one can
observe that for all three datasets, BootQA produced solutions with less
variability among different sample sizes compared to EIDQ. BootQA follows a
trend of having lower objective function values when the sub-problem size is
small and higher objective function values as the sub-problem size grows. In
the case of EIDQ, no definite trend with respect to the sub-problem size can
be observed. For instance, in GSDTSR, sometimes the objective function values
are comparatively high even with small sample sizes like 10 and 30.

We find that BootQA consistently achieves lower objective function values with
smaller sub-problem sizes (e.g., from 10 to 50), while larger objective
function values for larger sub-problem sizes, as shown in Fig. 3. One possible
reason is that for a larger sub-problem, the length of the qubit chain will be
longer, which affects the QA accuracy [56, 57]. In addition, for D-Wave QA,
all coefficients in the QUBO formulation need to be scaled down to fit the
fixed hardware bias and couplers determined by the physical properties of the
qubits and their interconnections [57]. For a larger sub-problem (with more
variables), the effective energy gap666Effective energy gap is the difference
of energy between the ground state and the first excited state of the quantum
system [58]. becomes smaller. This is because the problem Hamiltonian gets
more complex and has more energy levels, which results in a denser spectrum of
energy levels and a smaller effective energy gap, consequently leading to
lower optimization performance [57, 18].

By observing the trend of objective function values generated by BootQA in
Fig. 3, we can observe a rise of the objective function values in GSDTSR and
IOF/ROL at the sub-problem size being 110 and 100, respectively. The possible
reason is that the scaling effect on different QUBO formulations varies,
consequently affecting the results for different sub-problems.

Overall, in most cases for all datasets, BootQA performs better than EIDQ. To
establish the statistical significance of the results, we also evaluated the
values of $\mathit{FV}$ for all sub-problem sizes of BootQA and EIDQ with the
Mann-Whitney U statistical test and Vargha and Delaney’s $\hat{A}_{12}$
statistics. For all three datasets, the p-values are all less than 0.05,
showing a significant difference between BootQA and EIDQ. For GSDTSR and
IOF/ROL, the effect sizes are 0 (less than 0.5), indicating that BootQA is
significantly better than EIDQ with a large magnitude for all sub-problem
sizes. For the PaintControl dataset, the effect size is 0.062, which is also
less than 0.5, showing that BootQA significantly performs better than EIDQ
with a large magnitude in most sub-problem sizes.

We also compare BootQA and EIDQ with their best sub-problem sizes for each
dataset, regarding the $\mathit{FV}$ values. Results are summarized in Table.
2. BootQA gets the best results with the sub-problem sizes of $N=20$ for
GSDTSR and $N=30$ for IOF/ROL and PaintControl. For EIDQ, the best settings
are 70 for PaintControl, 160 for GSDTSR and IOF/ROL. The lowest $\mathit{FV}$
produced by BootQA in PaintControl, GSDTSR, and IOF/ROL are $1.22\text{e-}2$,
$1.82\text{e-}4$ and $2.46\text{e-}2$, respectively, while that for EIDQ are
$1.62\text{e-}2$, $1.55\text{e-}2$ and $4.87\text{e-}2$. Comparing the two
approaches, BootQA gets better performance in all datasets.

Table 2: Best sub-problem sizes of BootQA and EIDQ. $N$ is the sub-problem
size; $M$ denotes the number of subsets BootQA used for reaching 90% coverage;
$itr$: the average number of iterations EIDQ used to produce the final
solution.

Dataset | BootQA | $EIDQ$
---|---|---
Name | Size | $N$ | $M$ | $N$ | $itr$
PaintControl | 89 | 30 | 6 | 70 | 16
GSDTSR | 287 | 20 | 21 | 160 | 7
IOF/ROL | 1663 | 30 | 127 | 160 | 4

###  6.4 RQ4: Efficiency of BootQA

To compare the time efficiency, BootQA and EIDQ are set with their best sub-
problem sizes. For SA, we calculate the computation time of the whole
optimization process as exTime. For BootQA, EIDQ, and VQ, we employ the “QPU
access time” metric [18, 56] to measure the QPU portion in exTime, which is
obtained via the D-Wave QPU-API. Specifically, the QPU access time measures
the total time spent on Step 3 (programming, initialization, and sampling)
presented in Sect. 2. For BootQA and EIDQ, we use the time required for
bootstrap sampling and Energy Impact Decomposer (see Sect. 5.2) as their
decomposing time, respectively. Results are shown in Table 3.

Table 3: RQ4 – Time performance (in seconds) of the four approaches. Each
value is shown in the format of average ± standard deviation. exTime values
highlighted in the blue background are the smallest among all approaches in
one dataset.

Dataset | SA | BootQA | EIDQ | VQ
---|---|---|---|---
|  | exTime |  | exTime |  |  |
| exTime | Decomposing | QPU access | Embedding | Decomposing | QPU access | Embedding | exTime | Embedding
PaintControl | 0.440s ± 0.005 | <0.001 | 0.171s ± 0.006 | 40.725s ± 6.019 | 1.542s ± 2.333 | 0.531s ± 0.411 | 641.678s ± 529.882 | 0.036s ± 0.001 | 76.091s ± 15.516
GSDTR | 2.811s ± 0.021 | <0.001 | 0.890s ± 0.009 | 179.665s ± 10.211 | 1.438s ± 0.031 | 0.167s ± 0.001 | 1998.118s ± 385.059 | - | -
IOFRL | 86.333s ± 0.602 | <0.001 | 3.656s ± 0.024 | 994.821s ± 10.245 | 70.726s ± 0.427 | 0.293s ± 0.002 | 3459.223s ± 730.282 | - | -

Regarding exTime, comparing all four approaches, for the PaintControl dataset,
since VQ takes only one execution to solve the problem, its exTime is the
shortest while EIDQ’s exTime (the sum of the decomposing time and the QPU
access time) is the longest. For GSDTSR and IOF/ROL, BootQA’s exTime is the
shortest among all approaches except for VQ as it only applies to
PaintControl.

When looking at each approach’s time performance across the three datasets of
various sizes, we can observe from Table 3 that exTime of SA grows
significantly as the dataset size increases. Notably, the dataset size growth
from GSDTSR to IOF/ROL is around 5.8 times ($1663/287$), whereas SA’s exTime
surges around 30 times ($86.333/2.811$). For EIDQ, we observe that its
Decomposing time takes a large part of exTime, which mainly depends on the
number of iterations and the sub-problem size. The QPU access time of EIDQ is
very short, on the other hand. Moreover, the standard deviation of its
decomposing time varies more than the BootQA, which reflects the influence of
the number of iterations on the decomposing time. For BootQA, the decomposing
time of BootQA (i.e., bootstrap sampling time) is negligible for all datasets
(i.e., less than 0.001 seconds), and the main time cost of BootQA is the QPU
access time, which is affected by the problem size and the times of sampling
$M$.

When comparing the time performance of all four approaches across all three
datasets, exTime of SA and the decomposing time of EIDQ (i.e., the classical
portion of exTime) grows dramatically with the increase of dataset size, which
is, however, not the case for BootQA, where the decomposing time increases
from 0.171s only to 3.656s. Thus, for large datasets, SA and some hybrid QA
(e.g., EIDQ) may require considerable time to produce solutions.
Comparatively, BootQA serves as a more time-efficient method for large TCM
problems.

Regarding time for embedding, as discussed in Sect. 2, the general D-Wave QA
process contains a minor-embedding phase, during which the heuristic-based
D-Wave Advantage system [54] calculates an approximate mapping from a QUBO
graph onto a quantum hardware working graph. This means the embedding can
differ in each run, even for the same QUBO graph on the same hardware. As
shown in Table 3, the embedding time used by BootQA is the shortest as
compared to EIDQ and VQ. Generally, the embedding time grows with the increase
in the size of the QUBO graph [59]. However, we would like to mention that to
compare with SA, though BootQA requires a significant amount of time for
embedding, it is feasible to reuse the embedding across sub-problems, as we
will discuss in detail in Sect. 7. Therefore, the overall cost of applying
BootQA can be further reduced. Optimizing the time and effectiveness of
embedding is an active area of research [60, 61, 62, 63]. In the near future,
the possibility of having a general embedding for fully connected QUBO graphs
that can be used to run multiple problems in parallel will reduce the
embedding cost drastically [64].

###  6.5 Threats to Validity

There are several threats to validity [65]. We evaluated our approach on only
three datasets due to the limitation of hardware resources. However, the three
chosen datasets are industrial case studies from Google and ABB Robotics.
Their sizes range from 89 to 1663, which helps to evaluate the approaches with
problems of various scales. In addition, conducting experiments with more
datasets is constrained by the practical limitation on the QA hardware access,
which affects the scale of the experiment.

Regarding the QA hyper-parameters configuration, we used the default settings
from D-Wave in our experiment. Though we are aware that D-Wave QA solver
instances have several hyper-parameters777D-Wave solver parameter list:
https://docs.dwavesys.com/docs/latest/c_solver_parameters.html, different
settings of which may have an impact on the QA performance, empirically
identifying the best settings of the hyper-parameters is very costly, which we
cannot afford for now.

Another threat to the empirical evaluation is the metrics used for answering
RQs. We used the same fitness function for all approaches to evaluate their
effectiveness. We use the experiment’s average values of 10 repetitions to
ensure accurate results. For calculating the time efficiency of the
approaches, we used the standard metric, the QPU access time [18, 56]. To
establish the statistical significance of the results, we employed the Mann-
Whitney U and Vargha-Daleney’s $\hat{A}_{12}$ statistics to verify our
findings. With the above, we provide a fair evaluation of all approaches and
reduce the randomness during experiments.

##  7 Discussion

###  7.1 Enriching the QUBO formulation with constraints.

Our results showed that for all three datasets, BootQA performs better in
terms of $\mathit{FV}$ for smaller sub-problem size (i.e., $N$) since larger
problem sizes require more chains and couplers in the working graph. Moreover,
scaling is required to fit the problem into the physical hardware. Though
BootQA performs better with smaller $N$, it increases the number of $M$ as all
sub-problems together need to cover a required percentage of the dataset
(e.g., 90%). A large $M$ increases the overall execution time of QA, which
might limit applying BootQA in cases where a solution is needed within a
timing deadline. One solution is to optimize the QUBO formulation by
considering dependencies (e.g., as constraints) among test cases (e.g., one
test case needs to be executed before another). Our current QUBO formulation
for the TCM problem makes a fully connected QUBO graph that cannot directly
map to the QA hardware without using chains (see Section 2). Considering
dependencies among test cases during the QUBO formulation could help make the
QUBO graph sparsely connected, which can improve QA performance by requiring
smaller chains and coupler strengths [56]. Also, with sparsely connected
graphs, more variables can be mapped directly to physical hardware, which
allows the use of large sub-problem size $N$ without reducing the
effectiveness of the approach.

####  7.1.1 Reusing the embedding across sub-problems.

The minor-embedding phase is the most time-consuming part of the whole QA
process, as we observed from the RQ4 results. A good embedding can
significantly improve the accuracy and time performance of QA [56]. To solve a
TCM problem with BootQA, the sub-problem size $N$ is fixed, and given a fully
connected QUBO graph, one can easily reuse the embedding of one sub-problem to
solve a new sub-problem. One possible solution to find a good embedding is to
use search algorithms to find a good embedding of a fixed-size fully connected
QUBO graph. Such an embedding can be used for both fully and sparsely
connected QUBO graphs as long as the number of nodes in the graph remains the
same. Reusing embedding can significantly improve the time performance of QA,
hence making it applicable in real settings even with the currently limited
size of quantum hardware.

####  7.1.2 Hardware resource usage.

Current QA hardware has a limited number of qubits, which limits the size of
optimization problems that can be solved with QA. However, from the results of
RQ1, we observed that BootQA performs comparably to SA by dividing a bigger
problem into smaller sub-problems. Table 4 shows the average number of
physical qubits ($\mathit{NQ}$) used for solving the sub-problems with various
sizes throughout 10 repetitions with BootQA and EIDQ.

Table 4: Average number of physical qubits ($\mathit{NQ}$) used by BootQA and
EIDQ for solving all TCM problems and obtained $\mathit{FV}$ values.
$\mathit{NQ}$ required and $\mathit{FV}$ values produced by BootQA and EIDQ
with the best sub-problem sizes are highlighted in bold.

$N$ | Dataset
---|---
| PaintControl | GSDTSR | IOF/ROL
BootQA | EIDQ | BootQA | EIDQ | BootQA | EIDQ
$\mathit{NQ}$ | $\mathit{FV}$ | $\mathit{NQ}$ | $\mathit{FV}$ | $\mathit{NQ}$ | $\mathit{FV}$ | $\mathit{NQ}$ | $\mathit{FV}$ | $\mathit{NQ}$ | $\mathit{FV}$ | $\mathit{NQ}$ | $\mathit{FV}$
10 | 17.3 | 0.0125 | 17.2 | 0.0490 | 17.2 | 0.0002 | 17.2 | 0.0432 | 17.2 | 0.0253 | 17.2 | 0.0610
20 | 55.8 | 0.0125 | 55.9 | 0.0376 | 55.3 | 0.0001 | 55.8 | 0.0355 | 55.5 | 0.0248 | 55.6 | 0.0587
30 | 123.5 | 0.0122 | 122.9 | 0.0443 | 122.4 | 0.0002 | 123.4 | 0.0417 | 122.4 | 0.0247 | 122.5 | 0.0560
40 | 212.1 | 0.0126 | 212.5 | 0.0389 | 213.7 | 0.0005 | 213.4 | 0.0264 | 214.4 | 0.0249 | 214.5 | 0.0564
50 | 326.5 | 0.0128 | 331.9 | 0.0272 | 328.3 | 0.0007 | 328.4 | 0.0353 | 330.3 | 0.0262 | 330.6 | 0.0566
60 | 468.2 | 0.0158 | 470.9 | 0.0216 | 465.0 | 0.0012 | 471.6 | 0.0294 | 467.1 | 0.0300 | 468.4 | 0.0534
70 | 621.1 | 0.0183 | 629.8 | 0.0161 | 623.8 | 0.0030 | 633.5 | 0.0226 | 627.5 | 0.0362 | 624.3 | 0.0532
80 | 817.2 | 0.0201 | 821.7 | 0.0164 | 827.3 | 0.0037 | 813.1 | 0.0156 | 823.3 | 0.0387 | 826.5 | 0.0530
90 | - | - | - | - | 1045.2 | 0.0046 | 1032.1 | 0.0404 | 1040.7 | 0.0425 | 1055.6 | 0.0536
100 | - | - | - | - | 1274.0 | 0.0053 | 1270.0 | 0.0365 | 1279.2 | 0.0446 | 1284.1 | 0.0558
110 | - | - | - | - | 1560.4 | 0.0055 | 1535.4 | 0.0323 | 1567.0 | 0.0432 | 1560.3 | 0.0530
120 | - | - | - | - | 1882.2 | 0.0048 | 1884.0 | 0.0298 | 1887.1 | 0.0424 | 1854.0 | 0.0512
130 | - | - | - | - | 2160.1 | 0.0051 | 2282.7 | 0.0265 | 2223.8 | 0.0416 | 2286.5 | 0.0553
140 | - | - | - | - | 2610.9 | 0.0030 | 2589.5 | 0.0224 | 2632.5 | 0.0399 | 2619.2 | 0.0528
150 | - | - | - | - | 3038.6 | 0.0034 | 3143.7 | 0.0186 | 3020.8 | 0.0393 | 3043.9 | 0.0497
160 | - | - | - | - | 3475.0 | 0.0025 | 3406.8 | 0.0155 | 3462.1 | 0.0381 | 3406.7 | 0.0487

As shown in Table. 4, for each $N$, $\mathit{NQ}$ used by both approaches is
comparable. And, it grows dramatically with the increase of $N$ because the
length of qubit chains grows with the increase in the number of variables.
Specifically, for VQ with all 89 variables in PaintControl, the number of
qubits used is around 1000, which is enormous compared to the size of the
problem. In contrast, BootQA can get relatively good performance with a small
number of qubits; around 56 qubits were used when $N$ was set 20, and 123
qubits were used for $N$ set 30. For EIDQ, to get a good performance, as
compared to BootQA, a lot more qubits are required. For instance, around 630
(3407) qubits were needed for $N$ being 70 (160). Thus, for solving TCM
problems with a good performance by QA, the requirement of hardware for BootQA
is not as high as that for other approaches, making BootQA a potentially more
resource-efficient approach for solving these types of problems. In addition,
we observe that with the current hardware, using more qubits does not
guarantee good performance and the reasons are explained in RQ3 (Sect. 6.3)

##  8 Conclusion and Future Work

Quantum annealers aim to solve combinatorial optimization problems, including
those in software engineering, such as test optimization. In this paper, we
present the first work in the literature that provides a generic formulation
of the test case minimization (TCM) problem for quantum annealing (QA).
Moreover, given the fact that the current quantum annealers have a limited
number of quantum bits (qubits), we propose a sampling method to optimize the
use of physical qubits for TCM problems. We implemented our TCM formulation in
four optimization processes: classical simulated annealing (SA), QA without
sampling (named VQ), and QA with two different sampling methods (BootQA we
newly proposed in this paper and EIDQ tailored from D-Wave’s Kerberos). We
evaluate them on three real-world datasets of various scales. Results show
that BootQA performs similarly as SA, and outperforms both VQ and EIDQ in
terms of effectiveness. BootQA also shows higher time efficiency when solving
large-scale TCM problems compared with the other three. Our future work
includes optimizing the QUBO formulation to further improve the efficiency of
BootQA. We also plan to conduct more experiments with larger datasets.

## References

  * [1] AY. Kitaev, A. Shen, MN. Vyalyi, “Classical and quantum computing,“ _NY: Springer New York_ , pp. 203–217, 2007. [Online]. Available: https://doi.org/10.1007/978-0-387-36944-0_13
  * [2] I. Siloi, V. Carnevali, B. Pokharel, M. Fornari, and R. Di Felice, “Investigating the chinese postman problem on a quantum annealer,” _Quantum Machine Intelligence_ , vol. 3, no. 1, p. 3, 2021.
  * [3] A. Perdomo-Ortiz, J. Fluegemann, S. Narasimhan, R. Biswas, and V. N. Smelyanskiy, “A quantum annealing approach for fault detection and diagnosis of graph-based systems,” _The European Physical Journal Special Topics_ , vol. 224, pp. 131–148, 2015.
  * [4] D. Inoue and H. Yoshida, “Model predictive control for finite input systems using the D-Wave quantum annealer,” _Scientific Reports_ , vol. 10, no. 1, p. 1591, 2020.
  * [5] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, “Quantum computation by adiabatic evolution,” _arXiv preprint quant-ph/0001106_ , 2000.
  * [6] R. Mukherjee and K. S. Patnaik, “A survey on different approaches for software test case prioritization,” _J. King Saud Univ. Comput. Inf. Sci._ , vol. 33, no. 9, pp. 1041–1054, nov 2021. [Online]. Available: https://doi.org/10.1016/j.jksuci.2018.09.005
  * [7] R. Pan, M. Bagherzadeh, T. A. Ghaleb, and L. Briand, “Test case selection and prioritization using machine learning: A systematic literature review,” _Empirical Softw. Engg._ , vol. 27, no. 2, mar 2022. [Online]. Available: https://doi.org/10.1007/s10664-021-10066-6
  * [8] S. Verma, M. Pant, and V. Snasel, “A comprehensive review on nsga-ii for multi-objective combinatorial optimization problems,” _Ieee Access_ , vol. 9, pp. 57 757–57 791, 2021.
  * [9] A. Arrieta, S. Wang, U. Markiegi, A. Arruabarrena, L. Etxeberria, and G. Sagardui, “Pareto efficient multi-objective black-box test case selection for simulation-based testing,” _Information and Software Technology_ , vol. 114, pp. 137–154, 2019. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0950584918301721
  * [10] A. Panichella, R. Oliveto, M. Di Penta, and A. De Lucia, “Improving multi-objective test case selection by injecting diversity in genetic algorithms,” _IEEE Transactions on Software Engineering_ , vol. 41, no. 4, pp. 358–383, 2014.
  * [11] S. Wang, S. Ali, and A. Gotlieb, “Cost-effective test suite minimization in product lines using search techniques,” _J. Syst. Softw._ , vol. 103, no. C, pp. 370–391, may 2015. [Online]. Available: https://doi.org/10.1016/j.jss.2014.08.024
  * [12] A. Kulesa, M. Krzywinski, P. Blainey, and N. Altman, “Sampling distributions and the bootstrap,” 2015.
  * [13] M. Born and V. Fock, “Beweis des Adiabatensatzes,” _Zeitschrift für Physik_ , no. 6, 1928.
  * [14] S. Morita and H. Nishimori, “Mathematical foundation of quantum annealing,” _Journal of Mathematical Physics_ , vol. 49, no. 12, 2008.
  * [15] S. Yarkoni, E. Raponi, T. Bäck, and S. Schmitt, “Quantum annealing for industry applications: introduction and review,” _Reports on Progress in Physics_ , vol. 85, no. 10, p. 104001, sep 2022. [Online]. Available: https://dx.doi.org/10.1088/1361-6633/ac8c54
  * [16] T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse Ising model,” _Physical Review E_ , vol. 58, no. 5, p. 5355, 1998.
  * [17] M. Lewis and F. Glover, “Quadratic unconstrained binary optimization problem preprocessing: Theory and empirical analysis,” _Networks_ , vol. 70, no. 2, pp. 79–97, 2017.
  * [18] D-Wave Systems Inc., “Technical description of the d-wave quantum processing unit,” May 2021. [Online]. Available: https://docs.dwavesys.com/docs/latest/doc_qpu.html
  * [19] C. McGeoch and P. Farre, “The D-Wave advantage systems: An overview,” D-Wave Systems Inc., Tech. Rep., 2020. [Online]. Available: https://www.dwavesys.com/media/s3qbjp3s/14-1049a-a_the_d-wave_advantage_system_an_overview.pdf
  * [20] V. Choi, “Minor-embedding in adiabatic quantum computation: I. the parameter setting problem,” _Quantum Information Processing_ , vol. 7, pp. 193–209, 2008. [Online]. Available: https://doi.org/10.1007/s11128-008-0082-9
  * [21] G. Rosenberg, P. Haghnegahdar, P. Goddard, P. Carr, K. Wu, and M. L. de Prado, “Solving the optimal trading trajectory problem using a quantum annealer,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 10, no. 6, pp. 1053–1060, 2016.
  * [22] V. Kulkarni, M. Kulkarni, and A. Pant, “Quantum computing methods for supervised learning,” _Quantum Machine Intelligence_ , vol. 3, no. 2, p. 23, 2021.
  * [23] R. K. Nath, H. Thapliyal, and T. S. Humble, “A review of machine learning classification using quantum annealing for real-world applications,” _SN Computer science_ , vol. 2, pp. 1–11, 2021.
  * [24] M. Hibat-Allah, E. M. Inack, R. Wiersema, R. G. Melko, and J. Carrasquilla, “Variational neural annealing,” _Nature Machine Intelligence_ , vol. 3, no. 11, pp. 952–961, 2021.
  * [25] R. H. Warren, “Adapting the traveling salesman problem to an adiabatic quantum computer,” _Quantum information processing_ , vol. 12, pp. 1781–1785, 2013\.
  * [26] R. H. Warren, “Solving the traveling salesman problem on a quantum annealer,” _SN Applied Sciences_ , vol. 2, no. 1, p. 75, 2020.
  * [27] A. Syrichas and A. Crispin, “Large-scale vehicle routing problems: Quantum annealing, tunings and results,” _Computers & Operations Research_, vol. 87, pp. 52–62, 2017. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0305054817301260
  * [28] D. Inoue, A. Okada, T. Matsumori, K. Aihara, and H. Yoshida, “Traffic signal optimization on a square lattice with quantum annealing,” _Scientific reports_ , vol. 11, no. 1, pp. 1–12, 2021.
  * [29] H. Hussain, M. B. Javaid, F. S. Khan, A. Dalal, and A. Khalique, “Optimal control of traffic signals using quantum annealing,” _Quantum Information Processing_ , vol. 19, pp. 1–18, 2020.
  * [30] B. Denkena, F. Schinkel, J. Pirnay, and S. Wilmsmeier, “Quantum algorithms for process parallel flexible job shop scheduling,” _CIRP Journal of Manufacturing Science and Technology_ , vol. 33, pp. 100–114, 2021.
  * [31] T. Stollenwerk, V. Michaud, E. Lobe, M. Picard, A. Basermann, and T. Botter, “Agile earth observation satellite scheduling with a quantum annealer,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 57, no. 5, pp. 3520–3528, 2021.
  * [32] Y. Ding, X. Chen, L. Lamata, E. Solano, and M. Sanz, “Implementation of a hybrid classical-quantum annealing algorithm for logistic network design,” _SN Computer Science_ , vol. 2, pp. 1–9, 2021.
  * [33] M. H. Alkawaz and A. Silvarajoo, “A survey on test case prioritization and optimization techniques in software regression testing,” in _2019 IEEE 7th Conference on Systems, Process and Control (ICSPC)_ , 2019, pp. 59–64.
  * [34] T. Nithya and S. Chitra, “Soft computing-based semi-automated test case selection using gradient-based techniques,” _Soft Computing_ , vol. 24, no. 17, pp. 12 981–12 987, 2020.
  * [35] D. K. Yadav and S. Dutta, “Regression test case selection and prioritization for object oriented software,” _Microsystem Technologies_ , vol. 26, pp. 1463–1477, 2020.
  * [36] T. Çıngıl and H. Sözer, “Black-box test case selection by relating code changes with previously fixed defects,” in _Proceedings of the International Conference on Evaluation and Assessment in Software Engineering 2022_ , ser. EASE ’22. New York, NY, USA: Association for Computing Machinery, 2022, pp. 30–39. [Online]. Available: https://doi.org/10.1145/3530019.3530023
  * [37] J. Zhao, “Quantum software engineering: Landscapes and horizons,” _CoRR_ , vol. abs/2007.07047, 2020. [Online]. Available: https://arxiv.org/abs/2007.07047
  * [38] M. A. Serrano, R. Pérez-Castillo, and M. Piattini, Eds., _Quantum Software Engineering_. Springer International Publishing, 2022. [Online]. Available: https://doi.org/10.1007/978-3-031-05324-5
  * [39] A. Miranskyy, L. Zhang, and J. Doliskani, “Is your quantum program bug-free?” in _Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering: New Ideas and Emerging Results_ , ser. ICSE-NIER ’20. New York, NY, USA: Association for Computing Machinery, 2020, pp. 29–32. [Online]. Available: https://doi.org/10.1145/3377816.3381731
  * [40] A. Miranskyy and L. Zhang, “On testing quantum programs,” in _Proceedings of the 41st International Conference on Software Engineering: New Ideas and Emerging Results_ , ser. ICSE-NIER ’19. IEEE Press, 2019, pp. 57–60. [Online]. Available: https://doi.org/10.1109/ICSE-NIER.2019.00023
  * [41] A. García de la Barrera, I. García-Rodríguez de Guzmán, M. Polo, and M. Piattini, “Quantum software testing: State of the art,” _Journal of Software: Evolution and Process_ , vol. 35, no. 4, p. e2419, 2023\. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/smr.2419
  * [42] X. Wang, P. Arcaini, T. Yue, and S. Ali, “QuSBT: Search-based testing of quantum programs,” in _Proceedings of the ACM/IEEE 44th International Conference on Software Engineering: Companion Proceedings_ , ser. ICSE ’22. New York, NY, USA: Association for Computing Machinery, 2022, pp. 173–177. [Online]. Available: https://doi.org/10.1145/3510454.3516839
  * [43] X. Wang, T. Yu, P. Arcaini, T. Yue, and S. Ali, “Mutation-based test generation for quantum programs with multi-objective search,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , ser. GECCO ’22. New York, NY, USA: Association for Computing Machinery, 2022, pp. 1345–1353. [Online]. Available: https://doi.org/10.1145/3512290.3528869
  * [44] J. Wang, F. Ma, and Y. Jiang, “Poster: Fuzz testing of quantum program,” in _2021 14th IEEE Conference on Software Testing, Verification and Validation (ICST)_ , 2021, pp. 466–469.
  * [45] E. Mendiluze, S. Ali, P. Arcaini, and T. Yue, “Muskit: A mutation analysis tool for quantum software testing,” in _2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)_ , 2021, pp. 1266–1270.
  * [46] D. Fortunato, J. Campos, and R. Abreu, “Mutation testing of quantum programs written in QISKit,” in _Proceedings of the ACM/IEEE 44th International Conference on Software Engineering: Companion Proceedings_ , ser. ICSE ’22. New York, NY, USA: Association for Computing Machinery, 2022, pp. 358–359. [Online]. Available: https://doi.org/10.1145/3510454.3528649
  * [47] D. Fortunato, J. Campos, and R. Abreu, “QMutPy: A mutation testing tool for quantum algorithms and applications in Qiskit,” in _Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis_ , ser. ISSTA 2022\. New York, NY, USA: Association for Computing Machinery, 2022, pp. 797–800. [Online]. Available: https://doi.org/10.1145/3533767.3543296
  * [48] D. Fortunato, J. Campos, and R. Abreu, “Mutation testing of quantum programs: A case study with Qiskit,” _IEEE Transactions on Quantum Engineering_ , vol. 3, pp. 1–17, 2022.
  * [49] R. Abreu, J. a. P. Fernandes, L. Llana, and G. Tavares, “Metamorphic testing of oracle quantum programs,” in _Proceedings of the 3rd International Workshop on Quantum Software Engineering_ , ser. Q-SE ’22. New York, NY, USA: Association for Computing Machinery, 2023, pp. 16–23. [Online]. Available: https://doi.org/10.1145/3528230.3529189
  * [50] M. Paltenghi and M. Pradel, “MorphQ: Metamorphic testing of quantum computing platforms,” _CoRR_ , vol. abs/2206.01111, 2022. [Online]. Available: https://doi.org/10.48550/arXiv.2206.01111
  * [51] X. Wang, P. Arcaini, T. Yue, and S. Ali, “Application of combinatorial testing to quantum programs,” in _2021 IEEE 21st International Conference on Software Quality, Reliability and Security (QRS)_ , 2021, pp. 179–188.
  * [52] H. Spieker, A. Gotlieb, D. Marijan, and M. Mossige, “Reinforcement learning for automatic test case prioritization and selection in continuous integration,” in _Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis_ , ser. ISSTA 2017. New York, NY, USA: Association for Computing Machinery, 2017, pp. 12–22. [Online]. Available: https://doi.org/10.1145/3092703.3092709
  * [53] “D-wave hybrid,” D-wave systems, Tech. Rep., 2023.
  * [54] M. Catherine and F. Pau, “The d-wave advantage system: An overview,” D-Wave, Tech. Rep., 2022. [Online]. Available: https://www.dwavesys.com/media/s3qbjp3s/14-1049a-a_the_d-wave_advantage_system_an_overview.pdf
  * [55] A. Arcuri and L. Briand, “A practical guide for using statistical tests to assess randomized algorithms in software engineering,” in _Proceedings of the 33rd International Conference on Software Engineering_ , ser. ICSE ’11. New York, NY, USA: Association for Computing Machinery, 2011, pp. 1–10. [Online]. Available: https://doi.org/10.1145/1985793.1985795
  * [56] A. A. Abbott, C. S. Calude, M. J. Dinneen, and R. Hua, “A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing,” _International Journal of Quantum Information_ , vol. 17, no. 05, p. 1950042, 2019.
  * [57] C. D. Gonzalez Calaza, D. Willsch, and K. Michielsen, “Garden optimization problems for benchmarking quantum annealers,” _Quantum Information Processing_ , vol. 20, no. 9, sep 2021. [Online]. Available: https://doi.org/10.1007/s11128-021-03226-6
  * [58] A. Rajak, S. Suzuki, A. Dutta, and B. K. Chakrabarti, “Quantum annealing: an overview,” _Philosophical Transactions of the Royal Society A_ , vol. 381, no. 2241, p. 20210417, 2023.
  * [59] V. Choi, “Minor-embedding in adiabatic quantum computation: I. the parameter setting problem,” _Quantum Information Processing_ , vol. 7, pp. 193–209, 2008.
  * [60] S. Zbinden, A. Bärtschi, H. Djidjev, and S. Eidenbenz, “Embedding algorithms for quantum annealers with chimera and pegasus connection topologies,” in _High Performance Computing_ , P. Sadayappan, B. L. Chamberlain, G. Juckeland, and H. Ltaief, Eds. Cham: Springer International Publishing, 2020, pp. 187–206.
  * [61] P. Thai, M. T. Thai, T. Vu, and T. N. Dinh, “Fasthare: Fast hamiltonian reduction for large-scale quantum annealing,” in _2022 IEEE International Conference on Quantum Computing and Engineering (QCE)_ , 2022, pp. 114–124.
  * [62] K. Boothby, P. Bunyk, J. Raymond, and A. Roy, “Next-generation topology of d-wave quantum processors,” 2020.
  * [63] A. Barbosa, E. Pelofske, G. Hahn, and H. N. Djidjev, “Optimizing embedding-related quantum annealing parameters for reducing hardware bias,” in _Parallel Architectures, Algorithms and Programming_ , L. Ning, V. Chau, and F. Lau, Eds. Singapore: Springer Singapore, 2021, pp. 162–173.
  * [64] E. Pelofske, G. Hahn, and H. N. Djidjev, “Parallel quantum annealing,” _Scientific Reports_ , vol. 12, no. 1, pp. 1–11, 2022.
  * [65] C. Wohlin, P. Runeson, M. Hst, M. C. Ohlsson, B. Regnell, and A. Wessln, _Experimentation in Software Engineering_. Springer Publishing Company, Incorporated, 2012.