#  Quantum Amplitude Amplification Operators

Hyeokjea Kwon  Joonwoo Bae  School of Electrical Engineering, Korea Advanced
Institute of Science and Technology (KAIST), 291 Daehak-ro, Yuseong-gu,
Daejeon 34141, Republic of Korea.

###### Abstract

In this work, we characterize quantum iterations that generally perform
amplitude amplification for a desired state, and show how to construct quantum
database search algorithms such that the probability of finding a target keeps
increasing all the way through. Namely, exact quantum search algorithms with a
quadratic speedup can be generated. These are compared to fixed-point quantum
search algorithms known so far, for which it is shown that some iterations do
not perform amplitude amplification with a quadratic speedup: meanwhile, the
amplitude of a target can decrease. Then, we show that quantum amplitude
amplification can be achieved in a wide range of parameters, meaning that the
process is generically resilient to errors appearing in a practical
realization. Proof-of-principle demonstrations are shown in IBMQ Toronto, IBMQ
Boeblingen, and IonQ.

Recent advances with the noisy intermediate scalable quantum (NISQ)
technologies Preskill (2018) signify the usefulness of iterations of a quantum
circuit that may contain advantages over its classical counterpart Bravyi  _et
al._ (2018). Then, the iterations may be used to devise hybrid quantum-
classical algorithms toward more efficient computation over the existing
classical limitation Farhi  _et al._ ; Peruzzo  _et al._ (2014). For instance,
it is of great importance to find the capabilities of parametric quantum
circuits exploited in variational quantum algorithms, see e.g., Benedetti  _et
al._ (2019); Du  _et al._ (2020); Sim  _et al._ (2019).

This structure is in fact shared in common with Grover’s quantum database
search algorithm or quantum amplitude amplification in general Morales  _et
al._ (2018). Namely, a Grover iteration is a building block that is repeatedly
applied and leads to a quadratic speedup over classical search Grover (1997);
Bennett  _et al._ (1997). We also recall that the optimality proof of the
algorithm is concerned with the capability of single iterations whereby the
speedup is achieved by their cancatenation Zalka (1999); Boyer  _et al._
(1998).

It is worth to note two shortcomings in the Grover iterations, as follows.
They in fact leverage exact and fixed-point algorithms. The first is an error,
though sufficiently small up to $1/2^{n}$ for $n$-qubit states, which always
exist in a measurement readout stage. It has been shown that the errors can be
cleared out by improving the angle parameters in Grover iterations: then,
exact quantum search that finds a target with certainty is achieved Long
(2001); Høyer (2000); Toyama  _et al._ (2013). The second is that when a
target is multiple, the number should be provided in advance. Otherwise, the
algorithm shows oscillations between an initial and a target states Grover
(1997); Bennett  _et al._ (1997). Or, as a prescription, quantum counting is
required, beforehand Brassard  _et al._ (2002). Recently, it is also shown
that quantum counting can be much simpler Aaronson and Rall (2019); Suzuki
_et al._ (2020).

Fixed-point quantum search has been proposed, in which a given initial state
would arbitrarily converge to a target one. Thus, an a priori information
about the number of target items is not necessary. However, the price to pay
is to give up the quantum advantage: the $\pi/3$-algorithm is as fast as its
classical counterpart Grover (2005). Remarkably, it is possible to have a
fixed-point algorithm with a quadratic speedup Yoder  _et al._ (2014). As soon
as exact search is attempted, nonetheless, it is inevitable that a quadratic
speedup is ruled out Yoder  _et al._ (2014). Hence, a non-zero probability of
an error would remain in a measurement readout .

Therefore, so far, the shortcomings are not overcome simultaneously yet. As
long as a quadratic speedup is desired, either one of exact or fixed-point
search only is possible. It is natural to ask to identify a quantum iteration
that generally performs amplitude amplification. The identification may give
the close-up view to find how exact and fixed-point quantum search are
distinct. From a practical point of view, the iterations would be also a
useful building block in the NISQ algorithms, as quantum amplitude
amplification is a key process in various quantum computing applications,
e.g., optimization Baritompa  _et al._ (2005); Yidong Liao and Min-Hsiu Hsieh
and Chris Ferrie (2021), state preparation Soklakov and Schack (2005), high-
energy physics Wei  _et al._ (2020), cryptanalysis Jordan and Liu (2018);
Grassl  _et al._ (2016); Jaques  _et al._ (2020), etc. Moreover, the process
turns out be a naturally occurring phenomenon Roget  _et al._ (2020).

Along the line, one can see that the Grover iteration has two subroutines, an
oracle query and a specified diffusion operations. There is a high chance that
a diffusion step in the Grover iteration may be served by any unitary
transform Grover (1998). This readily means that quantum amplitude
amplification may be characterized in a wide range and also that the process
is robust to noise, i.e., fitted with NISQ technologies. The result is,
however, limited by the assumption that the oracle query operation works in a
noise-free manner.

In this work, we show the characterization of a quantum iteration that
generally performs amplitude amplification with a quadratic speedup. Namely, a
quantum amplitude amplification operator (QAAO) is identified. It is shown
that QAAOs can be constructed in a wide range of parameters: randomly
generated parameters can build a QAAO with a probability almost $1/2$. This
means that in practice QAAOs can be straightforwardly generated, and also that
QAAOs are generically resilient to errors appearing in the preparation of the
parameters, hence, fitted with NISQ technologies. Proof-of-principle
experimental demonstrations are shown in the cloud-based quantum computing
services of IBMQ and IonQ.

With the characterization, we show how to construct a sequence of QAAOs for
exact quantum search, i.e., exact search algorithms with a quadratic speedup.
It is shown that an optimal sequence of QAAOs reproduces the Grover algorithm
equipped with one extra iteration at the end to transform a resulting state to
precisely a target one. It is found that none of the known fixed-quantum
search algorithms is a sequence of QAAOs. Although this does not prevent
fixed-point quantum search from having a quadratic speedup, it is, however,
clear that the fixed-point algorithms cannot optimal. Further relations of
exact and fixed-point search algorithms are discussed.

