# Resource-Efficient and Self-Adaptive Quantum Search in a Quantum-Classical
Hybrid System

Zihao Jiang*, Zefan Du*, Shaolun Ruan
Juntao Chen, Yong Wang, Long Cheng, Rajkumar Buyya, and Ying Mao *Authors
contributed equally Z. Jiang, Z. Du, J. Chen and Y. Mao are with the
Department of Computer and Information Science, Fordham University, New York
City. E-mail: {zjiang86, zdu19, jchen504<EMAIL_ADDRESS>S. Ruan and Y.
Wang are with the School of Computing and Information Systems, Singapore
Management University. E-mail: {slruan.2021<EMAIL_ADDRESS>L. Cheng is
with the School of Control and Computer Engineering, North China Electric
Power University, Beijing, China. E-mail<EMAIL_ADDRESS>R. Buyya is with
the School of Computing and Information Systems, The University of Melbourne,
Australia. E-mail<EMAIL_ADDRESS>
###### Abstract

Over the past decade, the rapid advancement of deep learning and big data
applications has been driven by vast datasets and high-performance computing
systems. However, as we approach the physical limits of semiconductor
fabrication in the post-Moore’s Law era, questions arise about the future of
these applications. In parallel, quantum computing has made significant
progress with the potential to break limits. Major companies like IBM, Google,
and Microsoft provide access to noisy intermediate-scale quantum (NISQ)
computers. Despite the theoretical promise of Shor’s and Grover’s algorithms,
practical implementation on current quantum devices faces challenges, such as
demanding additional resources and a high number of controlled operations. To
tackle these challenges and optimize the utilization of limited onboard
qubits, we introduce ReSaQuS, a resource-efficient index-value searching
system within a quantum-classical hybrid framework. Building on Grover’s
algorithm, ReSaQuS employs an automatically managed iterative search approach.
This method analyzes problem size, filters less probable data points, and
progressively reduces the dataset with decreasing qubit requirements.
Implemented using Qiskit and evaluated through extensive experiments, ReSaQuS
has demonstrated a substantial reduction, up to 86.36% in cumulative qubit
consumption and 72.72% in active periods, reinforcing its potential in
optimizing quantum computing application deployment.

###### Index Terms:

Quantum Unstructured Search; Quantum Resource Management; Qubit Efficiency;
Self-adaptive Quantum Search;

##  I Introduction

Over the past decade, we have witnessed groundbreaking advancements in deep-
learning and big-data based applications. New algorithms, coupled with
increased computational power and modern design methodologies, have
facilitated a broad spectrum of applications, ranging from scientific data
processing to commercial image and speech recognition. At the backend side,
these developments are underpinned by massive datasets and powered by high-
performance computing systems with substantial computational resources.
However, in the post-Moore’s Law era, we are confronted by the looming
physical limitations of semiconductor fabrication. Combined with the ceaseless
growth of data volumes, this circumstance compels us to reassess the future of
these applications.

To navigate the challenges of this new era, researchers are turning to
emerging disciplines. Quantum computing provides a promising alternative. For
example, Google exhibited quantum supremacy with a 53-qubit quantum computer,
completing in 200 seconds a task projected to take 10,000 years on the world’s
largest classical computer. Given the potential, quantum-based applications
are gaining increasing attentions in both industry and academia.

Inherently rooted in quantum mechanics, quantum bits (qubits) offer
distinctive characteristics such as superposition and entanglement. Unlike
their classical counterparts’ deterministic states, a qubit in superposition
simultaneously embodies both the ’0’ and ’1’ states, significantly enhancing
its representative capacity. Furthermore, two qubits can be placed in an
entanglement state, meaning the measurement of one qubit is contingent on the
measurement of another.

Leveraging these distinctive properties, many algorithms have been proposed,
aiming to achieve quantum speedups. Among them, Grover’s algorithm stands as a
representative example. It targets on unstructured database search and
outperforms classical counterparts, yielding a quadratic speedup. With
Grover’s algorithm, the qubits start out in the uniform superpositions such
that the amplitudes of all data points are the same. Then, it utilizes an
oracle function $O$, a ”black box” function that only reflects the amplitudes
of the searching targets and remains others untouched. Next, the algorithm
applies another reflection that can amplify the amplitude of the searching
targets and deamplify others. With certain rounds of this amplitude
amplification process, the targets will have significantly higher amplitudes
compared to others. Each reflection is an invocation of Grover’s operator.
While classical unstructured searching algorithms operate with an $O(N)$
complexity, Grover’s algorithm impressively trims it down to $O(\sqrt{N})$.

Grover’s search algorithm, along with its generalized version Quantum
Amplitude Estimation (QAE), has garnered significant interest due to its
genericity and quadratic speedup, serving as a cornerstone for myriad quantum-
based applications [1, 2, 3, 4, 5, 6, 7]. Brassard et al. [8] for instance,
have proposed a quantum counting algorithm that combines Grover’s and Shor’s
[9] algorithms to count the number of targets in a given dataset. This can be
perceived as an implementation of QAE based on Quantum Phase Estimation (QPE).
However, despite Grover’s search and QAE’s potential for substantial speedups,
its main component, QPE, grapples with two major obstacles: the requirement
for extra qubits and numerous controlled operations. These challenges render
QPE impractical in the Noisy Intermediate-Scale Quantum (NISQ) era,
characterized by limited quantum resources, including qubits [10, 11, 12, 13].

Optimized algorithms have been suggested to bypass QPE’s reliance [10, 11, 12,
13], potentially enhancing the efficiency of quantum counting and searching on
NISQ quantum computers [14, 15, 16, 17]. However, these solutions maintain the
same problem size in each Grover’s search iteration and fails to reduce the
resources, e.g., qubits, requirement. In the literature, IQuCS [18]
successfully reduces the search size iteratively by using classical data post-
posting. However, its algorithms rely on an administrator-specified threshold
that lacks adaptability in different search contexts.

The address the challenges, we introduce RESAQuS that considers an
unstructured dataset consisting of (index, value) pairs. The input data from
clients are values, and the index is the unstructured number that represents
data. RESAQuS utilizes Grover’s algorithm to search for targeted data points.
However, instead of finishing the entire search with multiple repeated
invocations, RESAQuS sets breakpoints to divide the entire search into
multiple iterations. Each iteration is an individual Grover’s search with a
reduced number of invocations. Based on the analysis of results after each
iteration, RESAQuS filters out non-target pairs and uses the remaining data
for the next iteration. The reduced dataset results in fewer qubits required.
Furthermore, on the classical part of the system, RESAQuS adopts a self-
adaptive clustering method for data filtering. Additionally, RESAQuS updates
the list of indexes and reconstructs the values iteratively, which further
reduces the number of required qubits. The following summarizes the main
contributions of this paper:

  * •

We propose, RESAQuS, a resource-efficient and self-adaptive quantum search
algorithm in a quantum-classical hybrid system for unstructured dataset of
(index, value) pairs.

  * •

In RESAQuS, our self-adaptive algorithms re-generates indexes and values to
achieve resource efficiency. Meanwhile, it maintains the mapping from the
generated data points to original ones and returns the original searching
(index, value) pairs.

  * •

Furthermore, RESAQuS utilizes a self-adaptive clustering algorithm analysis
the analyze quantum state fidelities after each iteration and filter out the
non-target data points without finishing the entire search. The self-adaptive
nature accommodate the searches with different problem sizes.

  * •

We implement RESAQuS with Qiskit, a popular quantum programming framework.
Intensive experiments are conducted with both Qiskit cloud simulator and
experiments on IBM-Q. Additionally, we propose Cumulative-Qubit Consumption
(CQC) to evaluate the qubit resource usage. The results demonstrate that
RESAQuS reduced CQC by up to 86.36% comparing to the state-of-the-arts.
Additionally, it reduces active periods by up to 72.72% on quantum workers in
the cluster mode.

The rest of this paper is organized as follows. Section II discusses the
related works. Section III introduces the basics of quantum computing and
Grover’s algorithm. We present our RESAQuS system design and algorithms in
Section IV. Comprehensive evaluations of the developed RESAQuS are provided in
Section V. Section VI concludes the work.

##  II Related Work

As the physical limits of semiconductor fabrication draw near, the race for
quantum computing development is intensifying. Major players and emerging
startups, including IBM, Google, Amazon, and IonQ, have initiated public
access to quantum systems.

In the quantum landscape, foundational algorithms, such as Grover’s algorithm
[19], Shor’s algorithm [20], quantum phase estimation [21], and variational
quantum circuits [22], attract tremendous attention that aims to observe a
quantum speedup on real devices in various applications. While these
algorithms, in theory, can deliver quadratic or even exponential speedups [23,
24, 25, 26], their practical deployment on NISQ devices presents formidable
challenges. Quantum phase estimation, for instance, requires additional qubits
and a substantial number of controlled operations, which are currently
unfeasible due to the constraints of low-qubit count and noise in quantum
hardware.

Building on these fundamental quantum components, advancements have been
observed in the realms of quantum deep learning [27, 28, 29, 30, 31, 26, 32,
33, 34, 35], quantum visualization [36, 37, 38, 39, 40, 41] and big data
analytics [42, 43, 44, 45]. Despite these improvements, the high quantum
resource requirements remains a significant hurdle to achieving commercial
deployment at scale in real-world scenarios. For instance, while QuGAN [29]
and QuClassi [27] demonstrate impressive performance in model building, their
results are based on a merely 4-dimensional dataset on the IBM-Q platform.
This is primarily due to the limitations of current NISQ hardware which offer
a limited qubits and suffer from noise-related issues.

Various optimizations have been proposed to address the resource-intensive
nature of QPE operations in quantum counting and searching, which hinders
their practicality on NISQ machines [2, 10, 11, 12, 13]. An exemplary approach
is the depth optimization method presented in [2]. This approach harnesses
multi-stage processing, along with global and local applications of Grover’s
operators, to achieve a substantial 20% reduction in circuit depth.
Additionally, MLQAE [10] combines multiple iterations of Grover’s algorithm
with maximum likelihood estimation to reduce the qubit requirement. Wie et al.
[11] proposes the use of Hadamard tests as less expensive alternatives to QPE.
Another approach, introduced in [12], presents a simplified quantum computing
algorithm that operates without QPE but introduces a significant overhead. A
recent effort called IQAE [13] reduces the overhead by iteratively
postprocessing quantum results using only Grover’s operator. These optimized
solutions have the potential to improve the efficiency of quantum counting and
searching on NISQ computers [15, 17]. However, these optimizations often focus
on specific problems or can be challenging to implement. Additionally,
existing approaches treat algorithms as indivisible tasks with the same
problem size in each iteration. In contrast, IQuCS [18] proposes an iterative
approach that divides searching problems and effectively reduces the problem
size using classical data post-processing. However, IQuCS relies on an
administrator-specified threshold, which lacks adaptability in different
search contexts and imposes additional deployment prerequisites.

Building upon IQuCS, our approach, RESAQuS, tackles a quantum search problem
that deals with (index, value) pairs. Diverging from existing literature,
RESAQuS places emphasis on iteratively reducing the input dataset by filtering
out non-target elements. This reduction is achieved through quantum state
fidelity analysis performed on the classical part. Furthermore, we introduce
self-adaptive algorithms to accommodate diverse searching settings. By
progressively reducing the input data in each iteration, RESAQuS maximizes the
utilization of qubits, resulting in an efficient completion of the search
task.

##  III Background and Motivation

The foundational unit in classical computing is the bit, which represents a
logical state with possible values $1$ and $0$. Classical computing commonly
implements bits using electromagnetic phenomena.

The theory of quantum mechanics describes the physical properties of nature at
atomic and subatomic scales, providing the foundations for understanding
quantum computing. Two fundamental phenomena in the theory are superposition
and entanglement, which form the building blocks in this field. Quantum bits,
or qubits, are capable of realizing these phenomena. Unlike classical bits, a
qubit can simultaneously represent $0$ and $1$ in the superposition. It
collapses to a deterministic state, $0$ or $1$, upon measurement.

###  III-A Qauntum States

Orthogonal vectors can represent the states of a qubit. Equation 1 represents
a qubit’s 0 and 1 state.

$|0\rangle=\begin{bmatrix}1\\\
0\end{bmatrix},\qquad|1\rangle=\begin{bmatrix}0\\\ 1\end{bmatrix}$ (1)

A universal qubit’s state $|q\rangle$ can be written as Equation 2,

$|q\rangle=\alpha|0\rangle+\beta|1\rangle,$ (2)

where

$|\alpha|^{2}+|\beta|^{2}=1$ (3)

The vector $|q\rangle$ is called a state vector of qubits, representing the
linear combination or superposition of two states associated with qubits [46].
In Equation 3, $\alpha$ and $\beta$, the amplitudes associated with each
state, can also be interpreted as the probability for the qubit to be in
states $|0\rangle$ and $|1\rangle$, respectively. When the qubit’s state is
measured, these amplitudes represent the probability of the superposition
collapsing into each state. Equation 3 is derived from the normalization
requirement, which ensures the probability of a qubit being in any state.

###  III-B Quantum Gates

Quantum computers encode and manipulate data using quantum gates. The two main
types of quantum gates are rotation gates, which perform a rotation about an
axis, and controlled gates, which operate on a qubit depending on the value of
a control qubit.

Rotation Gates: Rotation gates enable qubit rotations by adjusting parameters.
The matrix representation of the generalized single-rotation gate $R$ is
presented in Equation 4.

$R(\theta,\phi)=\left[\begin{array}[]{cc}\cos\frac{\theta}{2}&-ie^{-i\phi}\sin\frac{\theta}{2}\\\
-ie^{-i\phi}\sin\frac{\theta}{2}&\cos\frac{\theta}{2}\end{array}\right].$ (4)

Three commonly used special cases of the general rotation gate are the
$R_{X}$, $R_{Y}$, and $R_{Z}$ gates, as shown in (5)-(7). These gates
represent rotations in the $x$, $y$, and $z$ planes, respectively. They can be
expressed as follows: $R_{X}(\theta)$: This gate represents a rotation about
the $x$-axis by an angle $\theta$. It is a special case of the general
rotation gate, where $\phi=0$. $R_{Y}(\theta)$: This gate represents a
rotation about the $y$-axis by an angle $\theta$. It is another special case
of the general rotation gate, where $\phi=\frac{\pi}{2}$. $R_{Z}(\theta)$:
This gate represents a rotation about the $z$-axis by an angle $\theta$. The
derivation of $R_{Z}$ from the general rotation gate is more involved and is
not included here. These special cases provide specific rotations around the
corresponding axes, enabling precise control over the quantum state during
quantum computations.

$R_{X}(\theta)=\left[\begin{array}[]{cc}\cos\frac{\theta}{2}&-i\sin\frac{\theta}{2}\\\
-i\sin\frac{\theta}{2}&\cos\frac{\theta}{2}\end{array}\right]=R(\theta,0)$ (5)

$R_{Y}(\theta)=\left[\begin{array}[]{cc}\cos\frac{\theta}{2}&-\sin\frac{\theta}{2}\\\
\sin\frac{\theta}{2}&\cos\frac{\theta}{2}\end{array}\right]=R(\theta,\frac{\pi}{2})$
(6)

$R_{Z}(\theta)=\left[\begin{array}[]{cc}e^{\frac{-i\theta}{2}}&0\\\
0&e^{\frac{-i\theta}{2}}\end{array}\right]$ (7)

Hadamard Gate: The Hadamard gate is a fundamental gate in quantum computation.
It is a single-qubit gate that puts a qubit into the superposition. The gate
can be represented by Equation 8:

$H=\frac{1}{\sqrt{2}}\left[\begin{array}[]{cc}1&1\\\ 1&-1\end{array}\right].$
(8)

The coefficient $\frac{1}{\sqrt{2}}$ in (8) accounts for the normalization of
state amplitudes, ensuring that the sum of their squares is equal to 1. Each
state has a probability of $\frac{1}{2}$ and an amplitude of
$\frac{1}{\sqrt{2}}$.

Two-Qubit Rotation Gates: There are operations that act as two-qubit
rotations, applying an equal rotation to both qubits. These gates are
described by the following equations (9)–(11). Note that these gates are
represented by $4\times 4$ matrices, unlike the single-qubit gates that are
$2\times 2$ matrices. This is because, in a two-qubit gate, each qubit has two
possible measurements, resulting in four possible outcomes ($|00\rangle$,
$|01\rangle$, $|10\rangle$, $|11\rangle$), as opposed to the two outcomes seen
in single-qubit gates.

$R_{XX}(\theta)=\left[\begin{array}[]{cccc}\cos\frac{\theta}{2}&0&0&-i\sin\frac{\theta}{2}\\\
0&\cos\frac{\theta}{2}&-i\sin\frac{\theta}{2}&0\\\
0&-i\sin\frac{\theta}{2}&\cos\frac{\theta}{2}&0\\\
-i\sin\frac{\theta}{2}&0&0&\cos\frac{\theta}{2}\end{array}\right]$ (9)

$R_{YY}(\theta)=\left[\begin{array}[]{cccc}\cos\frac{\theta}{2}&0&0&i\sin\frac{\theta}{2}\\\
0&\cos\frac{\theta}{2}&-i\sin\frac{\theta}{2}&0\\\
0&-i\sin\frac{\theta}{2}&\cos\frac{\theta}{2}&0\\\
i\sin\frac{\theta}{2}&0&0&\cos\frac{\theta}{2}\end{array}\right]$ (10)

$R_{ZZ}(\theta)=\left[\begin{array}[]{cccc}e^{-i\frac{\theta}{2}}&0&0&0\\\
0&e^{-i\frac{\theta}{2}}&0&0\\\ 0&0&e^{-i\frac{\theta}{2}}&0\\\
0&0&0&e^{-i\frac{\theta}{2}}\end{array}\right]$ (11)

###  III-C Controlled Gates

In addition to two-qubit gates that involve rotations, there are also gates
that utilize a control qubit and a target qubit. These gates, known as
controlled gates, perform specific operations on the target qubit based on the
value of the control qubit. We introduce three main types of controlled gates
below.

CNOT Gate: The CNOT gate is a commonly used example of a two-qubit gate in
quantum computing. It operates by flipping the value of the target qubit if
and only if the control qubit is measured as 1. Otherwise, it leaves the
target qubit unchanged. The CNOT gate can be represented by the following
matrix:

$CNOT=\left[\begin{array}[]{cccc}1&0&0&0\\\ 0&0&0&1\\\ 0&0&1&0\\\
0&1&0&0\end{array}\right].$ (12)

Controlled Rotation Gates: Equations (13)–(15) represent controlled rotation
gates in matrix notation. These gates are similar to the CNOT gate, but
instead of flipping the state of the target qubit, they apply a rotation
operation based on the measurement of the control qubit.

$\centering CR_{X}(\theta)=\left[\begin{array}[]{cccc}1&0&0&0\\\ 0&1&0&0\\\
0&0&\cos\frac{\theta}{2}&-\sin\frac{\theta}{2}\\\
0&0&-\sin\frac{\theta}{2}&\cos\frac{\theta}{2}\end{array}\right]\@add@centering$
(13)

$\centering CR_{Y}(\theta)=\left[\begin{array}[]{cccc}1&0&0&0\\\ 0&1&0&0\\\
0&0&\cos\frac{\theta}{2}&-\sin\frac{\theta}{2}\\\
0&0&\sin\frac{\theta}{2}&\cos\frac{\theta}{2}\end{array}\right]\@add@centering$
(14)

$\centering CR_{Z}(\theta)=\left[\begin{array}[]{cccc}1&0&0&0\\\ 0&1&0&0\\\
0&0&e^{\frac{i\theta}{2}}&0\\\
0&0&0&e^{\frac{i\theta}{2}}\end{array}\right]\@add@centering$ (15)

The CSWAP gate offers an advantage by requiring only the measurement of the
ancilla qubit. When qubits are directly measured, their states collapse,
resulting in the loss of superposition. However, with the SWAP test and the
use of the CSWAP gate, it becomes possible to maintain the superposition of
the other qubits. This is achieved by measuring the quantum state fidelity
through the ancilla qubit instead of directly measuring the qubits themselves.
Consequently, this approach minimizes the information lost during measurement.
By leveraging the CSWAP gate and the SWAP test, the superposition and
entanglement of the qubits can be preserved, allowing for accurate fidelity
measurements without compromising the quantum state.

###  III-D Grover’s Algorithm

In classical computing, the linear or sequential search algorithm is typically
employed to search through an unsorted database. This approach involves
examining each element in the database until the desired item is found.
Consequently, the time complexity of this algorithm is $O(N)$, where $N$
represents the number of items in the database. On average, this method
requires searching through approximately $\frac{N}{{2}}$ elements before
finding the target item. In the quantum domian, Lov Grover proposed an
algorithm that harnesses the unique properties of quantum computing to achieve
a quadratic speed improvement for unstructured search problems. Grover’s
algorithm exhibits a complexity of $O(\sqrt{N})$. The algorithm employs a
black box function called an oracle to facilitate the search process. This
oracle alters the phase of the solution states, effectively allowing the
algorithm to home in on the desired solution more efficiently. The oracle is
expressed as a diagonal matrix. In a two-qubit system, if the desired state is
$|11\rangle$, then the oracle, $U_{t}$, admits the following form:

$U_{t}=\begin{bmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ 0&0&0&-1\end{bmatrix}.$
(16)

For each state $|x\rangle$ in the list, we have

$U_{t}|x\rangle=\begin{cases}|x\rangle,&\text{for}\quad x\neq t,\\\
-|x\rangle,&\text{for}\quad x=t,\\\ \end{cases}$ (17)

where $t$ is our target item $|11\rangle$.

The algorithm uses amplitude amplification to increase the probability of
measuring the target state. Beginning from a uniform superposition
$|s\rangle$, which can be expressed as $|s\rangle=H^{\otimes
n}|0\rangle^{n}=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle$, vectors
$|s\rangle,|s^{\prime}\rangle$ and $|t\rangle$, can be used to calculate the
reflection angle $\theta$. Assume vectors $|s^{\prime}\rangle$ and $|t\rangle$
are perpendicular, then
$|s\rangle=sin\theta|t\rangle+cos\theta|s^{\prime}\rangle$. By solving for
$\theta$, the reflection angle can be expressed by [47]

$\theta=\arcsin\langle s|t\rangle=\arcsin\frac{1}{\sqrt{N}}.$ (18)

Next, we use the oracle reflection $U_{f}$ to reflect the state $|s\rangle$
across the $|s^{\prime}\rangle$. This switches the amplitude in front of the
$|t\rangle$ to negative. Then, we use another reflection $U_{s}$ on the state
$|s\rangle$ where $U_{s}=2|s\rangle\langle s|-1$ to map the state to
$U_{s}U_{f}|s\rangle$. These two reflections make the state $|s\rangle$ closer
to the state $|t\rangle$ and decrease the amplitudes of the other states. We
repeat these two steps $n$ times and obtain the state $|\psi_{n}\rangle$,
where $|\psi_{n}\rangle=(U_{s}U_{f})^{n}|s\rangle$ [47].

A 3-Qubit Example: Figure 1 represents the quantum circuit with associated
gate operations for a 3-qubit Grover’s algorithm. The qubits required for
Grover’s algorithm can be calculated by $n=\log_{2}N$. In this example, we
have $N=8$, which requires $n=3$ qubits. The reflecting angle $\theta$ is

$\theta=\arcsin\frac{1}{\sqrt{8}}.$ (19)

Let us start with finding one target state, e.g., $|111\rangle$. As shown on
Figure 1, Hadamard gates are placed to all the qubits to put them onto the
superposition state, yielding the quantum state $|\phi_{1}\rangle$ at this
moment,

$\begin{split}|\phi_{1}\rangle=\frac{1}{\sqrt{8}}(|000\rangle+|001\rangle+|010\rangle+|011\rangle+|100\rangle\\\
+|101\rangle+|110\rangle+|111\rangle).\end{split}$ (20)

Then, we use an oracle function to mark the target state, which leads to state
$|\phi_{2}\rangle$

$\begin{split}|\phi_{2}\rangle=\frac{1}{\sqrt{8}}(|000\rangle+|001\rangle+|010\rangle+|011\rangle+|100\rangle\\\
+|101\rangle+|110\rangle-|111\rangle).\end{split}$ (21)

The third step is to apply the amplitude amplification process to the qubits
based on the following procedure:

  1. 1.

Apply the Hadamard gates and the Rotation $X$ gates to all three qubits;

  2. 2.

Apply a controlled $Z$ gate with the control qubits $q_{0}$ and $q_{1}$ and
the target qubit $q_{2}$;

  3. 3.

Apply the Hadamard gates and the Rotation $X$ gates to all three qubits again.

Finally, we get probability distribution of the quantum states as shown in
Figure 2. Please note that under a larger dataset, the amplification process
will be repeated multiple times to obtain targeted states.

Figure 1: Grover’s Algorithm with 3 qubits Figure 2: 3-Qubit Example: State
Probabilities

Grover’s algorithm can be used to find multiple target states in a list by
resorting to the transformation of statevector. By initializing the
statevector with all states in $|0\rangle$, we can switch the state
$|0\rangle$ to state $|1\rangle$ if it is a target state. For example, if the
target state is $|000\rangle,|010\rangle$ and $|111\rangle$, the statevector
transformation will be

$[0,0,0,0,0,0,0,0]\rightarrow[1,0,1,0,0,0,0,1].$ (22)

When the quantum system is measured, we will observe the target state with a
higher probability compared to others. However, to increase the difference of
probabilities between searching targets and others, the amplification process
will be repeated multiple times. With each repetition, target states’
probability continues to increase. The number of repetitions required depends
on several factors, including the number of target states, the size of the
dataset, and the number of qubit.

##  IV RESAQuS Solution Design

This section presents our solution design for quantum search, including the
RESAQuS system architecture and the algorithms.

###  IV-A System Architecture

We first introduce the problem setting and then describe the system
architecture of RESAQuS, a quantum-classical system designed for searching
targeted (index, value) pairs. The system receives a set of $n$ initial
values, ${v_{1},...v_{i},...v_{n}}\in D$, each of which is associated with an
index to form the (index, value) pairs. The set of targets,
${v_{i},...v_{j}}\in T$, is specified by the users, and the objective is to
find the corresponding indexes of the targets.

To achieve this goal, we utilize Grover’s search algorithm, which is described
in Section III-D. However, the original algorithm cannot be directly applied.
First, it only amplifies the amplitude of the targeted states and does not
output the targets and indexes. Moreover, since both the indexes and values
need to be encoded, the qubit requirement is higher than that of value-only
searches. Therefore, our goal is to output the targeted (index, value) pairs
while reducing the number of required qubits.

We propose a hybrid approach that combines quantum and classical computing
resources. Specifically, the system consists of a quantum part and a classical
part. The quantum part is responsible for implementing Grover’s search
algorithm to amplify the amplitude of the targeted states, and the classical
part performs postprocessing to extract the (index, value) pairs and reduces
the required number of qubits.

Figure 3: RESAQuS System Architecture

The hierarchical structure of RESAQuS’s system architecture is displayed in
Figure 3, which demonstrates a quantum-classical system design. Input data,
e.g., unstructured databases, is submitted to the classical component to the
Data Preprocessing module. During this phase, the module analyzes the data’s
size, index ranges, and extracts metadata for subsequent processing.

The Index/Value Management module receives the data from two possible sources,
(1) Data Preprocessing and (2) Quantum State Analysis. Its functionalities
divided into two scenarios. When the data comes from Data Preprocessing
module, the system employs its original index and value associations.
Otherwise, the module regenerates new indexes and values after filtering out
unlikely data points, as informed by the Quantum State Analyst module. In this
case, the module maintains a mapping between generated and original
indexes/values in order to return the original values at the end. Algorithm 1
Updating Indexes, Algorithm 2 Updating Values and Algorithm 3 maintain the
original Indexes are implemented in this module which will be described in
detail in the next subsection.

The Quantum Data Encoder module accepts the processed data from the
Index/Value Manager and encodes the classical data to quantum qubits. As our
data updates every iteration, the encoding should be updated accordingly. The
Amplification Preparation module calculates the number of amplitude
amplifications, e.g., reflections, based on the iteration number and previous
results. This number is used by the Logical Circuit Generator to prepare a
logical circuit, e.g, construct the oracle function, for quantum search.

The generated logical circuit is passed to a quantum computer, where Grover’s
search algorithm is conducted with a given number of amplitude amplification
within the Quantum Circuit Executor module. The quantum states are measured by
the Quantum State Measurement module and transferred back to the classical
component for further processing at the end of the search.

Upon receiving the results, the Quantum State Analyst module is activated to
perform Algorithm 4 Filter. If the algorithm finds all solutions, their
original indexes will be returned. Otherwise, it conducts filtering to ensure
that only potential solutions enter the next iteration. With this feature, the
problem set is reduced when the Index/Value Management modules are called in
the second and following rounds. Consequently, fewer qubits are required to
continue the search. Meanwhile, the mappings between current and original
indexes and values are maintained.

###  IV-B Algorithms Design

In this subsection, we describe the details of our algorithms in the system.
Table I summarizes the notations adopted in the algorithms. RESAQuS aims to
reduce the problem size iteratively, which leads to a reduction of required
qubits. The system achieves the reduction by updating the indexes and values
of the input data at each iteration, except for the first one that is input by
clients. At the end, however, it returns the original (index, value) pairs.
Therefore, RESAQuS has to preserve the mapping between original (index, value)
pairs with generated ones.

TABLE I: Notation Table

$k$ | the updating indexes of the original index
---|---
$PM$ | The dictionary map data set in the last iteration.
$Q_{j}$ | The qubits that we need at iteartion $j$.
$d_{i}$ | The $i^{th}$ element in the input data set.
$D_{j}$ | The input data set at iteration $j$.
$p_{i}$ | The $i^{th}$ element in the binary number set.
$P_{j}$ | The [index, value] pair binary number set which is generated by $D_{j}$ at iteration $j$.
$m_{i}$ | The $i^{th}$ element in the dictionary map.
$M_{j}$ | The dictionary map that pairs the index and value at iteration $j$.
$GBP(d)$ | The function that generates [index, value] pair
| binary number set by input data set $d$.
$GM(d)$ | The function that generates the dictionary map
| that pairs the index and value by input binary data set $d$.
$GI(a,B)$ | The function that gets the index of input $a$ in a list $B$.
$H(a)$ | The function that generates the hash value of the input $a$.
$MapI$ | The dictionary map that pairs the current indexes $k$ and original indexes $m_{i}$.
$GP_{j}$ | The probability dictionary that is generated by Grover’s Algorithm at iteration $j$.
$gp_{i}$ | The $i^{th}$ element in probability dictionary.
$CD(a,b)$ | The function that computes the distance between $a$ and $b$.
$CQ(d)$ | The function that computes the required qubits by input data set $d$.
$nce_{i}$ | the mean value of $c_{i}$

Algorithm 1 Updating Indexes, UI($M_{j}$)

1: Input: $M_{j}$

2: Initialization: $k=0$

3: for all $m_{i}\in M_{j}$ do

4: $MapI\leftarrow[m_{i}(i),k]$

5: $k++$

6: end for

7: return $MapI$

####  IV-B1 Index Updates and Mapping Maintenance

Algorithm 1 is used to generate new indexes for input data $M_{j}$, which is
entered by client, at the beginning of each iteration except for the first
one. It first accepts the input data $M_{j}$ and initialize the index $k$
(Line 1-2). Then, the algorithms creates a new dictionary $MapI$ to store the
current index $k$ from $0$ and the original index $m_{i}$ in dictionary to
maintain the mapping between them (Line 3-6). Lastly, it return the new
dictionary $MapI$ that will be used by Algorithm 3 (Line 7).

Algorithm 2 Updating Values, UV($D,T$)

1: Inputs: $D$: Input dataset, $T$: Searching targets

2: Initialization: $L=[~{}],C=[~{}]$

3: $C\leftarrow H(T)$

4: for all $d_{i}\in D$ do

5: if $H(d_{i})\in C$ then

6: $L\leftarrow GI(H(d_{i}),C)$

7: else

8: $C\leftarrow H(d_{i})$

9: $L\leftarrow GI(H(d_{i}),C)$

10: end if

11: end for

12: return $L$

####  IV-B2 Value Updates

Algorithm 2 aims to update remaining values after each iteration so that the
searching range in the input dataset can be reduced to the number of different
values. It first accepts input data set $D$, and the target value $T$ (Line
1). The system initializes two empty lists, $L$ and $C$. and appends the hash
value of the target to $C$ (Line 2 -3). Then, RESAQuS directs into two
branches for each date point in $D$ based on the hash value. (1) If the hash
value is in $C$, its index in $C$ is appended to $L$ as its new value; (2) If
its hash value is not in $C$, its hash value is appended to $C$ first, then
its value is updated to the index of its hash value in $C$, and appended to
$L$ (Line 4-11). Finally, it returns the output list $L$ of updated values
(Line 12).

Algorithm 3 Maintain Indexes, MI($M_{j},MapI$)

1: Inputs: $M_{j},MapI$

2: Initialization: $M=\\{~{}\\}$

3: for all $m_{i}\in M_{j}$ do

4: $M\leftarrow[MapI,m_{i}(value)]$

5: end for

6: return $M$

####  IV-B3 Maintain Index Mapping

While Algorithm 1-2 reduce the searching range by reorganizing the indexes and
values. However, RESAQuS is designed to return the original (index, value)
pairs to the clients. Therefore, the system requires to dynamically manage a
mapping between generated (index, value) pairs with the original ones.

Algorithm 3 maintains the mapping in each iteration except for the first one.
Initially, it accepts the dictionary map $M_{j}$ that pairs the index and
value at iteration $j$, and the dictionary map $MapI$ that pairs the current
indexes $k$ and original indexes $m_{i}$. These information come from the
previous iteration (Line 1). Then, it initializes the empty dictionary $M$
(Line 2). RESAQuS stores each original index which corresponds to the element
$m_{i}$ from $MapI$ to the new dictionary $M$ (Line 3-5). It returns the
generated dictionary with updated mappings, $M$ (Line 6).

Algorithm 4 Filter, F($GP_{j}$)

1: Inputs: $GP_{j}$

2: $c1=[~{}],c2=[~{}]$

3: $ce1=gp_{1}$

4: $ce2=gp_{n}$

5: repeat

6: for all $gp_{i}\in GP_{j}$ do

7: if $CD(gp_{i},ce1)<CD(gp_{i},ce2)$ then

8: $c1\leftarrow gp_{i}$

9: else

10: $c2\leftarrow gp_{i}$

11: end if

12: end for

13: $nce1=sum(c1)/len(c1)$

14: $nce2=sum(c2)/len(c2)$

15: until $ce=nce~{}\textbf{or}{}~{}i=mi$

16: if $ce1>ce2$ then

17: return $c1$

18: else

19: return $c2$

20: end if

####  IV-B4 Filtering Data Points

The Algorithms 1-3 focus on updating (index, value) pairs and maintaining the
mappings. While these techniques can reduce the range of search space, they
fail to reduce the data points within the dataset. To further reduce the
problem size, we propose a self-adaptive filtering algorithm to process the
state probabilities after each quantum search.

Algorithm 4 presents our filtering algorithm. Specifically, it categorizes the
data points into two clusters, potential targets and non-targets. The input
data is the state-probability dictionary $GP_{j}$ that is generated by quantum
search at iteration $j$ (Line 1). It then initializes two clusters $c1$ and
$c2$ (Line 2). The maximum and minimum values in the probability dictionary
are used as the centroid of the two clusters (Line 3-4). Lines 5-15 represent
a processing in each iteration. The system first calculates the distance
between each value in the probability dictionary and the two centroids, and
assign them to the closer cluster. After the assignments, we calculate the
mean of the clusters to obtain new centroids. If the new centroids are the
same as the original centroids, it means that we have reached convergence, and
the loop ends. We also set a maximum number of loops to prevent infinite
looping. Eventually, it return the cluster that has a larger centroid (Line
16-20). The principle of this algorithm is that in the probability dictionary,
the probability of the targets is much larger than that of the non-targets.

####  IV-B5 Integrated Iterative Quantum Search

Based on the Algorithms 1-4, the entire quantum-classical search process in
RESAQuS is shown in Algorithm 5. Initially, the input data set $D$, target
values $T$, and maximum iteration number $J$ are loaded (Line 1). The first
iteration is different from the second and following iterations as it
processes the original (index, value) pairs. It first calls Algorithm 2 to
update the values of the input data $D$. However, since Algorithm 2 defaults
the target values from $0$ to $n-1$, which the $n$ is the number of the
searching targets, these updated target value corresponds to Algorithm 1.
Then, $CQ$ calculates the number of qubits required for this iteration $Q_{1}$
(Line 4). Next, $GBP$ converts the input data $D_{1}$ to binary data $P_{1}$
(Line 5). After that, we run Grover’s search with input binary data $P_{1}$
(Line 6). Afterward, the system obtains the generated probability dictionary
$GP_{1}$ using Algorithm 4 and converts the probability dictionary $GP_{1}$
into a dictionary of indexes and values $M_{1}$ (Line 7-8). At the end of the
first iteration, we update the maximum iteration number $j$ to $1$, and
initialize the dictionary map data set $PM$ which will be in previous
iteration (Line 9-10).

From the second iteration onwards (Line 11-23), we start the while loop with
conditions. After each iteration, if the results of this iteration differ from
those of the previous one and the maximum number of iterations has not been
reached, the next iteration will be performed (Line 11). If the results of
this iteration are the same as those of the previous iteration or the maximum
number of iterations has been reached, the iteration stops. Then, it stores
the results of the previous iteration and uses Algorithm 1 to store the
original indexes of the input data in the beginning of the iteration (Line
12-13). Next, it updates the values of the input data $D_{j}$ using Algorithm
2 (Line 14-15). After we have the updated input $D_{j}$, we did the same steps
as the first iteration. It calculates the number of qubits required for this
iteration $Q_{j}$ with $D_{j}$, converts the input data $D_{j}$ to binary data
$P_{j}$, runs Grover’s algorithm with input binary data $P_{j}$, filters the
generated probability dictionary $GP_{j}$ using Algorithm 4, and converts the
probability dictionary $GP_{j}$ into a data dictionary of indexes and values
$M_{j}$ (Line 16-21). Finally, It maps the original indexes of the input data
before the end of the iteration by using Algorithm 3 (Line 21). At the end of
the loop, it also update the iteration number $j$ by adding $1$ (Line 22).
Ultimately, it returns the targeted (index, value) pairs (Line 24).

Algorithm 5 Iterative Quantum Search, IQS($D,T,J$)

1: Input:

1: $D:$ input dataset

1: $T:$ searching targets

1: $J:$ maximum iteration number

2: $D_{1}=UV(D,T)$

3: $T=[0,...n-1]$

4: $Q_{1}=CQ(D_{1})$

5: $P_{1}=GBP(D_{1})$

6: $GP_{1}=QuantumSearch(P_{1})$

7: $GP_{1}=F(GP_{1})$

8: $M_{1}=GM(GP_{1})$

9: $j=1$

10: $PM=\\{~{}\\}$

11: while $PM\neq M_{j}\And j<J$ do

12: $PM=M_{j}$

13: $MapI=SI(M_{j})$

14: $D_{j}=M_{j}(value)$

15: $D_{j}=UV(D_{j},T)$

16: $Q_{j}=CQ(D_{j})$

17: $P_{j}=GBP(D_{j})$

18: $GP_{j}=Grover^{\prime}sSearch(P_{j})$

19: $GP_{j}=F(GP_{j})$

20: $M_{j}=GM(GP_{j})$

21: $M_{j}=RI(M_{j},MapI)$

22: $j++$

23: end while

24: return $M_{j}$

##  V Evaluation

In this section, we evaluate RESAQuS with different settings and
configurations.

###  V-A System Implementation and Settings

RESAQuS is implemented in Python 3.8 and the IBM Qiskit Quantum Computing
simulator package. We use the Aer simulator as our backend to simulate a
noise-free environment. Grover’s algorithm is implemented using Qiskit’s
amplitude amplifiers APIs [48], and the number of shots is set to 24000.

As mentioned in Section IV, we convert the input data into binary values to
run Grover’s algorithm. Each binary value consists of an (index, value) pair:
the first part is its index and the second part is its value. For example,
$001001$ has 4 index qubits and 2 value qubits, indicating that its index is 2
with a value of 1. The evaluation considers two types of systems,

  * •

Standalone Mode: one classical machine combined with one quantum machine in
the system. In this configuration, the client, represented by the classical
machine, communicates with the quantum machine directly.

  * •

Cluster Mode: multiple classical machines integrate with multiple quantum
machines. In this configuration, the clients, represented by multiple
classical machines, submit searching jobs to a classical manager, who further
distributes the workload to multiple quantum workers.

###  V-B Evaluation Metrics

In the experiments, we compare RESAQuS with two state-of-the-art solutions in
the literature.

  * •

GSearch [49]: The Grover’s Search with IBM Qiskit implementation. It is a
quantum-only solution that utilizes a single iteration with the optimal number
of invocations of Grover’s operator, e.g., amplitude amplification process.

  * •

IQuCS [18]: The Grover’s Search with iterative post-processing on classical
computers. It is a threshold-based solution, such that a pre-defined threshold
is employed to filter out non-target in each iteration.

We conduct the same experiments with GSearch, IQuCS and RESAQuS to compare
their performance. Specifically, $optimal\\_num\\_iterations$ method in the
Grover APIs is used to determine the optimal number of iterations for Grover’s
algorithm [50]. The both of GSearch and IQuCS algorithms are threshold based.
GSearch’s threshold set $0.01$ to ensure finding the target by filtering the
non-target, and IQuCS’s thresholds are 1 times of mean value of probability.
There will be a special case of IQuCS’s threshold, which will be explained in
the following subsection.

Furthermore, we utilize three key metrics to analyze and compare the results:
(1) accuracy: the percentage of targets that have been successfully
identified; (2) total number of invocations: the number of invocations of
Grover’s operator, which is repeated amplitude amplification in Grover’s
algorithm, and (3) cumulative qubits consumption (CQC): the value that
represents the qubit consumption of an iterative quantum-classical search
algorithm. Specifically, the $CQC$ is defined by

$CQC=\sum_{i=1}^{i=n}C_{i}\times N_{q_{i}},$ (23)

where $i$ is the iteration number, $C_{i}$ is the number of Grover’s operator
invocations at iteration $i$, and $N_{q_{i}}$ is the number of qubits at
iteration $i$. A larger value of CQC indicates a more resource-intensive
algorithm. In GSearch, $CQC=Q\times I$, where $Q$ is the qubits required by
the algorithm and $I$ is the optimal number of iterations. In IQuCS and
RESAQuS, $CQC=\sum_{i=1}^{i=n}I_{i}\times Q_{i}$, where $I_{i}$ is the number
of Grover’s algorithm invocation at iteration $i$ and $Q_{i}$ is the number of
qubits required at iteration $i$. In IQuCS, the invocation number equals 1
when the iteration number is odd. Otherwise, the invocation number equals 2.
In RESAQuS, the invocation number always equals 1.

Figure 4: 15-5 Experiments: (a) Probabilities of GSearch in
Iteration-1-Invocation-1 (Left) and Iteration-2-Invocation-2 (Right); (b)
Probabilities of IQuCS in Iteration-1-Invocation-1 (Left) and
Iteration-3-Invocation-2 (Right); (c) Probabilities of RESAQuS in
Iteration-1-Invocation-1 (Left) and Iteration-2-Invocation-2

###  V-C Standalone Mode

In this setting, we have one classical machine and one quantum machine in the
system. We conducted three experiments with different data sizes and searching
targets.

Each of the three experiments included a graph comparing the results of three
algorithms using the same invocation. The X-axis represents the index value,
while the Y-axis represents probability, depicted through a blue bar chart.
Within the graph, the red line signifies the average probability of the
target, the green line represents the average probability of the non-target,
and the disparity between them is shaded in red on the left and green on the
right.

####  V-C1  Dataset-15 with 5 searching targets

In this experiment, our input data size is 15 with 5 searching targets. The
initial qubit requirement (e.g., the first iteration) is 8, with 4 qubits for
indexes and 4 qubits for values. Figure 4(a) shows the probability
distributions of GSearch with different numbers invocations. Since GSearch is
a single-iteration algorithm, this figure illustrates two individual
experiments.

The left graph of Figure 4(a) displays the results with only 1 invocation.
Although the five largest probabilities in the Figure 4(a) are clearly found,
GSearch finds $9$ targets in the $1$ iteration, with the largest probabilities
are $3.48\%$ and the smallest is $0.42\%$. The average probability of these 9
target states is 2.00%, while the average probability value of the rest states
is 0.33%, the highest probability value in the non-target is only 0.41%. The
right graph displays the distribution with 2 invocations, it is as same as the
left. $7$ targets are selected by GSearch this iteration with the largest
probabilities are $8.77\%$ and the smallest is $0.31\%$. The average
probability value of the target is 6.09%, while the average probability value
of the non-target is 0.23%.

As the invocation increases, the difference between the average probability of
the target and non-target also increases. It continues to grow until the
invocation reaches 5, at which point GSearch can successfully find all 5
targets, resulting in an accuracy of 100%, and CQC is $8\times 5$ = 40. By
comparing with the other two algorithms, we can see that the target average we
finally found is much higher than the non-standard average in Figure 4.

Figure 4(b) shows the results of IQuCS. As IQuCS is a threshold-based
solution, we set the threshold to 1. In the first iteration, 10 states are
filtered out, and in the second iteration, no data is filtered out. According
to its algorithm, IQuCS reaches the termination condition. The left graph of
Figure 4(b) represents the results after the first iteration with 1
invocation. At this point, the average probability of the targets is 3.22%,
and the average probability of the non-targets is 0.33%. The right graph
displays the results after the second iteration, which is when IQuCS
terminates. The average probability of the targets increases to 19.18%, and
the average probability of the non-targets is 0.37%. The significant
difference between the two clearly indicates the targets. Therefore, the
accuracy is 100.00% in 3 invocations with 2 iterations, and the CQC is
$8\times 1+4\times 2$ = 16.

Figure 4(c) shows the graph of RESAQuS. It also filters out 10 states in the
first iteration, which results in 4 qubits in the second iteration. RESAQuS
also finishes the search in 2 iterations and finds 5 target states, with the
probability of the targets and the average value the same as the IQuCS’s. The
CQC is $8+4$ = 12, which is a 70.00% reduction of GSearch and a 25.00%
reduction of IQuCS.

####  V-C2 Dataset-40 with 15 searching targets

In this experiment, we increase the input data size to 40, with 15 targets to
be found. The increased data size requires more qubits. Our initial qubits are
10, with 6 qubits for index and 4 qubits for value.

In Figure 5(a), the left graph shows the first invocation, in which we find 17
target states at this moment. Their average probability of 0.75% is much
higher than the average non-target states probability of 0.09%. The right
graph shows the second invocation finding 16 targets with an average
probability of targets 2.03%, and an average probability of non-targets 0.07%.
This time, we find 15 targets when the optimal iteration number become 6. The
CQC of GSearch is $10\times 6$ = 60.

Figure 5: 40-15 Experiments: (a) Probabilities of GSearch in
Iteration-1-Invocation-1 (Left) and Iteration-2-Invocation-2 (Right); (b)
Probabilities of IQuCS in Iteration-1-Invocation-1 (Left) and
Iteration-3-Invocation-2 (Right); (c) Probabilities of RESAQuS in
Iteration-1-Invocation-1 (Left) and Iteration-2-Invocation-2

For IQuCS, when using 1 as the threshold, we encounter an algorithm error. In
the first iteration, 16 data items are filtered out, and 24 remaining data
items are sent to the next iteration. In the second iteration, the system
filters out 9 data items. It looks like the algorithm find all the targets.
However, in the third iteration, 15 target data are filtered out by the
system. Since we do not have any data remaining, the system terminates with an
error message. The reason for this situation is due to the erroneous threshold
selection. The threshold of IQuCS is too sensitive, and it is difficult for us
to control the threshold in iteration. This fact motivates us to develop
RESAQuS in replace of IQuCS.

When setting the threshold to 0.8, it uses 4 iterations to find 15 target
states. The remaining data after each iteration is 30, 21, 15, and 15. Figure
5(b) shows the results. The target average probability and non-target average
probability change from 0.49% to 3.92%, and from 0.09% to 2.42%, respectively.
The CQC is $10+10\times 2+9+5\times 2$ = 49

Figure 5(c) shows the results of RESAQuS. It only takes two iterations to find
15 target values. The average probability of the targets and the average
probability of the non-targets are similar to the results of IQuCS. The
accuracy is 100.00%, and the CQC is $10+5$ = 15. This represents a 75.0%
reduction compared to Grover’s algorithm and a 69.39% reduction compared to
IQuCS.

####  V-C3 Dataset-80 with 20 searching targets

This experiment involves finding 20 targets among 80 data points. Our initial
qubits are 12, with 7 qubits for index and 5 qubits for value.

Figure 6(a) displays the probability distribution graph of GSearch. This time,
the final optimal iteration number is 11. We can observe that the optimal
iteration number also increases as the number of input data and required
qubits increases. The CQC is $12\times 11$ = 132. In invocation 1, the system
only finds 23 target states. In invocation 2, the system still finds 22 target
states. The average target probability increases from $0.20$% to $0.53$%, and
the average non-target probability decreases from $0.023$% to $0.021$%.

Figure 6(b) gives us the process graph of IQuCS. In this case, we set the
threshold to 1. It uses 4 iterations and finds exactly 20 targets. After each
iteration, the number of remaining data is 51, 34, 20, and 20. In each
iteration, the number of qubits is 12, 10, 8, and 6, respectively. The CQC is
$12+10\times 2+8+6\times 2$ = 52.

The iterative process of RESAQuS is Figure 6(c). It still only uses two
iterations and finds all 20 targets. In the first iteration, 60 data are
filtered out. In the second iteration, the system only uses 6 qubits to
implement the algorithm. The result of iteration 2 is the same as the result
of iteration 1, so we stop the iteration and find the targets, with an average
target probability of 4.79% and an average non-target probability of 0.09%.
The CQC is $12+6$ = 18, which indicates an 86.36% reduction of GSearch and a
65.38% reduction of IQuCS.

According to three experiments conducted using three different algorithms,
/sol employed fewer invocations than GSearch. Not only did /sol use fewer
invocations, but it also had fewer iterations. Furthermore, from small to
large datasets, the average target probability of /sol and /soll exceeded the
values of non-average target probability. From Figure 6(c) (left), we can
observe that the difference between the average target probability and non-
average target probability for /soll is even greater than that of /sol at the
same iteration. Additionally, the average target probability of /soll is more
than 2 times greater than the non-average target probability in all
experiments, even 10 times greater in Dataset-80.

Figure 6: 80-20 Experiments: (a) Probabilities of GSearch in
Iteration-1-Invocation-1 (Left) and Iteration-1-Invocation-2 (Right); (b)
Probabilities of IQuCS in Iteration-2-Invocation-1 (Left) and
Iteration-3-Invocation-2 (Right); (c) Probabilities of RESAQuS in
Iteration-1-Invocation-1 (Left) and Iteration-2-Invocation-2

####  V-C4 Cumulative Qubits Consumption Comparison

Figure 7 presents the qubits consumption for GSearch, IQuCS, and RESAQuS in
the above mentioned experiments, and the result is normalized with respect to
GSearch for comparison. Without post-processing, GSearch utilizes the same
number of qubits throughout the entire algorithm. Therefore, its qubits
consumption graph is always a rectangle, represented by the shaded area. The
light area stacked with the dark part is the qubits consumption graph of
IQuCS. We can see that it starts reducing the qubits requirement in the second
iteration due to post-processing on the classical side. The dark area is the
qubits consumption graph of RESAQuS. It sharply reduces the required qubits as
well as the number of iterations in all experiments. The area presents the CQC
value in the figure. Compared to GSearch, the CQC value of IQuCS decreases by
60.00% and the CQC value of RESAQuS decreases by 70.00% in the first
experiment; the CQC value of IQuCS decreases by 18.33% and the CQC value of
RESAQuS decreases by 75.00% in the second experiment; and the CQC value of
IQuCS decreases by 60.61% and the CQC value of RESAQuS decreases by 86.36% in
the third experiment. As the data size increases, we can observe that our
algorithm RESAQuS performs increasingly better than IQuCS and GSearch, with
increasing savings in the number of iterations, qubits required, and CQC.

Figure 7: Qubits Consumption

###  V-D Cluster Mode

In this configuration, our hybrid system contains multiple classical machines
and multiple quantum machines that form a computing cluster.

In our experiments, we submit 12 tasks to the hybrid system that contains 3
classical machines and 3 quantum workers. Specifically, we focus on resource
utilization of different solutions. These 12 tasks are repetitions of the
above-mentioned 3 different experiments, with each submitted 4 times. Figures
8,9 and 10 represent resource utilization of Gsearch, IQuCS, and RESAQuS on 3
quantum workers, respectively, each configured with 12 qubits. The $x$-axis
represents the number of invocations. The largest value on the $x$-axis is set
to 35 because, with Gsearch, worker-2 utilizes 34 invocations which is the
largest value among all experiments. The $y$-axis represents the normalized
CQC values on each worker. The colored areas in the figures represent the
active periods when qubits are occupied by searching tasks, and the shaded
areas represent idle periods when resources are available. The dashed lines
represent this specific worker’s average normalized CQC value during active
periods.

Figure 8 shows the results of GSearch in the 3-worker system. When processing
the same task, the number of qubits remains constant with each invocation as
it completes the entire search within one iteration. Therefore, the CQC value
also remains constant until the task is completed. For example, in Figure
8(c), during the periods of invocations 12 to 16, it represents the execution
of a single task in Experiment 1. This task requires 8 qubits which is 66.67%
when normalized to the maximum value of 12 qubits. The average CQC usage
across each worker is 83.95% in worker-1, 86.27% in worker-2, and 93.83% in
worker-3, respectively. Thus, the average CQC usage across all workers is
87.88%. The percentage active times for the three workers are $77.14$%,
$97.14$%, and $77.14$%, respectively. The average percentage active time
across all workers is $83.81$%.

(a) Worker 1

(b) Worker 2

(c) Worker 3

Figure 8: GSearch: Resource Usage in a 3-Worker Cluster Mode

Figure 9 presents the CQC using IQuCS. The average CQC usage across each
worker is 53.17% in worker-1, 65.08% in worker-2, and 69.05% in worker-3. The
average CQC across all workers is 62.90%, which is a 28.43% reduction of the
GSearch’s. The percentage active times are $51.43$%, $60.00$%, and $60.00$%,
with an average of $57.14$%, which is a $31.82$% reduction of the GSearch’s.

(a) Worker 1

(b) Worker 2

(c) Worker 3

Figure 9: IQuCS: Resource Usage in a 3-Worker Cluster Mode

Figure 10 presents the CQC using RESAQuS. The average CQC usage across each
worker is 50.00%, 62.50%, and 75.00%, with an overall average of 62.50%. This
yields a reduction of 28.88% compared to GSearch and a reduction of 0.64%
compared to IQuCS. Furthermore, the active periods for all workers amount to
22.86%, which is a 72.72% reduction compared to GSearch and a 60.00% reduction
compared to IQuCS. Therefore, using RESAQuSeffectively conserves computational
resources which reduces the overall activity time. This fact is evident by
comparing the shaded idle areas in Figures 8-10.

(a) Worker 1

(b) Worker 2

(c) Worker 3

Figure 10: RESAQuS: Resource Usage in a 3-Worker Cluster Mode

##  VI Conclusion

In this work, we present RESAQuS, a resource-efficient and self-adaptive
quantum-classical system for (index, value) unstructured search. Based on the
Grover’s algorithm, it utilizes a classical postprocessing approach to analyze
the resulting quantum state probabilities iteratively. Additionally, it
filters out the data points that are unlikely to be searching targets
according to the analysis. The remaining dataset is further processed into new
(index, value) pairs with a mapping to the original ones. With this design,
RESAQuS is able to reduce the dataset iteratively. The reduced dataset is fed
to RESAQuS in the next iteration for further processing until it becomes
stable.

With classical postprocessing, RESAQuS can signifcantly reduced the qubit
requirement and improve the resource efficiency. We implement RESAQuS with
Qiskit and evaluate it with extensive experiments under both standalone and
cluster modes. The results demonstrate that RESAQuS reduced cumulative-qubit
consumption by up to 86.36% comparing to the state-of-the-arts. Moreover, it
reduces active periods by up to 72.72% on quanutm workers in the cluster mode.

##  VII Acknowledgements

This research was supported in part by the National Science Foundation (NSF)
under grant agreements 2329020, 2301884, 2335788 and 2343535.

## References

  * [1] M. Grassl, B. Langenberg, M. Roetteler, and R. Steinwandt, “Applying grover’s algorithm to aes: quantum resource estimates,” in _Post-Quantum Cryptography_. Springer, 2016, pp. 29–43.
  * [2] K. Zhang and V. E. Korepin, “Depth optimization of quantum search algorithms beyond grover’s algorithm,” _Physical Review A_ , vol. 101, no. 3, p. 032346, 2020.
  * [3] T. Byrnes, G. Forster, and L. Tessler, “Generalized grover’s algorithm for multiple phase inversion states,” _Physical review letters_ , vol. 120, no. 6, p. 060501, 2018.
  * [4] M. E. Morales, T. Tlyachev, and J. Biamonte, “Variational learning of grover’s quantum search algorithm,” _Physical Review A_ , vol. 98, no. 6, p. 062333, 2018.
  * [5] R. Orus, S. Mugel, and E. Lizaso, “Quantum computing for finance: Overview and prospects,” _Reviews in Physics_ , vol. 4, p. 100028, 2019.
  * [6] K. Plekhanov, M. Rosenkranz, M. Fiorentini, and M. Lubasch, “Variational quantum amplitude estimation,” _Quantum_ , vol. 6, p. 670, 2022.
  * [7] S. B. Ramezani, A. Sommers, H. K. Manchukonda, S. Rahimi, and A. Amirlatifi, “Machine learning algorithms in quantum computing: A survey,” in _2020 international joint conference on neural networks (IJCNN)_. IEEE, 2020, pp. 1–8.
  * [8] G. Brassard, P. Høyer, and A. Tapp, “Quantum counting,” in _International Colloquium on Automata, Languages, and Programming_. Springer, 1998, pp. 820–831.
  * [9] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” _SIAM review_ , vol. 41, no. 2, pp. 303–332, 1999.
  * [10] Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto, “Amplitude estimation without phase estimation,” _Quantum Information Processing_ , vol. 19, no. 2, pp. 1–17, 2020.
  * [11] C. Wie, “Simpler quantum counting,” _Quantum Inf. Comput._ , vol. 19, no. 11&12, pp. 967–983, 2019. [Online]. Available: https://doi.org/10.26421/QIC19.11-12-5
  * [12] S. Aaronson and P. Rall, “Quantum approximate counting, simplified,” in _Symposium on Simplicity in Algorithms_. SIAM, 2020, pp. 24–32.
  * [13] D. Grinko, J. Gacon, C. Zoufal, and S. Woerner, “Iterative quantum amplitude estimation,” _npj Quantum Information_ , vol. 7, no. 1, pp. 1–6, 2021.
  * [14] P. Rao, K. Yu, H. Lim, D. Jin, and D. Choi, “Quantum amplitude estimation algorithms on ibm quantum devices,” in _Quantum Communications and Quantum Imaging XVIII_ , vol. 11507. SPIE, 2020, pp. 49–60.
  * [15] M. Willsch, D. Willsch, F. Jin, H. De Raedt, and K. Michielsen, “Benchmarking the quantum approximate optimization algorithm,” _Quantum Information Processing_ , vol. 19, no. 7, pp. 1–24, 2020.
  * [16] M. Amico, Z. H. Saleem, and M. Kumph, “Experimental study of shor’s factoring algorithm using the ibm q experience,” _Physical Review A_ , vol. 100, no. 1, p. 012305, 2019.
  * [17] E. Pelofske, J. Golden, A. Bärtschi, D. O’Malley, and S. Eidenbenz, “Sampling on nisq devices:” who’s the fairest one of all?”,” in _2021 IEEE International Conference on Quantum Computing and Engineering (QCE)_. IEEE, 2021, pp. 207–217.
  * [18] W. Mu, Y. Mao, L. Cheng, Q. Wang, W. Jiang, and P.-Y. Chen, “Iterative qubits management for quantum index searching in a hybrid system,” in _2022 IEEE International Performance, Computing, and Communications Conference (IPCCC)_. IEEE, 2022, pp. 283–289.
  * [19] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in _Proceedings of the twenty-eighth annual ACM symposium on Theory of computing_ , 1996, pp. 212–219.
  * [20] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in _Proceedings 35th annual symposium on foundations of computer science_. Ieee, 1994, pp. 124–134.
  * [21] G. D’Ariano, C. Macchiavello, and M. Sacchi, “On the general problem of quantum phase estimation,” _Physics Letters A_ , vol. 248, no. 2-4, pp. 103–108, 1998.
  * [22] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio _et al._ , “Variational quantum algorithms,” _Nature Reviews Physics_ , vol. 3, no. 9, pp. 625–644, 2021\.
  * [23] R. Babbush, J. R. McClean, M. Newman, C. Gidney, S. Boixo, and H. Neven, “Focus beyond quadratic speedups for error-corrected quantum advantage,” _PRX Quantum_ , vol. 2, no. 1, p. 010103, 2021.
  * [24] B. Baheri, Z. Xu, V. Chaudhary, Y. Mao, B. Fang, S. Xu, and Q. Guan, “Pinpointing the system reliability degradation in nisq machines,” in _2022 IEEE International Conference on Quantum Computing and Engineering (QCE)_. IEEE, 2022, pp. 646–652.
  * [25] A. Ambainis, A. Gilyén, S. Jeffery, and M. Kokainis, “Quadratic speedup for finding marked vertices by quantum walks,” in _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , 2020, pp. 412–424.
  * [26] T. Hoefler, T. Häner, and M. Troyer, “Disentangling hype from practicality: on realistically achieving quantum advantage,” _Communications of the ACM_ , vol. 66, no. 5, pp. 82–87, 2023.
  * [27] S. A. Stein, B. Baheri, D. Chen, Y. Mao, Q. Guan, A. Li, S. Xu, and C. Ding, “Quclassi: A hybrid deep neural network architecture based on quantum state fidelity,” _Proceedings of Machine Learning and Systems_ , vol. 4, 2022.
  * [28] S. Stein, Y. Mao, J. Ang, and A. Li, “Qucnn: A quantum convolutional neural network with entanglement based backpropagation,” in _2022 IEEE/ACM 7th Symposium on Edge Computing (SEC)_. IEEE, 2022, pp. 368–374.
  * [29] S. A. Stein, B. Baheri, D. Chen, Y. Mao, Q. Guan, A. Li, B. Fang, and S. Xu, “Qugan: A quantum state fidelity based generative adversarial network,” in _2021 IEEE International Conference on Quantum Computing and Engineering (QCE)_. IEEE, 2021, pp. 71–81.
  * [30] K. T. Schütt, M. Gastegger, A. Tkatchenko, K.-R. Müller, and R. J. Maurer, “Unifying machine learning and quantum chemistry with a deep neural network for molecular wavefunctions,” _Nature communications_ , vol. 10, no. 1, p. 5024, 2019.
  * [31] R. L’Abbate, A. D’Onofrio, S. Stein, S. Y.-C. Chen, A. Li, P.-Y. Chen, J. Chen, and Y. Mao, “A quantum-classical collaborative training architecture based on quantum state fidelity,” _IEEE Transactions on Quantum Engineering_ , 2024\.
  * [32] L. Alchieri, D. Badalotti, P. Bonardi, and S. Bianco, “An introduction to quantum machine learning: from quantum logic to quantum deep learning,” _Quantum Machine Intelligence_ , vol. 3, pp. 1–30, 2021.
  * [33] Y.-F. Yang and M. Sun, “Semiconductor defect detection by hybrid classical-quantum deep learning,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 2323–2332.
  * [34] A. Ajagekar and F. You, “Quantum computing based hybrid deep learning for fault diagnosis in electrical power systems,” _Applied Energy_ , vol. 303, p. 117628, 2021.
  * [35] A. D’Onofrio, A. Hossain, L. Santana, N. Machlovi, S. Stein, J. Liu, A. Li, and Y. Mao, “Distributed quantum learning with co-management in a multi-tenant quantum system,” in _2023 IEEE International Conference on Big Data (BigData)_. IEEE, 2023, pp. 221–228.
  * [36] S. Gunasekaran, J. E. Greenwald, and L. Venkataraman, “Visualizing quantum interference in molecular junctions,” _Nano letters_ , vol. 20, no. 4, pp. 2843–2848, 2020.
  * [37] S. Ruan, Q. Guan, P. Griffin, Y. Mao, and Y. Wang, “Quantumeyes: Towards better interpretability of quantum circuits,” _IEEE Transactions on Visualization and Computer Graphics_ , 2023.
  * [38] N. Li, F. Yan, and K. Hirota, “Quantum data visualization: A quantum computing framework for enhancing visual analysis of data,” _Physica A: Statistical Mechanics and its Applications_ , vol. 599, p. 127476, 2022.
  * [39] S. Ruan, R. Yuan, Y. Wang, Y. Lin, Y. Mao, W. Jiang, Z. Wang, W. Xu, and Q. Guan, “Venus: A geometrical representation for quantum state visualization,” _arXiv preprint arXiv:2303.08366_ , 2023.
  * [40] X. Liu, G. Farahi, C.-L. Chiu, Z. Papic, K. Watanabe, T. Taniguchi, M. P. Zaletel, and A. Yazdani, “Visualizing broken symmetry and topological defects in a quantum hall ferromagnet,” _Science_ , vol. 375, no. 6578, pp. 321–326, 2022.
  * [41] S. Ruan, Y. Wang, W. Jiang, Y. Mao, and Q. Guan, “Vacsen: A visualization approach for noise awareness in quantum computing,” _arXiv preprint arXiv:2207.14135_ , 2022.
  * [42] K. Das and A. Sadhu, “Experimental study on the quantum search algorithm over structured datasets using ibmq experience,” _Journal of King Saud University-Computer and Information Sciences_ , 2022.
  * [43] B. Baheri, D. Chen, B. Fang, S. A. Stein, V. Chaudhary, Y. Mao, S. Xu, A. Li, and Q. Guan, “Tqea: Temporal quantum error analysis,” in _2021 51st Annual IEEE/IFIP International Conference on Dependable Systems and Networks-Supplemental Volume (DSN-S)_. IEEE, 2021, pp. 65–67.
  * [44] F. Ablayev, M. Ablayev, J. Z. Huang, K. Khadiev, N. Salikhova, and D. Wu, “On quantum methods for machine learning problems part i: Quantum tools,” _Big data mining and analytics_ , vol. 3, no. 1, pp. 41–55, 2019.
  * [45] C. Ding, T.-Y. Bao, and H.-L. Huang, “Quantum-inspired support vector machine,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 33, no. 12, pp. 7210–7222, 2021.
  * [46] T. G. Wong, _Introduction to Classical and Quantum Computing_. Rooted Grove, 2022.
  * [47] E. Rieffel and W. Polak, _QUANTUM COMPUTING A Gentle Introduction_. MIT Press, 2011.
  * [48] “Ibm-q build-in algorithms,” https://qiskit.org/documentation/apidoc/algorithms.html.
  * [49] “Grover’s algorithm in ibm qiskit,” https://quantum-computing.ibm.com/composer/docs/iqx/guide/grovers-algorithm.
  * [50] “Bm-q optimal number of iterations,” https://qiskit.org/documentation/stubs/qiskit.algorithms.Grover.optimal_num_iterations.html#qiskit.algorithms.Grover.optimal_num_iterations.

|  Zihao Jiang graduated from high school in 2016 and came to the United
States to continue his education. In 2021, he received the bachelor of Art in
Statistics/Mathematics in Rutgers University in New Jersey. In 2022, he joined
Fordham University for a master of science degree in Data Science. During his
time at Fordham, he earned graduate assistantship and worked for Computer and
Information Science Department. He received his Master degree and Advanced
Certificate in Financial Econometrics and Data Analysis from Fordham
University in 2023.
---|---
|  Zefan Du received the bachelor of science in Mathematics at Purdue
University, West Lafayette, in 2021. He is currently pursuing his master of
science degree in Data Science at Fordham University, NY. He is a graduate
assistant at Fordhaam and expected to graduate in December 2023. His research
interests, which include meme-stock analysis and quantum computing, reflect a
diverse range of topics within the field of data science.
---|---
|  Shaolun Ruan is currently a Ph.D. candidate in School of Computing and
Information Systems at Singapore Management University. He received his
bachelor’s degree from the University of Electronic Science and Technology of
China majoring in Information Security at the School of Computer Science and
Engineering in 2019. His work focuses on developing novel graphical
representations that enable a more effective and smoother analysis using
machines, leveraging the methods from Data Visualization and Human-computer
Interaction.
---|---
|  Juntao Chen (S’15-M’21) received the Ph.D. degree in Electrical Engineering
from New York University (NYU), Brooklyn, NY, in 2020, and the B.Eng. degree
in Electrical Engineering and Automation with honor from Central South
University, Changsha, China, in 2014. He is currently an assistant professor
at the Department of Computer and Information Sciences and an affiliated
faculty member with the Fordham Center of Cybersecurity, Fordham University,
New York, USA. His research interests include cyber-physical security and
resilience, quantum AI and its security, game and decision theory, network
optimization and learning. He was a recipient of the Ernst Weber Fellowship,
the Dante Youla Award, and the Alexander Hessel Award for the Best Ph.D.
Dissertation in Electrical Engineering from NYU.
---|---
|  Yong Wang is currently an assistant professor in School of Computing and
Information Systems at Singapore Management University. His research interests
include data visualization, visual analytics and explainable machine learning.
He obtained his Ph.D. in Computer Science from Hong Kong University of Science
and Technology in 2018. He received his B.E. and M.E. from Harbin Institute of
Technology and Huazhong University of Science and Technology, respectively.
For more details, please refer to http://yong-wang.org.
---|---
|  Long Cheng is a Full Professor in the School of Control and Computer
Engineering at North China Electric Power University in Beijing. He received
Ph.D from National University of Ireland Maynooth in 2014. He was an Assistant
Professor at Dublin City University, and a Marie Curie Fellow at University
College Dublin. He also has worked at organizations such as Huawei
Technologies Germany, IBM Research Dublin, TU Dresden and TU Eindhoven. He has
published more than 90 papers in journals and conferences like TPDS, TON, TC,
TSC, TASE, TCAD, TVT, TCC, TBD, TITS, TSMC, TVLSI, JPDC, HPCA, CIKM, ICPP,
CCGrid and Euro-Par etc. His research focuses on distributed systems, deep
learning, cloud computing and process mining. Prof Cheng is a Senior Member of
the IEEE, an associate editor of IEEE Transactions on Consumer Electronics,
and Co-Chair of Journal of Cloud Computing.
---|---
|  Rajkumar Buyya is a Fellow of IEEE, Academia Europea, and Redmond Barry
Distinguished Professor and Director of the Cloud Computing and Distributed
Systems (CLOUDS) Laboratory at the University of Melbourne, Australia. He is
also serving as the founding CEO of Manjrasoft, a spin-off company of the
University, commercializing its innovations in Cloud Computing. He has
authored over 850 publications and seven textbooks including ”Mastering Cloud
Computing” published by McGraw Hill, China Machine Press, and Morgan Kaufmann
for Indian, Chinese and international markets respectively. Dr. Buyya is one
of the highly cited authors in computer science and software engineering
worldwide (h-index=167 g-index=365, and 147,500+ citations). He has been
recognised as a ”Web of Science Highly Cited Researcher” for seven times since
2016, ”Best of the World” twice for research fields (in Computing Systems in
2019 and Software Systems in 2021/2022/2023) as well as ”Lifetime Achiever”
and ”Superstar of Research” in ”Engineering and Computer Science” discipline
twice (2019 and 2021) by the Australian Research Review.
---|---
|  Ying Mao is an Associate Professor in the Department of Computer and
Information Science at Fordham University in the New York City. He received
his Ph.D. in Computer Science from the University of Massachusetts Boston in
2016. He was a Fordham-IBM research fellow. His research interests mainly
focus on the fields of quantum systems, quantum deep learning, quantum-
classical optimizations, system virtualization, cloud resource management,
data-intensive platforms and containerized applications.
---|---