# A new framework of sensor selection for developing a fault detection system
based on data-envelopment analysis

Amir Eshaghi Chaleshtori<EMAIL_ADDRESS>Abdollah Aghaie
<EMAIL_ADDRESS>School of Industrial Engineering,K.N.Toosi University of
Technology, Tehran, Iran

###### Abstract

Several methods have been proposed to identify which sensor sets are optimal
for finding and localizing faults under different conditions for mechanical
equipment. In order to preserve acceptable performance while minimizing costs,
it is crucial to identify the most effective set of sensors available.
Nevertheless, some sensor sets can behave differently in fault detection
because of uncertainty in the measurement data contaminated by noise
interference. This paper develops new sensor selection models using Data
Envelopment Analysis (DEA), which has proven helpful as a management approach
for determining an optimal number of sensors, associated costs, and sensor
performance in the fault diagnosis. We propose four linear optimization models
for sensor selection to design the fault detection system. The validity of the
presented models is demonstrated using a vibration dataset collected from a
gearbox. Based on the case study results, the proposed methods are effectively
superior to the other comparison sensor selection methods in fault detection
accuracy.

###### keywords:

Sensor selection, Fault diagnosis, Fault detection, Data envelopment analysis,
Sensor management.

##  1 Introduction

Failure detection of complex systems using the signals collected by multiple
sensors is essential in identifying incipient faults to prevent catastrophic
malfunctions, reducing productivity losses and interruptions to operations
while ensuring human safety[Buchaiah and Shakya, 2022]. Adding more sensors
may provide accurate fault detection results but will also lead to higher
sensor costs and occupy more space [Bhushan et al., 2008, Jung et al., 2020].
Consequently, selecting the most appropriate sensors is critical to satisfying
the failure analysis objectives while minimizing the related costs. The sensor
selection problem takes various forms, ranging from minor to larger
systems[Kulkarni et al., 2021]. In small systems, the selection of sensors is
primarily experimental and relatively straightforward, while for large complex
systems, it is more challenging and necessitates further analysis[Kulkarni et
al., 2021]. However, most of the suggested sensor selection methods are not
scalable, i.e., the selection method for small systems is not suitable for
large complex systems and vice versa[Clark et al., 2020b, Kulkarni et al.,
2021, Liesegang et al., 2021]. Moreover, previously sensor selection methods
were heavily dependent on the decision maker’s expertise, resulting in
subjective decisions[Chauhan and Soni, 2020, Ye et al., 2020, Kulkarni et al.,
2021]. However, an essential consideration when dealing with the sensor
selection problem is the adverse effect of uncertainty in the collected data
and measurement noise on diagnostic accuracy [Yamada et al., 2021, Nagata et
al., 2022]. Significant uncertainties impede the identification of minor
faults[Yamada et al., 2021]. Although a set of sensors satisfies fault
detection requirements, it is not guaranteed that diagnosis systems utilizing
these sensors will perform as expected when the uncertainties in the collected
data, such as measurement noise, are considered. Hence, it is necessary to
consider more realistic parameters in the sensor selection process than simply
selecting a minimum number of sensors that provide fault detection under ideal
conditions[Yamada et al., 2021]. Moreover, Bhushan et al. [Bhushan et al.,
2008] emphasized that the cost of a system is always an essential
consideration in its design. The same is true of fault detection systems as
well. Thus, it is imperative to regard the associated sensor costs[Kathiroli
and Selvadurai, 2021]. By translating these requirements into the sensor
selection problem, we would ensure that the fault diagnostic system could be
implemented with acceptable performance[Jung et al., 2020]. This paper
utilizes Data Envelopment Analysis (DEA) models to develop sensor selection
methods considering the properties of the sensors and related costs. A
significant benefit of DEA for the sensor selection is that it will provide a
composite measure of total performance, enabling a straightforward comparison
among sensors[Fancello et al., 2020, Yamada et al., 2021]. DEA also provides
information on the sensor performance indicators included in the final
score[Easton et al., 2002]. This information allows the expert to decide based
on specific measures[Horváthová and Mokrišová, 2020]. Moreover, DEA provides
metrics of efficiency (output/inputs) so that both input and output variables
are taken into account to make an accurate comparison between sensors[de Mello
et al., 2013]. In summary, the current work makes the following contributions:

  * 1.

This paper establishes a data-driven method that considers the properties of
sensor data and the associated costs.

  * 2.

This paper develops DEA models for selecting the informative sensors to design
a fault diagnosis system.

  * 3.

Outcomes from experiments on a multi-sensor dataset reveal that the presented
methods are highly effective at diagnosing faults.

This study is divided into the following sections. Section 2 surveys the
literature on the sensor selection problem. Section 3 introduces the
fundamental theories of the proposed approaches. Section 4 describes the
details related to the proposed sensor selection methods. Section 5 discusses
the experimental validation of the suggested methods. Lastly, the article
outlines its conclusions in section 6.

##  2 Literature review

Sensor selection methods are examined in many fields for choosing informative
sensors, such as prognostic health management[Cheng et al., 2010, Guan et al.,
2020, Chaleshtori et al., 2022], boost-stage rocket engines[Sowers, 2012],
turbo-fan engines [Sowers et al., 2009], aircraft engine health estimation
[Simon and Garg, 2009], plant equipment [Riedel et al., 2015], vehicle design
[Santi et al., 2005], and the polymer electrolyte membrane (PEM) fuel cell
[Mao and Jackson, 2016, Mao et al., 2018]. Moreover, Graph-based methods[Shieh
et al., 2001, Zhang and Vachtsevanos, 2007], semantic approaches[Schmidt and
Van Laerhoven, 2001, Kertiou et al., 2018], greedy algorithms[Zhang et al.,
2017, Clark et al., 2020a, Jung et al., 2020],knowledge-based methods[Riedel
et al., 2015, Jones et al., 2018], and grey clustering methods[Guan et al.,
2020] are the most widespread sensor selection methods in
literature.Furthermore, many optimization methods are employed based on convex
relaxation methods to solve sensor selection problems (as a heuristic
alternative to brute-force search)[Joshi and Boyd, 2008, Nonomura et al.,
2021], greedy methods [Manohar et al., 2018, Saito et al., 2021] and proximal
optimization algorithms [Dhingra et al., 2014, Nagata et al., 2021]. However,
various objective metrics concerning sensor selection algorithms exist. The
Fisher information matrix, ordinary linear least square estimation
[Peherstorfer et al., 2020, Nakai et al., 2021], and a steady state error
covariance matrix of the Kalman filter [Ye et al., 2018] exemplify sensor
selection objectives. Despite these established methodologies, noise
interference could only be considered occasionally in formulations. However,
there can be some challenges associated with noise due to the differences
between models and phenomena when processing acoustic signals [O’Connor et
al., 2016], vibrations [Castro-Triguero et al., 2013], and data-driven
modelling [Saito et al., 2021]. Liu et al.[Liu et al., 2016] considered an
assumption of noise with low correlation, and Joshi et al.[Joshi and Boyd,
2008] developed algorithms based on a general kernel of noise covariance
between sensors.
The purpose of this paper is to develop sensor selection methods to take into
account the properties of the sensors and associated costs using Data
Envelopment Analysis (DEA) models. The fault diagnostic system could be
implemented with acceptable performance if we translated these requirements
into the sensor selection problem. The current work will be described in the
following.

##  3 The suggested sensor selection method

This section explains the suggested framework and how to detect faults using
supervised machine learning algorithms. The framework involves two stages. In
the first stage, DEA models select significant sensors. It incorporates all
the characteristics of sensors and allows a final decision based on the system
state. The following parameters are considered when designing a practical
sensor selection framework: monotonicity, robustness, trendability,
detectability, variance, root mean square and sensor costs. In detail, these
parameters are calculated for each sensor. Then for each sensor, a virtual
input variable, defined as the weighted sum of the monotonicity, robustness,
trendability, detectability, and the root mean square, is created. Similarly,
a virtual output variable, defined as the weighted sum of sensor costs and the
variance, is created for each sensor. Figure 1 shows the defined virtual
variables for each sensor. Then, the virtual input and output variables are
fed into DEA models to find the efficient sensors according to the system
state and sensor requirements for condition monitoring. In the second stage,
machine-learning algorithms are trained using the most efficient sensor data
to determine equipment failures and test the accuracy of sensor selection
models. Figure 2 shows a schematic illustration of the proposed method. The
considered parameters are defined in the following subsection.

Figure 1: The proposed decision making unit(Sensor). Figure 2: Flowchart of
the proposed methodology.

###  3.1 The performance parameters of sensor selection framework

  * 1.

Monotonicity:In order to extract information from trends that are increasing
or decreasing, the monotonicity metric is used.It is expressed as follows:

$\text{ Monotonicity }=\frac{1}{k}\sum_{j=1}^{k}\sum_{x\in
c_{j}}\frac{1}{N-1}\left|\\#\frac{d}{dx}>*-\\#\frac{d}{dx}<\cdot\right|$ (1)

where $k$ and $N$ represents the number of states and the number of data
within each state,$c_{j}$ represents the $j^{th}$ state, and
$\frac{d}{dx}=x_{n+1}-x_{n}$ is the difference between two successive data.
The value of the monotonicity is between 0 to 1.

  * 1.

Robustness:In order to calculate the robustness, the trend and residual
components are extracted. The residual component ($res_{x}$) of the signal $x$
is extracted by subtracting the smoothed signal $sm_{x}$(trend) from the
original signal $x$, as follows. This paper utilizes the wavelet denoising
algorithm proposed by Ref.[Bnou et al., 2020] to estimate the smoothed signal.

$\text{ Robustness }=\frac{1}{k}\sum_{j=1}^{k}\frac{1}{N}\sum_{x\in
c_{j}}e^{-\left|\frac{res_{x}}{x}\right|}\quad;\text{ res }_{x}=x-sm_{x}$ (2)

where $k$ and $N$ represents the number of states and the number of data
within each state,$c_{j}$ represents the $j^{th}$ state.

  * 1.

Trendability:According to the trendability metric, a given signal and its
lagged version exhibit similarity over successive time intervals. The signal
is measured in terms of the relationship between its current and past values.

$\text{ Trendibility
}=\frac{1}{k}\sum_{j=1}^{k}\sum_{t=\cdot}^{T}\sum_{\tau=\cdot}^{T-1}\sum_{x_{t}\in
c_{j}}\left|x_{t}\left(x_{t-\tau}\right)^{T}\right|$ (3)

where $k$ and $N$ represents the number of states and the number of data
within each state,$c_{j}$ represents the $j^{th}$ state.$T$ represents the
time length of the signal and $\tau$ shows the time lag.

  * 1.

Detectability:It refers to the ability to distinguish between different
states. The Fisher discriminant ratio is used to compare the scatter between
states and the scatter within states [Powell et al., 2013]. This ratio forms
the basis of the detectability metric. As a result, we calculate it as
follows:

$\text{ Detectability
}=\frac{\sum_{j}n_{j}\left(\bar{x}_{j}-\overline{\bar{x}}\right)\left(\bar{x}_{j}-\overline{\bar{x}}\right)^{T}}{\sum_{j}\sum_{x\in
c_{j}}\left(x-\bar{x}_{j}\right)\left(x-\bar{x}_{j}\right)^{T}}$ (4)

where $\bar{x}_{j}$ indicate the average value of $j^{th}$
state,$\overline{\bar{x}}$ represents the mean value of all data,and $n_{j}$
is the number of data in the $j^{th}$ state.

  * 1.

Variance:The variance is a measure of dispersion, which indicates how far the
signal deviates from its average.

$\text{ Variance }=\frac{1}{k}\sum_{j=1}^{k}\frac{1}{N-1}\sum_{x\in
c_{j}}\left(x-\bar{x}_{j}\right)\left(x-\bar{x}_{j}\right)^{T}$ (5)