Figure 1:  (A) The Grover iteration corresponds to consecutive rotations in
the space spanned by a target state $|t\rangle$ and its complement
$|t^{\perp}\rangle$. (B) The probability of finding a target state is plotted
in the case of $8$ qubits. The probability is monotonically increasing. (C)
The path of an evolving state in the sphere is shown by Grover iterations from
an initial to target states.

## Method

Throughout, let us consider $n$-qubit states and write by $N=2^{n}$, and also
suppose a single target for convenience. An initial and target $n$-qubit
states are denoted by $|s_{0}\rangle$ and $|t\rangle$, respectively. The
orthogonal complement to the target state from the initial state can be found
and is denoted by $|t^{\perp}\rangle$. Then, a state defined in the space can
be written as

$\displaystyle|s(\theta,\phi)\rangle=e^{i\phi}\sin(\frac{\theta}{2})|t\rangle+\cos(\frac{\theta}{2})|t^{\perp}\rangle$
(1)

for some $\theta$ and $\phi$. A state in the above can be depicted on a sphere
specified by two angles $\theta$ and $\phi$, see Fig, 1. For convenience, let
us fix an initial state:

$\displaystyle\mathrm{initial~{}state~{}:~{}~{}}|s_{0}\rangle=|s(\theta_{0},\phi_{0}=0)\rangle.$

An initial state may be prepared as a uniform superposition of all states,
i.e., $|s_{0}\rangle=H^{\otimes n}|0\rangle^{\otimes n}$ where $H$ denotes a
Hadamard gate. In this case, we have $\theta_{0}=2\sin^{-1}\sqrt{1/N}$.

In quantum amplitude amplification it is aimed to increase the amplitude of a
target state, or equivalently, the probability of finding a target state. Let
$G$ denote an iteration applied to a state $|s(\theta,\phi)\rangle$. The
probability of finding a target after an iteration may change by

$\displaystyle p_{1}(\mathrm{target})-p_{0}(\mathrm{target})$

where $p_{j}(\mathrm{target})=|\langle t|G^{j}|s(\theta,\phi)\rangle|^{2}$ for
$j=0,1$.

Definition. An iteration $G$ is a quantum amplitude amplification operator
(QAAO) for a state if the probability of finding a target state increases with
a quadratic speedup, i.e.,
$p_{1}(\mathrm{target})-p_{0}(\mathrm{target})=O(N^{-1/2})$, so that a target
state may be found in $O(\sqrt{N})$ applications.

When the probability increases by a single iteration, a resulting state can be
found to be closer to a target one. In the sphere in Fig. 1, the process can
be seen as a rotation and decomposed as follows,

$\displaystyle G(\beta,\gamma)=D(\beta)R(\gamma),~{}\mathrm{where}~{}$
$\displaystyle D(\beta)=e^{-i\beta|s_{0}\rangle\langle
s_{0}|}~{}\mathrm{and}~{}R(\gamma)=e^{-i\gamma|t\rangle\langle t|}$ (2)

for $\beta,\gamma\in[-\pi,\pi]$. Note that a diffusion operation $D(\beta)$ is
constructed with an initial state. In Fig. 2, a circuit for the diffusion step
is shown for an initial state with $\theta_{0}=2\sin^{-1}\sqrt{1/N}$. The
other one $R(\gamma)$ is called oracular operation based on an oracle query,
denoted by a one-way function $f(x)=\delta_{t,x}$ for $x\in\\{0,1\\}^{n}$. The
oracle works as, $U|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle$ for
$x,y\in\\{0,1\\}^{n}$. In Fig. 2, a circuit for the operation $R(\gamma)$ is
shown. Note also that the Grover iteration is reproduced by
$\beta=\gamma=\pi$.

Figure 2:  A circuit of an iteration by a QAAO is shown, where a target and an
initial states are denoted by $|t\rangle=|t_{1}t_{2}\cdots t_{n}\rangle$ and
$|s_{0}\rangle$, respectively. An oracle gate $R(\gamma)$ (green) applies a
controlled-phase gate that realizes the transformation, $|t\rangle\mapsto
e^{-i\gamma}|t\rangle$, for a target state only. A diffusion gate $D(\beta)$
(orange) is constructed with the a priori information about an initial state.
Note that a phase gate is denoted by $P(\alpha)=\mathrm{diag}[1,e^{i\alpha}]$.

One may consider other operations than a diffusion one to define a QAAO. It
has been shown that when $\gamma=\pi$, almost any unitary transformation may
serve a diffusion step Grover (1998). It is actually important to find a QAAO
as a rotation in the space spanned by $\\{|t\rangle,t^{\perp}\rangle\\}$
whenever a sufficiently high probability of a target is desired at the end.
For instance, a transverse field operator which may be feasible in a NISQ
scenario may be replaced with a diffusion operator $D(\beta)$ Jiang  _et al._
(2017). Then, a resulting state may be no longer seen in the state space of
$|t\rangle$ and $|t^{\perp}\rangle$. The consequence is that the probability
of finding a target state would be about $1/2$ at the end. When a partial
diffusion is applied, a similar conclusion can be drawn that the probability
would not be sufficiently high Liu and Zhou (2021). We recall that the quantum
iterations in Eq. (2) have been used to compose the fixed-point quantum search
algorithm with an optimal query complexity shown in Ref. Yoder  _et al._
(2014), where the probability of a target at the end can be made sufficiently
high.

Having identified quantum iterations of interest, we introduce an increment by
an iteration for a state $|s(\theta,\phi)\rangle$ as follows,

