2021

[1]Kwangmin Yu

1]Computational Science Initiative, Brookhaven National Laboratory, Upton, New
York, 11973, USA

2]Department of Chemistry, Stony Brook University, Stony Brook, New York,
11794-3400, USA

3]C.N. Yang Institute for Theoretical Physics, Stony Brook University, Stony
Brook, New York, 11794-3840, USA

# Quantum multi-programming for Grover’s search

Gilchan Park<EMAIL_ADDRESS>Kun Zhang<EMAIL_ADDRESS><EMAIL_ADDRESS>Vladimir Korepin<EMAIL_ADDRESS>[  [  [

###### Abstract

Quantum multi-programming is a method utilizing contemporary noisy
intermediate-scale quantum computers by executing multiple quantum circuits
concurrently. Despite early research on it, the research remains on quantum
gates or small-size quantum algorithms without correlation. In this paper, we
propose a quantum multi-programming (QMP) algorithm for Grover’s search. Our
algorithm decomposes Grover’s algorithm by the partial diffusion operator and
executes the decomposed circuits in parallel by QMP. We proved that this new
algorithm increases the rotation angle of the Grover operator which, as a
result, increases the success probability. The new algorithm is implemented on
IBM quantum computers and compared with the canonical Grover’s algorithm and
other variations of Grover’s algorithms. The empirical tests validate that our
new algorithm outperforms other variations of Grover’s algorithms as well as
the canonical Grover’s algorithm.

###### keywords:

Quantum Computing; NISQ Algorithm; Multi-Programming; Grover’s Search.

##  1 Introduction

In recent years, unprecedented development has taken place in a range of
quantum computing. In particular, significant progress has been made in
building quantum computers by companies, such as IBM, Google, Intel, and
Rigetti in superconducting architecture, and IonQ and Honeywell (Quantinuum)
in trapped ion architecture, respectively. The companies adapting
superconducting architecture have announced around $50$ qubits quantum
computers. In particular, IBM is operating a $127$-qubit quantum computer
IBM_127q , which is the largest number of qubits now. On the other hand,
trapped ion quantum computers show better fidelity and full connectivity
between qubits even though the number of qubits doesn’t exceed $20$ now.
Regardless of the architecture, these Noisy-Intermediate Scale Quantum (NISQ)
Preskill2018quantumcomputingin  computers suffer from several noises and
errors such as measurements error, multi-qubit gate error, and even worse,
short decoherence times. Therefore, these contemporary quantum devices fail to
produce reliable outputs for deep circuits with many gates today. Even though
the quantum computer vendors are releasing better quantum computers in terms
of Quantum Volume moll2018quantum ; cross2019validating , which is a method to
measure and quantify the computational power of a quantum device, the quantum
device still remains far not only from the quantum supremacy in practical
problems, but also from implementing traditional quantum algorithms such as
number factoring shor1994algorithms , simulating quantum systems
lloyd1996universal , unstructured search groverQuantumMechanicsHelps1997 , and
solving linear systems of equations harrow2009quantum . Furthermore, the
availability of fault-tolerant quantum computers remains out of reach for now
or decades away. Therefore, an imperative problem we face is efficiently using
contemporary NISQ devices to achieve a quantum advantage.

In this vein, Variational Quantum Algorithms (VQAs), such as Quantum
Approximate Optimization Algorithm (QAOA) farhi2014quantum , Variation Quantum
Eigensolver (VQE) peruzzo2014variational , and Quantum Neural Networks
farhi2018classification ; altaisky2001quantum ; beer2020training ;
cong2019quantum , have drawn attention as a promising candidate to achieve
quantum advantage on NISQ devices. A different approach on NISQ devices is
improving the traditional quantum algorithms such as Quantum Amplitude
Estimation (QAE) aaronson2020quantum ; suzuki2020amplitude ; yu2020practical ;
grinko2021iterative ; rao2020quantum  and Grover’s search zhang2020depth ;
zhang2021implementation ; zhang2022quantum  to work on NISQ devices. These
approaches are developing quantum algorithms suitable for NISQ devices. In
particular, these algorithms struggle with long circuit depth. The former
algorithms use classical computers in the middle, this undermines the quantum
speed-up in spite of better accuracy and fidelity due to the shorter circuit
depth.

Another approach to utilize contemporary noisy quantum computers more
efficiently is by overlapping multiple circuits das2019case . This method,
called Quantum Multi-Programming (QMP), utilizes the NISQ devices by executing
multiple quantum circuits concurrently. The quantum circuits executed
concurrently can be different and even have different circuit depths. The main
motivation of the QMP is that the number of qubits of NISQ computers is much
greater than the Quantum Volume (QV). In particular, superconducting quantum
computers have limited connectivity between qubits and low quantum volume
compared to trapped ion quantum computers. IBM’s quantum volume, $V_{Q}$,
definition is shown as follows:

${\displaystyle\log_{2}V_{Q}={\underset{m}{\operatorname{arg\,max}}}\left\\{\min\left[m,d(m)\right]\right\\}}$

where $m$ is the number of qubits and $d(m)$ is the depth of the model circuit
with $m$-qubits cross2019validating . One depth of the model circuit is
composed of a random permutation of the qubits involved in the test, followed
by random two-qubit gates. Therefore, the depth of the model circuit is
greater than the circuit depth. This expresses the maximum volume, width
($m$), and depth ($d(m)$), of the model circuits that can be implemented
successfully on average by the computer. For example, $\it IBM\\_Washington$
quantum computer has $127$ qubits with QV $64$. This means the model circuit
with $6$-qubits runs reliably at six depths of the model circuit on average on
$\it{IBM\\_Washington}$. Since the quantum volume is the upper bound having a
reliable output, this also means the $7$-qubit correlated system with the
circuit depth of the model circuit fails to make reliable output even though
$\it{IBM\\_Washington}$ has $127$ qubits. Another examples are that
$\it{IBMQ\\_Kolkata}$, $\it{IBMQ\\_Montreal}$, and $\it{IBMQ\\_Mumbai}$ have
$27$ qubits and QV $128$. Other superconducting quantum computers share
similar properties such as limited connectivity between qubits, and more
qubits than the QV. Therefore, it is imperative to use more efficiently the
capacity of the contemporary superconducting quantum devices and the QMP is a
recently suggested method for this purpose.

However, QMP on NISQ devices is not straightforward because QMP accompanies
unfavorable impacts on the whole system such as measurement timing of the
concurrent circuits das2019case  and crosstalk between different circuits
ohkura2022simultaneous . In addition to those issues, efficient qubit mapping
between the logical qubits and the physical qubits, and task scheduling are
studied liu2021qucloud ; niu2021enabling ; niu2022parallel , as well as the
comparison of QMP between trapped ion and superconducting quantum devices
niu2022multi . In spite of those preliminary studies for QMP, applying QMP to
quantum algorithms is not developed well. We were able to find only one piece
of literature that accelerated by QMP in Ref. resch2021accelerating .

In this study, we apply QMP to Grover’s search algorithm to enhance the
performance of the algorithm on NISQ computers. This algorithm decomposes
Grover’s algorithm by the partial diffusion operator and places the decomposed
circuits in parallel. This algorithm increases the rotation angle of the
Grover operator so that, as a result, increases the success probability. The
detail of the algorithm is described in Sec. 3.3. This QMP variation of
Grover’s search outperforms Grover’s search and several variations of it. The
empirical results are described in Sec. 4.

##  2 Grover’s search algorithm

Since the main contribution of this paper is a new variation of Grover’s
search algorithm and the key component of the new variation is the partial
diffusion operator, we briefly review Grover’s search algorithm and its
variation, partial Grover’s search algorithm.

###  2.1 Original Grover’s search algorithm

The original Grover’s search algorithm finds a target item (if there are
multiple target items) in an unstructured database
groverQuantumMechanicsHelps1997 . Suppose that the total number of items in
the database is $N=2^{n}$. For each item, we can use a basis vector $\ket{i}$
in the Hilbert space $\mathcal{H}_{2}^{\otimes n}$ to represent each item. The
power of quantum computation lies in quantum superposition. We can set the
initial state as a uniform superposition of all the basis vectors, given by

$\ket{s_{n}}=H^{\otimes n}\ket{0}^{\otimes n},$ (1)

with the single-qubit Hadamard gate $H$ NC10 . Note that all the Hadamard
gates can be applied in parallel.

The target item, or the target state, can be recognized by the oracle. In
Grover’s search algorithm, the oracle is designed to reflect the sign of all
the target states. It can be expressed as

$O_{T}=1\\!\\!1-2\sum_{t\in T}\ket{t}\bra{t},$ (2)

with the set of all target states $T$. Assume that the number of target states
is
${M=\mbox{{}\rm\sf\leavevmode\hbox{}\hbox{}T\/}$.Giventheinitialstate$\ket{s_n}$,applyingtheoraclecannotincreasetheprobabilityoffindingthetargetstate.Wewouldneedanoracle-
independentoperation,calledthediffusionoperator.Itisdefinedas\begin{equation}D_{n}=1\\!\\!1_{2^{n}}-2\ket{s_{n}}\bra{s_{n}}.\end{equation}Thediffusionoperator$D_n$reflectstheamplitudesofallstatesintermsoftheiraverage.Thereforetheamplitudesoftargetandnon-
targetstatesaremixed(diffused).\par
CombiningtheoracleandthediffusionoperatorgivestheGroveroperator,denotedas\begin{equation}G_{n}=D_{n}O_{T}.\end{equation}RepeatedlyapplyingtheGroveroperatorontheinitialstate$\ket{s_n}$wouldincreasetheamplitudesoftargetstates.Theprobabilityoffindingoneofthetargetstatesafter$j$iterationoftheGroveroperatoris\begin{equation}\absolutevalue{\bra{t}G^{j}_{n}\ket{s_{n}}}^{2}=\sin^{2}\left((2j+1)\sin^{-1}\left(\sqrt{\frac{M}{N}}\right)\right).\end{equation}When$M/N\ll
1$,onecaneasilyseethatif$j$approaches$\pi\sqrt{N/M}/4$,thesuccessprobabilityapproaches1.Thenweonlyneed$\mathcal{O}(\sqrt{N/M})$numbersoforacletofindthetargetstate.Comparedtotheclassicalexhaustivesearchwithcomplexity$\mathcal{O}(N-M)$,Grover^{\prime}ssearchalgorithmhasaquadraticspeedup.\par\par\par\par\@@numbered@section{subsection}{toc}{Partial
Grover's search algorithm} \par Although the diffusion operator is oracle
independent, it consumes computational resources. Specifically, the $n$-qubit
diffusion operator is single-qubit-equivalent to the $n$-qubit Toffoli gate
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{NC10}{\@@citephrase{(}}{\@@citephrase{)}}}. In practice,
the $n$-qubit Toffoli gate is hard to be implemented on NISQ computers when
$n$ is large. The $n$-qubit Toffoli gate has to be decomposed into elementary
single- and two-qubit gates. If the physical qubits are not connected,
additional SWAP gates are also needed. \par To reduce the physical resources
of the diffusion operators, Grover first proposed the partial diffusion
operators in the quantum search algorithm \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{groverTradeoffsQuantumSearch2002}{\@@citephrase{(}}{\@@citephrase{)}}}.
The local diffusion operator reflects the amplitudes in the subspace of the
database. It has the form
\begin{equation}D_{m}=\left(1\\!\\!1_{2^{m}}-2\ket{s_{m}}\bra{s_{m}}\right)\otimes
1\\!\\!1_{2^{b}},\end{equation} with $b+m=n$. In other words, $b$ qubits are
untouched by $D_{m}$. We also call it the local diffusion operator. The local
diffusion operator $D_{m}$ is always easier to be implemented than the global
diffusion operator $D_{n}$ on real computers with $m<n$. Correspondingly, we
have the local Grove operator, given by
\begin{equation}G_{m}=D_{m}O_{T}.\end{equation} Note that the local Grover
operator has the same oracle as the global diffusion operator since the oracle
is set once the problem to be solved is set. \par The local diffusion operator
is also introduced to the partial search problem \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{GR05,KG06}{\@@citephrase{(}}{\@@citephrase{)}}}. It finds
partial bits of the target state. It trades accuracy for speed. The quantum
partial search algorithm is realized by the operator
$G_{n}G^{j_{2}}_{m}G^{j_{1}}_{n}$. The number of iterations $j_{1}$ and
$j_{2}$ is correlated in order to maximize the success probability. Meanwhile,
one can also minimize the total number of oracles $j_{1}+j_{2}$ to give the
optimal quantum partial search algorithm \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{Korepin05}{\@@citephrase{(}}{\@@citephrase{)}}}. Note that
the quantum partial search algorithm for unevenly distributed multi-target
states is studied in detail in Refs. \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{choi2007quantum,
zhang2018quantum}{\@@citephrase{(}}{\@@citephrase{)}}}. \par\par There is
another way to design the search algorithm via the local diffusion operator.
For simplicity, we assume that the database has a unique target state in the
following, namely $M=1$. First, we can prepare the initial state
$\ket{s_{m}}\otimes\ket{l}$ with the random bits $l\in\\{0,1\\}^{b}$.
Correspondingly, the target state $\ket{t}$ is partitioned into
$\ket{t}=\ket{t_{2}}\otimes\ket{t_{1}}$. The partial target bit $t_{1}$ is
also called the target block in the quantum partial search algorithm. The
random guess has the success probability $1/2^{b}$ that $l=t_{1}$. If
$l=t_{1}$, applying $G^{j}_{m}$ on $\ket{s_{m}}\otimes\ket{l}$ can find the
rest of target bits $t_{2}$. The total success probability of finding the
target state is
\begin{equation}\frac{\sin^{2}\left((2j+1)\sin^{-1}\left(\sqrt{\frac{1}{2^{m}}}\right)\right)}{2^{b}}.\end{equation}
Since part of the target bits are found by quantum search, part of by random
guess, such implementation is also called the hybrid classical-quantum search
algorithm \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{zhang2021implementation}{\@@citephrase{(}}{\@@citephrase{)}}}.
Not only do we need less number of oracles to achieve the maximal success
probability, but all the global diffusion operators are replaced by the local
diffusion operators. However, the drawback is obvious, namely the factor
$1/2^{b}$ in the success probability. The multi-programming method aims to
improve the success probability by removing $1/2^{b}$ from the success
probability in Eq. (\ref{eq:succ_prob_partial}) by executing the partial
search circuits in parallel. See \ref{subsec:new_algorithm} for details.
\par\par\par\par\@@numbered@section{section}{toc}{Quantum Multi-Programming
for Grover's search} \par In spite of the unprecedented advance in quantum
devices in recent years, NISQ computers are still susceptible to errors. Even
though quantum error correction (QEC) code can be added to reduce the errors,
the QEC code is another burden to NISQ computers. To utilize contemporary
noisy quantum computers more efficiently, the quantum multi-programming (QMP)
is suggested in Ref. \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{das2019case}{\@@citephrase{(}}{\@@citephrase{)}}} and
related studies followed \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{ohkura2022simultaneous, liu2021qucloud, niu2021enabling,
niu2022parallel, niu2022multi}{\@@citephrase{(}}{\@@citephrase{)}}}. The main
motivation of the QMP is that the number of qubits of NISQ computers is much
greater than the quantum volume (QV). QMP fills the gap between relatively
many qubits and relatively low QV of NISQ devices by executing multiple
quantum circuits concurrently, enhancing the throughput and utilization of
NISQ devices. After reviewing several issues in QMP briefly, we describe our
new algorithm in Sec. \ref{subsec:new_algorithm}.
\par\par\par\par\@@numbered@section{subsection}{toc}{Crosstalk between
circuits} \par The effect of crosstalk between qubits is studied in detail by
P. Murali et al in \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{murali2020software}{\@@citephrase{(}}{\@@citephrase{)}}}.
They suggested several rules to mitigate crosstalk between qubits. The
relation between the number of physical buffers and the error rate was studied
by Ohkura et al \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{ohkura2022simultaneous}{\@@citephrase{(}}{\@@citephrase{)}}}.
They introduced a physical buffer, which is the number of idle qubits between
quantum circuits. They tested a different number of controlled-X (CX) gates
with a different number of physical buffers. In the test, they used the
metric, probability of successful trial (PST) introduced in Ref.
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{tannu2019not}{\@@citephrase{(}}{\@@citephrase{)}}} as
follows. \par\begin{equation*}PST=\frac{\textup{Number of successful
trials}}{\textup{Total number of trials}}\end{equation*} \linebreak[1.5]
\par\par Ohkura et al.~{}\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{ohkura2022simultaneous}{\@@citephrase{(}}{\@@citephrase{)}}}
concluded that only $1$ physical buffer is sufficient until $30$ CX gates
because there is no PST decrease compared to a single circuit of CX gates when
physical buffers $1$, $2$, and $3$ are inserted between the CX gates. Also,
their experiments show that the PST does not decrease even though there is no
physical buffer between the quantum circuits when only $10$ CX gates are used.
Therefore, we use one physical buffer for our implementations.
\par\par\par\par\par\par\par\@@numbered@section{subsection}{toc}{Other issues
in QMP} \par One crucial issue of QMP is measurement timing. When quantum
circuits having different circuit depths run concurrently, the measurement
timing influences the shortest circuit. This effect was studied in Ref.
\cite[cite]{\@@bibref{Authors Phrase1YearPhrase2}{das2019case,
ohkura2021crosstalk}{\@@citephrase{(}}{\@@citephrase{)}}}. In these studies,
they suggested delaying shorter circuits to align the measurement timing. In
our case, since the circuits in QMP have the same depth, we do not need to
consider the measurement timing. \par\par Another important issue in QMP is
efficient physical qubit mapping. Systematic qubit mapping algorithms are
developed \cite[cite]{\@@bibref{Authors Phrase1YearPhrase2}{das2019case,
liu2021qucloud, niu2022parallel,
niu2021enabling}{\@@citephrase{(}}{\@@citephrase{)}}}. Even though these qubit
mapping algorithms are also important for ordinary quantum circuits (Not QMP),
efficient qubit mapping is more crucial in QMP because QMP involves more
qubits.
\par\par\par\par\par\par\par\par\@@numbered@section{subsection}{toc}{New
algorithm} \par\par\begin{figure}[t!]
\centering\includegraphics[width=433.62pt]{example_12q.pdf}
\@@toccaption{{\lx@tag[ ]{{1}}{Plots of success probabilities of three
methods. This figure shows the success probabilities of Grover's search
algorithm (GSA), partial Grover's search algorithm without multi-programming
(No QMP) and quantum multi-programming search algorithm (QMP) with respect to
$j$-times repeated Grover's operators in the GSA case or partial diffusion
operators in the No QMP and QMP cases. These plots use one target out of
$12$-qubit search domain ($4096$ items) with $b=1,2$, and $3$. The value of
$b$ represents the number of qubits for preset value in the partial Grover's
search algorithm (No QMP). Therefore, we have $2^{b}$ blocks in the No QMP
case, and $2^{b}$ circuits in the QMP search
algorithm.}}}\@@caption{{\lx@tag[: ]{{Figure 1}}{Plots of success
probabilities of three methods. This figure shows the success probabilities of
Grover's search algorithm (GSA), partial Grover's search algorithm without
multi-programming (No QMP) and quantum multi-programming search algorithm
(QMP) with respect to $j$-times repeated Grover's operators in the GSA case or
partial diffusion operators in the No QMP and QMP cases. These plots use one
target out of $12$-qubit search domain ($4096$ items) with $b=1,2$, and $3$.
The value of $b$ represents the number of qubits for preset value in the
partial Grover's search algorithm (No QMP). Therefore, we have $2^{b}$ blocks
in the No QMP case, and $2^{b}$ circuits in the QMP search algorithm.}}}
\@add@centering\end{figure} \par\par The key idea of our new algorithm is
placing the partial search algorithm in Sec. \ref{subsec:divde_conquery} in
parallel through QMP. Instead of a random choice of one block in the algorithm
in Sec. \ref{subsec:divde_conquery}, we place all the cases on one quantum
computer. When we have $n$-qubit search domain and apply $m$-qubit ($m<n$)
partial search, we have $b(=n-m)$-qubit guesses in the partial search
algorithm. The success probability of finding the target states (solutions) is
\par\begin{equation*}\frac{\sin^{2}\left((2j+1)\sin^{-1}\left(\sqrt{\frac{1}{2^{m}}}\right)\right)}{2^{b}}\end{equation*}
\par\noindent as described in Eq. (\ref{eq:succ_prob_partial}). When we place
$B(=2^{b})$-circuits in the QMP, we have $B$ times better success probability
as follows:
\begin{equation}\sin^{2}\left((2j+1)\sin^{-1}\left(\sqrt{\frac{1}{2^{m}}}\right)\right).\end{equation}
The canonical Grover's algorithm has the success probability as follows:
\begin{equation}\sin^{2}\left((2j+1)\sin^{-1}\left(\sqrt{\frac{1}{N}}\right)\right).\end{equation}
\par\noindent where we have $N=2^{n}$. When we rewrite Eq.
(\ref{eq:QMPGS_succ_prob}) in terms of $B$ and $N$, we have
\begin{equation}\sin^{2}\left((2j+1)\sin^{-1}\left(\sqrt{B}\sqrt{\frac{1}{N}}\right)\right).\end{equation}
Since $\sin^{-1}\left(\sqrt{\frac{1}{N}}\right)$ in Eq.
(\ref{eq:GS_succ_prob}) is the rotation angle of the Grover operator, we have
the rotation angle of our QMP Grover's search algorithm as follows:
\begin{equation}\theta_{MP}=\sin^{-1}\left(\sqrt{B}\sqrt{\frac{1}{N}}\right).\end{equation}
On the other hand, the quantum states of the blocks which do not include the
targets remain amplitude $\sqrt{B/N}$. \par\par\par\par\par\par\par When we
have $0<\sqrt{\frac{1}{N}}<\sqrt{B}\sqrt{\frac{1}{N}}<1$, the arcsine function
is an increasing function. Therefore, we have $\theta_{MP}$ which is greater
than the rotation angle of the canonical Grover's algorithm. The greater
rotation angle increases the efficiency of the search algorithm.
\par\par\par\par Figure \ref{fig:ex_probability} shows the success
probabilities of Grover's search algorithm (GSA), partial Grover's search
algorithm without multi-programming (No QMP), and quantum multi-programming
search algorithm (QMP) with respect to $j$-times repeated Grover's operators
in the GSA case and partial diffusion operators in the No QMP and QMP cases,
respectively. These plots use one target out of $12$-qubit search domain
($4096$ items) with $b=1,2$, and $3$. The value of $b$ represents the number
of qubits for preset value in the partial Grover's search algorithm (No QMP).
Therefore, we have $2^{b}$ blocks in the No QMP case, and $2^{b}$ circuits in
the QMP search algorithm. These plots compare the success probabilities of
three quantum search algorithms in theory. The success probabilities of GSA,
No QMP, and QMP are shown in Eq.
(\ref{eq:succ_prob_GS}),(\ref{eq:succ_prob_partial}), and
(\ref{eq:QMPGS_succ_prob_reform}), respectively. In this specific case, the
GAS has the rotation angle of $\sin^{-1}\left(\frac{1}{\sqrt{2^{12}}}\right)$
($\approx 1.56256\times 10^{-2}$ radian) regardless of $b$. On the other hand,
the QMP and the No QMP have the rotation angle of
$\sin^{-1}\left(\sqrt{2^{b}}\frac{1}{\sqrt{2^{12}}}\right)$. Therefore, the
rotation angles are $\sin^{-1}\left(\frac{1}{\sqrt{2^{11}}}\right)$,
$\sin^{-1}\left(\frac{1}{\sqrt{2^{10}}}\right)$, and
$\sin^{-1}\left(\frac{1}{\sqrt{2^{9}}}\right)$ when we have $b=1,2$, and $3$,
respectively. Hence, the success probabilities of the QMP and the No QMP
increase as the $b$ increases in a fixed $j$. Even though the success
probability of the No QMP is lower than the success probability of the QMP
because it is divided by $2^{b}$, it is still greater than the success
probability of the GSA. The efficiency of the No QMP over the GSA is detailed
in Ref. \cite[cite]{\@@bibref{Authors Phrase1YearPhrase2}{zhang2020depth,
zhang2021implementation}{\@@citephrase{(}}{\@@citephrase{)}}}. Also, these
plots show that the QMP is much more efficient than the No QMP as we have
greater $b$. When we have $b=3$, the QMP needs $14$-times iteration of the
partial Grover's operators to achieve $90\%$ success probability while the GAS
needs $40$-times iteration of the partial Grover's operators to achieve $90\%$
success probability.
\par\par\par\par\par\par\par\par\par\@@numbered@section{subsection}{toc}{Partial
measurement} \par The result of each quantum circuit in QMP is a partial
measurement related to the circuit. The partial measurement for each circuit
is post-processed after measuring all circuits since the partial measurement
probability is the sum of all other uninvolved qubits measurement probability.
A sample code extracting partial measurement sampling out of the whole
measurement sampling is listed in Appendix \ref{app:meas}. A figure-of-merit
regarding measurement in QMP, Trial Reduction Factor (TRF), is introduced in
Ref. \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{das2019case}{\@@citephrase{(}}{\@@citephrase{)}}}. The
criterion describes the ratio of the number of the circuit which executes
individually (baseline) to the number of trials of the QMP circuit. In our
case, the sampling results of each circuit can be extracted from the whole
measurement as described above, the TRF is $B$ (the number of circuits of the
QMP). \par\par\par\par\par\begin{figure}[t]
\centering\begin{lx@subfloat@@figure}\includegraphics[width=212.47617pt]{./D4M4.pdf}\@@toccaption{{\lx@tag[
]{{a}}{Circuit diagram}}}\@@caption{{\lx@tag[ ]{{(a)}}{Circuit
diagram}}}\end{lx@subfloat@@figure} ~{}
\begin{lx@subfloat@@figure}\includegraphics[width=212.47617pt]{./hist_4q_no_qmp_sim.pdf}\@@toccaption{{\lx@tag[
]{{b}}{Sampling histogram}}}\@@caption{{\lx@tag[ ]{{(b)}}{Sampling
histogram}}}\end{lx@subfloat@@figure} \@@toccaption{{\lx@tag[ ]{{2}}{The
canonical Grover's search. This figure shows the quantum circuit diagram of
the canonical Grover's search with target $\ket{1011}$ and its sampling
histogram with $8192$ trials (shots).}}}\@@caption{{\lx@tag[: ]{{Figure
2}}{The canonical Grover's search. This figure shows the quantum circuit
diagram of the canonical Grover's search with target $\ket{1011}$ and its
sampling histogram with $8192$ trials (shots).}}} \@add@centering\end{figure}
\par\par\par\par\par\par\par\@@numbered@section{subsection}{toc}{Example}
\par\par\par\par\par\par\par\begin{figure}[t!]
\centering\includegraphics[width=173.44534pt]{./q4_QMP.pdf}
\@@toccaption{{\lx@tag[ ]{{3}}{Quantum circuit diagram of the QMP. This figure
shows the quantum circuit diagram of the QMP for the circuit in Fig
\ref{fig:qc_4q_no_qmp_sim}.}}}\@@caption{{\lx@tag[: ]{{Figure 3}}{Quantum
circuit diagram of the QMP. This figure shows the quantum circuit diagram of
the QMP for the circuit in Fig \ref{fig:qc_4q_no_qmp_sim}.}}}
\@add@centering\end{figure} \par\par\par\par\par In this section, we explain
our new algorithm with an example. Even though this algorithm works with
multiple search targets (solutions), this example has one target for
simplicity. The multiple targets case is explained in
Sec.~{}\ref{sec:multi_target} in detail. In the bit ordering convention, the
rightmost and the uppermost qubits are the least significant bit (LSB) in the
bra-ket notation and the quantum circuit, respectively. In this example, we
have the target $\ket{1011}$ ($\ket{MSB\leftrightarrow LSB}$). Figure
\ref{fig:qc_4q_no_qmp_sim} shows a diagram for the quantum circuit in Qiskit
of the canonical Grover's search. The Grover's operator is applied once.
Therefore, the success probability of this search is
$\sin^{2}\left(3~{}\sin^{-1}\left(\sqrt{\frac{1}{2^{4}}}\right)\right)\approx
0.472656$. The simulation result of $8192$ trials (shots) is shown in Fig.
\ref{fig:qc_4q_no_qmp_sim}. The target sampling probability is $0.464$ which
is consistent with the theoretical success probability.
\par\par\par\par\par\par\par\begin{figure}[t!]
\centering\begin{lx@subfloat@@figure}\includegraphics[width=212.47617pt]{./hist_4q_qmp_sim_all.pdf}\@@toccaption{{\lx@tag[
]{{a}}{Whole measurement}}}\@@caption{{\lx@tag[ ]{{(a)}}{Whole
measurement}}}\end{lx@subfloat@@figure} ~{}~{}
\begin{lx@subfloat@@figure}\includegraphics[width=212.47617pt]{./hist_4q_qmp_sim_extract_one_figure.pdf}\@@toccaption{{\lx@tag[
]{{b}}{Partial measurement}}}\@@caption{{\lx@tag[ ]{{(b)}}{Partial
measurement}}}\end{lx@subfloat@@figure} \@@toccaption{{\lx@tag[ ]{{4}}{The
sampling histogram of the circuit of Fig. \ref{fig:qc_4q_qmp_sim} with $8192$
trials (shots). Figure (a) shows the result of the whole measurement of the
circuit in Fig. \ref{fig:qc_4q_qmp_sim}. The result of Circuit 1 is the
sampling of measurement of qubit $q_{2}$ and $q_{3}$. This partial measurement
in Fig. (b) is estimated by the algorithm listed in Appendix \ref{app:meas}
based on the sampling result shown in Fig. (a).}}}\@@caption{{\lx@tag[:
]{{Figure 4}}{The sampling histogram of the circuit of Fig.
\ref{fig:qc_4q_qmp_sim} with $8192$ trials (shots). Figure (a) shows the
result of the whole measurement of the circuit in Fig.
\ref{fig:qc_4q_qmp_sim}. The result of Circuit 1 is the sampling of
measurement of qubit $q_{2}$ and $q_{3}$. This partial measurement in Fig. (b)
is estimated by the algorithm listed in Appendix \ref{app:meas} based on the
sampling result shown in Fig. (a).}}} \@add@centering\end{figure}
\par\par\par\par\par\par\par\par\par\par The QMP circuit diagram is shown in
Fig. \ref{fig:qc_4q_qmp_sim}. The diffusion operators are partial diffusion
operators. The QMP circuit is composed of four partial search circuits with
initial guesses of the first and the second qubits. For example, the first
circuit is placed on qubits from $q_{0}$ to $q_{3}$. The first and the second
qubit, $q_{0}$ and $q_{1}$, are initialized by $\ket{00}$. The second circuit
is placed on qubits from $q_{4}$ to $q_{7}$. The first and the second qubit of
the second circuit, $q_{4}$ and $q_{5}$, of the circuit, are initialized by
$\ket{01}$. In each circuit, since the first and the second qubits are
initialized with specific bits and the third and the fourth qubits are
superpositioned with the Hadamard gates, only the third and the fourth qubits
are measured. \par\par\par\par\par From the sampling result of $8192$ trials
(shots) shown in Fig. \ref{fig:hist_4q_no_qmp_sim_partial} (a), we extract the
partial measurement sampling by using the code in Appendix \ref{app:meas}. The
sampling results of each circuit of the QMP are shown in Fig.
\ref{fig:hist_4q_no_qmp_sim_partial} (b). The result of Circuit 1 is the
sampling of measurement of qubit $q_{2}$ and $q_{3}$. The result of Circuit 2
is the sampling of measurement of qubit $q_{5}$ and $q_{6}$. Since the first
and the second qubits from the right (LSB) of the target $\ket{1011}$ are
$\ket{11}$, the fourth circuit includes the target and all other circuits do
not have the target. Therefore, the partial diffusion operators of the first,
the second, and the third circuits do not amplify the amplitude of the initial
quantum states after the Hadamard gates and they have a uniform distribution
of $25\%$ probability as shown in Fig. \ref{fig:hist_4q_no_qmp_sim_partial}.
On the other hand, since the fourth circuit includes the target, the partial
diffusion operator amplifies the quantum states of the target. The success
probability of the fourth circuit is
$\sin^{2}\left(3~{}\sin^{-1}\left(\sqrt{2^{2}}\sqrt{\frac{1}{2^{4}}}\right)\right)=1.0$
which is consistent with the histogram of the circuit $4$ in Fig.
\ref{fig:hist_4q_no_qmp_sim_partial} and Eq.
(\ref{eq:QMPGS_succ_prob_reform}).
\par\par\par\par\par\par\par\par\par\@@numbered@section{subsection}{toc}{Extension
to multiple targets} \par\par\par\par\begin{figure}[t!]
\centering\begin{lx@subfloat@@figure}\includegraphics[width=212.47617pt]{./hist_5q_no_qmp_sim.pdf}\@@toccaption{{\lx@tag[
]{{a}}{The canonical GS}}}\@@caption{{\lx@tag[ ]{{(a)}}{The canonical
GS}}}\end{lx@subfloat@@figure} ~{}~{}
\begin{lx@subfloat@@figure}\includegraphics[width=212.47617pt]{./hist_5q_qmp_sim_extract_one_figure.pdf}\@@toccaption{{\lx@tag[
]{{b}}{The QMP GS}}}\@@caption{{\lx@tag[ ]{{(b)}}{The QMP
GS}}}\end{lx@subfloat@@figure} \@@toccaption{{\lx@tag[ ]{{5}}{The result of
multiple targets. The simulation results of the example of three targets out
of five qubit search domains with $8192$ trials (shots). Figure (a) shows the
result of the canonical Grover's search and Fig. (b) shows the result of the
QMP Grover's search.}}}\@@caption{{\lx@tag[: ]{{Figure 5}}{The result of
multiple targets. The simulation results of the example of three targets out
of five qubit search domains with $8192$ trials (shots). Figure (a) shows the
result of the canonical Grover's search and Fig. (b) shows the result of the
QMP Grover's search.}}} \@add@centering\end{figure} \par\par The quantum
partial search algorithm for multi-target states is studied in detail in Refs.
\cite[cite]{\@@bibref{Authors Phrase1YearPhrase2}{choi2007quantum,
zhang2018quantum}{\@@citephrase{(}}{\@@citephrase{)}}} including the uneven
distributions of the targets over the partial blocks. Based on the study of
the multi-target case of the partial Grover's search, we extend the QMP
Grover's search and the success probability of the QMP Grover's search in Eq.
(\ref{eq:QMPGS_succ_prob_reform}) is extended to multiple target case as
follows:
\begin{equation}\sin^{2}\left((2j+1)\sin^{-1}\left(\sqrt{B}\sqrt{\frac{M_{i}}{N}}\right)\right)\end{equation}
where $M_{i}$ is the number of targets in $i$-th block and the total number of
targets, $M=\displaystyle\sum_{i=1}^{B}M_{i}$. This success probability per
block depends on the number of targets belonging to the block. As with the
single target case, the quantum states of the blocks which do not include the
targets remain amplitude $\sqrt{B/N}$. \par\par We demonstrate the multiple
target case of the QMP Grover's search with three targets, $\ket{10110}$,
$\ket{10001}$, and $\ket{11001}$. Similar to Sec. \ref{sec:example1}, the
search domain is group by four blocks, $\ket{***~{}00}$, $\ket{***~{}01}$,
$\ket{***~{}10}$, and $\ket{***~{}11}$ (number by block $1$, $2$, $3$, and
$4$, respectively), with the same bit ordering convention. Therefore, the
target $\ket{10110}$ belongs to block $3$ the targets $\ket{10001}$ and
$\ket{11001}$ belong to block $2$, respectively. \par\par Figure
\ref{fig:hist_5q_no_qmp_sim} (a) is the sampling histogram of the canonical
Grover's search and Fig. \ref{fig:hist_5q_no_qmp_sim} (b) is the result of our
new algorithm, QMP Grover's search. In those simulations, the Grover operators
are applied once. The success probability of the canonical GS is
$\sin^{2}\left(3~{}\sin^{-1}\left(\sqrt{\frac{3}{2^{5}}}\right)\right)\approx
0.645996$ (refer to Eq. (\ref{eq:succ_prob_GS})) and Fig.
\ref{fig:hist_5q_no_qmp_sim} (a) shows that the sum of the three probabilities
of the three targets is $0.642$. \par\par In the QMP Grover's search as shown
Fig. \ref{fig:hist_5q_no_qmp_sim} (b), the success probabilities depend on the
number of targets in the block. Since the block $3$ (or the circuit $3$)
includes one target, $\ket{10110}$, its success probability is
$\sin^{2}\left(3~{}\sin^{-1}\left(\sqrt{4}\sqrt{\frac{1}{2^{5}}}\right)\right)\approx
0.78125$ (refer to Eq. (\ref{eq:QMPGS_succ_prob_reform})). The block $2$ (or
the circuit $2$) includes two targets, $\ket{10001}$ and $\ket{11001}$.
Therefore, its success probability is
$\sin^{2}\left(3~{}\sin^{-1}\left(\sqrt{4}\sqrt{\frac{2}{2^{5}}}\right)\right)=1.0$.
The histogram of the circuit $2$ shows that the two targets have about $0.5$
probabilities and the probabilities of non-target are zero. Since the circuit
$1$ and $4$ do not include the targets, each quantum state remains in its
initial state $\sqrt{1/8}$ as shown in Fig. \ref{fig:hist_5q_no_qmp_sim} (b).
\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\@@numbered@section{section}{toc}{Empirical
tests} \par This section describes and compares the result of the five-qubit
quantum search problem with one target on several IBM quantum computers. Our
QMP algorithm for Grover's search is compared with the partial Grover's search
algorithm of the $3$-qubit guess and the $2$-qubit guess cases. Before
reviewing the experiment results, we briefly describe the metrics for the
comparison. \par\par\par\par\@@numbered@section{subsection}{toc}{Experimental
metrics} \par We use the following two criteria to compare the different
quantum circuit implementations. The success probability is a criterion for
Grover's search algorithm. We suggest the expected quantum circuit volume to
compare the efficiency of the implementations.
\par\par\par\@@numbered@section{subsubsection}{toc}{Success probability} \par
The success probability depends on the ratio of the number of targets
(solutions) to the size of the search domain and the number of the Grover
operator. The success probabilities for Grover's search, the partial Grover's
search, and our new QMP search algorithm are described in Eq.
(\ref{eq:succ_prob_GS}), (\ref{eq:succ_prob_partial}), and
(\ref{eq:QMPGS_succ_prob_reform}), respectively.
\par\par\par\@@numbered@section{subsubsection}{toc}{Expected quantum circuit
volume} We propose a metric, Quantum Circuit Volume (QCV), for the usage of
quantum computer resources of a quantum circuit as follows:
\par\begin{equation}QCV(O)=nq(O)\times d(O).\end{equation} \noindent where $O$
is a quantum circuit implementation of a quantum algorithm, $nq(O)$ is the
total number of qubits used to implement $O$, and $d(O)$ is the circuit depth
of the implementation $O$. The QCV measures how much quantum computer
resource, qubits (space), and circuit depth (time), are used. \par Also, we
propose a comparison metric, Expected Quantum Circuit Volume (EQCV), as an
extension of the expected depth in Ref. \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{zhang2021implementation,
zhang2022quantum}{\@@citephrase{(}}{\@@citephrase{)}}}. The expected depth is
a normalization of the circuit depth by the success probability. It is the
ratio of the circuit depth to the success probability. It describes the
efficiency of the search algorithm or the implementation. \par\par However,
the expected circuit depth is not appropriate to compare the resource
efficiency between the canonical Grover's search algorithm and its QMP
variation because the QMP uses several times more qubits than the canonical
Grover's search. Hence we define EQCV as follows:
\par\begin{equation}EQCV(O)=\frac{QCV(O)}{\textup{Success Probability
of}~{}O}.\end{equation} \par The circuit depth in the expected depth is
replaced by the QCV in the EQCV. We use the EQCV instead of the expected depth
to compare the efficiency of the algorithms in this section. In this
experiment, our QMP implementation has multiple times QCV than the partial
Grover's search implementation. For example, when two qubits are fixed for
guess in the partial Grover's search, the QMP of it has four circuits. So the
QCV of the QMP is four times greater than the QCV of the partial Grover's
search.
\par\par\par\par\par\par\par\par\par\@@numbered@section{subsection}{toc}{Quantum
circuit implementation} \par\par\par This section describes the quantum
circuit implementation which is used in these experiments. We use the same bit
order convention with the convention in Sec. \ref{sec:example1} and
\ref{sec:multi_target}. In this bit ordering convention, the rightmost and the
uppermost qubits are the least significant bit (LSB) in the bra-ket notation
and the quantum circuit, respectively. \par\par\par\begin{itemize}
\par\itemize@item@D5M5: the original five-qubit Grover's search algorithm with
one iteration of the Grover operator (with a five-qubit diffusion operator).
Here D5 suggests the five-qubit diffusion operator; M5 suggests performing the
five-qubit measurements. It has the quantum circuit diagram \begin{center}
\includegraphics[height=120.00018pt]{D5M5.pdf} \end{center}
\par\par\itemize@item@D5D5M5: the original five-qubit Grover's search
algorithm with two iterations of the Grover operator. It has the quantum
circuit diagram \begin{center}
\includegraphics[height=120.00018pt]{D5D5M5.pdf} \end{center}
\par\par\itemize@item@G2D3M3: randomly guess the values of two qubits (denoted
as G2) then apply the local Grover operator with a three-qubit diffusion
operator and measure the three qubits. It has the quantum circuit diagram
\begin{center} \includegraphics[height=120.00018pt]{G2D3M3.pdf} \end{center}
Here $X$ is the Pauli-$x$ gate and $l_{1},l_{2}\in\\{0,1\\}$ are randomly
chosen. \par\par\itemize@item@G3D2M2: randomly guess the values of three
qubits then apply the local Grover operator with a two-qubit diffusion
operator and measure the two qubits. It has the quantum circuit diagram
\begin{center} \includegraphics[height=120.00018pt]{G3D2M2.pdf} \end{center}
\par\end{itemize} \par An important module of those above implementations is
the five-qubit Toffoli gate (four-qubit-controlled X gate). This five-qubit
Toffoli is used for the five-qubit oracle ($O_{T}$) and five-qubit diffusion
operator ($D_{5}$). For the five-qubit Toffoli gate, we followed the
implementation in Ref. \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{zhang2022quantum}{\@@citephrase{(}}{\@@citephrase{)}}}.
The implementation details and experimental results of partial Grover’s search
are detailed in Refs. \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{zhang2021implementation,
zhang2022quantum}{\@@citephrase{(}}{\@@citephrase{)}}}. In particular, the
5-qubit cases are detailed in Sec. 4.5 and Table 13 in Ref.
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{zhang2021implementation}{\@@citephrase{(}}{\@@citephrase{)}}}.
\par\par\par\par\par\@@numbered@section{subsection}{toc}{Experimental setting}
\par We conducted the experiments of the designed quantum circuits on the two
IBM quantum computers including $\it{IBM\\_Washington}$ ($127$ qubits, $64$
QV) and $\it IBMQ\\_Brooklyn$ ($65$ qubits and $32$ QV). We have the target
$\ket{10110}$ ({MSB} $\leftrightarrow$ {LSB}) as the solution, and the G2D3M3
and G3D2M2 circuits take the initial values of two and three LSB qubits and
measure the rest qubits, respectively. In order to efficiently implement the
five-qubit Toffoli gate, one ancillary qubit is added
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{zhang2022quantum}{\@@citephrase{(}}{\@@citephrase{)}}}.
Thus the number of qubits in a circuit is six. \par To prepare the quantum
circuit for the IBM quantum computers, first, we constructed the whole multi-
programming circuit like the circuit diagram in Fig. \ref{fig:qc_4q_qmp_sim}.
After that, we applied the Qiskit transpiler to the whole QMP circuit with the
optimization level of $3$ for each target IBM quantum computer. To run the
experiments of G2D3M3 and G3D2M2 circuits, $24$ ($6$: qubits in a circuit
$\times$ 4: circuits (number of cases of guess qubit values - 00,01,10,11))
and 48 qubits are used, respectively. The logical qubits are aligned for
consecutive logical qubits to form a circuit in the whole QMP circuit from
index $0$. For example, the first circuit has from qubit $0$ to qubit $5$ and
the second circuit has from qubit $6$ to qubit $11$. We tested two different
QMP circuits for G2D3M3 and G3D2M2. One is represented by ``QMP (default)" and
the another is represented by ``QMP (manual)''. The former used the Qiskit
transpiler without additional options except for the optimization level and
the latter added the initial qubit mapping (``initial\\_layout'' option) in
addition to the optimization level. The initial qubit layout for QMP (manual)
is designed to guarantee at least one (physical) buffer qubit between each
circuit in the QMP circuit as recommended in Sec. \ref{sec:Crosstalk}, and for
logical qubits in a circuit to be allocated physically adjacent as well as
better connectivity, and fewer errors of qubits and connections. In QMP
(manual), we arbitrarily selected the physical qubits to satisfy the above
conditions of QMP (manual). Figure. \ref{fig:G2D3M3_brooklyn_layout},
\ref{fig:G2D3M3_washington_layout}, and \ref{fig:G3D2M2_washington_layout}
show the qubit mapping layouts on $\it IBM\\_Washington$ and $\it
IBMQ\\_Brooklyn$. Also, the figures show the difference between QMP (default)
and QMP (manual). In the G3D2M2 case, QMP (manual) needs $48$ qubits and
additional buffer qubits. Due to the lack of qubit layout mapping space
satisfying the conditions of QMP (manual) in $\it IBMQ\\_Brooklyn$ (Refer to
Fig. \ref{fig:G2D3M3_brooklyn_layout} for $\it IBMQ\\_Brooklyn$ layout),
G3D2M2 was tested only on $\it IBM\\_Washington$. \par\par For the comparison,
we also ran the partial Grover's search without QMP (``No QMP''), which
operated on a single circuit with the solution values for guess qubits while
the QMP circuit includes all circuits for possible bit strings as explained in
Sec. \ref{sec:QMP-GS}. More details with respect to the partial Grover's
search without QMP is discussed in Sec. \ref{subsec:divde_conquery} and Ref.
\cite[cite]{\@@bibref{Authors Phrase1YearPhrase2}{zhang2020depth,
zhang2021implementation,
zhang2022quantum}{\@@citephrase{(}}{\@@citephrase{)}}}. No QMP circuits used
the same initial qubit mapping with QMP (default). That is, they are
transpiled with optimization level $3$ and without the initial qubit mapping
layout (with the ``initial\\_layout=None'' option). The original five-qubit
Grover's search algorithm (GSA) also ran on a single circuit on $\it
IBM\\_Washington$. They were transpiled in the same manner as QMP (manual).
\par\par The experiments were performed with $8192$ trials (shots) and 30
running repetitions, and we used the average value of the $30$ repetitions for
the height of the histograms with the standard deviation error bar in Sec.
\ref{sec:results}.
\par\par\par\par\par\par\par\@@numbered@section{subsection}{toc}{Experiment
results} \par In this section, we discuss the experimental results. The
circuit depth and qubit mapping layout in this discussion are listed in
Appendix \ref{app:no_qmp_orig_grover_layout}.
\par\par\@@numbered@section{subsubsection}{toc}{Success probability}
\par\begin{figure}[t!]
\centering\includegraphics[width=429.28616pt]{./probability.pdf}
\@@toccaption{{\lx@tag[ ]{{6}}{Success probabilities of the experimental
results. Refer to Sec. \ref{sec:implementation} and Sec. \ref{sec:setting} for
each experimental case. The upper dotted red line and the lower dotted red
line are the success probabilities of Honeywell quantum computer (HQC)
($49.0\%$) and IonQ quantum computer ($9.3\%$) from Ref.
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{zhang2022quantum}{\@@citephrase{(}}{\@@citephrase{)}}}.
The experiments were performed with $8192$ trials (shots) and 30 running
repetitions, and we used the average value of the $30$ repetitions for the
height of the histograms with the standard deviation error bar.
}}}\@@caption{{\lx@tag[: ]{{Figure 6}}{Success probabilities of the
experimental results. Refer to Sec. \ref{sec:implementation} and Sec.
\ref{sec:setting} for each experimental case. The upper dotted red line and
the lower dotted red line are the success probabilities of Honeywell quantum
computer (HQC) ($49.0\%$) and IonQ quantum computer ($9.3\%$) from Ref.
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{zhang2022quantum}{\@@citephrase{(}}{\@@citephrase{)}}}.
The experiments were performed with $8192$ trials (shots) and 30 running
repetitions, and we used the average value of the $30$ repetitions for the
height of the histograms with the standard deviation error bar. }}}
\@add@centering\end{figure} \par\par Figure. \ref{fig:test_probability}
demonstrates the success probabilities of the experiments. The success
probabilities for Grover's search (GSA), the partial Grover's search (No QMP),
and our new QMP search algorithm (QMP) are described in Eq.
(\ref{eq:succ_prob_GS}), (\ref{eq:succ_prob_partial}), and
(\ref{eq:QMPGS_succ_prob_reform}), respectively. This histogram shows that the
QMP outperforms the GSA and the No QMP. \par The theoretical success
probabilities of D5M5 and D5D5M5 are $25.8\%$ and $60.2\%$, respectively (Eq.
(\ref{eq:succ_prob_GS})). On the other hand, because of the quantum noise,
their measured success probabilities ($2.3\%$ and $3.1\%$, respectively as
shown in Fig. \ref{fig:test_probability}) of them are much lower than the
theoretical probabilities. The No QMP circuits of G2D3M3 and G3D2M2 have
$19.5\%$ and $12.5\%$ theoretical success probabilities, respectively (Eq.
(\ref{eq:succ_prob_partial})). As shown in Fig. \ref{fig:ex_probability}, the
No QMP circuits have a lower success probability when they have more blocks.
On the other hand, the QMP circuits of G2D3M3 and G3D2M2 have $78.1\%$ and
$100\%$ theoretical success probabilities, respectively (Eq.
(\ref{eq:QMPGS_succ_prob_reform})). This is consistent with Fig.
\ref{fig:ex_probability} that the success probabilities increase when they
have more blocks. As shown in Fig. \ref{fig:ex_probability}, QMP results
outperform the GSA and the No QMP circuits regardless of qubit mapping manners
(default or manual). The main reason for this is that the QMP circuits have
greater theoretical success probabilities than the others as shown in Fig.
\ref{fig:ex_probability} \par In the comparison between G2D3M3 and G3D2M2 on
$\textit{IBM\\_Washington}$, the QMP circuits of G3D2M2 have much greater
success probabilities than G2D3M3 and the former has shorter circuit depths
than the latter as shown in Fig. \ref{fig:test_eqcv}. Therefore, the QMP
circuits show a big increase in success probabilities from G2D3M3 ($12.0\%$
for QMP (default) and $20.1\%$ for QMP (manual)) to G3D2M2 ($41.6\%$ for QMP
(default) and $70.1\%$ for QMP (manual)). \par\par In the comparison between
$\textit{IBM\\_Washington}$ and $\textit{IBMQ\\_Brooklyn}$, the results from
$\textit{IBM\\_Washington}$ show a little bit better results than the results
from $\textit{IBMQ\\_Brooklyn}$ as shown in the middle of Fig.
\ref{fig:test_probability}. We think this is because
$\textit{IBM\\_Washington}$ has a greater quantum volume ($64$) than the
quantum volume ($32$) of $\textit{IBMQ\\_Brooklyn}$. \par In the comparison
between QMP implementations, QMP (manual) outperforms QMP (default) as shown
in Fig. \ref{fig:test_probability}. The manual mapping gets benefits not only
from a buffer qubit to mitigate crosstalk between circuits but also from
shorter circuit depth. As shown in Fig. \ref{fig:G2D3M3_brooklyn_layout},
\ref{fig:G2D3M3_washington_layout}, and \ref{fig:G3D2M2_washington_layout} in
Appendix \ref{app:no_qmp_orig_grover_layout}, QMP (default) circuits have
$1.7\sim 2.3$ times longer circuit depths. QMP (default) does not guarantee
for logical qubits in a circuit to be always allocated adjacent physically due
to variance of the calibration data. For example, the logical qubits (from $0$
to $5$) of the first circuit of the QMP circuit are mapped to separated
physical qubits (nine qubit distance between qubit $3$ and qubit $5$) as shown
in Fig. \ref{fig:G2D3M3_brooklyn_layout} (a). This kind of physical mapping
separation in one circuit is observed in all QMP (default) in Fig.
\ref{fig:G2D3M3_brooklyn_layout} (a), \ref{fig:G2D3M3_washington_layout} (a),
and \ref{fig:G3D2M2_washington_layout} (a). Even worse is the qubit separation
by the qubits of other circuits. In Fig. \ref{fig:G3D2M2_washington_layout}
(a), qubit $0$ is in the middle of qubits $12$ and $14$ which are qubits for
the third circuit. Those qubit separations require a lot of SWAP gates to
connect them. On the other hand, QMP (manual) is designed to avoid those
problems as well as better connectivity, and fewer errors of qubits and
connections. This shows how crucial the initial qubit mapping is on NISQ
computers. For more efficient and systematic qubit mapping, advanced qubit
mapping algorithms \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{das2019case, liu2021qucloud, niu2022parallel,
niu2021enabling}{\@@citephrase{(}}{\@@citephrase{)}}} can be applied to our
QMP algorithm. \par\par These experimental results are also compared with the
results from trapped ion quantum computers such as Honeywell Quantum Computer
(HQC) ($49.0\%$) and IonQ quantum computer ($9.3\%$) (dotted red lines). The
HQC and the IonQ quantum computer results are from $D5D5M5$ of the GSA and
$G3D2M2$ of the No QMP, respectively in Ref. \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{zhang2022quantum}{\@@citephrase{(}}{\@@citephrase{)}}}.
These cases are chosen because they are the highest success probabilities out
of various experimental settings with the same problem (one target out of
$32$) in Ref. \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{zhang2022quantum}{\@@citephrase{(}}{\@@citephrase{)}}}.
The same circuit implementation is used for the HQC and the IonQ quantum
computer cases as described in Sec. \ref{sec:implementation}. Figure
\ref{fig:test_probability} shows how much the QMP improves the success
probability compared to trapped ion quantum computers. The main reason the QMP
of G3D2M2 has a higher success probability than the probability of HQC D5D5M5
is that the former has a greater theoretical success probability than the
latter despite the higher quantum volume $1024$ of the latter. This result
shows a way to redeem the relatively low quantum volume of superconducting
quantum computers by using more qubits.
\par\par\par\par\par\par\@@numbered@section{subsubsection}{toc}{Expected
quantum circuit volume} \par\begin{figure}[t!]
\centering\includegraphics[width=411.93767pt]{./EQCV.pdf}
\@@toccaption{{\lx@tag[ ]{{7}}{EQCV of the experimental results. Refer to Sec.
\ref{sec:implementation} and Sec. \ref{sec:setting} for each experimental
case. The experiments were performed with $8192$ trials (shots) and 30 running
repetitions, and we used the average value of the $30$ repetitions for the
height of the histograms with the standard deviation error
bar.}}}\@@caption{{\lx@tag[: ]{{Figure 7}}{EQCV of the experimental results.
Refer to Sec. \ref{sec:implementation} and Sec. \ref{sec:setting} for each
experimental case. The experiments were performed with $8192$ trials (shots)
and 30 running repetitions, and we used the average value of the $30$
repetitions for the height of the histograms with the standard deviation error
bar.}}} \@add@centering\end{figure} \par\par Figure \ref{fig:test_eqcv} shows
each case's Expected Quantum Circuit Volume (EQCV). EQCV is a criterion to
measure circuit implementation efficiency with respect to the success
probability. The smaller EQCV is the more efficient circuit implementation on
a quantum device. The G3D2M2 circuits have the shortest circuit depths than
the other circuits and the highest success probability even though they have
two times and eight times more qubits than G2D3M3 and the GSA, respectively.
Therefore, the G3D2M2 circuits show the best EQCV. On the other hand, the GSA
circuits have the longest circuit depths and the lowest success probability
even though they have four times and eight times a smaller number of qubits
than G2D3M3 and G3D2M2, respectively. Hence, they show the worst EQCV. The
circuit depth and the qubit mapping layout of each experiment case are listed
in Appendix \ref{app:no_qmp_orig_grover_layout}. In the GAS cases, even though
D5D5M5 has a little bit greater success probability than D5MD, the circuit
depth of the former is much longer than the depth of the latter. So, the EQCV
of D5M5 is smaller than the EQCV of D5D5M5. In the G2D3M3 comparison, each
case has similar circuit depths on both $\textit{IBM\\_Washington}$ and
$\textit{IBMQ\\_Brooklyn}$.
\par\par\par\par\par\par\par\par\@@numbered@section{section}{toc}{Conclusion
and perspective} We propose a QMP Grover search algorithm. This new algorithm
has a bigger rotation angle than the angle of the canonical Grover operator as
shown in Eq. (\ref{eq:QMPGS_angle}). Also, we showed that this new algorithm
is more efficient than the canonical Grover's algorithm on IBM quantum
computers and we expect that this advantage will be applied to other
superconducting quantum computers. In the case of multiple targets, since the
success probability of each block depends on the number of targets, that is,
the distribution of targets, it is possible to apply a different number of
partial Grover operators per block. This accompanies different circuit depths
per block, and this is also allowed in QMP. The different target densities in
blocks (circuits) in the QMP will be studied in our future work. In this
study, even though we adapted a simple qubit mapping method (QMP (manual)),
systematic qubit mapping algorithms are studied in Ref.
\cite[cite]{\@@bibref{Authors Phrase1YearPhrase2}{das2019case, liu2021qucloud,
niu2022parallel, niu2021enabling}{\@@citephrase{(}}{\@@citephrase{)}}}. These
qubit mapping algorithms will be useful to implement more complicated QMP
circuits in a bigger quantum system. Also, recently developed error mitigation
methods, such as crosstalk mitigation \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{
ohkura2022simultaneous,murali2020software}{\@@citephrase{(}}{\@@citephrase{)}}},
hardware-aware compiling \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{niu2021enabling}{\@@citephrase{(}}{\@@citephrase{)}}}, and
qubit partitioning \cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{niu2021enabling,
niu2022parallel}{\@@citephrase{(}}{\@@citephrase{)}}}, will be studied and
implemented with our new QMP algorithm for our future work. \par\par Our new
quantum algorithm shows a way to redeem the relatively low quantum volume of
superconducting quantum computers by using more qubits. We utilize the fact
that superconducting quantum computers have much more qubits than quantum
volumes. Also, the limited connectivity of superconducting quantum computers
can be an advantage to applying QMP because it reduces crosstalk between each
circuit in QMP. \par Even though QMP has more advantages in superconducting
quantum computers, it can be applied to trapped ion quantum computers. The
number of circuits running concurrently is limited due to the relatively small
number of qubits. However, this QMP Grover's search will have a shorter
circuit depth than the canonical Grover's search and this will increase the
accuracy of the result. \par From an algorithmic point of view, applying QMP
to a quantum algorithm is not straightforward because it needs a decomposition
of the algorithm. In Grover's search case, we applied partial Grover's search
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{groverTradeoffsQuantumSearch2002}{\@@citephrase{(}}{\@@citephrase{)}}}.
However, if a QMP of a quantum algorithm reduces the circuit depth, then the
QMP algorithm will have many benefits from the shorter circuit depth on NISQ
devices. Therefore, it will be valuable to develop QMP algorithms for quantum
algorithms. \par The number of blocks in the QMP is limited by the number of
qubits of the target quantum processor and the search problem size although
the efficiency of the QMP circuit increases as a more number of blocks are
used as shown in Fig. \ref{fig:ex_probability}. Therefore, the usage of this
algorithm is limited when quantum processors have a small number of qubits
like $\it IBMQ\\_Kolkata$, $\it IBMQ\\_Montreal$, $\it IBMQ\\_Mumbai$.
However, this QMP algorithm will be more useful as the number of qubits of
quantum processes increases to more than one thousand.
\par\par\par\par\par\@@unnumbered@section{section}{}{Acknowledgments} \par\par
We would like to thank the Brookhaven National Laboratory operated IBM-Q Hub.
This research used quantum computing resources of the Oak Ridge Leadership
Computing Facility, which is a DOE Office of Science User Facility supported
under Contract DE-AC05-00OR22725. This research used resources of the National
Energy Research Scientific Computing Center, a DOE Office of Science User
Facility supported by the Office of Science of the U.S. Department of Energy
under Contract No. DE-AC02-05CH11231 using NERSC award DDR-ERCAP0022229. We
acknowledge the access to IonQ and Honeywell Quantum Solution through the
Microsoft Azure Quantum grant No. 35984. The work of Vladimir Korepin was
supported by the U.S. Department of Energy, Office of Science, National
Quantum Information Science Research Centers, Co-design Center for Quantum
Advantage (C2QA) under Contract No. DE-SC0012704.
\par\par\par\@@unnumbered@section{section}{}{Data Availability} \par\par All
codes and the datasets generated during and/or analyzed during the current
study are available in the GitHub repository,
https://github.com/yukwangmin/QMP\\_GS. \par\par\par\par
\par\par\par\par\par\@@numbered@section{appendix}{toc}{Partial Measurement}
\par\par{\@listings{\@@listings@block{1}{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\footnotesize\@lst@startline{\lx@tags{\lx@tag@intags[]{{1}}\lx@tag@intags[autoref]{1}\lx@tag@intags[refnum]{{1}}\lx@tag@intags[typerefnum]{{line
1}}}}{\@listingGroup{ltx_lst_keyword}{\color[rgb]{1,0,1}import}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{numpy}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{as}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{np}}\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{2}}\lx@tag@intags[autoref]{2}\lx@tag@intags[refnum]{{2}}\lx@tag@intags[typerefnum]{{line
2}}}}\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{3}}\lx@tag@intags[autoref]{3}\lx@tag@intags[refnum]{{3}}\lx@tag@intags[typerefnum]{{line
3}}}}{\@listingGroup{ltx_lst_comment}{\color[rgb]{0,0.6,0}\\#{\@listingGroup{ltx_lst_space}{
}}count{\@listingGroup{ltx_lst_space}{ }}:{\@listingGroup{ltx_lst_space}{
}}return{\@listingGroup{ltx_lst_space}{ }}of{\@listingGroup{ltx_lst_space}{
}}result.get\textunderscore
counts()}}\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{4}}\lx@tag@intags[autoref]{4}\lx@tag@intags[refnum]{{4}}\lx@tag@intags[typerefnum]{{line
4}}}}{\@listingGroup{ltx_lst_comment}{\color[rgb]{0,0.6,0}\\#{\@listingGroup{ltx_lst_space}{
}}N{\@listingGroup{ltx_lst_space}{ }}:{\@listingGroup{ltx_lst_space}{
}}The{\@listingGroup{ltx_lst_space}{ }}total{\@listingGroup{ltx_lst_space}{
}}number{\@listingGroup{ltx_lst_space}{ }}of{\@listingGroup{ltx_lst_space}{
}}bits{\@listingGroup{ltx_lst_space}{ }}of{\@listingGroup{ltx_lst_space}{
}}the{\@listingGroup{ltx_lst_space}{ }}whole{\@listingGroup{ltx_lst_space}{
}}measurement}}\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{5}}\lx@tag@intags[autoref]{5}\lx@tag@intags[refnum]{{5}}\lx@tag@intags[typerefnum]{{line
5}}}}{\@listingGroup{ltx_lst_comment}{\color[rgb]{0,0.6,0}\\#{\@listingGroup{ltx_lst_space}{
}}least{\@listingGroup{ltx_lst_space}{ }}:{\@listingGroup{ltx_lst_space}{
}}The{\@listingGroup{ltx_lst_space}{ }}least{\@listingGroup{ltx_lst_space}{
}}significant{\@listingGroup{ltx_lst_space}{
}}bit{\@listingGroup{ltx_lst_space}{ }}index{\@listingGroup{ltx_lst_space}{
}}of{\@listingGroup{ltx_lst_space}{ }}the{\@listingGroup{ltx_lst_space}{
}}partial{\@listingGroup{ltx_lst_space}{
}}measurement}}\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{6}}\lx@tag@intags[autoref]{6}\lx@tag@intags[refnum]{{6}}\lx@tag@intags[typerefnum]{{line
6}}}}{\@listingGroup{ltx_lst_comment}{\color[rgb]{0,0.6,0}\\#{\@listingGroup{ltx_lst_space}{
}}n{\@listingGroup{ltx_lst_space}{ }}:{\@listingGroup{ltx_lst_space}{
}}The{\@listingGroup{ltx_lst_space}{ }}number{\@listingGroup{ltx_lst_space}{
}}of{\@listingGroup{ltx_lst_space}{ }}bits{\@listingGroup{ltx_lst_space}{
}}for{\@listingGroup{ltx_lst_space}{ }}partial{\@listingGroup{ltx_lst_space}{
}}measurement}}\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{7}}\lx@tag@intags[autoref]{7}\lx@tag@intags[refnum]{{7}}\lx@tag@intags[typerefnum]{{line
7}}}}{\@listingGroup{ltx_lst_keyword}{\color[rgb]{1,0,1}def}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{partitionMeasurement}}({\@listingGroup{ltx_lst_identifier}{count}},{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{N}},{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{least}},{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{n}}):\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{8}}\lx@tag@intags[autoref]{8}\lx@tag@intags[refnum]{{8}}\lx@tag@intags[typerefnum]{{line
8}}}}\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{9}}\lx@tag@intags[autoref]{9}\lx@tag@intags[refnum]{{9}}\lx@tag@intags[typerefnum]{{line
9}}}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{cnt}}{\@listingGroup{ltx_lst_space}{
}}={\@listingGroup{ltx_lst_space}{
}}\textbraceleft\textbraceright\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{10}}\lx@tag@intags[autoref]{10}\lx@tag@intags[refnum]{{10}}\lx@tag@intags[typerefnum]{{line
10}}}}\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{11}}\lx@tag@intags[autoref]{11}\lx@tag@intags[refnum]{{11}}\lx@tag@intags[typerefnum]{{line
11}}}}\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{12}}\lx@tag@intags[autoref]{12}\lx@tag@intags[refnum]{{12}}\lx@tag@intags[typerefnum]{{line
12}}}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_keyword}{\color[rgb]{1,0,1}for}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{i}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_keyword}{\color[rgb]{1,0,1}in}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_keyword
ltx_lst_keywords2}{\color[rgb]{1,0,1}range}}(2\textasteriskcentered\textasteriskcentered{\@listingGroup{ltx_lst_identifier}{n}}):\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{13}}\lx@tag@intags[autoref]{13}\lx@tag@intags[refnum]{{13}}\lx@tag@intags[typerefnum]{{line
13}}}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{key}}{\@listingGroup{ltx_lst_space}{
}}={\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{f}}{\@listingGroup{ltx_lst_string}{\color[rgb]{0.58,0,0.82}\textquoteright\textbraceleft\textbraceleft
0:0\textgreater\textbraceleft n\textbraceright
b\textbraceright\textbraceright\textquoteright}}.{\@listingGroup{ltx_lst_keyword
ltx_lst_keywords2}{\color[rgb]{1,0,1}format}}({\@listingGroup{ltx_lst_identifier}{i}})\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{14}}\lx@tag@intags[autoref]{14}\lx@tag@intags[refnum]{{14}}\lx@tag@intags[typerefnum]{{line
14}}}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{cnt}}[{\@listingGroup{ltx_lst_identifier}{key}}]{\@listingGroup{ltx_lst_space}{
}}={\@listingGroup{ltx_lst_space}{
}}0\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{15}}\lx@tag@intags[autoref]{15}\lx@tag@intags[refnum]{{15}}\lx@tag@intags[typerefnum]{{line
15}}}}\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{16}}\lx@tag@intags[autoref]{16}\lx@tag@intags[refnum]{{16}}\lx@tag@intags[typerefnum]{{line
16}}}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_keyword}{\color[rgb]{1,0,1}for}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{j}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_keyword}{\color[rgb]{1,0,1}in}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_keyword
ltx_lst_keywords2}{\color[rgb]{1,0,1}range}}(2\textasteriskcentered\textasteriskcentered{\@listingGroup{ltx_lst_identifier}{n}}):\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{17}}\lx@tag@intags[autoref]{17}\lx@tag@intags[refnum]{{17}}\lx@tag@intags[typerefnum]{{line
17}}}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{key}}{\@listingGroup{ltx_lst_space}{
}}={\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{f}}{\@listingGroup{ltx_lst_string}{\color[rgb]{0.58,0,0.82}\textquoteright\textbraceleft\textbraceleft
0:0\textgreater\textbraceleft n\textbraceright
b\textbraceright\textbraceright\textquoteright}}.{\@listingGroup{ltx_lst_keyword
ltx_lst_keywords2}{\color[rgb]{1,0,1}format}}({\@listingGroup{ltx_lst_identifier}{j}})\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{18}}\lx@tag@intags[autoref]{18}\lx@tag@intags[refnum]{{18}}\lx@tag@intags[typerefnum]{{line
18}}}}\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{19}}\lx@tag@intags[autoref]{19}\lx@tag@intags[refnum]{{19}}\lx@tag@intags[typerefnum]{{line
19}}}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_keyword}{\color[rgb]{1,0,1}for}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{i}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_keyword}{\color[rgb]{1,0,1}in}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_keyword
ltx_lst_keywords2}{\color[rgb]{1,0,1}range}}(2\textasteriskcentered\textasteriskcentered({\@listingGroup{ltx_lst_identifier}{N}}-{\@listingGroup{ltx_lst_identifier}{n}})):\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{20}}\lx@tag@intags[autoref]{20}\lx@tag@intags[refnum]{{20}}\lx@tag@intags[typerefnum]{{line
20}}}}{\@listingGroup{ltx_lst_space}{ }}{\@listingGroup{ltx_lst_keyword
ltx_lst_keywords2}{\color[rgb]{1,0,1}bin}}{\@listingGroup{ltx_lst_space}{
}}={\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{f}}{\@listingGroup{ltx_lst_string}{\color[rgb]{0.58,0,0.82}\textquoteright\textbraceleft\textbraceleft
0:0\textgreater\textbraceleft N-n\textbraceright
b\textbraceright\textbraceright\textquoteright}}.{\@listingGroup{ltx_lst_keyword
ltx_lst_keywords2}{\color[rgb]{1,0,1}format}}({\@listingGroup{ltx_lst_identifier}{i}})\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{21}}\lx@tag@intags[autoref]{21}\lx@tag@intags[refnum]{{21}}\lx@tag@intags[typerefnum]{{line
21}}}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{nkey}}{\@listingGroup{ltx_lst_space}{
}}={\@listingGroup{ltx_lst_space}{ }}{\@listingGroup{ltx_lst_keyword
ltx_lst_keywords2}{\color[rgb]{1,0,1}bin}}[:{\@listingGroup{ltx_lst_identifier}{N}}-{\@listingGroup{ltx_lst_identifier}{n}}-{\@listingGroup{ltx_lst_identifier}{least}}]{\@listingGroup{ltx_lst_space}{
}}+{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{key}}{\@listingGroup{ltx_lst_space}{
}}+{\@listingGroup{ltx_lst_space}{ }}{\@listingGroup{ltx_lst_keyword
ltx_lst_keywords2}{\color[rgb]{1,0,1}bin}}[{\@listingGroup{ltx_lst_identifier}{N}}-{\@listingGroup{ltx_lst_identifier}{n}}-{\@listingGroup{ltx_lst_identifier}{least}}:]\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{22}}\lx@tag@intags[autoref]{22}\lx@tag@intags[refnum]{{22}}\lx@tag@intags[typerefnum]{{line
22}}}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{cnt}}[{\@listingGroup{ltx_lst_identifier}{key}}]{\@listingGroup{ltx_lst_space}{
}}+={\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{count}}.{\@listingGroup{ltx_lst_identifier}{get}}({\@listingGroup{ltx_lst_identifier}{nkey}},{\@listingGroup{ltx_lst_space}{
}}0)\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{23}}\lx@tag@intags[autoref]{23}\lx@tag@intags[refnum]{{23}}\lx@tag@intags[typerefnum]{{line
23}}}}\@lst@endline\@lst@startline{\lx@tags{\lx@tag@intags[]{{24}}\lx@tag@intags[autoref]{24}\lx@tag@intags[refnum]{{24}}\lx@tag@intags[typerefnum]{{line
24}}}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_keyword}{\color[rgb]{1,0,1}return}}{\@listingGroup{ltx_lst_space}{
}}{\@listingGroup{ltx_lst_identifier}{cnt}}\@lst@endline}}{}\@@toccaption{{\lx@tag[
]{{1}}{A sample code for partial measurement extraction from the whole
measurement}}}\@@caption{{\lx@tag[: ]{Listing~1}{A sample code for partial
measurement extraction from the whole measurement}}}}}}
\par\par\par\par\@@numbered@section{appendix}{toc}{Qubit mapping layout and
circuit depth} \par\par\par \par\par\par In this section, the layout of IBM
quantum computers and qubit mappings are visualized. Each sub-figures are
results of qiskit.visualization.plot\\_circuit\\_layout() function calls in
Qiskit and the numbers in the black circles represent the logical qubits of
the QMP circuit before the transpiling. \par\begin{figure}[h]
\centering\begin{lx@subfloat@@figure}\includegraphics[width=173.44534pt]{G2D3M3_brooklyn_automatic_mapping_depth_154.pdf}\@@toccaption{{\lx@tag[
]{{a}}{QMP (default) layout (depth: 154)}}}\@@caption{{\lx@tag[ ]{{(a)}}{QMP
(default) layout (depth: 154)}}}\end{lx@subfloat@@figure}
\qquad\begin{lx@subfloat@@figure}\includegraphics[width=173.44534pt]{G2D3M3_brooklyn_manual_mapping_depth_86.pdf}\@@toccaption{{\lx@tag[
]{{b}}{QMP (manual) layout (depth: 86)}}}\@@caption{{\lx@tag[ ]{{(b)}}{QMP
(manual) layout (depth: 86)}}}\end{lx@subfloat@@figure}~{} \vspace{0.5cm}
\@@toccaption{{\lx@tag[ ]{{B1}}{Circuit mapping layouts for G2D3M3 on
IBMQ\\_Brooklyn.}}}\@@caption{{\lx@tag[: ]{{Figure B1}}{Circuit mapping
layouts for G2D3M3 on IBMQ\\_Brooklyn.}}} \@add@centering\end{figure}
\par\begin{figure}[h]
\centering\begin{lx@subfloat@@figure}\includegraphics[width=195.12767pt,height=151.76964pt]{G2D3M3_washington_automatic_mapping_depth_149.pdf}\@@toccaption{{\lx@tag[
]{{a}}{QMP (default) layout (depth: 149)}}}\@@caption{{\lx@tag[ ]{{(a)}}{QMP
(default) layout (depth: 149)}}}\end{lx@subfloat@@figure}
\qquad\begin{lx@subfloat@@figure}\includegraphics[width=195.12767pt,height=151.76964pt]{G2D3M3_washington_manual_mapping_depth_87.pdf}\@@toccaption{{\lx@tag[
]{{b}}{QMP (manual) layout (depth: 87)}}}\@@caption{{\lx@tag[ ]{{(b)}}{QMP
(manual) layout (depth: 87)}}}\end{lx@subfloat@@figure} \vspace{0.5cm}
\@@toccaption{{\lx@tag[ ]{{B2}}{Circuit mapping layouts for G2D3M3 on
IBM\\_Washington.}}}\@@caption{{\lx@tag[: ]{{Figure B2}}{Circuit mapping
layouts for G2D3M3 on IBM\\_Washington.}}} \@add@centering\end{figure}
\par\par\par\begin{figure}[h]
\centering\begin{lx@subfloat@@figure}\includegraphics[width=195.12767pt]{G3D2M2_washington_automatic_mapping_depth_113.pdf}\@@toccaption{{\lx@tag[
]{{a}}{QMP (default) layout (depth: 113)}}}\@@caption{{\lx@tag[ ]{{(a)}}{QMP
(default) layout (depth: 113)}}}\end{lx@subfloat@@figure}
\qquad\begin{lx@subfloat@@figure}\includegraphics[width=195.12767pt]{G3D2M2_washington_manual_mapping_depth_50.pdf}\@@toccaption{{\lx@tag[
]{{b}}{QMP (manual) layout (depth: 50)}}}\@@caption{{\lx@tag[ ]{{(b)}}{QMP
(manual) layout (depth: 50)}}}\end{lx@subfloat@@figure} \vspace{0.5cm}
\@@toccaption{{\lx@tag[ ]{{B3}}{Circuit mapping layouts for G3D2M2 on
IBM\\_Washington.}}}\@@caption{{\lx@tag[: ]{{Figure B3}}{Circuit mapping
layouts for G3D2M2 on IBM\\_Washington.}}} \@add@centering\end{figure}
\par\par\par\lx@pp@appendix@end
\par\par\par\par\par\par\par\par\par\par\par\par\LTX@newpage\par\par\par\par\par\par\par\par\thebibliography\bibcommenthead\@@lbibitem{IBM_127q}\NAT@@wrout{1}{}{}{}{(1)}{IBM_127q}\lx@bibnewblock
Yirka, B.: {IBM} announces development of 127-qubit quantum processor (2021).
\url{https://phys.org/news/2021-11-ibm-qubit-quantum-processor.html}
\par\@@lbibitem{Preskill2018quantumcomputingin}\NAT@@wrout{2}{}{}{}{(2)}{Preskill2018quantumcomputingin}\lx@bibnewblock
Preskill, J.: Quantum {C}omputing in the {NISQ} era and beyond. {Quantum} {2},
79 (2018). \url{https://doi.org/10.22331/q-2018-08-06-79}
\par\@@lbibitem{moll2018quantum}\NAT@@wrout{3}{}{}{}{(3)}{moll2018quantum}\lx@bibnewblock
Moll, N., Barkoutsos, P., Bishop, L.S., Chow, J.M., Cross, A., Egger, D.J.,
Filipp, S., Fuhrer, A., Gambetta, J.M., Ganzhorn, M., {et al.}: Quantum
optimization using variational algorithms on near-term quantum devices.
Quantum Science and Technology {3}(3), 030503 (2018)
\par\@@lbibitem{cross2019validating}\NAT@@wrout{4}{}{}{}{(4)}{cross2019validating}\lx@bibnewblock
Cross, A.W., Bishop, L.S., Sheldon, S., Nation, P.D., Gambetta, J.M.:
Validating quantum computers using randomized model circuits. Physical Review
A {100}(3), 032328 (2019)
\par\@@lbibitem{shor1994algorithms}\NAT@@wrout{5}{}{}{}{(5)}{shor1994algorithms}\lx@bibnewblock
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and
factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer
Science, pp. 124--134 (1994). Ieee
\par\@@lbibitem{lloyd1996universal}\NAT@@wrout{6}{}{}{}{(6)}{lloyd1996universal}\lx@bibnewblock
Lloyd, S.: Universal quantum simulators. Science {273}(5278), 1073--1078
(1996)
\par\@@lbibitem{groverQuantumMechanicsHelps1997}\NAT@@wrout{7}{}{}{}{(7)}{groverQuantumMechanicsHelps1997}\lx@bibnewblock
Grover, L.K.: Quantum {{Mechanics Helps}} in {{Searching}} for a {{Needle}} in
a {{Haystack}}. Physical Review Letters {79}(2), 325--328 (1997).
\url{https://doi.org/10.1103/PhysRevLett.79.325}
\par\@@lbibitem{harrow2009quantum}\NAT@@wrout{8}{}{}{}{(8)}{harrow2009quantum}\lx@bibnewblock
Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of
equations. Physical review letters {103}(15), 150502 (2009)
\par\@@lbibitem{farhi2014quantum}\NAT@@wrout{9}{}{}{}{(9)}{farhi2014quantum}\lx@bibnewblock
Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization
algorithm. arXiv preprint arXiv:1411.4028 (2014)
\par\@@lbibitem{peruzzo2014variational}\NAT@@wrout{10}{}{}{}{(10)}{peruzzo2014variational}\lx@bibnewblock
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P.J.,
Aspuru-Guzik, A., O’brien, J.L.: A variational eigenvalue solver on a photonic
quantum processor. Nature communications {5}(1), 1--7 (2014)
\par\@@lbibitem{farhi2018classification}\NAT@@wrout{11}{}{}{}{(11)}{farhi2018classification}\lx@bibnewblock
Farhi, E., Neven, H.: Classification with quantum neural networks on near term
processors. arXiv preprint arXiv:1802.06002 (2018)
\par\@@lbibitem{altaisky2001quantum}\NAT@@wrout{12}{}{}{}{(12)}{altaisky2001quantum}\lx@bibnewblock
Altaisky, M.: Quantum neural network. arXiv preprint quant-ph/0107012 (2001)
\par\@@lbibitem{beer2020training}\NAT@@wrout{13}{}{}{}{(13)}{beer2020training}\lx@bibnewblock
Beer, K., Bondarenko, D., Farrelly, T., Osborne, T.J., Salzmann, R.,
Scheiermann, D., Wolf, R.: Training deep quantum neural networks. Nature
communications {11}(1), 1--6 (2020)
\par\@@lbibitem{cong2019quantum}\NAT@@wrout{14}{}{}{}{(14)}{cong2019quantum}\lx@bibnewblock
Cong, I., Choi, S., Lukin, M.D.: Quantum convolutional neural networks. Nature
Physics {15}(12), 1273--1278 (2019)
\par\@@lbibitem{aaronson2020quantum}\NAT@@wrout{15}{}{}{}{(15)}{aaronson2020quantum}\lx@bibnewblock
Aaronson, S., Rall, P.: Quantum approximate counting, simplified. Symposium on
Simplicity in Algorithms, 24--32 (2020).
\url{https://doi.org/10.1137/1.9781611976014.5}. SIAM
\par\@@lbibitem{suzuki2020amplitude}\NAT@@wrout{16}{}{}{}{(16)}{suzuki2020amplitude}\lx@bibnewblock
Suzuki, Y., Uno, S., Raymond, R., Tanaka, T., Onodera, T., Yamamoto, N.:
Amplitude estimation without phase estimation. Quantum Information Processing
{19}(2), 75 (2020)
\par\@@lbibitem{yu2020practical}\NAT@@wrout{17}{}{}{}{(17)}{yu2020practical}\lx@bibnewblock
Yu, K., Lim, H., Rao, P.: Practical numerical integration on {NISQ} devices.
In: Quantum Information Science, Sensing, and Computation XII, vol. 11391, p.
1139106 (2020). SPIE
\par\@@lbibitem{grinko2021iterative}\NAT@@wrout{18}{}{}{}{(18)}{grinko2021iterative}\lx@bibnewblock
Grinko, D., Gacon, J., Zoufal, C., Woerner, S.: Iterative quantum amplitude
estimation. npj Quantum Information {7}(1), 1--6 (2021)
\par\@@lbibitem{rao2020quantum}\NAT@@wrout{19}{}{}{}{(19)}{rao2020quantum}\lx@bibnewblock
Rao, P., Yu, K., Lim, H., Jin, D., Choi, D.: Quantum amplitude estimation
algorithms on {IBM} quantum devices. In: Quantum Communications and Quantum
Imaging XVIII, vol. 11507, pp. 49--60 (2020). SPIE
\par\@@lbibitem{zhang2020depth}\NAT@@wrout{20}{}{}{}{(20)}{zhang2020depth}\lx@bibnewblock
Zhang, K., Korepin, V.E.: Depth optimization of quantum search algorithms
beyond {G}rover's algorithm. Physical Review A {101}(3), 032346 (2020)
\par\@@lbibitem{zhang2021implementation}\NAT@@wrout{21}{}{}{}{(21)}{zhang2021implementation}\lx@bibnewblock
Zhang, K., Rao, P., Yu, K., Lim, H., Korepin, V.: Implementation of efficient
quantum search algorithms on {NISQ} computers. Quantum Information Processing
{20}(7), 1--27 (2021)
\par\@@lbibitem{zhang2022quantum}\NAT@@wrout{22}{}{}{}{(22)}{zhang2022quantum}\lx@bibnewblock
Zhang, K., Yu, K., Korepin, V.: Quantum search on noisy intermediate-scale
quantum devices. Europhysics Letters {140}(1), 18002 (2022).
\url{https://doi.org/10.1209/0295-5075/ac90e6}
\par\@@lbibitem{das2019case}\NAT@@wrout{23}{}{}{}{(23)}{das2019case}\lx@bibnewblock
Das, P., Tannu, S.S., Nair, P.J., Qureshi, M.: A case for multi-programming
quantum computers. In: Proceedings of the 52nd Annual IEEE/ACM International
Symposium on Microarchitecture, pp. 291--303 (2019)
\par\@@lbibitem{ohkura2022simultaneous}\NAT@@wrout{24}{}{}{}{(24)}{ohkura2022simultaneous}\lx@bibnewblock
Ohkura, Y., Satoh, T., Van~{}Meter, R.: Simultaneous execution of quantum
circuits on current and near-future {NISQ} systems. IEEE Transactions on
Quantum Engineering (2022)
\par\@@lbibitem{liu2021qucloud}\NAT@@wrout{25}{}{}{}{(25)}{liu2021qucloud}\lx@bibnewblock
Liu, L., Dou, X.: {QuCloud}: A new qubit mapping mechanism for multi-
programming quantum computing in cloud environment. In: 2021 IEEE
International Symposium on High-Performance Computer Architecture (HPCA), pp.
167--178 (2021). IEEE
\par\@@lbibitem{niu2021enabling}\NAT@@wrout{26}{}{}{}{(26)}{niu2021enabling}\lx@bibnewblock
Niu, S., Todri-Sanial, A.: Enabling multi-programming mechanism for quantum
computing in the {NISQ} era. arXiv preprint arXiv:2102.05321 (2021)
\par\@@lbibitem{niu2022parallel}\NAT@@wrout{27}{}{}{}{(27)}{niu2022parallel}\lx@bibnewblock
Niu, S., Todri-Sanial, A.: How parallel circuit execution can be useful for
{NISQ} computing? In: 2022 Design, Automation \& Test in Europe Conference \&
Exhibition (DATE), pp. 1065--1070 (2022). IEEE
\par\@@lbibitem{niu2022multi}\NAT@@wrout{28}{}{}{}{(28)}{niu2022multi}\lx@bibnewblock
Niu, S., Todri-Sanial, A.: Multi-programming cross platform benchmarking for
quantum computing hardware. arXiv preprint arXiv:2206.03144 (2022)
\par\@@lbibitem{resch2021accelerating}\NAT@@wrout{29}{}{}{}{(29)}{resch2021accelerating}\lx@bibnewblock
Resch, S., Gutierrez, A., Huh, J.S., Bharadwaj, S., Eckert, Y., Loh, G.,
Oskin, M., Tannu, S.: Accelerating variational quantum algorithms using
circuit concurrency. arXiv preprint arXiv:2109.01714 (2021)
\par\@@lbibitem{NC10}\NAT@@wrout{30}{}{}{}{(30)}{NC10}\lx@bibnewblock Nielsen,
M.A., Chuang, I.L.: Quantum computation and quantum information. Cambridge
University Press, Cambridge (2010)
\par\@@lbibitem{groverTradeoffsQuantumSearch2002}\NAT@@wrout{31}{}{}{}{(31)}{groverTradeoffsQuantumSearch2002}\lx@bibnewblock
Grover, L.K.: Trade-offs in the quantum search algorithm. Physical Review A
{66}(5), 052314 (2002)
\par\@@lbibitem{GR05}\NAT@@wrout{32}{}{}{}{(32)}{GR05}\lx@bibnewblock Grover,
L.K., Radhakrishnan, J.: Is partial quantum search of a database any easier?
In: Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in
Algorithms and Architectures, pp. 186--194 (2005). ACM
\par\@@lbibitem{KG06}\NAT@@wrout{33}{}{}{}{(33)}{KG06}\lx@bibnewblock Korepin,
V.E., Grover, L.K.: Simple algorithm for partial quantum search. Quantum
Information Processing {5}(1), 5--10 (2006)
\par\@@lbibitem{Korepin05}\NAT@@wrout{34}{}{}{}{(34)}{Korepin05}\lx@bibnewblock
Korepin, V.E.: Optimization of partial search. Journal of Physics A:
Mathematical and General {38}(44), 731 (2005)
\par\@@lbibitem{choi2007quantum}\NAT@@wrout{35}{}{}{}{(35)}{choi2007quantum}\lx@bibnewblock
Choi, B.-S., Korepin, V.E.: Quantum partial search of a database with several
target items. Quantum Information Processing {6}(4), 243--254 (2007)
\par\@@lbibitem{zhang2018quantum}\NAT@@wrout{36}{}{}{}{(36)}{zhang2018quantum}\lx@bibnewblock
Zhang, K., Korepin, V.: Quantum partial search for uneven distribution of
multiple target items. Quantum Information Processing {17}(6), 1--20 (2018)
\par\@@lbibitem{murali2020software}\NAT@@wrout{37}{}{}{}{(37)}{murali2020software}\lx@bibnewblock
Murali, P., McKay, D.C., Martonosi, M., Javadi-Abhari, A.: Software mitigation
of crosstalk on noisy intermediate-scale quantum computers. In: Proceedings of
the Twenty-Fifth International Conference on Architectural Support for
Programming Languages and Operating Systems, pp. 1001--1016 (2020)
\par\@@lbibitem{tannu2019not}\NAT@@wrout{38}{}{}{}{(38)}{tannu2019not}\lx@bibnewblock
Tannu, S.S., Qureshi, M.K.: Not all qubits are created equal: A case for
variability-aware policies for nisq-era quantum computers. In: Proceedings of
the Twenty-Fourth International Conference on Architectural Support for
Programming Languages and Operating Systems, pp. 987--999 (2019)
\par\@@lbibitem{ohkura2021crosstalk}\NAT@@wrout{39}{}{}{}{(39)}{ohkura2021crosstalk}\lx@bibnewblock
Ohkura, Y.: Crosstalk-aware {NISQ} {M}ulti-programming. Faculty Policy
Manage., Keio Univ., Tokyo, Japan (2021) \par\endthebibliography
\par\par\par\par\par\par\par\par\par\par\par\@add@PDF@RDFa@triples\par\end{document}$