where $k$ and $N$ represents the number of states and the number of data
within each state,$c_{j}$ represents the $j^{th}$ state, and $\bar{x}_{j}$
indicate the average value of $j^{th}$ state.

  * 1.

Root mean square(RMS):This term refers to the calculated overall energy and
amplitude of a given signal. According to the RMS, the following formula is
provided:

$RMS=\frac{1}{k}\sum_{j=1}^{k}\sqrt{\frac{1}{N}\sum_{x\in c_{j}}x^{2}}$ (6)

  * 1.

Sensor costs:The cost of any system is always a factor in its design; the same
applies to fault detection systems. Sensor costs are typically evaluated by
considering the costs associated with sensor acquisition, installation,
communication, replacement, disassembly, and inspection[Xu et al., 2005, Zhang
et al., 2018].

For the bearing fault diagnosis, higher values of monotonicity,trendability,
robustness, detectability, and RMS are desirable[Duong et al., 2018].
Moreover, lower variance and sensor cost values are preferred [Kulkarni et
al., 2021]. Thus, the following DEA models have output variables:
monotonicity, trendability, robustness, detectability, and RMS, while input
variables are variance and sensor costs.

###  3.2 The DEA models

The DEA approach uses linear programming to convert multiple input and output
variables into a quantitative measure of productivity efficiency[Easton et
al., 2002]. Efficiencies are used to measure how efficiently resources are
utilized and how processes are performed when they transform input variables
into output variables. Efficiency is a relative concept since it implies that
a unit’s performance is compared against a standard. The DEA analyzes the
relative efficiency of decision-making units (DMUs). We consider sensors as
DMUs in our proposed application, shown in Figure 1.

####  3.2.1 The CCR model

Constant Returns to Scale, or CCR, is the first basic DEA model developed by
Charnes et al.[Charnes et al., 1978]. In a typical DEA model, input and output
variables are predetermined, and a comparison of the efficiency of similar
elements is attempted. Thus, DMUs are considered the elements to be compared.
Each DMU’s efficiency is defined as the weighted sum of output variables
divided by the weighted sum of inputs. An efficient unit has a score of one.
As an additional benefit of DEA, it does not require any subjective weighting
procedures, and an overall performance score is derived as an efficiency score
for a DMU. By assigning weights to input and output variables using the
calculation model, the decision-maker does not have to make subjective
decisions to maximize the DMU’s efficiency. The traditional DEA model utilizes
a linear divisive programming approach to calculate the relative efficiency of
any DMU.

$\begin{gathered}\max z_{l}:\frac{\sum_{r}u_{r}y_{rl}}{\sum_{s}v_{s}o_{sl}}\\\
\text{ Subject to: }\\\
0\leq\frac{\sum_{r}u_{r}y_{rl}}{\sum_{s}v_{s}o_{sl}}\leq 1\quad\forall
l=1,\ldots,k\\\ u_{r},v_{s}\geq 0\quad\forall r=1,2,\ldots,N,\forall
s=1,2,\ldots,M\end{gathered}$ (7)

In the objective function of the CCR model, the efficiency of the $l^{th}$ DMU
is maximized. Using the Equation(7), all DMUs are defined based on the weights
selected for $l$. Equation (7) provides that the efficiency of all DMUs is
between 0 and 1. In the final constraint, the weights of output and input
variables must all be positive.

####  3.2.2 The BCC model

Banker et al.[Banker et al., 1984] developed the BCC model to calculate
efficiencies that did not result in a proportionate change in input or output
variables according to changes in input or output variables. Depending on the
approach, input or output variables may be the focus of the BCC model. The
input-oriented model produces the same inputs with the minimum amount that can
be formulated as follows:

$\begin{gathered}\max
z_{l}:\frac{\sum_{r}u_{r}y_{rl}+u_{0}}{\sum_{s}v_{s}o_{sl}}\\\ \text{ Subject
to: }\\\ 0\leq\frac{\sum_{r}u_{r}y_{rl}+u_{0}}{\sum_{s}v_{s}o_{sl}}\leq
1\quad\forall l=1,\ldots,k\\\ u_{r},v_{s}\geq 0\quad\forall
r=1,2,\ldots,N,\forall s=1,2,\ldots,M\\\ u_{0}\text{ : free }\end{gathered}$
(8)

while the output-oriented model is designed to maximize output variables with
the least amount of inputs which can be formulated as follows:

$\begin{gathered}\max
z_{l}:\frac{\sum_{r}u_{r}y_{rl}}{\sum_{s}v_{s}o_{sl}+v_{0}}\\\ \text{ Subject
to: }\\\ 0\leq\frac{\sum_{r}u_{r}y_{rl}}{\sum_{s}v_{s}o_{sl}+v_{0}}\leq
1\quad\forall l=1,\ldots,k\\\ u_{r},v_{s}\geq 0\quad\forall
r=1,2,\ldots,N,\forall s=1,2,\ldots,M\\\ v_{0}:\text{ free }\end{gathered}$
(9)

Both objective functions have a maximum efficiency of the $l^{th}$ DMU. Using
Equations (8) and (9), each DMU is defined in terms of the weights selected
for $l$. Accordingly, the efficiency of all DMUs lies between 0 and 1. In both
models, the final constraints require all output and input variables to have a
positive weight.

####  3.2.3 The additive model

Additive DEA aims to maximize output variables for a minimum amount of input
variables[Jin et al., 2023, Chen et al., 2023]. The objective function of this
model is a summation of weighted input and output variables that can be
expressed as follows:

$\begin{gathered}\max z_{l}:\sum_{r}u_{r}y_{rk}-\sum_{s}v_{s}o_{sl}-w_{0}\\\
\text{ Subject to: }\\\
\sum_{r}u_{r}y_{rl}\leq\sum_{s}v_{s}o_{sl}+w_{0}\quad\forall l=1,\ldots,k\\\
u_{r},v_{s}\geq 1\quad\forall r=1,2,\ldots,N,\forall s=1,2,\ldots,M\\\
w_{0}\text{ : free }\end{gathered}$ (10)

According to the objective function, the efficiency of the $l^{th}$ DMU is
maximized. The DMUs are a function of the weights selected for $l$, using the
Equation(10). A reference Equation (10) states that the efficiency of all DMUs
is between 0 and 1. All output and input variables must have positive weights
in the final constraint.

##  4 Experiments

###  4.1 Dataset for experiments

The experiments are conducted using Spectra Quest’s Gear Fault Diagnosis
Simulator to create gear fault diagnostic data for condition monitoring. The
Gearbox Fault Diagnostic Simulator (GFDS) developed by Spectra Quest has been
designed to simulate industrial gearboxes for prognostics and diagnostics.
Data are generated using GFDS for two cases: a healthy condition and a
condition with a broken tooth, as shown in Table1 . Four vibration sensors are
placed on the body of the gearbox in four different directions, and the
vibration signals are recorded under varying loading conditions from zero
loads to 90%[Malik et al., 2019]. Hence, 40 vibration data have been derived
from the sensors under various loading conditions. In our study, we select 500
consecutive sets of data points for each gearbox condition to examine the
performance of the proposed sensor selection method. Figures 3 show the
vibration data collected under varying loading conditions from zero loads to
90%.

Table 1: An overview of each bearing state and its corresponding label in the dataset. Status | label
---|---
Healthy condition | 1
Broken tooth condition | 2

(a) Sensor1

(b) Sensor2

(c) Sensor3

(d) Sensor4

Figure 3: The collected vibration data under varying loading conditions.

###  4.2 Overview of the evaluation criteria

There have been several performance metrics proposed based on the binary
confusion matrix. Five of these metrics are the focus of our study, which can
be summarized as follows:

  * 1.

Accuracy:Generally, the accuracy metric is defined as the proportion of
correct predictions to the number of observations that can be defined as
follows:

$\text{Accuracy}=\frac{TP+TN}{TP+TN+FP+FN}$ (11)

  * 1.

Recall:The recall is used to determine the percentage of correctly classified
patterns that can be expressed as follows:

$Recall^{+}=\frac{TP}{TP+FN}$ (12) $Recall^{-}=\frac{TN}{TN+FP}$ (13)

  * 1.

Precision:In classification problems, precision is a proportion of positive
patterns correctly predicted based on total predicted patterns that can be
defined as follows:

$Precision^{+}=\frac{TP}{TP+FP}$ (14)

$Precision^{-}=\frac{TN}{TN+FN}$ (15)

  * 1.

F-score:In this metric, recall and precision values are expressed as a
harmonic mean that can be expressed as follows:

$F^{+}=2.\frac{precision^{+}.recall^{+}}{precision^{+}+recall^{+}}$ (16)
$F^{-}=2.\frac{precision^{-}.recall^{-}}{precision^{-}+recall^{-}}$ (17)

  * 1.

The area under the ROC curve(AUC):The AUC is an index used to measure the
performance of a statistical diagnosis algorithm. One can determine how
effectively a particular classifier can quantitatively separate two groups
based on ROC curves. The ROC curve shows the trade-off between the probability
of detection or the true positive rate, also known as sensitivity or recall,
and the probability of a false alarm or false positive rate.

###  4.3 Procedures for experiments

Sensor selection begins with an analysis of the system and determines the
sensor requirements for condition monitoring that allows for identifying the
most informative sensor by DEA models. For this study, we simulate the sensor
costs reported in Table2. Additionally, we calculate a number of parameters
related to the gearbox vibration data, including monotonicity, robustness,
trendability, detectability, variance, and RMS.

Table 2: The simulated sensor costs($). Sensor | Load condition(%) | Purchase cost | Installation cost | Replacement cost | Disassembly cost | Inspection cost
---|---|---|---|---|---|---
1 | 0 | 201.48 | 67.85 | 82 | 186.86 | 168.27
10 | 199.59 | 91.54 | 338.57 | 133.39 | 131.87
20 | 212.26 | 79.26 | 51.39 | 113.11 | 191.19
30 | 213.24 | 77.49 | 282.47 | 135.34 | 153
40 | 193.17 | 95.86 | 295.19 | 93.21 | 128.05
50 | 203.16 | 64.29 | 310.61 | 98.08 | 208.64
60 | 201.70 | 87.86 | 75.33 | 209.06 | 200
70 | 208.33 | 87.69 | 169.93 | 210.99 | 155.37
80 | 210.41 | 69.02 | 127.96 | 158.80 | 165.28
90 | 211.90 | 78.39 | 290.02 | 88.19 | 160.43
2 | 0 | 196.11 | 53.79 | 179.42 | 112.16 | 108.46
10 | 209.43 | 52.70 | 323.19 | 128.38 | 121.27
20 | 208.62 | 76.54 | 104.55 | 192.50 | 144.52
30 | 192.37 | 88.96 | 129.14 | 82.11 | 111.58
40 | 190.93 | 96.70 | 93.66 | 85.89 | 195.67
50 | 203.45 | 56.50 | 90.82 | 103.15 | 106.68
60 | 218.67 | 78.44 | 310.79 | 168.93 | 110.95
70 | 198.23 | 73.47 | 223.91 | 180.25 | 103.39
80 | 206.31 | 50.60 | 214.96 | 168.74 | 111.19
90 | 194.39 | 66.86 | 93.49 | 141.78 | 139.69
3 | 0 | 211.79 | 58.11 | 305.91 | 154.94 | 122.62
10 | 195.42 | 89.71 | 236.62 | 120.60 | 206.50
20 | 203.70 | 65.56 | 155.29 | 182.02 | 138.94
30 | 210.07 | 76.43 | 203.97 | 105.89 | 105.32
40 | 216.40 | 58.28 | 170.54 | 174.09 | 203.97
50 | 218.66 | 80.10 | 72.79 | 105.14 | 214.23
60 | 205.06 | 63.15 | 121.97 | 130.48 | 140.13
70 | 191.57 | 82.70 | 87 | 165.71 | 95.22
80 | 191.93 | 84.46 | 105.17 | 186.89 | 115.35
90 | 195.50 | 87.41 | 121.99 | 91.11 | 135.99
4 | 0 | 214.74 | 72.53 | 175.18 | 207.33 | 161.50
10 | 195.39 | 54.19 | 64.90 | 186.27 | 115.92
20 | 213.87 | 61.45 | 320.81 | 146.69 | 162.59
30 | 195.04 | 95.67 | 333.44 | 139.71 | 177.44
40 | 217.67 | 57.62 | 197.26 | 141.21 | 110.38
50 | 198.55 | 91.29 | 196.78 | 121.97 | 96.09
60 | 193.49 | 76.92 | 151.32 | 149.67 | 120.64
70 | 195.29 | 99.81 | 320.02 | 149.98 | 123.67
80 | 207.33 | 53.91 | 160.77 | 192.01 | 138.11
90 | 202.62 | 72.13 | 83.36 | 188.89 | 149.58