$\displaystyle\triangle(\beta,\gamma):=\lvert\langle
t|G(\beta,\gamma)|s(\theta,\phi)\rangle\rvert^{2}-\lvert\langle
t|s(\theta,\phi)\rangle\rvert^{2}.~{}~{}$ (3)

Then, an iteration $G(\beta,\gamma)$ is characterized as a QAAO for the state
if its increment shows a quadratic speedup, i.e.,
$\Delta(\beta,\gamma)=O(N^{-1/2})>0$.

As an instance, for the Grover iteration the increment is given by
$\Delta(\pi,\pi)=2N^{-1/2}$. As the iteration is repeatedly applied, the
probability of finding a target state increases until a resulting state is
around the target one, see Fig. 1 (B). The path of a state evolved by Grover
iterations is shown in Fig. 1 (C), as a rotation from an initial to a target
states in the sphere.

After all, with QAAOs an efficient and exact search algorithm may be
constructed as their sequence such that,

$\displaystyle|t\rangle=G(\beta_{K},\gamma_{K})G(\beta_{K-1},\gamma_{K-1})\cdots
G(\beta_{1},\gamma_{1})|s_{0}\rangle$ (4)

for some $K=O(\sqrt{N})$. That is, exact search algorithms with a quadratic
speedup are thus generated. In what follows, let us present the
characterization of QAAOs.

It is straightforward to compute and simplify the increment as follows,

$\displaystyle\triangle(\beta,\gamma)$ $\displaystyle=$ $\displaystyle
A(\beta)\cos\theta+B(\beta,\gamma)\sin\theta$ (5)

where

$\displaystyle A(\beta)$ $\displaystyle=$
$\displaystyle\sin^{2}\frac{\beta}{2}\sin^{2}\theta_{0},$ $\displaystyle
B(\beta,\gamma)$ $\displaystyle=$
$\displaystyle-C(\beta,\gamma)\sin\frac{\beta}{2}\sin\theta_{0},~{}\mathrm{and}$
$\displaystyle C(\beta,\gamma)$ $\displaystyle=$
$\displaystyle\cos\frac{\beta}{2}\sin\varphi+\sin\frac{\beta}{2}\cos\varphi\cos\theta_{0}$

and $\varphi=\phi-\gamma$. Since $\sin\theta_{0}=O(N^{-1/2})$, we have that
$A(\beta)=O(N^{-1})$ and $B(\beta,\gamma)=O(N^{-1/2})$. Therefore, it is
essential to have $B(\beta,\gamma)>0$ for a quadratic speedup.

Proposition 1. An iteration $G(\beta,\gamma)$ in Eq. (3) is a QAAO for a state
$|s(\theta,\phi)\rangle$ if $B(\beta,\gamma)>cN^{-1/2}$ for some $c>1$. It is
almost probability $1/2$ that randomly chosen parameters
$\beta,\gamma\in[-\pi,\pi]$ define a QAAO.

Since the lower bound $cN^{-1}$ is close to zero when $N$ tends to be large,
we consider the range of the parameters where $B(\beta,\gamma)>0$. Then, it
turns out that $B(\beta,\gamma)>0$ for a half range of
$\beta,\gamma\in[-\pi,\pi]$, see Appendix A. This means that it is feasible to
generate sequences of QAAOs with a high probability and also to realize an
exact search algorithm in Eq. (4). Parameters $(\beta_{i},\gamma_{i})$ can be
systematically obtained as follows.

an initial state $|s_{0}\rangle:=|s(\theta_{0},\phi_{0})\rangle$

parameters $S=\\{(\beta_{i},\gamma_{i})\\}$

procedure $P_{G}$$(|s_{0}\rangle)$

$S\leftarrow\emptyset$

for $i=1$ to $L$ do

do

generate $(\beta_{i},\gamma_{i})$ for a state
$|s(\theta_{i-1},\phi_{i-1})\rangle$

while $B(\beta_{i},\gamma_{i})\leq cN^{-1/2}$

$S\leftarrow S\cup\\{(\beta_{i},\gamma_{i})\\}$

$i\leftarrow i+1$

end for

return $S$

end procedure

Algorithm 1 Parameter Generator ($P_{G}$)

With a set of parameters defining QAAOs at hands, exact quantum search
algorithms can be constructed.

an initial state $|s_{0}\rangle:=|s(\theta_{0},\phi_{0})\rangle$

a target state $|t\rangle$

procedure $Q$$(|s_{0}\rangle)$

$S\leftarrow P_{G}(|s_{0}\rangle)$

return $G(\beta_{L},\gamma_{L})\cdots G(\beta_{1},\gamma_{1})|s_{0}\rangle$

end procedure

Algorithm 2 Exact Quantum Search (Q)  Figure 3:  A sequence of near-optimal
QAAOs with parameters randomly chosen from Eq. (8) is considered in cases of
$8$ qubits. The $y$-axis is the probability of finding a target state and the
$x$-axis the number of oracle queries. Note that the optimal number of the
oracle queries is $18$, and here it is about $25$ with the near-optimal QAAOs.
(A) A sequence of parameters are chosen by allowing an error $\delta=0.05\pi$.
The path on the sphere is not much deviated from the Grover algorithm, see
Fig. (1). (B) An error is allowed up to $\delta=0.2\pi$, and (C) up to
$\delta=0.3\pi$. In all cases, the probability of finding a target keeps
increasing and sufficiently high at the end.

For instance, we have generated QAAOs for $8$-qubit states and applied to
realize amplitude amplification, which are plotted in Figs. 3 and 4 (C). One
can find that the amplitude of a target state keeps increasing all the way
through. The path of an evolving state by QAAOs on the sphere can be compared
to the optimal one by Grover iterations in Fig. 1 (C) where the increment is
stepwise maximal.

Among exact search algorithms, an optimal one can be found as follows. This
shows the Grover iteration.