Comparative analysis is performed among the proposed sensor selection
models(The CCR, The IO-BCC, the OO-BCC, and the additive) and traditional
methods, such as sensor selection based on correlation analysis implemented by
Khalid et al.[Khalid et al., 2021], the mRMR algorithm proposed by Peng et
al.[Peng et al., 2005], and the Extra Tree Classifier technique(ETC) suggested
by Sharaff[Sharaff and Gupta, 2019]. Moreover, we apply the well-known
supervised machine learning classifiers for the fault classification,
including the support vector machine (SVM), the k-nearest neighbor classifier
(KNN), and the naive Bayes algorithm. It is crucial to tune the
hyperparameters of machine learning classifiers. As a result, we use a five-
fold cross-validation method to optimize the hyperparameters to minimize the
adverse effects of data volatility. Specifically, we utilize four folds for
training and the left for testing. Once the parameters have been evaluated
five times for all training data, we will select the parameters that produce
the best results for the classification of the test data.

##  5 Results and discussions

###  5.1 Results

Table 3 compares the results obtained by SVM, KNN, and naive Bayes algorithms
in comparison with the proposed sensor selection methods. Based on the
classification results of various comparison methods, Table 3 summarizes the
classification results for the healthy condition $(+)$ and the broken tooth
condition $(-)$. It is evident from Table 3 that the CCR-KNN method performs
better than others since the least number of sensors is used. A minimum number
of sensors is selected using the CCR model(26 sensors), whereas a higher
number is selected using the other DEA models(29 sensors). The CCR-KNN, the
IOBCC-KNN, the OOBCC-KNN, the additive-KNN, and the OOBCC-KNN have better
classification accuracy than other methods. Figures 4,5, and 6 illustrate how
the confusion matrix is used to evaluate the classifier’s performance. As a
result of the confusion matrix, it is possible to accurately predict whether a
healthy for the additive-SVM, the OOBCC-SVM, the IOBCC-SVM, the CCR-SVM, the
OOBCC-KNN, the additive-KNN, the IOBCC-KNN, and CCR-KNN methods. Further, the
CCR-KNN, the IOBCC-KNN, the OOBCC-KNN, the additive-KNN, and the OOBCC-KNN are
the most accurate methods for identifying broken tooth conditions.

Table 3: The comparison results of DEA models. Method | # selected sensors | Accuracy(%) | $Recall^{+}$ | $Recall^{-}$ | $Precision^{+}$ | $Precision^{-}$ | $F-score^{+}$ | $F-score^{-}$ | AUC
---|---|---|---|---|---|---|---|---|---
CCR-KNN | 26 | 100 | 1 | 1 | 1 | 1 | 1 | 1 | 1
IOBCC-KNN | 29 | 100 | 1 | 1 | 1 | 1 | 1 | 1 | 1
OOBCC-KNN | 29 | 100 | 1 | 1 | 1 | 1 | 1 | 1 | 1
Additive-KNN | 29 | 100 | 1 | 1 | 1 | 1 | 1 | 1 | 1
CCR-SVM | 26 | 99.2 | 1 | 0.984 | 0.9843 | 1 | 0.9921 | 0.9919 | 0.992
IOBCC-SVM | 29 | 81.9 | 1 | 0.638 | 0.7342 | 1 | 0.8467 | 0.779 | 0.819
OOBCC-SVM | 29 | 100 | 1 | 1 | 1 | 1 | 1 | 1 | 1
Additive-SVM | 29 | 50.3 | 1 | 0.006 | 0.5015 | 1 | 0.668 | 0.0119 | 0.503
CCR-NaiveBayes | 26 | 74.4 | 0.526 | 0.962 | 0.9326 | 0.6699 | 0.6726 | 0.7898 | 0.744
IOBCC-NaiveBayes | 29 | 76.5 | 0.574 | 0.956 | 0.9288 | 0.6918 | 0.7095 | 0.8059 | 0.765
OOBCC-NaiveBayes | 29 | 76.9 | 0.576 | 0.962 | 0.9381 | 0.6941 | 0.7138 | 0.8064 | 0.769
Additive-NaiveBayes | 29 | 76.6 | 0.58 | 0.952 | 0.9236 | 0.6939 | 0.7125 | 0.8027 | 0.766

(a) CCR-KNN

(b) IOBCC-KNN

(c) OOBCC-KNN

(d) Additive-KNN

Figure 4: Confusion matrixes for different comparative KNN models.

(a) CCR-SVM

(b) IOBCC-SVM

(c) OOBCC-SVM

(d) Additive-SVM

Figure 5: Confusion matrixes for different comparative SVM models.

(a) CCR-naive Bayes

(b) IOBCC-naive Bayes

(c) OOBCC-naive Bayes

(d) Additive-naive Bayes

Figure 6: Confusion matrixes for different comparative naive Bayes models.

###  5.2 Discussions

We compare the performance of the CCR-KNN method with others, including the
correlation analysis method(Pearson), the mRMR, and the ETC algorithms with
SVM, KNN, and the naive Bayes classifiers. The performance results are
summarized in Table 4. Despite selecting fewer sensors than the CCR method,
the ETC algorithm produces lower classification performance than our proposed
method. Pearson-KNNs exhibit similar performance results to CCR-KNN; however,
it involves utilizing the maximum number of sensors, resulting in overfitting,
complexity, and lower generalizability in the learning process. Figures 7,8,
and 9 illustrate the possibility of accurately determining whether a system is
healthy with the Pearson-KNN, the Pearson-SVM, and the ETC-SVM. Additionally,
only the Person-KNN and the ETC-KNN provide the most accurate method of
identifying broken tooth states.

Table 4: The results of the comparison between the proposed and other methods. Method | # selected sensors | Accuracy(%) | $Recall^{+}$ | $Recall^{-}$ | $Precision^{+}$ | $Precision^{-}$ | $F-score^{+}$ | $F-score^{-}$ | AUC
---|---|---|---|---|---|---|---|---|---
CCR-KNN | 26 | 100 | 1 | 1 | 1 | 1 | 1 | 1 | 1
Pearson-KNN | 40 | 100 | 1 | 1 | 1 | 1 | 1 | 1 | 1
Pearson-SVM | 40 | 93.8 | 1 | 0.876 | 0.8897 | 1 | 0.9416 | 0.9288 | 0.938
Pearson-NaiveBayes | 40 | 80.1 | 0.656 | 0.054 | 0.9239 | 0.0761 | 0.7672 | 0.6317 | 0.801
ETC-KNN | 16 | 99.8 | 0.996 | 1 | 1 | 0.996 | 0.998 | 0.998 | 0.998
ETC-SVM | 16 | 99.7 | 1 | 0.994 | 0.994 | 1 | 0.997 | 0.997 | 0.997
ETC-NaiveBayes | 16 | 76.1 | 0.702 | 0.82 | 0.7959 | 0.7335 | 0.746 | 0.7743 | 0.761
mRMR-KNN | 21 | 99.9 | 0.998 | 1 | 1 | 0.998 | 0.999 | 0.999 | 0.999
mRMR-SVM | 21 | 99.6 | 1 | 0.992 | 0.9921 | 1 | 0.996 | 0.996 | 0.996
mRMR-NaiveBayes | 21 | 81.4 | 0.774 | 0.854 | 0.8413 | 0.7907 | 0.8062 | 0.8211 | 0.814

(a) Pearson-KNN

(b) Pearson-SVM

(c) Pearson-naive Bayes

Figure 7: Confusion matrixes for different comparative Pearson methods.

(a) ETC-KNN

(b) ETC-SVM

(c) ETC-naive Bayes

Figure 8: Confusion matrixes for different comparative ETC methods.

(a) mRMR-KNN

(b) mRMR-SVM

(c) mRMR-naive Bayes

Figure 9: Confusion matrixes for different comparative mRMR methods.

##  6 Conclusions and prospects

In this article, a DEA-based sensor selection framework is presented for the
design of a fault diagnostic system. The healthy and faulty states are
classified using supervised machine learning classifiers (SVM, KNN, and naive
Bayes). This paper provides a case study demonstrating the proposed approach’s
effectiveness based on the gearbox’s vibration signal. As a result of the
computational results, it has been indicated that DEA-based sensor selection
approaches result in fewer sensors and a greater degree of accuracy in
identifying faults. As a result of this study, the DEA-based sensor selection
approaches are applicable in other case studies. For future research, this may
serve as an approach for the efficient design of sensor selection for fault
diagnosis. In addition, it is an important future direction to include the
dynamics in modelling, estimation, and sensor selection. Feedback control
should consider this. A future extension of this research will focus on
metrics relating to observability and controllability.

### Acknowledgements

The authors have declared no conflicts of interest regarding their research,
authorship, or publication of this article.