Proposition 2. A maximal increment by a QAAO for a state
$|s(\theta,\phi)\rangle$ depends on the range of $\theta$. For
$\theta\in[0,\pi-2\theta_{0})$, the optimal parameters are $\beta=\pm\pi$ and
$\gamma=\phi-\pi$. For an initial state $\phi=0$, the condition corresponds to
the Grover iteration. For $\theta\in[\pi-2\theta_{0},\pi]$, the optimal
parameters are given by

$\displaystyle\beta^{*}$ $\displaystyle=$ $\displaystyle\pm
2\arcsin(\cos\frac{\theta}{2}\csc\theta_{0})~{}~{}\mathrm{and}~{}~{}$
$\displaystyle\gamma^{*}$ $\displaystyle=$
$\displaystyle\phi+\pi-\arctan(\cot\frac{\beta^{*}}{2}\sec\theta_{0}).$ (6)

For an initial state prepared in a uniform superposition of all states i.e.,
$\theta_{0}=2\sin^{-1}\sqrt{1/N}$ and $\phi=0$, optimal and exact quantum
search is realized by $K^{*}+1$ optimal QAAOs:

$\displaystyle|t\rangle=G(\beta^{*},\gamma^{*})G^{K^{*}}(\pi,\pi)|s_{0}\rangle$
(7)

where $K^{*}=\lfloor\pi\sqrt{N}/4-1/2\rfloor$.

The proof is shown in Appendix $B$. Proposition $2$ in fact reproduces a proof
of the optimality of the Grover iteration for those states far from a target
one. When a state is closer to a target, i.e., a state
$|s(\theta,\phi)\rangle$ with $\theta\geq\pi-2\theta_{0}$ that may be obtained
after Grover iterations $K^{*}$ times, the Grover iteration is no longer a
QAAO for the state; by the iteration the probability of finding a target state
would decrease. This also explains why the Grover algorithm has to stop right
after $K^{*}$ iterations, at which a measurement therefore reads a target
state with an error $O(N^{-1})$.

For exact and optimal search shown in Eq. (7), an extra iteration
$G(\beta^{*},\gamma^{*})$ is additionally needed. This in fact performs an
exact transformation from the state resulting by the Grover algorithm to a
target one precisely. We also remark that to achieve an exact transformation,
it is essential to exploit an oracle query $e^{-i\gamma|t\rangle\langle t|}$
with $\gamma\neq\pi$, whereas the Grover iteration is with $\gamma=\pi$ all
the time.

Let us now consider a set of parameters which are $\delta$-close to optimal
ones. As QAAOs can be defined in a wide range of parameters from Proposition
$1$, optimal QAAOs may be robust to noise in the preparation of the optimal
parameters. These parameters are generated as $(\beta_{k},\gamma_{k})$ for
$1\leq k\leq K^{*}+1$ by allowing errors up to $\delta$:

$\displaystyle\mathrm{for}~{}~{}k\in[1,K^{*}],~{}\beta_{k},\gamma_{k}\in[\pi-\delta,\pi+\delta]$
$\displaystyle\mathrm{and}~{}~{}|\beta_{K^{*}+1}-\beta^{*}|\leq\delta~{}\mathrm{and}~{}|\gamma_{K^{*}+1}-\gamma^{*}|\leq\delta.$
(8)

For instance, cases with $\delta=0.05\pi,0.2\pi,0.3\pi$ are considered and
those QAAOs are concatenated. In Fig. 3, the probability of finding a target
state is plotted in the cases of $8$ qubits. The sequences achieve a
sufficiently high probability of finding a target state at the end. It is also
shown that QAAOs are generically resilient to errors in the preparation of
optimal parameters.

Figure 4:  Quantum amplitude amplification is performed in cases of $8$
qubits. The $x$-axis is the number of oracle uses, and the $y$-axis the
probability of finding a target state. (A) Fixed-point quantum search with an
optimal query complexity is plotted Yoder  _et al._ (2014). The amplitude of a
target state decreases meanwhile, and the oracle is called $45$ times. (B) The
$\pi/3$-algorithm is plotted Grover (2005). The amplitude increases all the
time till $10^{3}$ oracle calls, without a quantum speedup. (C) QAAOs are
randomly generated and concatenated so that the amplitude keeps increasing
until it reaches to $1$ after the oracle calls $50$ times.

## Comparison

Having identified a quantum iteration for amplitude amplification, we revisit
fixed-point quantum search algorithms. In the $\pi/3$-algorithm, an initial
state converges arbitrarily to a target one by the iterations. Thus, it is not
necessary to know when an algorithm has to stop. However, it takes $O(N)$
times that a target state is found with a sufficiently high probability Grover
(2005). Then, it is clear that some of the iterations are not QAAOs. In Fig.
(4) (B), the probability of finding a target state is plotted and it is shown
that the probability keeps increasing by the iterations, some of which do not
correspond to a QAAO.

It is remarkable that a fixed-point search algorithm with a quadratic speedup
has been presented Yoder  _et al._ (2014). The algorithm is structured as it
is shown in Eq. (2), and starts by fixing a lower bound to the probability of
obtaining a target state at the end. From the bound, a minimal number of
iterations $L=(\sqrt{N})$ are provided as well as the sequence of parameters
$(\beta_{j},\gamma_{j})$ specifically via the Chebyshev polynomials, see
Appendix C for the detail.

Then, a measurement readout after $L^{{}^{\prime}}$ iterations with
$L^{{}^{\prime}}>L$ finds a target state with a probability higher than the
bound fixed in the beginning. Note that, after $L$ iterations, the probability
fluctuates within the bound. However, as soon as exact search is attempted,
i.e., by putting the lower bound to $1$, a quadratic speedup disappears.

In Fig. 4 (A), the probability of finding a target state is plotted for $8$
qubits. It is shown that the probability decreases meanwhile during some of
the iterations, see Appendix C for the details and also Table 1. This
immediately shows that the algorithm is not a sequence of QAAOs. Thus, we have
shown that none of the fixed-point algorithms so far can be realized by QAAOs
only. One may assert that it is necessary to include iterations that are not
QAAOs to compose a fixed-point quantum search algorithm.