## References

  * Banker et al. [1984] Banker, R.D., Charnes, A., Cooper, W.W., 1984.  Some models for estimating technical and scale inefficiencies in data envelopment analysis.  Management science 30, 1078–1092.
  * Bhushan et al. [2008] Bhushan, M., Narasimhan, S., Rengaswamy, R., 2008.  Robust sensor network design for fault diagnosis.  Computers & Chemical Engineering 32, 1067–1084.
  * Bnou et al. [2020] Bnou, K., Raghay, S., Hakim, A., 2020.  A wavelet denoising approach based on unsupervised learning model.  EURASIP Journal on Advances in Signal Processing 2020, 1–26.
  * Buchaiah and Shakya [2022] Buchaiah, S., Shakya, P., 2022.  Bearing fault diagnosis and prognosis using data fusion based feature extraction and feature selection.  Measurement 188, 110506.
  * Castro-Triguero et al. [2013] Castro-Triguero, R., Murugan, S., Gallego, R., Friswell, M.I., 2013.  Robustness of optimal sensor placement under parametric uncertainty.  Mechanical Systems and Signal Processing 41, 268–287.
  * Chaleshtori et al. [2022] Chaleshtori, A.E., et al., 2022.  Data fusion techniques for fault diagnosis of industrial machines: a survey.  arXiv preprint arXiv:2211.09551 .
  * Charnes et al. [1978] Charnes, A., Cooper, W.W., Rhodes, E., 1978.  Measuring the efficiency of decision making units.  European journal of operational research 2, 429–444.
  * Chauhan and Soni [2020] Chauhan, V., Soni, S., 2020.  Mobile sink-based energy efficient cluster head selection strategy for wireless sensor networks.  Journal of Ambient Intelligence and Humanized Computing 11, 4453–4466.
  * Chen et al. [2023] Chen, Q., Chen, S., Liu, D., 2023.  Regret-based cross efficiency evaluation method in a general two-stage dea system.  Computers & Industrial Engineering 175, 108828.
  * Cheng et al. [2010] Cheng, S., Azarian, M.H., Pecht, M.G., 2010.  Sensor systems for prognostics and health management.  Sensors 10, 5774–5797.
  * Clark et al. [2020a] Clark, E., Brunton, S.L., Kutz, J.N., 2020a.  Multi-fidelity sensor selection: Greedy algorithms to place cheap and expensive sensors with cost constraints.  IEEE Sensors Journal 21, 600–611.
  * Clark et al. [2020b] Clark, E., Kutz, J.N., Brunton, S.L., 2020b.  Sensor selection with cost constraints for dynamically relevant bases.  IEEE Sensors Journal 20, 11674–11687.
  * Dhingra et al. [2014] Dhingra, N.K., Jovanović, M.R., Luo, Z.Q., 2014.  An admm algorithm for optimal sensor and actuator selection, in: 53rd IEEE Conference on Decision and Control, IEEE. pp. 4039–4044.
  * Duong et al. [2018] Duong, B.P., Khan, S.A., Shon, D., Im, K., Park, J., Lim, D.S., Jang, B., Kim, J.M., 2018.  A reliable health indicator for fault prognosis of bearings.  Sensors 18, 3740.
  * Easton et al. [2002] Easton, L., Murphy, D.J., Pearson, J.N., 2002.  Purchasing performance evaluation: with data envelopment analysis.  European Journal of Purchasing & Supply Management 8, 123–134.
  * Fancello et al. [2020] Fancello, G., Carta, M., Serra, P., 2020.  Data envelopment analysis for the assessment of road safety in urban road networks: A comparative study using ccr and bcc models.  Case studies on transport policy 8, 736–744.
  * Guan et al. [2020] Guan, F., Cui, W.W., Li, L.F., Wu, J., 2020.  A comprehensive evaluation method of sensor selection for phm based on grey clustering.  Sensors 20, 1710.
  * Horváthová and Mokrišová [2020] Horváthová, J., Mokrišová, M., 2020.  Comparison of the results of a data envelopment analysis model and logit model in assessing business financial health.  Information 11, 160.
  * Jin et al. [2023] Jin, F., Guo, S., Cai, Y., Liu, J., Zhou, L., 2023.  2-tuple linguistic decision-making with consistency adjustment strategy and data envelopment analysis.  Engineering Applications of Artificial Intelligence 118, 105671.
  * Jones et al. [2018] Jones, P.M., Lonne, Q., Talaia, P., Leighton, G.J., Botte, G.G., Mutnuri, S., Williams, L., 2018.  A straightforward route to sensor selection for iot systems.  Research-Technology Management 61, 41–50.
  * Joshi and Boyd [2008] Joshi, S., Boyd, S., 2008.  Sensor selection via convex optimization.  IEEE Transactions on Signal Processing 57, 451–462.
  * Jung et al. [2020] Jung, D., Dong, Y., Frisk, E., Krysander, M., Biswas, G., 2020.  Sensor selection for fault diagnosis in uncertain systems.  International journal of control 93, 629–639.
  * Kathiroli and Selvadurai [2021] Kathiroli, P., Selvadurai, K., 2021.  Energy efficient cluster head selection using improved sparrow search algorithm in wireless sensor networks.  Journal of King Saud University-Computer and Information Sciences .
  * Kertiou et al. [2018] Kertiou, I., Benharzallah, S., Kahloul, L., Beggas, M., Euler, R., Laouid, A., Bounceur, A., 2018.  A dynamic skyline technique for a context-aware selection of the best sensors in an iot architecture.  Ad Hoc Networks 81, 183–196.
  * Khalid et al. [2021] Khalid, S., Hwang, H., Kim, H.S., 2021.  Real-world data-driven machine-learning-based optimal sensor selection approach for equipment fault detection in a thermal power plant.  Mathematics 9, 2814.
  * Kulkarni et al. [2021] Kulkarni, A., Terpenny, J., Prabhu, V., 2021.  Sensor selection framework for designing fault diagnostics system.  Sensors 21, 6470.
  * Liesegang et al. [2021] Liesegang, S., Muñoz, O., Pascual-Iserte, A., 2021.  Sensor selection and distributed quantization for energy efficiency in massive mtc.  IEEE Transactions on Communications 69, 8518–8533.
  * Liu et al. [2016] Liu, S., Chepuri, S.P., Fardad, M., Maşazade, E., Leus, G., Varshney, P.K., 2016.  Sensor selection for estimation with correlated measurement noise.  IEEE Transactions on Signal Processing 64, 3509–3522.
  * Malik et al. [2019] Malik, H., Pandya, Y., Parashar, A., Sharma, R., 2019.  Feature extraction using emd and classifier through artificial neural networks for gearbox fault diagnosis, in: Applications of Artificial Intelligence Techniques in Engineering. Springer, pp. 309–317.
  * Manohar et al. [2018] Manohar, K., Brunton, B.W., Kutz, J.N., Brunton, S.L., 2018.  Data-driven sparse sensor placement for reconstruction: Demonstrating the benefits of exploiting known patterns.  IEEE Control Systems Magazine 38, 63–86.
  * Mao and Jackson [2016] Mao, L., Jackson, L., 2016.  Selection of optimal sensors for predicting performance of polymer electrolyte membrane fuel cell.  Journal of Power Sources 328, 151–160.
  * Mao et al. [2018] Mao, L., Jackson, L., Davies, B., 2018.  Effectiveness of a novel sensor selection algorithm in pem fuel cell on-line diagnosis.  IEEE Transactions on Industrial Electronics 65, 7301–7310.
  * de Mello et al. [2013] de Mello, J.C.C.S., Meza, L.A., da Silveira, J.Q., Gomes, E.G., 2013.  About negative efficiencies in cross evaluation bcc input oriented models.  European Journal of Operational Research 229, 732–737.
  * Nagata et al. [2021] Nagata, T., Nonomura, T., Nakai, K., Yamada, K., Saito, Y., Ono, S., 2021.  Data-driven sparse sensor selection based on a-optimal design of experiment with admm.  IEEE Sensors Journal 21, 15248–15257.
  * Nagata et al. [2022] Nagata, T., Yamada, K., Nonomura, T., Nakai, K., Saito, Y., Ono, S., 2022.  Data-driven sensor selection method based on proximal optimization for high-dimensional data with correlated measurement noise.  arXiv preprint arXiv:2205.06067 .
  * Nakai et al. [2021] Nakai, K., Yamada, K., Nagata, T., Saito, Y., Nonomura, T., 2021.  Effect of objective function on data-driven greedy sparse sensor optimization.  IEEE Access 9, 46731–46743.
  * Nonomura et al. [2021] Nonomura, T., Ono, S., Nakai, K., Saito, Y., 2021.  Randomized subspace newton convex method applied to data-driven sensor selection problem.  IEEE Signal Processing Letters 28, 284–288.
  * O’Connor et al. [2016] O’Connor, M., Kleijn, W.B., Abhayapala, T., 2016.  Distributed sparse mvdr beamforming using the bi-alternating direction method of multipliers, in: 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE. pp. 106–110.
  * Peherstorfer et al. [2020] Peherstorfer, B., Drmac, Z., Gugercin, S., 2020.  Stability of discrete empirical interpolation and gappy proper orthogonal decomposition with randomized and deterministic sampling points.  SIAM Journal on Scientific Computing 42, A2837–A2864.
  * Peng et al. [2005] Peng, H., Long, F., Ding, C., 2005.  Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy.  IEEE Transactions on pattern analysis and machine intelligence 27, 1226–1238.
  * Powell et al. [2013] Powell, M.A., Kaliki, R.R., Thakor, N.V., 2013.  User training for pattern recognition-based myoelectric prostheses: Improving phantom limb movement consistency and distinguishability.  IEEE Transactions on Neural Systems and Rehabilitation Engineering 22, 522–532.
  * Riedel et al. [2015] Riedel, M., Arroyo, E., Fay, A., 2015.  Knowledge-based selection of principle solutions for sensors and actuators based on standardized plant description and semantic concepts, in: 2015 IEEE 20th Conference on Emerging Technologies & Factory Automation (ETFA), IEEE. pp. 1–8.
  * Saito et al. [2021] Saito, Y., Nonomura, T., Yamada, K., Nakai, K., Nagata, T., Asai, K., Sasaki, Y., Tsubakino, D., 2021.  Determinant-based fast greedy sensor selection algorithm.  IEEE Access 9, 68535–68551.
  * Santi et al. [2005] Santi, L., Sowers, T., Aguilar, R., 2005.  Optimal sensor selection for health monitoring systems, in: 41st AIAA/ASME/SAE/ASEE Joint Propulsion Conference & Exhibit, p. 4485.
  * Schmidt and Van Laerhoven [2001] Schmidt, A., Van Laerhoven, K., 2001.  How to build smart appliances?  IEEE personal communications 8, 66–71.
  * Sharaff and Gupta [2019] Sharaff, A., Gupta, H., 2019.  Extra-tree classifier with metaheuristics approach for email classification, in: Advances in computer communication and computational sciences. Springer, pp. 189–197.
  * Shieh et al. [2001] Shieh, J., Huber, J., Fleck, N., Ashby, M., 2001.  The selection of sensors.  Progress in materials science 46, 461–504.
  * Simon and Garg [2009] Simon, D.L., Garg, S., 2009.  A systematic approach to sensor selection for aircraft engine health estimation.  Technical Report.
  * Sowers [2012] Sowers, T.S., 2012.  Systematic sensor selection strategy (S4) user guide.  Technical Report.
  * Sowers et al. [2009] Sowers, T.S., Fittje, J.E., Kopasakis, G., Simon, D.L., 2009.  Expanded application of the systematic sensor selection strategy for turbofan engine diagnostics, in: Turbo Expo: Power for Land, Sea, and Air, pp. 531–541.
  * Xu et al. [2005] Xu, K., Wang, Q., Hassanein, H., Takahara, G., 2005.  Optimal wireless sensor networks (wsns) deployment: minimum cost with lifetime constraint, in: WiMob’2005), IEEE International Conference on Wireless And Mobile Computing, Networking And Communications, 2005., IEEE. pp. 454–461.
  * Yamada et al. [2021] Yamada, K., Saito, Y., Nankai, K., Nonomura, T., Asai, K., Tsubakino, D., 2021.  Fast greedy optimization of sensor selection in measurement with correlated noise.  Mechanical Systems and Signal Processing 158, 107619.
  * Ye et al. [2018] Ye, L., Roy, S., Sundaram, S., 2018.  On the complexity and approximability of optimal sensor selection for kalman filtering, in: 2018 Annual American Control Conference (ACC), IEEE. pp. 5049–5054.
  * Ye et al. [2020] Ye, L., Woodford, N., Roy, S., Sundaram, S., 2020.  On the complexity and approximability of optimal sensor selection and attack for kalman filtering.  IEEE Transactions on Automatic Control 66, 2146–2161.
  * Zhang and Vachtsevanos [2007] Zhang, G., Vachtsevanos, G., 2007.  A methodology for optimum sensor localization/selection in fault diagnosis, in: 2007 IEEE Aerospace Conference, IEEE. pp. 1–8.
  * Zhang et al. [2017] Zhang, H., Ayoub, R., Sundaram, S., 2017.  Sensor selection for kalman filtering of linear dynamical systems: Complexity, limitations and greedy algorithms.  Automatica 78, 202–210.
  * Zhang et al. [2018] Zhang, Z., Mehmood, A., Shu, L., Huo, Z., Zhang, Y., Mukherjee, M., 2018.  A survey on fault diagnosis in wireless sensor networks.  IEEE Access 6, 11349–11364.


# Adiabatic oracle for Grover’s algorithm

Bin Yan  Theoretical Division, Los Alamos National Laboratory, Los Alamos, New
Mexico 87545, USA  Center for Nonlinear Studies, Los Alamos National
Laboratory, Los Alamos, New Mexico 87545, USA  Nikolai A. Sinitsyn
Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico
87545, USA

###### Abstract

Grover’s search algorithm was originally proposed for circuit-based quantum
computers. A crucial part of it is to query an oracle — a black-box unitary
operation. Generation of this oracle is formally beyond the original algorithm
design. Here, we propose a realization of Grover’s oracle for a large class of
searching problems using a quantum annealing step. The time of this step grows
only logarithmically with the size of the database. This suggests an efficient
path to application of Grover’s algorithm to practically important problems,
such as finding the ground state of a Hamiltonian with a spectral gap over its
ground state.

_Introduction—_ Despite the rapid growth of the research on noisy
intermediate-scale quantum (NISQ) computers Preskill (2018), the available
quantum processors are still far from implementing well-known quantum
algorithms with many qubits. An example is the famous Grover’s algorithm
Grover (1997); Boyer  _et al._ (1998), which achieves a quadratic quantum
speedup in searching through an unsorted database. To date, experimental
demonstrations of Grover’s algorithm have been restricted to systems with only
a few qubits Chuang  _et al._ (1998); Vandersypen  _et al._ (2000); Walther
_et al._ (2005); Brickman  _et al._ (2005); DiCarlo  _et al._ (2009); Barz
_et al._ (2012); Figgatt  _et al._ (2017); Zhang  _et al._ (2021).

If the database has $N$ records, Grover’s algorithm finds a target element
$\omega$ that is specified by a function

$f(m)=\begin{cases}1\quad{\rm for}~{}m=\omega,\\\ 0\quad{\rm
for}~{}m\neq\omega,\end{cases}$

where $m$ labels the database elements. Classically, the best deterministic
strategy is to query the database until the target element is found. This
takes on average $\sim N$ steps (oracle quries). In the Grover’s algorithm,
one assumes the problem function $f$ can be mapped to a unitary operator,
$\hat{O}_{f}$, termed the “Grover’s oracle”, that performs

$\hat{O}_{f}|m\rangle=(-1)^{f(m)}|m\rangle$ (1)

in the quantum database represented by an orthonormal basis $|m\rangle$. The
algorithm finds the marked element in $\mathcal{O}(\sqrt{N})$ oracle queries,
achieving the optimal Bennett  _et al._ (1997); Zalka (1999) quadratic speedup
over classical algorithms.

The quantum speedup is interpreted with respect to the number of oracle
queries Nielsen and Chuang (2010)—the oracle is treated as a black-box whose
internal complexity is ignored. In practice, the state to which oracle should
point is known only implicitly. Implementations of the oracle on a quantum
circuit generally then create a large overhead Seidel  _et al._ (2023),
hindering the algorithm’s practical applications.

In this article, we propose a strategy to construct Grover’s oracle for a
class of important search problems, namely, for implementing minimum-finding
quantum algorithm Dürr and Hoyer (1996). This algorithm generally determines
the minimal index in an array of numbers, assuming that for any chosen
threshold number there is an oracle that marks all index states below this
threshold. Assuming that the oracle call takes only $\sim\log^{\alpha}{N}$
time, where $\alpha=O(1)$, Ref. Dürr and Hoyer (1996) showed that Grover’s
algorithm can be employed for updates of the threshold, which converge to the
minimum exponentially quickly. At the last stage, which will be in our focus,
only a single index is left below the threshold. Application of the standard
Grover’s algorithm then finds this minimal index. We will introduce a physical
process that changes sign of the amplitudes of states with energy below a
controllable chemical potential. This is achieved via a quasi-adiabatic
evolution during time that scales as $\mathcal{O}(\log^{\alpha}{N})$, as
required in Dürr and Hoyer (1996).

_A search problem—_ Let the initially unknown array of generally different
real numbers be encoded as eigenvalues of a diagonal Hermitian operator
$H_{f}$. One can think of such an operator as a realization of the Ising-type
Hamiltonian

$H_{f}=c_{0}\mathbb{I}+\sum_{k=1}^{n}c_{k}\sigma_{z}^{k}+\sum_{k_{1},k_{2}=1}^{n}c_{k_{1},k_{2}}\sigma_{z}^{k_{1}}\sigma_{z}^{k_{2}}+\ldots,$

where $\sigma_{z}^{k}$, $k=1,\ldots,n$ are the Pauli $z$-operators acting on
the $k$-th qubit, and $n$ is the number of the qubits in the register;
$\mathbb{I}$ is the unit operator. We assume that the energy scale is lifted
by a chemical potential, $c_{0}$, so that $H_{f}$ has both positive and at
least one negative eigenvalues. The goal is then to prepare an eigenstate of
$H_{f}$ that corresponds to the lowest negative eigenvalue.

Even if we had allowed only pairwise couplings between qubits, this problem
would generally be NP-hard Barahona (1982); Lucas (2014) and need $\sim 2^{n}$
computation time for deterministic classical algorithms. It is possible to
find the ground state of $H_{f}$ using standard adiabatic quantum annealing,
i.e., by implementing the time evolution

$H(t)=A(t)H_{f}+B(t)H_{M},$ (2)

where $t$ runs through a sufficiently large time $T$. $A(t)$ grows from zero
and $B(t)$ decreases to zero. $H_{M}$ is an operator whose ground state is
easy to prepare at $t=0$.

However, so far, there is no evidence that such a process can outperform
classical algorithms without having considerable additional information about
$H_{f}$. Even when its ground state is separated by a large gap from the rest
of the spectrum, having no information about the precise position of this
energy and the size of this gap, the time-dependent protocol generally passes
through time moments when the gaps become exponentially small Laumann  _et
al._ (2015); Yan and Sinitsyn (2022).

The main idea of our approach is to use quantum annealing not to find the
ground state of $H_{f}$ directly but rather to realize the Grover’s oracle
operation that is needed for the quantum algorithm that finds the ground
state. The protocol that we will construct is similar to the one in Ref. Hen
(2014), in the sense that we will use an ancillary spin to implement the
desired unitary operation by quantum annealing. However, the approach in Hen
(2014) relied on a high degeneracy of the original Hamiltonian, which is not
the case for $H_{f}$ in our work. Instead, we will achieve our goal with three
additions to the control protocol: (i) instead of a single ancillary qubit we
will use either an ancillary spin-1 particle or two ancillary qubits; (ii) the
evolution will start not with a ground but rather with an excited state; (iii)
we do not require to measure the ancillary spin at the end of the annealing
step – the desired change of sign of the computational state amplitudes will
be produced by the topological phase generated during the unitary evolution.

In this Letter, we will focus on the situation when $c_{0}$ is such that only
the ground energy is negative, i.e., we are to find a single negative number
in an unsorted array of otherwise positive numbers, which are encoded as
eigenvalues of $H_{f}$. After generating the oracle we use it in the
conventional Grover’s algorithm, and thus identify the ground state in
$\sim\sqrt{N}$ steps with only a $\mathcal{O}(\log{N})$ overhead due to the
oracle implementation. The same annealing step for arbitrary $c_{0}$ would
mark all states with negative eigenvalues and thus enable the entire algorithm
Dürr and Hoyer (1996), but we will analyse this general case in detail
elsewhere.

Figure 1: Adiabatic evolution of an effective magnetic field direction for
$E_{m}>0$ (red path ${\cal C}_{+}$) and $E_{m}<0$ (${\cal C}_{-}$). When the
spin-1 is in the eigenstate with zero eigenvalue, the adiabatic phase of an
evolution over a closed loop is zero, whereas the path $\mathcal{C}$ that
flips the field direction generates a phase $\pi$ Robbins and Berry (1994).
The phase difference between $\mathcal{C}_{+}$ and $\mathcal{C}_{-}$ is then
$-\pi$.

_Adiabatic oracle—_ For an arbitrary state
$|\phi\rangle=\sum_{m}c_{m}|m\rangle$, our goal is to create an adiabatic
process that flips the sign of the target element, i.e.,

$\hat{O}_{f}|\phi\rangle=\sum_{m\neq\omega}c_{m}|m\rangle-
c_{\omega}|\omega\rangle.$ (3)

Here, the basis $|m\rangle$ of the quantum database is choosen as the
eigenbasis of the Hamiltonian $H_{f}$. First, we add an ancillary spin with
$S=1$, and then drive the system through an adiabatic process with the time-
dependent Hamiltonian

$H(t)=A(t)H_{f}\otimes S_{z}+B(t)S_{x},$ (4)

where $S_{z}$ and $S_{x}$ are spin-$1$ projection operators. We call the
corresponding unitary evolution operator the adiabatic oracle. However, we
stress that the net time of the evolution is not infinite but rather
sufficiently large to suppress nonadiabatic excitations.

Let the evolution start with the initial state

$|\psi(t=0)\rangle=|\phi\rangle\otimes|0_{x}\rangle,$ (5)

where $|0_{x}\rangle$ is an eigenstate of $S_{x}$ with zero eigenvalue. Time
evolution of the total system breaks into separate spin-$1$ sectors, i.e.,

$|\psi(t)\rangle=\sum_{m}c_{m}|m\rangle\otimes\hat{\mathcal{T}}e^{-i\int_{0}^{t}d\tau[A(\tau)E_{m}S_{z}+B(\tau)S_{x}]}|0_{x}\rangle,$
(6)

where $\hat{\mathcal{T}}$ is the time ordering operator, and $E_{m}$ is the
$m$-th eigenvalue of $H_{f}$. For each sector (labeled by $m$), the ancillary
spin-$1$ undergoes an adiabatic evolution: it starts in the eigenstate of
$S_{x}$ and hence must end up being in the eigenstate $|0_{z}\rangle$ of
$S_{z}$ with the same zero eigenvalue.

The evolution of the ancillary spin-$1$ in each sector can be viewed as if it
is driven by a time-dependent magnetic field
$\bm{b}=A(t)E_{m}\hat{z}+B(t)\hat{x}$. Suppose that for positive and negative
$E_{m}$, the final accumulated adiabatic phases are, respectively, $\phi_{+}$
and $\phi_{-}$. Figure 1 shows the corresponding paths of a unit vector
${\bm{b}}/|{\bm{b}}|$: $\mathcal{C_{+}}$ and $\mathcal{C_{-}}$. Let
$\mathcal{C}$ be a path that connects the end points of $\mathcal{C_{+}}$ and
$\mathcal{C_{-}}$, which are the opposite poles on the unit sphere. It is
known Robbins and Berry (1994) that for a spin-$1$ in its eigenstate with zero
eigenvalue, the adiabatic evolution along $\mathcal{C}$ produces a topological
phase $\phi=\pi$. Further more, for a closed loop, the adiabatic phase would
be zero Robbins and Berry (1994). Hence, $\phi_{-}-\phi_{+}=\phi=\pi$.
Therefore, after annealing, up to a global phase, the adiabatic state is

$|\psi(t=T)\rangle=\left(\sum_{m\neq\omega}c_{m}|m\rangle-
c_{\omega}|\omega\rangle\right)\otimes|0_{z}\rangle.$ (7)

That is, the ancillary spin ends up being in zero spin state of $S_{z}$, and
the oracle is realized.

Note also that the Hamiltonian $H(t)$ has always zero expectation for the
adiabatic eigenstate with zero ancillary spin projection on the effective
field. Hence, in all invariant sectors of $H(t)$, the generated dynamic phase
is identically zero. Remarkably, the phase difference between $\phi_{+}$ and
$\phi_{-}$ is thus topologically protected $\pi$-phase, i.e., it is invariant
under smooth deformations of the evolution paths specified by the time
dependence of $A(t)$ and $B(t)$ in the annealing schedule. Such a phase is
robust against imperfections in the driving protocol and spin Hamiltonian
Albash and Lidar (2018).