No. |  |  $\mathrm{State}$: ($\theta$, $\phi$) |  |  $\mathrm{Iteration}$: ($\beta$, $\gamma$) |  |  | $\triangle(\beta,\gamma)$
---|---|---|---|---|---|---|---
9 |  | (1.9147, 5.1123) |  | (2.8209, 2.895) |  |  | -0.0061
10 |  | (1.9018, 4.4555) |  | (2.4078, 2.6915) |  |  | -0.1007
11 |  | (1.6947, 3.2412) |  | (-1.4255, 1.4255) |  |  | -0.0596
12 |  | (1.5752, 3.2562) |  | (-2.6915, -2.4078) |  |  | -0.0575
Table 1:  Parameters in the fixed-point quantum search algorithm with an
optimal number of oracle queries are shown for cases of $8$ qubits. The
increment $\Delta$ is negative from the $9$th to $12$th iterations. This shows
the algorithm is not a sequence of QAAOs.

## Demonstration

Figure 5:  QAAOs for three-qubit states are demonstrated through cloud-based
quantum computing services in IBMQ Boeblingen, IBMQ Toronto, and IonQ. The
initial state is prepared as a uniform superposition of $8$ states, and the
target state is fixed by $|t\rangle=|110\rangle$. The geometry of qubits in
the devices is also shown, where the three qubits lated by $0$, $1$, and $2$
are allocated. (A) The Grover iteration $G(\pi,\pi)$ is performed. (B) A near-
optimal QAAO $G(2,634,\pi)$ is performed. Both cases show that the amplitude
of the target state is successfully amplified after an iteration. (C) In the
sphere of the target state and its complement, amplitude amplification in the
ideal case corresponds to a rotation by an angle $2\theta_{0}$, see also the
probability of the ideal case in (A). The probability obtained in IonQ (IBMQ
Toronto) in (A) is shown as a state resulting in the orange (green) colored
plane.  Figure 6:  QAAOs for three-qubit states are demonstrated in the IonQ
system. All states $|000\rangle,\cdots,|111\rangle$ are considered as target
ones. For instance, when the preparation shows a state $|abc\rangle$ fixed as
a target one, the detection shows a resulting state
$|a^{{}^{\prime}}b^{{}^{\prime}}c^{{}^{\prime}}\rangle$ for which the
amplitude is the most amplified. In (A), a QAAO $G(3.00,-2.98)$ is performed.
In (B), a QAAO $G(2.90,3.28)$ is implemented. Both show fairly comparable
amounts of amplification of the amplitude of a target state.

We here present proof-of-principle demonstrations of QAAOs in cloud-based
quantum computing services provided by IBMQ and IonQ. The demonstrations are
performed in IBMQ Toronto, IBMQ Boeblingen, and IonQ. The IBMQ hardware
implements superconducting qubits arrayed in a fixed geometry, see Fig. (5).
The IonQ system applies trapped ion qubits, which do not form a fixed
geometry. In both systems, circuits of QAAOs are designed as shown in Fig.
(2), and single iterations of QAAOs are demonstrated.

In Fig. 5, the results with IBMQ performed on Jan. 8 2021 and with IonQ on
Jan. 7 2021 are shown. The target state is fixed by $|110\rangle$. All of the
systems in IBMQ and IonQ show fairly comparable amount of amplification of the
amplitude of the target state. It is difficult to conclude a best performance
among the three. In Fig. 6, more results of the demonstrations with IonQ are
shown. These are performed on Mar. 16 2021. All of the three-qubit product
states are considered as a target state. Two near-optimal QAAOs are performed.
For all target states, it is demonstrated that the amplitude of a target state
is amplified by QAAOs.

The demonstrations in IBMQ and IonQ have shown that three-qubit QAAOs can be
realized in the cloud-based quantum computing services. In all cases, fairly
comparable performance of QAAOs is presented. The robustness of QAAOs to noise
is also demonstrated by showing that errors in the preparation of the
parameters can be tolerated. It may be anticipated that QAAOs can be used to
quantum computing applications in practice.

## Conclusion

In conclusion, we have characterized QAAOs, the quantum iterations that
generally perform amplification of the amplitude of a desired state. Our
results show that QAAOs can be identified in a wide range of parameters in
such a that randomly chosen parameters can construct a QAAO with probability
almost $1/2$. Thus, on the one hand, it is feasible to prepare sequences of
QAAOs. On the other hand, QAAOs are generically resilient to errors appearing
in the preparation of optimal parameters. We have shown that QAAOs can
generate quantum database search algorithms that find a target with a
quadratic speedup and also with certainty.

Proof-of-principle demonstrations of QAAOs for three qubits are presented
through the cloud-based quantum computing services in IBMQ and IonQ. The
results show fairly comparable amounts of amplification of target states. We
envisage that QAAOs may be applied in practical quantum computing
applications. Note that it has been shown that quantum amplitude amplification
plays a key role in quantum computing applications in general.

We remark, as mentioned above, our results generalize exact quantum
algorithms. In fact, all of the exact quantum search algorithms with a
quadratic speedup, known so far, can be reproduced as sequences of QAAOs. It
turns out that the Grover iterations are optimal when an evolving state is not
sufficiently close to a target one. Interestingly, it is shown that none of
the existing fixed-quantum algorithms can be a sequence of QAAOs. The
$\pi/3$-algorithm has no quantum speedup, from which it is clear that some of
the iterations are not QAAOs. The fixed-point quantum search with a quadratic
speedup consists of some iterations by which the probability of a target state
actually decreases. This shows that the fixed-point algorithm is not a series
of QAAOs and also cannot be optimal. Thus, a distinction between exact and
fixed-point algorithms is shown. One may assert that for fixed-point quantum
search it is essential to include iterations that are not QAAOs.