Alternatively, the oracle can be realized using two ancillary spins-$1/2$
instead of one spin-$1$. If the two spins-1/2 feel the same effective field
${\bm{b}}(t)$ then the subspace realized by $|\uparrow\uparrow\rangle$,
$(|\uparrow\downarrow\rangle+|\downarrow\uparrow\rangle)/\sqrt{2}$ and
$|\downarrow\downarrow\rangle$ remains invariant during the evolution. The
effective Hamiltonian in this subspace has the same matrix form as the spin-1
Hamiltonian in the same field. In appendix, we demonstrate two protocols for
the adiabatic oracle with ancillary spin-$1/2$ particles: one is probabilistic
involving projective measurements, the other is deterministic and starting the
evolution with an entangled input state.

Grover’s algorithm is comprised of repeated applications of the oracle, with
each iteration followed by another process described by the diffusion
operator, $\hat{O}_{s}=2|s\rangle\langle s|-\mathbb{I}$, where $|s\rangle$ is
the equal superposition of all the eigenstates of $H_{f}$—the initial input
state of Grover’s algorithm. $\hat{O}_{s}$ has the same structure as the
adiabatic oracle in a rotated basis, and hence can be realized analogously
using a proper time-dependent Hamiltonian. In appendix, we show that when
$|s\rangle$ is known explicitly, as in the diffusion operator, this
Hamiltonian has only binary qubit interactions.

_The time to implement the adiabatic oracle_ is determined by the gap $\Delta$
from the ground energy of $H_{f}$ to the rest of the spectrum (appendix). One
can reduce the non-adiabatic errors by increasing the quantum annealing time
$T$. This creates an overhead to the overall time of computation. However,
with suitable time dependent adiabatic schedules, one can suppress non-
adiabatic deviations exponentially fast in $T$ Lidar  _et al._ (2009); Ge  _et
al._ (2016); Albash and Lidar (2018). Since the adiabatic evolution of the
oracle breaks into $N$ spin-1 sectors corresponding to the eigenstates
$|m\rangle$ in Eq. (7), the gap to either lower or higher energy states
remains of order of $E_{m}$, which is of the order of the gap or larger.
Hence, the non-adiabatic error of a single oracle call is $\sim
Ne^{-\eta\Delta T}$, where $\eta$ is a numerical coefficient. For a fixed
error rate after $\sim\sqrt{N}$ repetitions of the oracle, one then needs a
running time of the oracle that scales only as $T\sim\log{N}$.

Although the adiabatic theorem predicts that the over-gap transitions are
generally suppressed exponentially, in practice, deviations may appear when
near the end points of the protocol the time-dependent field is nonanalytic or
experiences fast changes. An example of the protocol that achieves the
exponential suppression of the non-adiabatic errors is

$A(s),B(s)=[1\pm\tanh(s)]/2,$ (8)

where $s=t/T$ runs through $[-15,15]$. $T$ is a large total annealing time
that depends on $N$ only logarithmically. At the boundary of this interval,
the time-derivatives of the parameters are exponentially suppressed. This
makes an error due to the termination of time evolution exponentially small.

_Ground state of a non-Ising Hamiltonian—_ Let us now discuss the fact that
the quantum annealing step does not require the property for $H_{f}$ be an
Ising Hamiltonian. The latter has eigenstates with definite spin projections
along $z$-axis, which is suitable for application of the Grover’s algorithm.
Thus, the initial state $|s\rangle$ with spins polarized in the transverse
direction is an equal superposition of all the eigenstates of $H_{f}$. This
would not be true for a general non-Ising Hamiltonian. Nevertheless, in
Grover’s algorithm, if we know the overlap between the initial and the target
states, $\gamma=|\langle s|\omega\rangle|$, we can reach the optimal output
state with $\pi(4\gamma)^{-1}$ calls of the oracles.

For a generic complex Hamiltonian, we can start with a random initial state
$|s\rangle$ with an unknown overlap $\gamma$ to the target state. For such a
state $|s\rangle$, $\gamma$ is expected to have a sharp distribution centered
at $1/\sqrt{N}$. Using the ideas developed in Ref. Farhi and Gutmann (1998),
one can then run the Grover’s algorithm and measure the probability $P_{s}$ of
the initial state $|s\rangle$ at various running steps $N_{s}$ of the oracle
queries. Then, $P_{s}$ is an oscillatory function

$P_{s}=\sin^{2}{(2\gamma N_{s})}$ (9)

with periodicity of $\pi/(2\gamma)$. Thus, we determine $\gamma$ and then run
the Grover’s algorithm for finding the target state $|\omega\rangle$ (this
procedure is generally amplitude amplification Brassard  _et al._ (2000) for
the case where the overlap $\gamma$ is known). The strict requirement is that
the Hamiltonian must have (or can be modified to) a negative ground state
energy separated from the otherwise positive spectrum. A possible application
can be the search for many-body quantum scar states Turner  _et al._ (2018);
Serbyn  _et al._ (2021) of a generally nonintegrable Hamiltonian. Such states
often have eigenvalues that are separated from the rest of the spectrum, so
knowing their position only approximately, one can apply our version of the
Grover’s algorithm to prepare them.

_Numerical test—_ In order to test our expectations about the accuracy of the
adiabatic oracle, we simulated the adiabatic spin-$1$ oracle introduced above.
The model we studied was the famous one-dimensional spin-$1$ Affleck-Kennedy-
Lieb-Tasaki (AKLT) model Affleck  _et al._ (1987, 1988), i.e.,

$H_{\rm
AKLT}=\sum_{i}\frac{1}{2}\bm{S}_{i}\cdot\bm{S}_{i+1}+\frac{1}{6}\left(\bm{S}_{i}\cdot\bm{S}_{i+1}\right)^{2}+\frac{1}{3},$
(10)

where $\bm{S}=\\{S_{x},S_{y},S_{z}\\}$ – the vector of spin-$1$ matrices. With
periodic boundary condition, the AKLT model has a unique gapped ground state
at zero energy, which exhibits a symmetry-protected topological phase Pollmann
_et al._ (2012); Cirac  _et al._ (2021), and promises a resource for
measurement based quantum computing Kaltenbaek  _et al._ (2010); Wei  _et al._
(2011). Since the AKLT ground state has zero energy, we construct the problem
Hamiltonian $H_{f}$ by shifting the chemical potential, i.e.,
$H_{f}=c_{0}\mathbb{I}+H_{\rm AKLT}$, where $c_{0}$ is a negative constant
whose magnitude is on the order of the expected ground state gap.

We simulated the time-dependent Schrödinger equation with the Hamiltonian (4).
After each oracle call, the final state $|\phi_{T}\rangle$ at time $T$ is
compared to the ideal state $|\phi_{T}^{\rm id}\rangle$ (3). The errors are
quantified using the infidelity, i.e.,

$1-F(T)\equiv 1-|\langle\phi_{T}|\phi_{T}^{\rm id}\rangle|^{2}.$ (11)

Figure 2 shows the numerically found infidelity of the oracle for various
total quantum annealing time $T$. It is illustrated that a simple linear
schedule results in a power-law suppression of the non-adiabatic error. We
attribute this to the fact that the linear schedule is not analytic at the end
of the evolution. With schedule (8), which was almost free of this drawback,
we indeed achieved the desired exponential suppression of the oracle
imperfections.

Figure 2: Infidelity of the Grover’s oracle for the AKLT model with $3$ spins
for two adiabatic schedules (see the legend), as a function of the oracle
running time. The solid (dashed) back curve is the best fit to an exponential
(power-law) decay.

_Discussion and outlook—_ The adiabatic oracle for Grover’s algorithm
introduced in this work offers an unusual approach for implementing quantum
algorithms in hardware. There are aspects that make it distinct from the
conventional approaches.

Formally, the adiabatic and circuit-based quantum computing are equivalent in
the sense that they can be translated into each other during a polynomial time
for any fixed error tolerance level Mizel  _et al._ (2007); Albash and Lidar
(2018); Lloyd (1996); Georgescu  _et al._ (2014). However, to simulate a
single adiabatic oracle (of a running time $T\sim\log{N}$) on a quantum
circuit, one needs the simulation error to be dependent on $N$, namely, be as
small as $\sim 1/\sqrt{N}$ per quantum annealing step in order to maintain a
high success probability after $\sim\sqrt{N}$ oracle calls. Since the
simulation error on a circuit of length $L$ scales as $\sim T^{2}/L$ Lloyd
(1996), one needs a circuit length of order $\sqrt{N}\log^{2}{N}$ per one
oracle call. Given a finite time to implement each gate, the time of a circuit
version of our Grover’s oracle implementation would no longer scale with $N$
logarithmically. This suggests that the hybrid approach, in which the
annealing step generates an oracle, which is only then used as a part of a
gate-based quantum algorithm may be less time-consuming than the fully gate-
based quantum computing.

Preparing the adiabatic Hamiltonian, $H(s)$, can be highly costly as well. We
are not aware of an existing hardware that would convert an arbitrary original
Hamiltonian $H_{f}$ into the time-dependent Hamiltonian $H(s)$. One
possibility can be to use ultracold atomic computational qubits coupled via a
Feshbach resonance or some other type of excitation, such as the long-range
photonic cavity mode. The states $|1\rangle$ and $|-1\rangle$ of the ancillary
spin then should produce the magnetic field that brings the atoms close to the
resonance with the excitation. The induced coupling between computational
qubits should have then opposite signs for the opposite spin-1 directions,
which can be achieved by tuning the resonance to be above or below the
chemical potential, as in the measurements of out-of-time ordered correlators
Garttner  _et al._ (2017).

For the less general but still important NP-hard problem of $H_{f}$ with only
pairwise $zz$-interactions between qubits, the experimental demonstration of
our approach can be much more straightforward. The complexity of the
conversion of $H_{f}$ into $H(s)$ then follows from adding the interaction
between the computational and ancillary qubits. This requires changing
$\sim\log^{\alpha}N$ different coupling terms from $zz$ to $zzz$ type. Each
such a modification can be achieved nonperturbatively using only binary
interactions and two extra qubits per each $zz$-like term of $H_{f}$ Biamonte
(2008). The number of extra binary couplings and qubits then remains
$\sim\log^{\alpha}N$, which corresponds to only a logarithmic overhead on
hardware preparation. Thus, our adiabatic Grover’s oracle provides a definite
solution to NP-hard problems with a $\mathcal{O}(\sqrt{N})$ solution time
versus $O(N)$ for classical deterministic algorithms.

_Acknowledgement_ —The authors thank Rolando Somma for useful discussions,
especially for pointing to an alternative annealing strategy with ancillary
qubits starting in Bell state. This work was supported by the U.S. Department
of Energy (DOE), Office of Science, Office of Advanced Scientific Computing
Research, through the Quantum Internet to Accelerate Scientific Discovery
Program. B.Y. also acknowledges support from the Center for Nonlinear Studies
and the U.S. DOE under the LDRD program at Los Alamos.

## References

  * Preskill (2018) J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum 2, 79 (2018).
  * Grover (1997) L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack,” Phys. Rev. Lett. 79, 325–328 (1997).
  * Boyer  _et al._ (1998) M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight bounds on quantum searching,” Fortschr. Phys. 46, 493–505 (1998).
  * Chuang  _et al._ (1998) I. L. Chuang, N. Gershenfeld, and M. Kubinec, “Experimental implementation of fast quantum searching,” Phys. Rev. Lett. 80, 3408–3411 (1998).
  * Vandersypen  _et al._ (2000) L. M. K. Vandersypen, M. Steffen, M. H. Sherwood, C. S. Yannoni, G. Breyta, and I. L. Chuang, “Implementation of a three-quantum-bit search algorithm,” Appl. Phys. Lett. 76, 646–648 (2000).
  * Walther  _et al._ (2005) P. Walther, K. J. Resch, T. Rudolph, E. Schenck, H. Weinfurter, V. Vedral, M. Aspelmeyer, and A. Zeilinger, “Experimental one-way quantum computing,” Nature 434, 169–176 (2005).
  * Brickman  _et al._ (2005) K. A. Brickman, P. C. Haljan, P. J. Lee, M. Acton, L. Deslauriers, and C. Monroe, “Implementation of grover’s quantum search algorithm in a scalable system,” Phys. Rev. A 72, 050306 (2005).
  * DiCarlo  _et al._ (2009) L. DiCarlo, J. M. Chow, J. M. Gambetta, L. S. Bishop, B. R. Johnson, D. I. Schuster, J. Majer, A. Blais, L. Frunzio, S. M. Girvin, and R. J. Schoelkopf, “Demonstration of two-qubit algorithms with a superconducting quantum processor,” Nature 460, 240–244 (2009).
  * Barz  _et al._ (2012) S. Barz, E. Kashefi, A. Broadbent, J. F. Fitzsimons, A. Zeilinger, and P. Walther, “Demonstration of blind quantum computing,” Science 335, 303–308 (2012).
  * Figgatt  _et al._ (2017) C. Figgatt, D. Maslov, K. A. Landsman, N. M. Linke, S. Debnath, and C. Monroe, “Complete 3-qubit grover search on a programmable quantum computer,” Nat. Commun. 8, 1918 (2017).
  * Zhang  _et al._ (2021) K. Zhang, P. Rao, K. Yu, H. Lim, and V. Korepin, “Implementation of efficient quantum search algorithms on NISQ computers,” Quantum Inf. Process. 20, 233 (2021).
  * Bennett  _et al._ (1997) C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, “Strengths and weaknesses of quantum computing,” SIAM J. Comput. 26, 1510–1523 (1997).
  * Zalka (1999) C. Zalka, “Grover’s quantum searching algorithm is optimal,” Phys. Rev. A 60, 2746–2751 (1999).
  * Nielsen and Chuang (2010) M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information_ (Cambridge University Press, 2010).
  * Seidel  _et al._ (2023) Raphael Seidel, Colin Kai-Uwe Becker, Sebastian Bock, Nikolay Tcholtchev, Ilie-Daniel Gheorghe-Pop, and Manfred Hauswirth, “Automatic generation of grover quantum oracles for arbitrary data structures,” Quantum Sci. Technol. 8, 025003 (2023).
  * Dürr and Hoyer (1996) C. Dürr and P. Hoyer, “A quantum algorithm for finding the minimum,” arXiv:quant-ph/9607014 (1996).
  * Barahona (1982) F Barahona, “On the computational complexity of ising spin glass models,” J. Phys. A Math. Gen. 15, 3241 (1982).
  * Lucas (2014) A. Lucas, “Ising formulations of many NP problems,” Frontiers in Physics 2, 5 (2014).
  * Laumann  _et al._ (2015) C R Laumann, R Moessner, A Scardicchio, and S L Sondhi, “Quantum annealing: The fastest route to quantum computation?” Eur. Phys. J. Spec. Top. 224, 75–88 (2015).
  * Yan and Sinitsyn (2022) B. Yan and N. A. Sinitsyn, “Analytical solution for nonadiabatic quantum annealing to arbitrary ising spin hamiltonian,” Nat. Commun. 13, 2212 (2022).
  * Hen (2014) I. Hen, “Period finding with adiabatic quantum computation,” EPL 105, 50005 (2014).
  * Robbins and Berry (1994) J. M. Robbins and M. V. Berry, “A geometric phase for m=0 spins,” J. Phys. A Math. Gen. 27, L435 (1994).
  * Albash and Lidar (2018) T. Albash and D. A. Lidar, “Adiabatic quantum computation,” Rev. Mod. Phys. 90, 015002 (2018).
  * Lidar  _et al._ (2009) D. A. Lidar, A. T. Rezakhani, and A. Hamma, “Adiabatic approximation with exponential accuracy for many-body systems and quantum computation,” J. Math. Phys. 50, 102106 (2009).
  * Ge  _et al._ (2016) Y. Ge, A. Molnár, and J. I. Cirac, “Rapid adiabatic preparation of injective projected entangled pair states and gibbs states,” Phys. Rev. Lett. 116, 080503 (2016).
  * Farhi and Gutmann (1998) E. Farhi and S. Gutmann, “Analog analogue of a digital quantum computation,” Phys. Rev. A 57, 2403–2406 (1998).
  * Brassard  _et al._ (2000) G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, “Quantum amplitude amplification and estimation,”  (2000), arXiv:quant-ph/0005055 [quant-ph] .
  * Turner  _et al._ (2018) C. J. Turner, A. A. Michailidis, D. A. Abanin, M. Serbyn, and Z. Papić, “Weak ergodicity breaking from quantum many-body scars,” Nat. Phys. 14, 745–749 (2018).
  * Serbyn  _et al._ (2021) M. Serbyn, D. A. Abanin, and Z. Papić, “Quantum many-body scars and weak breaking of ergodicity,” Nat. Phys. 17, 675–685 (2021).
  * Affleck  _et al._ (1987) I. Affleck, T. Kennedy, E. H. Lieb, and H. Tasaki, “Rigorous results on valence-bond ground states in antiferromagnets,” Phys. Rev. Lett. 59, 799–802 (1987).
  * Affleck  _et al._ (1988) I. Affleck, T. Kennedy, E. H. Lieb, and H. Tasaki, “Valence bond ground states in isotropic quantum antiferromagnets,” Commun. Math. Phys. 115, 477–528 (1988).
  * Pollmann  _et al._ (2012) F. Pollmann, E. Berg, A. M. Turner, and M. Oshikawa, “Symmetry protection of topological phases in one-dimensional quantum spin systems,” Phys. Rev. B 85, 075125 (2012).
  * Cirac  _et al._ (2021) J. I. Cirac, D. Pérez-García, N. Schuch, and F. Verstraete, “Matrix product states and projected entangled pair states: Concepts, symmetries, theorems,” Rev. Mod. Phys. 93, 045003 (2021).
  * Kaltenbaek  _et al._ (2010) R. Kaltenbaek, J.n Lavoie, B. Zeng, S. D. Bartlett, and K. J. Resch, “Optical one-way quantum computing with a simulated valence-bond solid,” Nat. Phys. 6, 850–854 (2010).
  * Wei  _et al._ (2011) T-C Wei, I. Affleck, and R. Raussendorf, “Affleck-Kennedy-Lieb-Tasaki state on a honeycomb lattice is a universal quantum computational resource,” Phys. Rev. Lett. 106, 070501 (2011).
  * Mizel  _et al._ (2007) A. Mizel, D. A. Lidar, and M. Mitchell, “Simple proof of equivalence between adiabatic quantum computation and the circuit model,” Phys. Rev. Lett. 99, 070502 (2007).
  * Lloyd (1996) S. Lloyd, “Universal quantum simulators,” Science 273, 1073–1078 (1996).
  * Georgescu  _et al._ (2014) I. M. Georgescu, S. Ashhab, and F. Nori, “Quantum simulation,” Rev. Mod. Phys. 86, 153–185 (2014).
  * Garttner  _et al._ (2017) M. Garttner, J. Bohnet, and A. et al. Safavi-Naini, “Measuring out-of-time-order correlations and multiple quantum spectra in a trapped-ion quantum magnet,” Nature Physics 13, 781–786 (2017).
  * Biamonte (2008) J. D. Biamonte, “Nonperturbative $\mathit{k}$-body to two-body commuting conversion hamiltonians and embedding problem instances into ising spins,” Phys. Rev. A 77, 052331 (2008).

##  Appendix A Adiabatic Oracle with spin-$1/2$’s

The oracle Hamiltonian $H_{f}$ has eigenvalues that satisfy

$\begin{cases}E_{m}>0\quad{\rm for}~{}m\neq\omega,\\\ E_{m}<0\quad{\rm
for}~{}m=\omega.\end{cases}$ (12)

For an arbitrary state

$|\phi\rangle=\sum_{m}c_{m}|m\rangle,$ (13)

The oracle operation effectively implements the following effect:

$|\phi\rangle\rightarrow\sum_{m\neq\omega}c_{m}|m\rangle-
c_{\omega}|\omega\rangle.$ (14)

In the main text, we have shown that the oracle can be achieved with an
adiabatic process by coupling $H_{f}$ to an ancillary spin-$1$. In this
section, we demonstrate that the oracle can be realized with two ancillary
spin-$1/2$’s (qubits). The system $H_{f}$ and the two ancillary qubits will be
driven through an annealing process with total Hamiltonian from $t=0$ to a
total annealing time $t=T$,

$H(t)=A(t)H_{f}\otimes(\sigma^{a}_{z}+\sigma^{b}_{z})+B(t)(\sigma^{a}_{x}+\sigma^{b}_{x}),$
(15)

where $A(0)=B(T)=0$ and $A(T)=B(0)=1$. We will present two strategies with
different initial state preparation and final state readout.

Protocol 1: The system and two ancillary qubits are prepared in an initial
state

$|\psi(0)\rangle=|\phi\rangle\otimes|+\rangle|-\rangle,$ (16)

where $|\pm\rangle=(|0\rangle\pm|1\rangle)/\sqrt{2}$ is the $\pm 1$ eigenstate
of $\sigma_{x}$, and $|0\rangle$, $|1\rangle$ are the $+1$ and $-1$
eigenstates of $\sigma_{z}$, respectively. After the annealing with
Hamiltonian $H(t)$, the two ancillary qubits are measured in the $|\pm\rangle$
basis. If they are detected in the same state, the system is projected to the
desired state (14). Otherwise, the system state remains unchanged (in the
initial state $|\phi\rangle$).

Protocol 2: The system and two ancillary qubits are prepared in an initial
state

$|\psi(0)\rangle=|\phi\rangle\otimes\frac{|+\rangle|-\rangle+|-\rangle|+\rangle}{\sqrt{2}}.$
(17)

After annealing, the system and the ancillary qubits are decoupled, and the
system is in the desired state (14).

Demonstrations of the above protocols will be presented in the next section,
where we show that the reason for using two ancillary qubits prepared in the
opposite initial states is to remove the unwanted adiabatic phases—after the
adiabatic evolution, the two ancillary qubits accumulate adiabatic phases of
opposite signs, which cancel one another. Note also that the adiabatic oracle
in Protocol $1$ is implemented with a non-unity success probability ($1/2$, as
will be shown). However, since unsuccessful oracles leave the system state
unchanged, the correct oracle operation can be achieved in $\mathcal{O}(1)$
number of repetitions, which does not change the overall scaling of the
algorithm. Protocol $2$ does not involve the measurement process, but requires
the resource of Bell-state.

###  A.1 Proof of the validity of the adiabatic oracles

We first demonstrate protocol 1. The final state after the annealing process
can be computed as

$\hat{{\cal
T}}e^{-i\int_{0}^{T}H(t)\,dt}|\psi(0)\rangle=\sum_{m}c_{m}|m\rangle\otimes\hat{{\cal
T}}e^{-i\int_{0}^{T}dt\,\left[A(t)E_{m}\sigma^{a}_{z}+B(t)\sigma^{a}_{x}\right]}|+\rangle\otimes\hat{{\cal
T}}e^{-i\int_{0}^{T}dt\,\left[A(t)E_{m}\sigma^{b}_{z}+B(t)\sigma^{b}_{x}\right]}|-\rangle,$
(18)

where $\hat{\cal T}$ is time ordering operator. Hence, the total evolution
breaks into multiple $2$ dimensional sectors, labeled by ‘$m$’. For each
branching of the evolution, the energy gap is determined by the absolute value
of $E_{m}$. After annealing, the ancillary qubits will end up in the
eigenstate of $\sigma_{z}$, depending on the sign of the corresponding energy
$E_{m}$, i.e.,

$\hat{\cal
T}e^{-i\int_{0}^{T}dt~{}\left[A(t)E_{m}\sigma^{a}_{z}+B(t)\sigma^{a}_{x}\right]}|+\rangle=\begin{cases}e^{i\phi_{m}}|0\rangle\quad{\rm
for}~{}m\neq\omega,\\\ e^{i\phi_{\omega}}|1\rangle\quad{\rm
for}~{}m=\omega,\end{cases}$ (19)