In future investigations, on the practical side, it is interesting to optimize
quantum circuits of QAAOs, e.g. Zhang and Korepin (2020), and to make them
fitted to quantum computing applications in practice, e.g., optimization
Baritompa  _et al._ (2005); Yidong Liao and Min-Hsiu Hsieh and Chris Ferrie
(2021), state preparation Soklakov and Schack (2005), high-energy physics Wei
_et al._ (2020), cryptanalysis Jordan and Liu (2018); Grassl  _et al._ (2016);
Jaques  _et al._ (2020), etc. From a fundamental point of view, it would be
interesting to seek the characterization of quantum iterations for fixed-point
quantum search. It is left open to have a fixed-point quantum search algorithm
that finds a target with certainty and also with a quadratic speedup.

## Acknowledgement

This work was supported by National Research Foundation of Korea
(NRF-2019M3E4A1080001, NRF-2021R1A2C200630911), the ITRC (Information
Technology Research Center) Program (IITP-2021-2018-0-01402) and Samsung
Research Funding $\&$ Incubation Center of Samsung Electronics (Project No.
SRFC-TF2003-01).

## References

  * Preskill 2018 J. Preskill, Quantum 2, 79 (2018).
  * Bravyi  _et al._ 2018 S. Bravyi, D. Gosset, and R. König, Science 362, 308 (2018), https://science.sciencemag.org/content/362/6412/308.full.pdf .
  * 3 E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028 .
  * Peruzzo  _et al._ 2014 A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, Nature Communications 5, 4213 (2014).
  * Benedetti  _et al._ 2019 M. Benedetti, E. Lloyd, S. Sack, and M. Fiorentini, Quantum Science and Technology 4, 043001 (2019).
  * Du  _et al._ 2020 Y. Du, M.-H. Hsieh, T. Liu, and D. Tao, Phys. Rev. Research 2, 033125 (2020).
  * Sim  _et al._ 2019 S. Sim, P. D. Johnson, and A. Aspuru-Guzik, Advanced Quantum Technologies 2, 1900070 (2019), https://onlinelibrary.wiley.com/doi/pdf/10.1002/qute.201900070 .
  * Morales  _et al._ 2018 M. E. S. Morales, T. Tlyachev, and J. Biamonte, Phys. Rev. A 98, 062333 (2018).
  * Grover 1997 L. K. Grover, Phys. Rev. Lett. 79, 325 (1997).
  * Bennett  _et al._ 1997 C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani,  _SIAM Journal on Computing_ , SIAM Journal on Computing 26, 1510 (1997).
  * Zalka 1999 C. Zalka, Phys. Rev. A 60, 2746 (1999).
  * Boyer  _et al._ 1998 M. Boyer, G. Brassard, P. Høyer, and A. Tapp,  _Fortschritte der Physik_ , Fortschritte der Physik 46, 493 (1998).
  * Long 2001 G. L. Long, Phys. Rev. A 64, 022307 (2001).
  * Høyer 2000 P. Høyer, Phys. Rev. A 62, 052304 (2000).
  * Toyama  _et al._ 2013 F. M. Toyama, W. van Dijk, and Y. Nogami, Quantum Information Processing 12, 1897 (2013).
  * Brassard  _et al._ 2002 G. Brassard, P. Hø yer, M. Mosca, and A. Tapp,  _Quantum amplitude amplification and estimation_ , Contemp. Math., Vol. 305 (Amer. Math. Soc., Providence, RI, 2002).
  * Aaronson and Rall 2019 S. Aaronson and P. Rall, “Quantum approximate counting, simplified,” in  _Symposium on Simplicity in Algorithms (SOSA)_ (Society for Industrial and Applied Mathematics, 2019) pp. 24–32.
  * Suzuki  _et al._ 2020 Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto, Quantum Information Processing 19, 75 (2020).
  * Grover 2005 L. K. Grover, Phys. Rev. Lett. 95, 150501 (2005).
  * Yoder  _et al._ 2014 T. J. Yoder, G. H. Low, and I. L. Chuang, Phys. Rev. Lett. 113, 210501 (2014).
  * Baritompa  _et al._ 2005 W. P. Baritompa, D. W. Bulger, and G. R. Wood, SIAM J. on Optimization 15, 1170 (2005).
  * Yidong Liao and Min-Hsiu Hsieh and Chris Ferrie 2021 Yidong Liao and Min-Hsiu Hsieh and Chris Ferrie, arXiv:2103.17047 (2021).
  * Soklakov and Schack 2005 A. N. Soklakov and R. Schack, Optics and Spectroscopy 99, 211 (2005).
  * Wei  _et al._ 2020 A. Y. Wei, P. Naik, A. W. Harrow, and J. Thaler, Phys. Rev. D 101, 094015 (2020).
  * Jordan and Liu 2018 S. P. Jordan and Y. Liu, IEEE Security Privacy 16, 14 (2018).
  * Grassl  _et al._ 2016 M. Grassl, B. Langenberg, M. Roetteler, and R. Steinwandt, in  _Post-Quantum Cryptography_ , edited by T. Takagi (Springer International Publishing, Cham, 2016) pp. 29–43.
  * Jaques  _et al._ 2020 S. Jaques, M. Naehrig, M. Roetteler, and F. Virdia, Advances in Cryptology – EUROCRYPT 202039th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part II 12106, 280 (2020).
  * Roget  _et al._ 2020 M. Roget, S. Guillet, P. Arrighi, and G. Di Molfetta, Phys. Rev. Lett. 124, 180501 (2020).
  * Grover 1998 L. K. Grover, Phys. Rev. Lett. 80, 4329 (1998).
  * Jiang  _et al._ 2017 Z. Jiang, E. G. Rieffel, and Z. Wang, Phys. Rev. A 95, 062317 (2017).
  * Liu and Zhou 2021 J. Liu and H. Zhou, eprint=2103.14196 (2021).
  * Zhang and Korepin 2020 K. Zhang and V. E. Korepin, Phys. Rev. A 101, 032346 (2020).

## Appendix

### Appendix A: QAAOs in Proposition 1

It is clear that the condition that $B(\beta,\gamma)>cN^{-1/2}$ for some $c>1$
holds true a wide range of the parameters $\beta$ and $\gamma$. A simple
argument is that as $N$ tends to be very large, the right hand side quickly
converges to $0$. From Eq. (5), it suffices to find the range of
$\beta,\gamma\in[-\pi,\pi]$ such that it holds

$\displaystyle C(\beta,\gamma)\sin\frac{\beta}{2}<0.$ (9)

After some calculations, it is clear that since the trigonometric functions
are periodic, it is a half in the range of $\beta,\gamma\in[-\pi,\pi]$ where
the condition in Eq. (9) holds true. Note also that $C(\beta,\gamma)=0$
whenever the parameters satisfy,
$\varphi=2\cot^{-1}(-\cot\beta\cos\theta_{0})$. As an instance, the region
with $B(\beta,\gamma)>0$ in the parameter space is depicted for $8$-qubit
states, see Fig. (7).

Figure 7:  The region satisfying the condition $B(\beta,\gamma)>0$, the
grayed, is shown for $8$ qubits. The separation is plotted with the condition
$\varphi=2\cot^{-1}(-\cot\beta\cos\theta_{0})$.

### Appendix B: Proof of Proposition 2

Let us begin with an arbitrary state $|s(\theta,\phi)\rangle$ for
$\theta\in[0,\pi]$ and $\phi\in[0,2\pi]$. Note that the probability of finding
a target from the the state is given by $\sin^{2}\theta/2$, meaning that in
QAAOs it must be that $\theta\in[0,\pi]$. An increment introduced by
$G(\beta,\gamma)$ with $\beta,\gamma\in[-\pi,\pi]$ is denoted by
$\Delta(\beta,\gamma)$. For convenience, let us also introduce a parameter
$\varphi=\phi-\gamma\in(0,2\pi)$.

It is now aimed to find parameters $(\beta,\gamma)$ to define an optimal
iteration $G(\beta,\gamma)$. First of all, one can find an optimal
$\varphi^{*}$ as follows,

$\displaystyle\frac{\partial}{\partial\varphi}\Delta(\beta,\gamma)=0~{}\iff~{}\tan\varphi^{*}=\cot\frac{\beta}{2}\sec\theta_{0}.$
(10)

With the optimal one $\varphi^{*}$ above, one can also check that

$\displaystyle\frac{\partial^{2}}{\partial\varphi^{2}}\Delta(\beta,\gamma)\big{|}_{\varphi^{*}}<0.$

This shows the increment is maximal with the parameter $\varphi^{*}$ in Eq.
(10)

We recall that for a quadratic speedup, it is necessary to have

$\displaystyle B(\beta,\gamma)>0,~{}\mathrm{or~{}equivalently}$ (11)
$\displaystyle\cot\frac{\beta}{2}\sin\varphi+\cos\varphi\cos\theta_{0}<\sin\theta_{0}\cot\theta$
(12)

From Eq. (10), the condition above can be simplified as

$\displaystyle\varphi^{*}\in\Big{(}\frac{\pi}{2},\frac{3\pi}{2}\Big{)},~{}\mathrm{and}$
(13)
$\displaystyle\Big{|}\sin\frac{\beta}{2}\Big{|}\leq\Big{|}\frac{\sin\theta}{\sin\theta_{0}}\Big{|},$
(14)

respectively. From these, an optimal parameter $\gamma^{*}$ is obtained as
follows,

$\displaystyle\gamma^{*}=\phi+\pi-\arctan\Big{(}\cot\frac{\beta}{2}\sec\theta_{0}\Big{)}.$
(15)

Note that an optimal $\gamma^{*}$ can be defined when a state
$|s(\theta,\phi)\rangle$ is identified.

It is now left to find an optimal parameter $\beta^{*}$. Let us introduce
$t\in[0,2\theta_{0}]$ such that

$\displaystyle\sin\frac{t}{2}=\Big{|}\sin\frac{\beta}{2}\Big{|}\sin\theta_{0}.$
(16)

Then, let us rewrite the increment in terms of the optimal parameter
$\gamma^{*}$:

$\displaystyle\triangle(\beta,\gamma^{*})=\sin\Big{(}t+\frac{\theta}{2}\Big{)}\sin
t,$ (17)

which we maximize over $\beta$, see Eq. (16).

Similarly to the method we compute $\gamma^{*}$, one can find an optimal
$t^{*}$ as follows,

$\displaystyle\frac{\partial}{\partial
t}\Delta(\beta,\gamma^{*})=0~{}\iff~{}t^{*}=\pi-\theta.$ (18)

With the optimal one $t^{*}$ above, one can also check that

$\displaystyle\frac{\partial^{2}}{\partial
t^{2}}\Delta(\beta,\gamma^{*})\big{|}_{t^{*}}<0$

which shows the increment is maximal with the parameter $t^{*}$ in Eq. (18).
From Eq. (16) an optimal parameter $\beta^{*}$ can be therefore written as
follows,

$\displaystyle\beta^{*}=\pm
2\arcsin\Big{(}\cos\frac{\theta}{2}\csc\theta_{0}\Big{)}$ (19)

for $\theta\in[\pi-2\theta_{0},\pi]$. For $\theta\in[0,\pi-2\theta_{0}]$, Eq.
(17) can be rewritten as,

$\displaystyle\triangle(\beta,\gamma^{*})=\frac{1}{2}\Big{(}\cos\theta-\cos(\theta+t)\Big{)}.$
(20)