where $\phi_{m}$ and $\phi_{\omega}$ are the adiabatic phases accumulated
during the adiabatic evolution, whose values depend on $E_{m}$ and therefore
are not needed in the final result. However, it is not necessary for us to
know their exact values. The crucial point is that the second ancillary qubit
will accumulate corresponding adiabatic phases of opposite signs, that is,

$\hat{\cal
T}e^{-i\int_{0}^{T}dt~{}\left[A(t)E_{m}\sigma^{a}_{z}+B(t)\sigma^{a}_{x}\right]}|-\rangle=\begin{cases}-e^{-i\phi_{m}}|1\rangle\quad{\rm
for}~{}m\neq\omega,\\\ e^{-i\phi_{\omega}}|0\rangle\quad{\rm
for}~{}m=\omega.\end{cases}$ (20)

To show this, we use the resolution of the identity operator in terms of
Pauli-Y operators, $\mathbb{I}=\sigma_{y}^{2}$. Note that $\sigma_{y}$ flips
the sign of $\sigma_{x}$ and $\sigma_{z}$, i.e.,
$\sigma_{y}\sigma_{z(x)}\sigma_{y}=-\sigma_{z(x)}$, and applies to the basis
states as $\sigma_{y}|0\rangle=i|1\rangle$, $\sigma_{y}|1\rangle=-i|0\rangle$,
and $\sigma_{y}|-\rangle=i|+\rangle$. Therefore,

$\displaystyle\hat{\cal
T}e^{-i\int_{0}^{T}dt~{}\left[A(t)E_{m}\sigma^{a}_{z}+B(t)\sigma^{a}_{x}\right]}|-\rangle=$
$\displaystyle\sigma_{y}^{2}\hat{\cal
T}e^{-i\int_{0}^{T}dt~{}\left[A(t)E_{m}\sigma^{a}_{z}+B(t)\sigma^{a}_{x}\right]}\sigma_{y}^{2}|-\rangle$
(21) $\displaystyle=$ $\displaystyle i\sigma_{y}\hat{\cal
T}e^{i\int_{0}^{T}dt~{}\left[A(t)E_{m}\sigma^{a}_{z}+B(t)\sigma^{a}_{x}\right]}|+\rangle$
$\displaystyle=$
$\displaystyle\begin{cases}i\sigma_{y}e^{-i\phi_{m}}|0\rangle=-e^{-i\phi_{m}}|1\rangle\quad{\rm
for}~{}m\neq\omega,\\\
i\sigma_{y}e^{-i\phi_{\omega}}|1\rangle=e^{-i\phi_{\omega}}|0\rangle\quad{\rm
for}~{}m=\omega.\end{cases}$

Note that in the above equation, $\sigma_{y}$ “commutes” with the time
ordering operator $\hat{\mathcal{T}}$ in the sense that

$\sigma_{y}\hat{\mathcal{T}}e^{-i\int_{0}^{T}H(t)dt}\sigma_{y}=\lim_{\delta
t\rightarrow 0}\sigma_{y}e^{-iH(T-\delta t)\delta
t}\sigma_{y}^{2}\dots\sigma_{y}^{2}e^{-iH(\delta t)\delta
t}\sigma_{y}^{2}e^{-iH(0)\delta
t}\sigma_{y}=\hat{\mathcal{T}}e^{-i\int_{0}^{T}\sigma_{y}H(t)\sigma_{y}dt},$
(22)

for $H(t)$ which is linear in the Pauli operators $\sigma_{x}$ and
$\sigma_{z}$. Therefore, for each branching (fixed ‘$m$’), the adiabatic
phases from the two ancillary qubits then cancel out, resulting in the final
state

$\displaystyle\hat{\cal T}e^{-i\int_{0}^{T}H\,dt}|\psi(0)\rangle$ (23)
$\displaystyle=$
$\displaystyle-\sum_{m\neq\omega}c_{m}|m\rangle\otimes|0\rangle|1\rangle+c_{\omega}|\omega\rangle\otimes|1\rangle|0\rangle$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\sum_{m\neq\omega}c_{m}|m\rangle-
c_{\omega}|\omega\rangle\right)\left(\frac{|--\rangle-|++\rangle}{\sqrt{2}}\right)+\frac{1}{\sqrt{2}}\left(\sum_{m\neq\omega}c_{m}|m\rangle+c_{\omega}|\omega\rangle\right)\left(\frac{|+-\rangle-|-+\rangle}{\sqrt{2}}\right).$

Hence, if the two ancillary qubits are detected in the same states in the
$|\pm\rangle$ basis (with a successful rate $1/2$), the oracle operation is
realized. Otherwise, the system state remains unchanged.

Following the above derivation of the time evolution, we can directly
demonstrate protocol 2: If the two ancillary qubits are prepared in a Bell
state $(|+-\rangle+|-+\rangle)/\sqrt{2}$, the total system evolves as

$\sum_{m}c_{m}|m\rangle\otimes\frac{|+-\rangle+|-+\rangle}{\sqrt{2}}\rightarrow-\left(\sum_{m\neq\omega}c_{m}|m\rangle-
c_{\omega}|\omega\rangle\right)\otimes\frac{|01\rangle+|10\rangle}{\sqrt{2}}.$
(24)

That is, the ancillary qubits decouple with the system, and the oracle is
realized successfully. With the cost of using Bell correlations for the
ancillary qubits, we can archive a unit success probability without doing
projective measurements. Note also that the two ancillary qubits end up in the
Bell state in the $|0\rangle$, $|1\rangle$ basis, which can be transformed to
the Bell state in the $|\pm\rangle$ basis by single qubit rotations.
Therefore, the ancillary qubits can be ‘recycled’ and used to the next
repetition of the oracle.

Finally, we comment on the reason for why the adiabatic conditions can be
satisfied efficiently. We have shown that for two ancillary qubits the
evolution splits into independent pseudo-spin-1/2 sectors, with a
characteristic magnetic field values that are not smaller than a threshold
value of order $|E_{m}|$ in the $m$-th sector. Since we assume that the
chemical potential is tuned to be somewhere inside the gap between the ground
and excited states, the minimal value of $|E_{m}|$ is ${\rm
min}(|E_{0}|,|E_{1}|)=O(\Delta)$. Hence, there is always a finite gap of order
$\Delta$ or larger in all invariant phase space sectors. Using general
arguments of the Landau-Zener theory, the nonadiabatic transition probability
is then suppressed by an expoential factor
$e^{-\eta^{\prime}|\Delta^{2}/(d\Delta/dt)|}$, where $\eta^{\prime}$ is a
protocol-dependent $O(1)$ constant. For a protocol of duration $T$, the rough
estimate gives $d\Delta/dt\sim\Delta/T$. Hence, the probability of a
nonadiabatic transition in each sector is given by $e^{-\eta\Delta T}$, where
$\eta$ is another constant.

###  A.2 Simulations

Figure 3: Averaged infidelity of the Grover’s oracle for a $2$-qubit system
with Hamiltonian (25) for two adiabatic schedules (see the legend), as a
function of the oracle running time. The solid (dashed) back curve is the best
fit to an exponential (power-law) decay.

We now present a numerical simulation for Protocol $1$ introduced in the
previous section. Let us consider the problem Hamiltonian to be the simplest
possible $n$-qubit Hamiltonian

$H_{f}=(n-1)\varepsilon\mathbb{I}+\sum_{i=1}^{n}\varepsilon_{i}\sigma_{z}^{i},$
(25)

where all $\varepsilon_{i}$ have the same magnitude $\varepsilon$ but
arbitrary signs. This Hamiltonian has the ground state energy $-\varepsilon$
with a gap $2\varepsilon$ over it. This particular case study serves as an
illustration of the adiabatic oracle, rather than tackling a real
computationally hard problem, since the ground state of this non-interacting
Hamiltonian is easy to find. The main reason to consider it is that the
corresponding time-dependent Hamiltonian for the adiabatic oracle,

$H(t)=\sum_{\alpha=a,b}\left[A(t)\left((n-1)\varepsilon+\varepsilon_{i}\sum_{i=1}^{n}\sigma_{z}^{i}\right)\sigma^{\alpha}_{z}+B(t)\sigma^{\alpha}_{x}\right],$
(26)

has only binary couplings $\varepsilon_{i}$ and local fields acting on the
qubits. This makes it most suitable for experimental demonstrations. Hence,
the example that we will work out here can serve as a guide for the simplest
experimental demonstration of our approach to the Grover’s algorithm.

As we have already shown, the quantum annealing with this Hamiltonian realizes
Grover’s oracle action on an arbitrary initial state of $n$ qubits. In this
oracle, the string $f$ is trivially encoded in the known ground state of
$H_{f}$ by setting the signs of $\varepsilon_{i}$. Realization of such a
Hamiltonian with controllable couplings in hardware has already been
demonstrated. An example is the DWave machine that can perform quantum
annealing for a Hamiltonian with programmable binary couplings of thousands of
qubits. In order to test our expectations about the accuracy of the adiabatic
oracle, we simulated both the generation of Grover’s oracle and the entire
process of computation of the ground state of Hamiltonain (25) using Grover’s
algorithm.

First, we simulated the time-dependent Schrödinger equation with the
Hamiltonian (26), with the initial state of the ancillary qubits given by
protocol $1$. After each oracle call, the four possible post-measurement
states, $|\phi_{k}\rangle_{k=0,\dots,3}$, of the final state were compared to
the corresponding expected ideal states $|\phi^{\rm
ideal}_{k}\rangle_{k=0,\dots,3}$. To quantify the error induced by the
nonadiabatic excitations, we computed the averaged infidelity

$1-\overline{F}=1-\sum_{k=0}^{3}|\langle\phi_{k}|\phi^{\rm
ideal}_{k}\rangle|^{2}/4.$ (27)

Figure 3 shows the numerical results for the averaged infidelity of the oracle
for various total quantum annealing time. It is illustrated that a simple
linear schedule results in a power-law suppression of the non-adiabatic error.
We attribute this to the fact that the linear schedule is not analytic at the
end of the evolution. With the schedule (8) in the main text, which was free
of this drawback, we indeed achieved the desired exponential suppression of
the oracle imperfections.

Next, we simulated the entire Grover’s algorithm with repeated generation of
the adiabatic oracle and the diffusion operation for a four-qubit system. The
initial state of the system was prepared in
$|s\rangle=\prod_{i}^{\otimes}|+\rangle_{i}$, where $|+\rangle$ is the
positive eigenstate of $\sigma^{i}_{x}$. This is an equal superposition of all
the eigenstates of the Ising Hamiltonian $H_{f}$. The diffusion operator was
realized using quantum annealing: the corresponding Hamiltonian was obtained
from $H_{f}$ in (25) by replacing $\sigma^{i}_{z}\rightarrow\sigma^{i}_{x}$
for all spins. The resulting Hamiltonian only contains terms with binary
couplings. In the four-qubit case, one gets the optimal output state (closest
to the ground state) after three successful implementations of the oracle and
the diffusion operation. This is clearly demonstrated in Fig. 4, which depicts
the fidelity of the output state with respect to the target state, for three
typical simulations. Since the measurement process after each oracle call is
probabilistic, we simulated these random processes and shown in the figure
three realizations of the process of the whole Grover algorithm. All such
simulations confirmed our estimates for the performance of our approach.

Figure 4: Three typical simulations of the fidelity (with respect to the
target state) after $N_{r}$ operation steps of Grover algorithm. The
simulations are performed for a $4$-qubit system. Circle (square) correspond
to the oracle (diffusion) operation. Open (closed) markers correspond to
successful (failed) operations. Dashed line indicate the expected optimal
fidelity ($\sim 0.96$) after $3$ successful realizations of the oracle.