The increment above is non-negative for all $\theta\in[0,\pi-2\theta_{0})$ and
maximized at $t=2\theta_{0}$. From these, an optimal parameter is obtained as
$\beta^{*}=\pm\pi$.

### Appendix C: Fixed-point quantum search with an optimal number of queries

The fixed-point quantum search algorithm with an optimal number of queries 20
works even if the a priori information $\lambda=|\langle
t|s(\theta_{0},\phi_{0})\rangle|$ for an initial state
$|s(\theta_{0},\phi_{0})\rangle$ is not provided, i.e., quantum counting that
verifies $\lambda$ is not needed. One has to fix a lower bound to the
probability of finding the target at the end: let $\delta^{2}$ denote an error
rate in the worst case so that the probability of a target at the end is not
lower than $1-\delta^{2}$. This also tells least number of iterations $K^{*}$
such that for all $K^{{}^{\prime}}\geq K^{*}$ one can have
$P_{K^{{}^{\prime}}}\geq 1-\delta^{2}$.

Given an error bound $\delta^{2}$, the parameters $(\beta_{i},\gamma_{i})$ of
$K^{*}$ iterations are given by Chebyshev polynomials. The $k$-th Chebyshev
polynomial of the first kind is denoted by
$T_{k}(x)=\cos\Big{(}k\cos^{-1}(x)\Big{)}$. Then, the parameters
$(\beta_{i},\gamma_{i})$ are given by

$\displaystyle\beta_{i}=\gamma_{K^{*}-i+1}=2\cot^{-1}\Big{(}\tan(2\pi
i/K^{*})\sqrt{1-\eta^{2}}\Big{)}$ (21)

where $\eta^{-1}=T_{1/K^{*}}(1/\delta)$.

The algorithm for $8$ qubits and a single target item is considered. In Table
2, the parameters $(\beta_{i},\gamma_{i})$ are shown. The error bound is taken
as $\delta=0.316$, from which the sequence of parameters are generated from
Eq. (21) and listed in the table. Then, one has $P_{K^{{}^{\prime}}}\geq 0.9$
for $K^{{}^{\prime}}\geq 20$, see also Fig. 8.

No. |  |  $\mathrm{State}$: ($\theta$, $\phi$) |  |  $\mathrm{Iteration}$: ($\beta$, $\gamma$) |  |  | $\triangle(\beta,\gamma)$ |  | QAAO
---|---|---|---|---|---|---|---|---|---
1 |  | (0.1251, 0) |  | (3.1291, 3.1354) |  |  | 0.0309 |  | O
2 |  | (0.3752, 6.2727) |  | (3.1162, 3.1228) |  |  | 0.0598 |  | O
3 |  | (0.6252, 6.244) |  | (3.102, 3.1093) |  |  | 0.0847 |  | O
4 |  | (0.8746, 6.1934) |  | (3.0857, 3.0941) |  |  | 0.1036 |  | O
5 |  | (1.1218, 6.1143) |  | (3.0659, 3.0763) |  |  | 0.1141 |  | O
6 |  | (1.3633, 5.9948) |  | (3.0401, 3.0539) |  |  | 0.1133 |  | O
7 |  | (1.5914, 5.8145) |  | (3.0033, 3.0235) |  |  | 0.0975 |  | O
8 |  | (1.7881, 5.5385) |  | (2.9433, 2.9775) |  |  | 0.0608 |  | O
9 |  | (1.9147, 5.1123) |  | (2.8209, 2.895) |  |  | -0.0061 |  | X
10 |  | (1.9018, 4.4555) |  | (2.4078, 2.6915) |  |  | -0.1007 |  | X
11 |  | (1.6947, 3.2412) |  | (-1.4255, 1.4255) |  |  | -0.0596 |  | X
12 |  | (1.5752, 3.2562) |  | (-2.6915, -2.4078) |  |  | -0.0575 |  | X
13 |  | (1.46, 4.4549) |  | (-2.895, -2.8209) |  |  | 0.0245 |  | O
14 |  | (1.5091, 5.0453) |  | (-2.9775, -2.9433) |  |  | 0.0719 |  | O
15 |  | (1.653, 5.4069) |  | (-3.0235, -3.0033) |  |  | 0.0946 |  | O
16 |  | (1.8456, 5.6353) |  | (-3.0539, -3.0401) |  |  | 0.1001 |  | O
17 |  | (2.0619, 5.7743) |  | (-3.0763, -3.0659) |  |  | 0.0931 |  | O
18 |  | (2.2888, 5.8423) |  | (-3.0941, -3.0857) |  |  | 0.077 |  | O
19 |  | (2.518, 5.834) |  | (-3.1093, -3.102) |  |  | 0.0541 |  | O
20 |  | (2.7389, 5.6917) |  | (-3.1228, -3.1162) |  |  | 0.0269 |  | O
21 |  | (2.912, 5.1506) |  | (-3.1354, -3.1291) |  |  | -0.0028 |  | X
Table 2: The fixed-point algorithm in 20 is performed for $8$ qubits. An
initial state is prepared as $H^{\otimes 8}|0\rangle^{\otimes 8}$ from which
the initial condition is given by, $\theta_{0}=2\sin^{-1}\sqrt{2^{-8}}\approx
0.1251$ and $\phi_{0}=0$, see Eq. (1). For the state, an iteration with
$(\beta_{1},\gamma_{1})=(3.1291,3.1354)$ is applied and the amplitude
increases by $\triangle=0.0309$. It is shown that for the increment is
negative, i.e., $\Delta<0$, from the $9$th to $12$th iterations.  Figure 8:
The probability of finding a target is plotted in the fixed-point algorithm
showin in 20 for $8$ qubits. The $x$-axis denotes the number of iterations, in
which each iteration exploits an oracle query twice. The iterations for the
$9$th to the $12$th steps are not QAAOs for the states under evolution.
Numerical data are shown in Table 2.