# Quantum exact search with adjustable parameters and its applications

Guanzhong Li and Lvzhou Li
Institute of Quantum Computing and Computer Theory,
School of Computer Science and Engineering,
Sun Yat-sen University, Guangzhou 510006, China Email:
<EMAIL_ADDRESS><EMAIL_ADDRESS>(corresponding author)

###### Abstract

Grover’s algorithm provides a quadratic speedup over classical algorithms to
search for marked elements in an unstructured database. The original algorithm
is probabilistic, returning a marked element with bounded error. When it is
known beforehand there are $M$ marked elements in $N$ elements, there exist
several schemes to achieve the exact version that returns a marked element
with certainty, by using the generalized Grover’s iteration
$G(\alpha,\beta):=S_{r}(\beta)\,S_{o}(\alpha)$, where the phase oracle
$S_{o}(\alpha)$ multiplies a marked state by $e^{i\alpha}$, and the phase
rotation $S_{r}(\beta)$ multiplies the initial state $\ket{\psi_{0}}$ (an
equal-superposition of all states) by $e^{-i\beta}$. However, in all the
existing schemes the value range of $\alpha$ and $\beta$ is limited; for
instance, in the three early schemes $\alpha$ and $\beta$ are determined by
$M/N$.

Thus, a natural question arises: Given the phase oracle $S_{o}(\alpha)$ with
an arbitrary angle $\alpha$, or the phase rotation $S_{r}(\beta)$ with an
arbitrary angle $\beta$, can we always construct an exact search algorithm
without sacrificing the quadratic speedup advantage? The significance of this
problem lies not only in the expansion of mathematical form, but also in its
application value. We answer the question affirmatively, by presenting a
search framework with adjustable parameters. Technically, we propose the
fixed-axis-rotation (FXR) method where each iteration of the search algorithm
can be geometrically seen as rotating about a fixed axis on the Bloch sphere.
Furthermore, two applications of the proposed search framework are developed:
the first is to learn exactly the secret string hidden by the Hamming distance
oracle, and the other to solve the element distinctness promise problem
deterministically. The two applications correspond to the two different cases
where $\alpha$ or $\beta$ is fixed respectively.

##  1 Introduction

###  1.1 Background

Grover’s algorithm [1] is one of the most fundamental algorithms in quantum
computing, as it provides a quadratic speedup for the unstructured search
problem. In this problem, the user is allowed to query an oracle, which
outputs information about whether an element is marked, after receiving the
element index. In quantum computing, one may input superposition of different
indexes to the oracle, and it will also output a superposition of answers.
Grover’s algorithm cleverly makes use of this characteristic and achieves
quadratic speedup compared to classical query-based search algorithms. It also
works in the very general context, because the oracle is regarded as a black
box so that there need not be any promise on the structure of the database.
This black box feature makes it easy to generalize Grover’s algorithm to
quantum amplitude amplification [2], which has become an important subroutine
in designing many other quantum algorithms.

Due to its great importance, research even just on Grover’s algorithm itself
has never stopped ever since it was proposed. One question is whether Grover’s
algorithm can be made exact, as the original Grover’s algorithm can only
output a marked element with a high probability, but not with certainty. To
this end, three methods [2, 3, 4] were proposed, which are based on different
ideas but all, for the first step, change the two phase flip operations in the
original Grover’s algorithm to the following general operations:

$S_{o}(\alpha)=e^{i\alpha\,\Pi_{\mathcal{M}}},$ (1)
$S_{r}(\beta)=e^{-i\beta\,\ket{\psi_{0}}\bra{\psi_{0}}}.$ (2)

$S_{o}(\alpha)$ rotates the phase of the marked states by $e^{i\alpha}$, where
$\Pi_{\mathcal{M}}$ represents orthogonal projector onto the subspace spanned
by marked states. $S_{r}(\beta)$ rotates the phase of the initial state
$\ket{\psi_{0}}$ (an equal-superposition of all indexes) by $e^{-i\beta}$.
Note that when $\alpha=\beta=\pi$, the generalized Grover’s operation

$G(\alpha,\beta):=S_{r}(\beta)\,S_{o}(\alpha)$ (3)

recovers to the original Grover’s iteration. A quantum circuit which realizes
the generalized Grover’s operation $G(\alpha,\beta)$ using twice the standard
oracle $O_{f}$ is shown in Fig. 1.

Figure 1:  A quantum circuit to realize the generalized Grover’s operation
$G(\alpha,\beta)=S_{r}(\beta)\,S_{o}(\alpha)$. The first $n$ horizontal lines
represents working qubits storing $N=2^{n}$ element indexes, and the last line
represents an ancillary qubit initially set to $\ket{0}$. The standard oracle
$O_{f}$ maps $\ket{x}\ket{b}$ to $\ket{x}\ket{b\oplus f(x)}$, where $\oplus$
is the XOR operation, and the Boolean function $f(x)=1$ iff $x$ represents a
marked element index. The vertical line with circles is the multiple
controlled-NOT gate which flips the ancillary qubit whenever the first $n$
qubits are all $\ket{0}$. Correctness of the circuit implementing
$S_{o}(\alpha)$ can be easily verified by considering basis state $\ket{x}$
when $f(x)=0$ or $1$ separately. Note that $S_{r}(\beta)$ is equal to
$H^{\otimes n}(I-(1-e^{-i\beta})\ket{0}^{\otimes n}\bra{0}^{\otimes
n})H^{\otimes n}$.

The three methods [2, 3, 4] then choose appropriate parameters
$\alpha,\beta,k$ based on different ideas (which we summarize them as ‘big-
small step’, ‘conjugate rotation’, and ‘3D rotation’), so that after $k$
iterations of $G(\alpha,\beta)$ to the initial state $\ket{\psi_{0}}$, an
equal superposition of marked states is produced, and measurement in the
computational basis will lead to a marked state with certainty. A summary of
them is presented in Table 1.

method | procedure | $k$
---|---|---
big-small step [2] | $G(\alpha_{1},-\beta_{1})G^{k}(\pi,\pi)\ket{\psi_{0}}$ | $\lfloor k_{\mathrm{opt}}\rfloor$
conjugate rotation [3] | $G^{k}(\alpha_{2},-\beta_{2})S_{o}(u)\ket{\psi_{0}}$ | $\lceil k_{\mathrm{opt}}\rceil$
3D rotation [4] | $G^{k}(\alpha_{3},-\alpha_{3})\ket{\psi_{0}}$ | $\lceil k_{\mathrm{opt}}\rceil$
Table 1: Three methods to achieve exact Grover search. Parameter
$k_{\mathrm{opt}}=\pi/2\theta-1/2$, where $\theta=2\arcsin\sqrt{\lambda}$, and
$\lambda=M/N$ is the proportion of marked elements. Parameters
$(\alpha_{1},\beta_{1})$ satisfy (are solution to) the complex valued equation
“$(-\cos\theta+i\cot\frac{\alpha_{1}}{2})\cot(2k+1)\frac{\theta}{2}=e^{i\beta_{1}}\sin\theta$”.
Parameters $(\alpha_{2},\beta_{2})$ satisfy the equations
“$\sin\frac{\alpha_{2}}{2}\sin\theta=\sin\frac{\pi-\theta}{2k}$” and
“$\tan\frac{\beta_{2}}{2}=\tan\frac{\alpha_{2}}{2}\cos\theta$”. Parameter
$u=\frac{\pi-\beta_{2}}{2}$. Parameter $\alpha_{3}$ satisfies the equation
“$\sin\frac{\pi}{4k+2}=\sin\frac{\alpha_{3}}{2}\sin\frac{\theta}{2}$”.

Compared to the original Grover’s algorithm, the three methods produce a
marked state with certainty while maintaining the quadratic speedup (note that
$k_{\text{opt}}\approx\frac{\pi}{4}\sqrt{\frac{M}{N}}$ ), but they require
knowledge of the ratio $\lambda=M/N$. In fact, the ratio $\lambda$ is
necessary to design quantum exact search algorithm, as it has been proved in
Ref. [5] that any quantum algorithm for exact search without knowing the
number $M$ of marked elements requires $N$ queries (by reducing the
computation of Boolean function $OR_{N}$ to exact search, and proving the
former requires $N$ queries to achieve certainty).

###  1.2 Contributions

As can be seen from Table 1, the parameters $\alpha,\beta$ in
$G(\alpha,\beta)=S_{r}(\beta)\,S_{o}(\alpha)$ are fixed once the ratio
$\lambda$ is known. One question now naturally arises as follows.

The question: Is it possible to achieve exact search when one of the
parameters $\alpha,\beta$ in $G(\alpha,\beta)$ is arbitrarily given? Or to be
more precise, when the angle $\alpha$ in phase oracle $S_{o}(\alpha)$, or the
angle $\beta$ in phase rotation $S_{r}(\beta)$ is arbitrarily given?

In this paper, we answer the above question affirmatively. Specifically, we
have the following two theorems for the two cases in which $\alpha$ or $\beta$
is arbitrarily given:

######  Theorem 1.

Given the phase oracle $S_{o}(\alpha)$ with an arbitrary angle
$\alpha\in(0,2\pi)$, whenever $k>k_{\mathrm{lower}}$, there always exits a
pair of parameters $(\beta_{1},\beta_{2})$, such that applying
$F_{xr,\alpha}:=G(\alpha,\beta_{2})G(\alpha,\beta_{1})$ to $\ket{\psi_{0}}$
for $k$ times will produce an equal superposition of marked states. The lower
bound of $k$ is

$k_{\mathrm{lower}}=\frac{\pi}{\Big{|}4\arcsin(\sqrt{\lambda}\sin\frac{\alpha}{2})\mod[-\frac{\pi}{2},\frac{\pi}{2}]\Big{|}}\in
O(1/\sqrt{\lambda}),$ (4)

where $\lambda\in(0,1)$ is the proportion of marked elements, and the notation
“$x\mod[-\frac{\pi}{2},\frac{\pi}{2}]$” means to add $x$ with an appropriate
integer multiples $l$ of $\pi$, such that
$x+l\pi\in[-\frac{\pi}{2},\frac{\pi}{2}]$.

######  Theorem 2.

Given the phase rotation $S_{r}(\beta)$ with an arbitrary angle
$\beta\in(0,2\pi)$, whenever $k>k_{\mathrm{lower}}$, there always exits a pair
of parameters $(\alpha_{1},\alpha_{2})$, such that applying
$F_{xr,\beta}:=G(\alpha_{1},\beta)G(\alpha_{2},\beta)$ to $\ket{\psi_{0}}$ for
$k$ times will produce an equal superposition of marked states. The lower
bound of $k$ is

$k_{\mathrm{lower}}=\frac{\pi}{\Big{|}4\arcsin(\sqrt{\lambda}\sin\frac{\beta}{2})\mod[-\frac{\pi}{2},\frac{\pi}{2}]\Big{|}}\in
O(1/\sqrt{\lambda}).$ (5)

In Section 2, two applications of the above results will be presented. Here we
have a look at the proof outline.

Proof outline of Theorem 1 and 2: The proof is divided into two parts:

1\. To derive the explicit equations that parameters $(k,\beta_{1},\beta_{2})$
or $(k,\alpha_{1},\alpha_{2})$ need to satisfy. This is done in Section 3 with
the final equations shown by Eqs. (34),(35) for $(k,\beta_{1},\beta_{2})$; and
Eqs. (36),(37) for $(k,\alpha_{1},\alpha_{2})$. We first determine the effect
of $F_{xr}=G(\alpha_{2},\beta_{2})G(\alpha_{1},\beta_{1})$ in its invariant
subspace spanned by $\ket{R}$ and $\ket{T}$, which are the equal-superposition
of unmarked and marked states respectively. In fact, $F_{xr}$ can be seen as a
rotation $R_{\vec{n}}(\phi)$ composing of four rotations
$S_{r}(\beta_{2})S_{o}(\alpha_{2})S_{r}(\beta_{1})S_{o}(\alpha_{1})$ on the
Bloch sphere of basis $\\{\ket{R},\ket{T}\\}$, so we can then calculate the
rotation parameters $\vec{n}$ and $\phi$ of $F_{xr,\alpha}$ and $F_{xr,\beta}$
(Lemma 4). The Bloch sphere interpretation of single-qubit operations provides
us with the tool to deal with the exponentiation $F_{xr}^{k}$, because of the
equation $R^{k}_{\vec{n}}(\phi)=R_{\vec{n}}(k\phi)$. Then by considering the
real and imaginary part of $0=\bra{R}F_{xr,\alpha}^{k}\ket{\psi_{0}}$ or
$0=\bra{R}F_{xr,\beta}^{k}\ket{\psi_{0}}$, we obtain the equations that
parameters $(k,\beta_{1},\beta_{2})$ or $(k,\alpha_{1},\alpha_{2})$ need to
satisfy.

2\. To prove that whenever $k$ is greater than $k_{\mathrm{lower}}$, there
exists a solution $(\beta_{1},\beta_{2})$ or $(\alpha_{1},\alpha_{2})$ to
their corresponding equations. This part is quite technical and is shown in
Section 4, where we make use of 3D geometry (Lemma 6) and the intermediate
value theorem of continuous function on closed intervals. We only show the
proof for the case where $\alpha$ is fixed, since the proof for $\beta$ being
fixed is almost the same, but we point out some differences in Section 4.5.

Remark: We call the procedure in Theorem 1 and 2 the fixed-axis-rotation (FXR)
method, because the exponentiation $F_{xr}^{k}$ can be seen as rotating about
a fixed axis for $k$ times on the Bloch sphere. The peculiar notation in the
denominator of Eq. (4) only takes effect when $\lambda$ is large, because when
$\lambda$ is small, $4\arcsin(\sqrt{\lambda}\sin\frac{\alpha}{2})$ will always
be in $[0,\frac{\pi}{2}]$, and $k_{\mathrm{lower}}$ will be of order
$O(1/\sqrt{\lambda})$, maintaining the quadratic speedup. The same goes for
Eq. (5).

###  1.3 Related work and paper structure

A special case of Theorem 1 with $\alpha=\pi$ was considered by Roy et al. in
[6], where the deterministic two-parameter (D2p) protocol was proposed. The
D2p protocol obtains zero failure rate by applying $G(\pi,\beta_{1})$ and
$G(\pi,\beta_{2})$, alternatively, to the initial state $\ket{\psi_{0}}$ until
$k\geq\lceil k_{\mathrm{opt}}\rceil$ oracle queries are made. When $k$ is
even, the last iteration is $G(\pi,\beta_{2})$; when $k$ is odd, the last
iteration is $G(\pi,\beta_{1})$ and the equations which parameters
$(\beta_{1},\beta_{2})$ need to satisfy are more complicated. Compared to the
D2p protocol, our FXR method iterates $F_{xr}$ as one piece for $k$ times,
regardless of the parity of $k$, therefore only one system of equations needs
to be solved to obtain parameters $(\beta_{1},\beta_{2})$. Moreover, they
claimed that the equations can always be solved when $k\geqslant
k_{\text{opt}}$ and $\lambda\leqslant 1/4$, but lack rigorous proof.

The rest of this paper is organized as follows. We first give two applications
of our results in Section 2. The first uses Theorem 1 and the other uses
Theorem 2. In Section 3 we describe the intuition behind our FXR method, and
derive the equations that parameters $(k,\beta_{1},\beta_{2})$ or
$(k,\alpha_{1},\alpha_{2})$ need to satisfy. In Section 4 we prove the
existence of solution $(\beta_{1},\beta_{2})$ or $(\alpha_{1},\alpha_{2})$ to
the corresponding equations whenever $k$ is greater than $k_{\mathrm{lower}}$.
Conclusion and future work are discussed in Section 5.

##  2 Applications

In this section, we present two applications of the search framework with
adjustable parameters. The first uses Theorem 1, and the second uses Theorem
2. It can be seen especially from the second application that the search
framework can be deployed in designing quantum exact algorithms no longer
restricted to Grover search problem, and the key step is to reduce the problem
under consideration to the problem of transforming initial state to target
state in a two-dimensional subspace with some obtained $G(\alpha,\beta)$. We
believe that the two applications shown below are only tip of the iceberg
demonstrating the usefulness of the search framework, and that more
interesting ones will be found in the future.

###  2.1 Identifying secret string exactly with Hamming distance oracle

Hunziker and Meyer [7] considered the problem of identifying a secret string
$s\in[k]^{n}$, by querying the Hamming distance oracle
$h_{s}(x)=dist(x,s)\,\text{mod}\,r$, where $r=\max\\{2,6-k\\}$, and
$dist(x,s)$ is the generalized Hamming distance between the query string $x$
and $s$, i.e., the number of components at which they differ. When
$k\in\\{2,3,4\\}$, Algorithm B proposed in [7] requires only one query to
identify $s$ exactly. However, the case of $k>4$ is more complicated, and we
recall the main idea proposed in [7] for this case in the following, where the
second step has a flaw and can be amended by using Theorem 1.

  1. (i)

Algorithm C proposed in [7] can be viewed as $n$ synchronous Grover search on
each position of $s$. In the $i$-th position, a Grover search with
$O(\sqrt{k})$ iterations is performed for finding one marked item out of $k$
items, and thus $s_{i}$ is identified correctly with probability at worst
$1-\frac{1}{k}$ [8]. As a result, the probability of identifying $s$ is at
least $(1-\frac{1}{k})^{n}$ which is bounded above $\frac{1}{2}+\epsilon$ when
$n<-k\ln(\frac{1}{2}+\epsilon)$.

  2. (ii)

The Grover search on each position can be adjusted to succeed with probability
$1$ by using one of the three methods in Table 1.

  3. (iii)

Thus, the condition $n<-k\ln(\frac{1}{2}+\epsilon)$ can be removed, which
leads to a quantum algorithm identifying $s$ with certainty and consuming
$O(\sqrt{k})$ queries.

Input: An oracle $O_{h_{s}}$ for $s\in[k]^{n}$ such that
$O_{h_{s}}|x\rangle|b\rangle=|x\rangle|b\oplus h_{s}(x)\rangle$.

Output: The secret string $s$.

Runtime: $O(\sqrt{k})$ queries to $O_{h_{s}}$. Succeeds with probability at
least $\frac{1}{2}+\epsilon$ when $n<-k\ln(\frac{1}{2}+\epsilon)$.

1

Procedure :

2 Initial the state to $|0\rangle^{\otimes n}|0\rangle\in(C_{k})^{\otimes
n}\otimes C_{2}$.

3Apply the unitary transformation $QFT_{k}^{\otimes n}\otimes(HX)$

4for  _ $i=1:\lfloor\frac{1}{2}(\pi/(2\arcsin(\frac{1}{\sqrt{k}}))-1)\rceil$_
do

5 apply the oracle $O_{h_{s}}$.

6 apply the unitary transformation $(QFT_{k}(I-2|0\rangle\langle
0|)QFT_{k}^{\dagger})^{\otimes n}\otimes I$

7 end for

Measure the first $n$ registers.

Algorithm 1 Algorithm C in [7]

However, as pointed out in [9], the second item above is not true, that is,
the algorithm cannot be adjusted to succeed with probability $1$ by using the
three methods in Table 1. We explain the reason below.

First note that when $k>4$, we have
$h_{s}(x)=({n-\sum_{i=1}^{n}\delta_{s_{i}x_{i}}})\bmod 2$, and the quantum
oracle works as $O_{h_{s}}|x\rangle|b\rangle=|x\rangle|b\oplus
h_{s}(x)\rangle$ where $\oplus$ denotes the bitwise XOR. More specifically,
the oracle $O_{h_{a}}$ works as follows:

$\displaystyle O_{h_{s}}(|x\rangle\otimes\ket{-})$
$\displaystyle=|x\rangle\otimes\frac{1}{\sqrt{2}}(|0\oplus
h_{s}(x)\rangle-|1\oplus h_{s}(x)\rangle)$ (6)
$\displaystyle=(-1)^{h_{s}(x)}|x\rangle\otimes\ket{-}$ (7)
$\displaystyle=(-1)^{(n-\sum_{i=1}^{n}\delta_{s_{i}x_{i}})\bmod
2}|x\rangle\otimes\ket{-}$ (8)
$\displaystyle=(-1)^{n-\sum_{i=1}^{n}\delta_{s_{i}x_{i}}}|x\rangle\otimes\ket{-}$
(9)
$\displaystyle=(-1)^{n}\mathop{\bigotimes}_{i=1}^{n}(-1)^{\delta_{s_{i}x_{i}}}|x_{i}\rangle\otimes\ket{-},$
(10)

where $\ket{-}$ denotes the state $\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$. The
trick employed there is phase pick-back as shown in Eq. (6) and Eq. (7),
adding a fixed phase $-1$ to $|x_{i}\rangle$ when $x_{i}$ is equal to $s_{i}$.
It should be pointed out that Eq. (9) holds as $(-1)^{l}=(-1)^{l\bmod 2}$ for
any $0\leq l\leq n$, but it will not hold if we replace $-1$ with $e^{i\phi}$
for general $\phi$, since $e^{i\phi l}=e^{i\phi l\bmod 2}$ no longer holds. On
the other hand, the three methods in Table 1 requires the phase oracle
$S_{o}(\alpha)$ to have arbitrary user-controllable angle $\alpha$. That is
why the step in the second item above cannot be adjusted to succeed with
probability $1$ by using the three methods in Table 1.

Nevertheless, we can use the FXR method instead, by setting the phase oracle’s
angle $\alpha=\pi$ and $\lambda=1/k$ in Theorem 1. We will then identify the
secret string $s$ by measuring the first $n$ registers, and what’s more, the
query complexity remains $O(\sqrt{k})$ by Eq. (4).

###  2.2 Solving element distinctness promise problem deterministically

The element distinctness problem is to determine whether a string
$x=(x_{1},x_{2},\ldots,x_{N})\in[M]^{N}$ of $N$ elements, where
$[M]=\\{1,2,\ldots,M\\}$ and $M\geq N$, contains two elements of the same
value. More precisely, we are given a black box (oracle) $O_{x}$ that when
queried index $i$ of the unknown string $x=(x_{1},x_{2},\ldots,x_{N})$, it
will output its value $x_{i}$, and the task now is to determine whether the
string $x$ contains two equal items $x_{i}=x_{j}$ (called colliding pair),
with as few queries to the index oracle $O_{x}$ as possible.

The problem is well-known both in classical and quantum computation. The
classical bounded-error query complexity (a.k.a decision tree complexity, see
[10] for more information) is shown to be $\Theta(N)$ by a trivial reduction
from the OR-problem [11]. In comparison, Ambainis [12, 13] proposed a
$O(N^{2/3})$-query quantum algorithm with bounded-error, and it is optimal:
the bounded-error quantum query complexity of element distinctness problem has
previously been shown to be $\Omega(N^{2/3})$ [14, 15, 16] by the polynomial
method [5]. The quantum algorithm proposed by Ambainis [12, 13] is developed
in two steps:

  1. (i)

Ambainis first designs a $O(N^{2/3})$-query quantum algorithm $\mathcal{A}$
which solves the simple case (promise problem) in which string $x$ contains at
most one colliding pair, by using quantum walk search on Johnson graph.

  2. (ii)

He then reduces the general case to this simple case, by sampling a sequence
of exponentially shrinking subsets to run $\mathcal{A}$. By showing the
probability that the sequence has a subset containing at most one colliding
pair is greater than $1/2$, and the overall query complexity remains the same
order, Ambainis successfully solves the element distinctness problem with
query complexity $O(N^{2/3})$.

This two stage process shows the promise problem that algorithm $\mathcal{A}$
solves is important. We formalize it in the following box.

Problem: the element distinctness promise problem input: index oracle $O_{x}$
hiding the unknown string $x=(x_{1},x_{2},\ldots,x_{N})\in[M]^{N}$. promise:
$x$ contains exactly one colliding pair $x_{i}=x_{j}$ with $i\neq j$; or
$x_{i}$s are distinct for $i\in[N]$. output: indexes $(i,j)$ of the colliding
pair $x_{i}=x_{j}$; or “all distinct”.

However, $\mathcal{A}$ is a one-sided error algorithm: if the string $x$
contains a colliding pair $x_{i}=x_{j}$, then $\mathcal{A}$ might asserts that
$x$ is “all distinct”, making a mistake; but if elements in $x$ are all
distinct, then $\mathcal{A}$ won’t err. This motivates us to develop in [17] a
quantum exact algorithm that solves the element distinctness promise problem
with $100\%$ success and has the same query complexity $\Theta(N^{2/3})$. The
design of our quantum exact algorithm can be roughly divided into the
following three steps:

  1. 1.

We first reduce the problem to quantum walk search on quasi-Johnson graph $G$,
based on Portugal’s staggered quantum walk model [18, 19], but we introduce
arbitrary phase angles in the two local diffusion operators, in order to
achieve certainty of success in the next two steps.

  2. 2.

We then reduce the quantum walk search on $G$ to exact Grover search problem
with an arbitrarily given phase rotation $S_{r}(\beta)$. This step is where
our novelty lies: we use Jordan’s lemma about common invariant subspaces of
two reflections and some intuition from rotation on the Bloch sphere, to
reduce the quantum walk’s five-dimensional invariant subspace further to a
two-dimensional space, enabling us to use the search framework.

  3. 3.

We use Theorem 2 to transform the initial state to the target state in the
reduced two-dimensional space obtained in step 2.

We have to use in the last step Theorem 2 instead of the other three methods
in Table 1, because in the phase rotation operator $S_{r}(\beta)$ that we’ve
obtained from step 2, the angle $\beta$ is a solution to some equations and is
therefore arbitrarily given.

##  3 The fixed-axis-rotation method

In this section, we first reformulate the problem of searching an unstructured
database based on phase oracles, and then describe our FXR method to achieve
quantum exact search with one of the parameters $\alpha,\beta$ in
$G(\alpha,\beta)$ being arbitrarily given. Finally, we derive the under-
determined system of equations that parameters $(\beta_{1},\beta_{2},k)$ or
$(\alpha_{1},\alpha_{2},k)$ need to satisfy respectively, when $\alpha$ or
$\beta$ is arbitrarily given.

###  3.1 Preliminaries

In the problem of searching an unstructured database, suppose that there are
$N$ elements in the database, $M$ of which are marked, so the ratio of marked
elements $\lambda=M/N$ is known in advance. Suppose the marked elements’
indexes are represented by the computational basis $\\{\ket{t_{j}}\mid
j=1,2,\ldots,M\\}:=\mathcal{M}$, and the unmarked ones by $\\{\ket{r_{j}}\mid
j=1,2,\ldots,N-M\\}$. Then the phase oracle $S_{o}(\alpha)$ is

$S_{o}(\alpha)=e^{i\alpha}\sum_{j=1}^{M}\ket{t_{j}}\bra{t_{j}}+\sum_{j=1}^{N-M}\ket{r_{j}}\bra{r_{j}}=e^{i\alpha\,\Pi_{\mathcal{M}}},$
(11)

which rotates the phase of the marked states $\ket{t_{j}}$ by an angle
$\alpha$ and keeps the unmarked states $\ket{r_{j}}$ unchanged. We now want to
design an quantum exact search algorithm which outputs one of the marked
states with certainty, by querying the oracle $S_{o}(\alpha)$ or applying
$S_{r}(\beta)$ as few as possible.

As usual, we starts with preparing an equal-superposition state

$\ket{\psi_{0}}=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\ket{j},$ (12)

which can be produced by, for example, applying $H^{\otimes n}$ to
$\ket{0}^{\otimes n}$ (when $2^{n}=N$). If we denote by $\ket{R},\ket{T}$ the
equal-superposition of unmarked and marked states respectively:

$\ket{R}:=\frac{1}{\sqrt{N-M}}\sum_{j=1}^{N-M}\ket{r_{j}},\quad\ket{T}:=\frac{1}{\sqrt{M}}\sum_{j=1}^{M}\ket{t_{j}}.$
(13)

Then $\ket{\psi_{0}}$ lies in the two-dimensional subspace $\mathcal{H}_{0}$
spanned by orthonormal vectors $\ket{R}$ and $\ket{T}$, i.e.

$\mathcal{H}_{0}=\text{span}\\{\ket{R},\ket{T}\\},$ (14)

and can be expressed as
$\ket{\psi_{0}}=\sqrt{1-\lambda}\ket{R}+\sqrt{\lambda}\ket{T}$. It is easy to
see that subspace $\mathcal{H}_{0}$ is invariant under the phase oracle
$S_{o}(\alpha)$, which has the following matrix representation in its basis
$\\{\ket{R}=[1,0]^{T}\ ,\ket{T}=[0,1]^{T}\\}$:

$S_{o}(\alpha)=\begin{bmatrix}1&0\\\ 0&e^{i\alpha}\end{bmatrix}.$ (15)

The phase rotation $S_{r}(\beta)$ is defined by

$S_{r}(\beta)=I-(1-e^{-i\beta})\ket{\psi_{0}}\bra{\psi_{0}}=e^{-i\beta\,\ket{\psi_{0}}\bra{\psi_{0}}},$
(16)

which also maps subspace $\mathcal{H}_{0}$ to itself, and has the following
matrix representation in the same basis:

$S_{r}(\beta)=\begin{bmatrix}1-(1-e^{-i\beta})(1-\lambda)&-(1-e^{-i\beta})\sqrt{\lambda(1-\lambda)}\\\
-(1-e^{-i\beta})\sqrt{\lambda(1-\lambda)}&1-(1-e^{-i\beta})\lambda\end{bmatrix}.$
(17)

In fact,
$S_{r}(\beta)=I-(1-e^{-i\beta})\left(\sqrt{1-\lambda}\ket{R}+\sqrt{\lambda}\ket{T}\right)\left(\sqrt{1-\lambda}\bra{R}+\sqrt{\lambda}\bra{T}\right)$.
Thus, $\bra{R}S_{r}(\beta)\ket{R}=1-(1-e^{-i\beta})(1-\lambda)$,
$\bra{R}S_{r}(\beta)\ket{T}=\bra{T}S_{r}(\beta)\ket{R}=-(1-e^{-i\beta})\sqrt{\lambda(1-\lambda)}$,
and $\bra{T}S_{r}(\beta)\ket{T}=1-(1-e^{-i\beta})\lambda$, giving the matrix
representation in Eq. (17).

With subspace $\mathcal{H}_{0}$ in mind, designing an quantum exact search
algorithm now boils down to transforming the initial state
$\ket{\psi_{0}}=[\sqrt{1-\lambda},\,\sqrt{\lambda}]^{T}$ to the target state
$\ket{T}=[0,1]^{T}$, by multiplying a series of parameterized matrices
$S_{r}(\beta)$ and $S_{o}(\alpha)$ for as few times as possible.

###  3.2 Overview of the FXR method

The geometry intuition underlying our FXR method is that one needs only two
rotations of noncollinear axes to span the full $SU(2)$ space. In the case
when $\alpha$ is fixed, the two rotations are $G(\alpha,\beta_{1})$ and
$G(\alpha,\beta_{2})$. And in the case when $\beta$ is fixed, the two
rotations are $G(\alpha_{1},\beta)$ and $G(\alpha_{2},\beta)$. So by applying

$F_{xr,\alpha}=G(\alpha,\beta_{2})G(\alpha,\beta_{1}),\quad\text{or}\quad
F_{xr,\beta}=G(\alpha_{2},\beta)G(\alpha_{2},\beta)$ (18)

to initial state $\ket{\psi_{0}}$ for a number of $k$ times, where parameters
$(\beta_{1},\beta_{2},k)$ or $(\alpha_{1},\alpha_{2},k)$ are to be determined
later in Section 3.3, we hope to get $\ket{T}$ (possibly up to some global
phase).

We have to iterate $F_{xr,*}$ for above a number of times for the following
reason. Note that $F_{\text{xr},*}$ will be a fixed rotation once the pair of
parameters $(\alpha_{1},\alpha_{2})$ or $(\beta_{1},\beta_{2})$ therein is
fixed, so in order to transform $\ket{\psi_{0}}$ to $\ket{T}$ by iterating
this fixed rotation, we must require the direction of the rotation to be
correct: from $\ket{\psi_{0}}$ straight toward $\ket{T}$. This is actually a
constraint that we impose on the rotation axis of $F_{\text{xr},*}$, and will
in turn leads to a constraint relation [specifically, Eq. (imag)] on the pair
of variable parameters, as explained by step 2 in the proof of Lemma 6.
However, this constraint relation also results in the range of the rotation
angle $\phi$ of $F_{\text{xr},*}$ to be small, compared to the spherical
distance between the initial state $\ket{\psi_{0}}$ and the target state
$\ket{T}$. Therefore, we have to rotate for a number of times in order to
reach $\ket{T}$ from $\ket{\psi_{0}}$. The reason explained just now is only a
geometric intuition, for more rigorous proof of the feasibility of our FXR
method when $k>k_{\text{lower}}$, please refer to Section 4.

###  3.3 Equations that parameters need to satisfy

In a nutshell, the equation that parameters $(\beta_{1},\beta_{2},k)$ or
$(\alpha_{1},\alpha_{2},k)$ need to satisfy is the following:

$0=\bra{R}F_{xr,\alpha}^{k}\ket{\psi_{0}},\quad\text{or}\quad
0=\bra{R}F_{xr,\beta}^{k}\ket{\psi_{0}}.$ (19)

Because in the two-dimensional subspace $\mathcal{H}_{0}$, a state is equal to
$\ket{T}$ up to some global phase if and only if it is orthogonal to
$\ket{R}$. What now stands in our way to solve this equation is the
exponentiation of matrix, i.e. $F_{xr,*}^{k}$. Luckily, the Bloch sphere
representation of single-qubit states and operations provides the tool we
need. We summarize some facts about it in Lemma 3, and one may find its proof
in the standard textbook [20].

######  Lemma 3.

Some facts about single-qubit states and operations in the Bloch sphere
representation are as follows.

  1. (1)

Any single-qubit state $\ket{\psi}$ (unit vector in the two-dimensional
Hilbert space) can be written as

$\ket{\psi}=\cos\frac{\theta}{2}\ket{0}+e^{i\phi}\sin\frac{\theta}{2}\ket{1},$
(20)

up to some irrelevant global phase $e^{i\varphi}$ which does not affect
measurement outcome, so $\ket{\psi}$ can be mapped to a unit vector
$[\cos\phi\sin\theta,\sin\phi\sin\theta,\cos\theta]^{T}$ on the unit sphere of
$\mathbb{R}^{3}$ (the Bloch sphere).

  2. (2)

Any single-qubit operation $U$ (two-dimensional unitary matrix) can be
decomposed to

$U=e^{i\varphi}R_{\vec{n}}(\phi),$ (21)

where

$\displaystyle R_{\vec{n}}(\phi)$ $\displaystyle=\cos\frac{\phi}{2}\cdot
I-i\sin\frac{\phi}{2}\cdot(n_{x}X+n_{y}Y+n_{z}Z)$ (22)
$\displaystyle=\begin{bmatrix}c_{\phi}-is_{\phi}n_{z}&-is_{\phi}n_{x}-s_{\phi}n_{y}\\\
-is_{\phi}n_{x}+s_{\phi}n_{y}&c_{\phi}+is_{\phi}n_{z}\end{bmatrix}$ (23)

represents a rotation by an angle $\phi$ about the axis
$\vec{n}=(n_{x},n_{y},n_{z})$ of the Bloch sphere. We use here (and in the
sequel) the following shorthand for trigonometric functions:

$s_{\phi}\equiv\sin\frac{\phi}{2},\quad c_{\phi}\equiv\cos\frac{\phi}{2}.$
(shorthand 1)

Note that rotation $R_{\vec{n}}(\phi)$ is determined by parameters $c_{\phi}$
and $s_{\phi}\vec{n}$.

  3. (3)

The exponentiation of $R_{\vec{n}}(\phi)$ has the following nice expression:

$R^{k}_{\vec{n}}(\phi)=R_{\vec{n}}(k\phi).$ (24)

It means that rotation about a fixed axis by angle $\phi$ for $k$ times, is
equal to a rotation about the same axis by angle $k\phi$.

  4. (4)

The composition of two arbitrary rotation, i.e.
$R_{\vec{n}_{2}}(\phi_{2})R_{\vec{n}_{1}}(\phi_{1})$, is also a rotation
$R_{\vec{n}}(\phi)$ with parameters given by

$\displaystyle c_{\phi}$
$\displaystyle=c_{\phi_{1}}c_{\phi_{2}}-(s_{\phi_{1}}\vec{n}_{1})\cdot(s_{\phi_{2}}\vec{n}_{2}),\
\text{and}$ (25) $\displaystyle s_{\phi}\vec{n}$
$\displaystyle=c_{\phi_{2}}(s_{\phi_{1}}\vec{n}_{1})+c_{\phi_{1}}(s_{\phi_{2}}\vec{n}_{2})+(s_{\phi_{2}}\vec{n}_{2})\times(s_{\phi_{1}}\vec{n}_{1}).$
(26)

We first introduce some notations about the initial state $\ket{\psi_{0}}$.
Let

$\sqrt{\lambda}=\sin\frac{\theta}{2}=s_{\theta},\quad\sqrt{1-\lambda}=\cos\frac{\theta}{2}=c_{\theta}.$
(27)

Then the initial state can be expressed as
$\ket{\psi_{0}}=\sqrt{1-\lambda}\ket{R}+\sqrt{\lambda}\ket{T}=c_{\theta}\ket{0}+s_{\theta}\ket{1}$.
It is, by Lemma 3.(1), the unit vector $[\sin\theta,0,\cos\theta]^{T}$ on the
Bloch sphere (with $\ket{R}$ and $\ket{T}$ being the north and south pole
respectively), and lies in the $xz$-plane forming an angle of $\theta$ with
the positive $z$-axis.

As can be seen from Lemma 3.(3), Eq. (24) provides us with the tool to deal
with the exponentiation $F_{xr,*}^{k}$ in Eq. (19). To use this tool, we
should decompose $F_{xr,*}$ into the form of Eq. (21). This is done in Lemma
4.

######  Lemma 4.

The effect of $F_{xr,\alpha}$ on the Bloch sphere is a rotation
$R_{\vec{n}}(\phi)$ whose parameters $c_{\phi},s_{\phi}\vec{n}$ are given by
Eqs. (B), (61), (68), (73) in Appendix B. For $F_{xr,\beta}$, its rotation
parameters are given by Eqs. (B), (62), (69), (74). We leave out the explicit
expression here, because they are only intermediate results to deal with Eq.
(19).

###### Proof.

The proof is divided into three steps, with detailed calculation presented in
Appendix B:

1\. We first decompose $S_{o}(\alpha)$ and $S_{r}(\beta)$ into the form of Eq.
(21). This is shown in the following Lemma 5. Its proof is presented in
Appendix A, which may also provide some idea on how to decompose a two-
dimensional unitary matrix into the form of Eq. (21).

######  Lemma 5.

The two-dimensional unitary matrices $S_{o}(\alpha)$ and $S_{r}(\beta)$, i.e.
Eq. (15) and Eq. (17), have the following decomposition in the form of Eq.
(21):

$\displaystyle S_{o}(\alpha)$
$\displaystyle=e^{i\alpha/2}\left(c_{\alpha}I-i\,s_{\alpha}Z\right)=e^{i\alpha/2}\
R_{R}(\alpha),$ (28) $\displaystyle S_{r}(\beta)$
$\displaystyle=e^{-i\beta/2}\left(c_{\beta}I-i\,s_{\beta}(s_{2\theta}X+c_{2\theta}Z)\right)=e^{-i\beta/2}\
R_{\psi_{0}}(\beta),$ (29)

which in the Bloch sphere represents a rotation about the positive $z$-axis
(i.e. $\ket{R}$) by an angle of $\alpha$, and a rotation about the axis
$[\sin\theta,0,\cos\theta]^{T}$ (i.e. $\ket{\psi_{0}}$) by an angle of
$\beta$, respectively.

2\. We then determine the effect of
$G(\alpha,\beta)=S_{r}(\beta)S_{o}(\alpha)$ on the Bloch sphere. As global
phase is irrelevant in the measurement outcome, we only need to consider
$R_{\psi_{0}}(\beta)$ and $R_{R}(\alpha)$. By direct calculation and using
some properties of Pauli matrices: $XZ=iY$ and $Z^{2}=I$, it is easy to obtain
the parameters [shown in Eqs. (46), (47)] of the following rotation:

$G^{\prime}(\alpha,\beta):=R_{\psi_{0}}(\beta)R_{R}(\alpha).$ (30)

3\. Finally, we determine the effects of
$F_{xr,\alpha}=G(\alpha,\beta_{2})G(\alpha,\beta_{1})$ and
$F_{xr,\beta}=G(\alpha_{2},\beta)G(\alpha_{1},\beta)$, or equivalently, the
parameters of the following rotations

$\displaystyle
F^{\prime}_{xr,\alpha}=G^{\prime}(\alpha,\beta_{2})G^{\prime}(\alpha,\beta_{1}),\quad
F^{\prime}_{xr,\beta}=G^{\prime}(\alpha_{2},\beta)G^{\prime}(\alpha_{1},\beta).$
(31)

Using Lemma 3.(4) and with some calculation (see Appendix B), we find that the
parameters of the above two rotations are as claimed in Lemma 4. ∎

We now consider the equation

$0=\bra{R}R^{k}_{\vec{n}}(\phi)\ket{\psi_{0}},$ (32)

which is equivalent to Eq. (19), when $\vec{n},\phi$ are substituted by the
corresponding rotation parameters of $F^{\prime}_{xr,\alpha}$ or
$F^{\prime}_{xr,\beta}$ shown in Lemma 4. By Eq.(24) in Lemma 3.(3), the
exponentiation $[R_{\vec{n}}(\phi)]^{k}$ is equal to

$R_{\vec{n}}(k\phi)=\begin{bmatrix}c_{k\phi}-is_{k\phi}n_{z}&-is_{k\phi}n_{x}-s_{k\phi}n_{y}\\\
-is_{k\phi}n_{x}+s_{k\phi}n_{y}&c_{k\phi}+is_{k\phi}n_{z}\end{bmatrix}.$ (33)

Substituting it into Eq. (32), and letting its real and imaginary parts both
to be zero, we obtain the following under-determined system of equations that
parameters $(\beta_{1},\beta_{2},k)$ or $(\alpha_{1},\alpha_{2},k)$ need to
satisfy:

$\displaystyle 0$
$\displaystyle=\sqrt{1-\lambda}\cos\frac{k\phi}{2}-\sqrt{\lambda}\sin\frac{k\phi}{2}\
n_{y},$ (real) $\displaystyle 0$ $\displaystyle=\sqrt{1-\lambda}\
n_{z}+\sqrt{\lambda}\ n_{x}.$ (imag)

To be more precise, by substituting Eq. (68) of $s_{\phi}n_{y}$ into Eq.
(real); and by substituting Eqs. (61), (73) of $s_{\phi}n_{x},s_{\phi}n_{z}$
into Eq. (imag), and after some rearrangement (dividing both sides by
$c_{\beta_{1}}c_{\beta_{2}}$, and then regrouping terms by
$t_{\beta_{1}}:=s_{\beta_{1}}/c_{\beta_{1}}$ and
$t_{\beta_{2}}:=s_{\beta_{2}}/c_{\beta_{2}}$, and finally multiplying back
$c_{\beta_{1}}c_{\beta_{2}}$), we obtain the explicit equations that
$(\beta_{1},\beta_{2},k)$ need to satisfy in Theorem 1 as follows:

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\sin\frac{\phi}{2}\cos\frac{k\phi}{2}-2\lambda\sin\frac{k\phi}{2}[-\sin\alpha\cos\frac{\beta_{1}}{2}\sin\frac{\beta_{2}}{2}+(1-2\lambda)(1-\cos\alpha)\sin\frac{\beta_{1}}{2}\sin\frac{\beta_{2}}{2}],$
(34) $\displaystyle 0$ $\displaystyle=$
$\displaystyle-\sin\frac{\beta_{1}}{2}\sin\frac{\beta_{2}}{2}\sin\alpha(1-2\lambda)+\sin\frac{\beta_{1}}{2}\cos\frac{\beta_{2}}{2}[(1-2\lambda)\cos\alpha+2\lambda]$
(35)
$\displaystyle+\cos\frac{\beta_{1}}{2}\sin\frac{\beta_{2}}{2}\cos\alpha+\cos\frac{\beta_{1}}{2}\cos\frac{\beta_{2}}{2}\sin\alpha,$

where angle $\phi$ satisfies Eq. (B).

Similarly, the explicit equations that $(\alpha_{1},\alpha_{2},k)$ need to
satisfy in Theorem 2 are the following:

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\sin\frac{\phi}{2}\cos\frac{k\phi}{2}-2\lambda\sin\frac{k\phi}{2}[-\sin\frac{\alpha_{1}}{2}\cos\frac{\alpha_{2}}{2}\sin\beta+(1-2\lambda)\sin\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}(1-\cos\beta)],$
(36) $\displaystyle 0$ $\displaystyle=$
$\displaystyle-\sin\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}(1-2\lambda)\sin\beta+\sin\frac{\alpha_{1}}{2}\cos\frac{\alpha_{2}}{2}\cos\beta$
(37)
$\displaystyle-\cos\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}(2\lambda+(1-2\lambda)\cos\beta)+\cos\frac{\alpha_{1}}{2}\cos\frac{\alpha_{2}}{2}\sin\beta,$

where angle $\phi$ satisfies Eq. (B).

##  4 Existence of parameters when $k>k_{\text{lower}}$

In this section we prove the sufficient condition for our FXR method to
succeed: whenever the number of iterations $k$ is fixed to be greater than
$k_{\mathrm{lower}}$ [see Eq. (4) or (5)], there exits a solution
$(\beta_{1},\beta_{2})$ or $(\alpha_{1},\alpha_{2})$ to the system of
equations (real), (imag). More explicitly, Eqs. (34), (35) for
$(\beta_{1},\beta_{2})$; and Eqs. (36), (37) for $(\alpha_{1},\alpha_{2})$.
Their value can be determined numerically by using, for example, MATLAB.

We first prove for the case when $\alpha$ is fixed (Theorem 1) from Section
4.1 to 4.4. The proof for the case when $\beta$ is fixed (Theorem 2) is almost
the same, but we point out some differences in Section 4.5.

The outline of our proof for the existence of solution $(\beta_{1},\beta_{2})$
to Eqs. (real), (imag) whenever $k$ is greater than $k_{\text{lower}}$ [see
Eq. (4)] is as follows, one may find it helpful before delving into the
details.

  1. 1.

In Section 4.1 we first deal with Eq. (imag), which does not contain $k$. Thus
solving it will give us a family of continuous functions
$\beta_{2}=f(\beta_{1})+2l\pi$ for $l\in\mathbb{Z}$, which allows us to regard
the RHS of Eq. (real) as a univariate function of $\beta_{1}$.

  2. 2.

Let $R_{\vec{n}}(\phi):=F^{\prime}_{xr,\alpha}$, we prove in Lemma 6 that
there exists a pair of special parameters
$(\beta_{1}^{\prime},\beta_{2}^{\prime})$ satisfying Eq. (imag) (so we can
denote the branch of continuous functions $f+2l\pi$ that pass through
$(\beta_{1}^{\prime},\beta_{2}^{\prime})$ by $\hat{f}$ ) such that $\phi=0$.
And in Lemma 7 we find another pair of parameters
$(\beta_{1}^{\prime\prime},\beta_{2}^{\prime\prime})$ on $\hat{f}$ such that
$\phi/2\in\\{\phi_{0},\pi-\phi_{0}\\}$, where $\phi_{0}$ is shown by Eq. (39).

  3. 3.

Then in Section 4.4, by substituting $\beta_{2}=\hat{f}(\beta_{1})$ into Eq.
(B) about $c_{\phi}$, we get another continuous function regarding $\phi$:
$\phi/2=g(\beta_{1})$, and from step 2 we know that $g(\beta_{1}^{\prime})=0$
and $g(\beta_{1}^{\prime\prime})\geq\phi_{0}$. Thus by the continuity of $g$,
when $k$ is big enough that $\pi/k\leq\phi_{0}$ [this inequality gives us the
lower bound on $k$ shown in Eq. (4)], there exists
$\beta_{1}^{\prime\prime\prime}$ such that
$\phi/2=g(\beta_{1}^{\prime\prime\prime})=\pi/k$.

  4. 4.

Finally, by substituting the above two continuous functions
$\beta_{2}=\hat{f}(\beta_{1})$ and $\frac{\phi}{2}=g(\beta_{1})$ into the RHS
of Eq. (real), we obtain a continuous function $F(\beta_{1})$. Since
$\frac{\phi}{2}=g(\beta_{1}^{\prime})=0$ and
$\frac{\phi}{2}=g(\beta_{1}^{\prime\prime\prime})=\pi/k$ from step 3, we know
that $F(\beta_{1}^{\prime})>0$ and $F(\beta_{1}^{\prime\prime\prime})<0$.
Therefore by the intermediate value theorem of continuous function on closed
interval, we conclude that there exists $\hat{\beta}_{1}$ such that
$F(\hat{\beta}_{1})=0$, which completes the proof.

###  4.1  Eq. (imag) leads to continuous function $\beta_{2}=f(\beta_{1})$

Consider Eq. (imag), or equivalently Eq. (35), we find that
$t_{2}:=\tan\frac{\beta_{2}}{2}$ is a function of
$t_{1}:=\tan\frac{\beta_{1}}{2}$ as follows.

$t_{2}=-\frac{t_{1}\big{[}(1-2\lambda)c_{2\alpha}+2\lambda\big{]}+s_{2\alpha}}{c_{2\alpha}-t_{1}s_{2\alpha}(1-2\lambda)}$
(2f1)

Note that when $\beta_{1}$ satisfies
$t_{1}=\frac{c_{2\alpha}}{s_{2\alpha}(1-2\lambda)}$, the denominator of the
RHS of Eq. (2f1) will become zero. We call this $\beta_{1}$ the potential
‘discontinuity point’. If we define $\beta_{2}=f(\beta_{1})$ by taking
‘$2\arctan$’ of the RHS of Eq. (2f1), then because the range of $2\arctan$ is
$(-\pi,\pi)$, $f$ will jump from $-\pi$ to $\pi$, or vice-versa, at this
‘discontinuity point’. This phenomenon is shown in Fig. 2 by the discontinuous
black curve between the two horizontal red lines, where the red lines
represent the range of $2\arctan$. However, one can always translate the
continuous segment on one side of the ‘discontinuity point’ up or down by
$2\pi$, and concatenate it with the other side, to form a new continuous
function, which we still denote by $\beta_{2}=f(\beta_{1})$. Thus, we say that
function $\beta_{2}=f(\beta_{1})$ is inherently continuous. A more rigorous
proof considering different cases of potential ‘discontinuity point’ can be
found in Lemma 8.

Figure 2:  Image of function $\beta_{2}=f(\beta_{1})$ when
$\lambda=0.2,\alpha=0.6\pi$. Black curve between the two horizontal red line
represents $f$ obtained by taking $\arctan$ of Eq. (2f1), blue curve outside
the two horizontal line represents translation of continuous segment of $f$ to
form new continuous $f$.

Because the period of $\tan x$ is $\pi$, we have actually obtained a family of
continuous functions $\beta_{2}=f(\beta_{1})+2l\pi,\ \beta_{1}\in[-\pi,\pi]$
which satisfy Eq. (2f1), where $l\in\mathbb{Z}$. In other words, the solutions
$(\beta_{1},\beta_{2})$ to Eq. (imag) constitutes a family of parallel
continuous function (curve) $\beta_{2}=f(\beta_{1})+2l\pi,\,\forall
l\in\mathbb{Z}$ in the two-dimensional plane of $(\beta_{1},\beta_{2})$.

###  4.2  A pair of special parameters
$(\beta_{1}^{\prime},\beta_{2}^{\prime})$

In this subsection, we present our key observation (Lemma 6) that there exists
a pair of parameters $(\beta_{1}^{\prime},\beta_{2}^{\prime})$ satisfying Eq.
(imag) such that the rotation angle $\phi$ of $R_{\vec{n}}(\phi)$ is zero!
This is done by reasoning with 3D geometry rather than solving Eqs.(35), (B)
directly (which is likely to be intractable).

######  Lemma 6.

There exists a pair of parameters $(\beta_{1}^{\prime},\beta_{2}^{\prime})$
satisfying Eq. (imag) such that $R_{\vec{n}}(\phi):=F^{\prime}_{xr,\alpha}$ is
the identity transformation $I$, which implies $\phi=0$.

###### Proof.

The proof is divided into four steps:

1\. We first show that there exists a specific angle $\beta_{1}^{\prime}$ such
that $R_{\vec{n}}(\phi)$ keeps $\ket{\psi_{0}}$ still as follows.

From Lemma 5 we know that
$G^{\prime}(\alpha,\beta)=R_{\psi_{0}}(\alpha)R_{R}(\alpha)$ represents: a
rotation about $\ket{R}$ by angle $\alpha$, followed by a rotation about
$\ket{\psi_{0}}$ by angle $\beta$ on the Bloch sphere, which are illustrated
by the two intersecting small blue circle shown in Fig. 3.(b).

(a)

(b)

Figure 3:  Bloch sphere interpretation on the effect of $R_{\psi_{0}}(\beta)$
and $R_{R}(\alpha)$ on the initial state $E(\ket{\psi_{0}})$. (a) Perspective
of (b) from the positive $y$-axis. $\mathop{AN}\limits^{\longrightarrow}$
bisects $\angle EAI$. (b) Bigger blue circle $EFMF^{\prime}E$ represents the
trajectory of $E$ under rotation $R_{R}(\alpha)$. Smaller blue circle
$FGF^{\prime}LF$ represents the trajectory of $F$ under rotation
$R_{\psi_{0}}(\beta)$.

Changing perspective to look at the $xz$-plane from the positive $y$-axis, one
gets the view shown by Fig. 3.(a). The horizontal dashed black line
$\overline{EM}$ represents the circular trajectory of $E(\ket{\psi_{0}})$
under rotation $R_{R}(\alpha)$. The oblique dashed red line $\overline{GL}$
(which is perpendicular to $\mathop{AE}\limits^{\longrightarrow}$) represents
the circular trajectory of $F$ under rotation $R_{\psi_{0}}(\beta_{1})$. We
now consider the trajectory of $E$ under operation
$R_{\vec{n}}(\phi)=G^{\prime}(\alpha,\beta_{2})G^{\prime}(\alpha,\beta_{1})$.
Firstly, suppose $R_{R}(\alpha)$ rotates $E$ to $F$ on $\overline{EM}$. Then,
applying $R_{\psi_{0}}(\beta_{1})$ rotates $F$ to any point on the oblique red
dashed line $\overline{GL}$. So there exists an angle
$\beta_{1}=\beta_{1}^{\prime}$ such that $R_{\psi_{0}}(\beta_{1}^{\prime})$
rotates $F$ to $F^{\prime}$, which is the the other intersecting point of
‘circle’ $\overline{EM}$ and ‘circle’ $\overline{GL}$ (shown in Fig. 3.(b)).
In the view of Fig. 3.(a), $F^{\prime}$ coincides with $F$. Finally,
$R_{R}(\alpha)$ rotates $F^{\prime}$ back to $E$, which is on the axis of
rotation $R_{\psi_{0}}(\beta_{2}^{\prime})$, so applying
$R_{\psi_{0}}(\beta_{2}^{\prime})$ keeps $E$ still. In the view of Fig. 3.(b),
the overall effect of $R_{\vec{n}}(\phi)$ on $E$ is the trajectory
$\overset{\frown}{EF}-\overset{\frown}{FGF^{\prime}}-\overset{\frown}{F^{\prime}E}-E$.

2\. We now show that Eq. (imag) holds if and only if the rotation axis
$\vec{n}$ of $R_{\vec{n}}(\phi)$ satisfies
$\braket{T}{\vec{n}}=\braket{\psi_{0}}{\vec{n}}$, which is equivalent to
$\vec{n}$ being on the perpendicular bisectionplane of $\overline{EI}$.

Note that on the Bloch sphere, $\ket{T}=[0,0,-1]$ and
$\ket{\psi_{0}}=[\sin\theta,0,\cos\theta]=[2\sqrt{\lambda(1-\lambda)},0,(1-2\lambda)]$,
so $\braket{T}{\vec{n}}=\braket{\psi_{0}}{\vec{n}}$ is equivalent to
$-n_{z}=2\sqrt{\lambda(1-\lambda)}n_{x}+(1-2\lambda)n_{z}$, which is
equivalent to $0=\sqrt{1-\lambda}\ n_{z}+\sqrt{\lambda}\ n_{x}$, and it’s
exactly Eq. (imag).

Next we would like to show that the rotation axis $\vec{n}$ of
$R_{\vec{n}}(\phi)$ is on the perpendicular bisectionplane of $\overline{EI}$,
if and only if $\braket{T}{\vec{n}}=\braket{\psi_{0}}{\vec{n}}$. Suppose
$\vec{n}$ is represented by $\mathop{AN}\limits^{\longrightarrow}$. Then the
former condition is equivalent to $|NE|=|NI|$, because the bisectionplane is
all the points in the $\mathbb{R}^{3}$ space that are equidistant from $E$ and
$I$. Suppose $|NE|=|NI|$, then we have $\triangle ANE\cong\triangle ANI$ (note
that these two triangle might not be coplanar, because $\vec{n}$ is not
necessarily in the xz-plane), because all their sides are equal to $1$. Thus
the projections of $AE,AI$ to $AN$ are of the same length, which implies
$\braket{T}{\vec{n}}=\braket{\psi_{0}}{\vec{n}}$, finishing the ‘only if’
part. Conversely, if the projections are of the same length, then it can be
seen that the two right triangles formed by projection are congruent (note
that $|AE|=|AI|=1$), so $\angle EAN=\angle IAN$. Thus we have $\triangle
EAN\cong\triangle IAN$. Therefore, $|NE|=|NI|$ which completes the ‘if’ part.

3\. Take any branch of the continuous function family
$\beta_{2}=f(\beta_{1})+2l\pi$, and let
$\beta_{2}^{\prime}=f(\beta_{1}^{\prime})$. Then the pair of parameters
$\beta_{1}^{\prime},\beta_{2}^{\prime}$ satisfy Eq. (imag), and thus by step 2
we know the rotation axis $\vec{n}\,(\mathop{AN}\limits^{\longrightarrow})$ of
$R_{\vec{n}}(\phi)$ is not collinear with $\ket{\psi_{0}}(E)$. Because
$R_{\vec{n}}(\phi)$ keeps $\ket{\psi_{0}}$ still by step 1, and that any
nontrivial three-dimensional rotation can only keep its axis still, we
conclude that the parameters $\beta_{1}^{\prime},\beta_{2}^{\prime}$ makes
$R_{\vec{n}}(\phi)$ become the trivial transformation $I$.

4\. From Eq. (B), one would notice that when one of the $\beta_{i}$ is added
by $2\pi$, the sign of $\cos\phi$ would change. So there is a minor problem in
step 3, that is, $R_{\vec{n}}(\phi)$ might be $\pm I$. But adding $2\pi$ to
$\beta_{i}$ does not change the geometry effect of rotation in the Bloch
sphere. Thus the analysis in step 3 still works, except that
$R_{\vec{n}}(\phi)$ might be $-I$. But we can always let
$\beta_{2}^{\prime}\leftarrow\beta_{2}^{\prime}+2k\pi$, where $k\in\\{0,1\\}$
such that $\cos\phi=+1$. Then this new pair of
$(\beta_{1}^{\prime},\beta_{2}^{\prime})$ makes $R_{\vec{n}}(\phi)=I$ and the
angle $\phi=0$. ∎

Because $(\beta_{1}^{\prime},\beta_{2}^{\prime})$ in Lemma 6 satisfy Eq.
(imag), we can always find a branch $\hat{f}$ of
$\beta_{2}=f(\beta_{1})+2l\pi$ such that
$\beta_{2}^{\prime}=\hat{f}(\beta_{1}^{\prime})$. This continuous function
$\hat{f}$ will be frequently used in the rest of this section.

###  4.3 Another pair of special parameters
$(\beta_{1}^{\prime\prime},\beta_{2}^{\prime\prime})$

######  Lemma 7.

Let $\beta_{1}^{\prime\prime}=-\alpha$ and
$\beta_{2}^{\prime\prime}=\hat{f}(\beta_{1}^{\prime\prime})$, then the
rotation angle $\phi$ of $R_{\vec{n}}(\phi)$ satisfy
$\cos\frac{\phi}{2}\in\\{\cos 4\phi^{\prime},-\cos 4\phi^{\prime}\\}$.

###### Proof.

Inspired by Ref. [4], we find that when the two phase angles have opposite
sign, i.e. $G^{\prime}(\alpha,-\alpha)=R_{\psi_{0}}(-\alpha)R_{R}(\alpha)$,
the rotation axis of $G^{\prime}(\alpha,-\alpha)$ satisfies Eq. (imag), and
the rotation angle $\phi_{d}$ is $4\phi^{\prime}$ with

$\sin\phi^{\prime}=\sqrt{\lambda}\sin\frac{\alpha}{2}.$ (38)

In fact, from Eq. (46) we have
$c_{\phi_{d}}=c^{2}_{\alpha}+s^{2}_{\alpha}(1-2\lambda)=1-2\lambda
s^{2}_{\alpha}=\cos 2\phi^{\prime}$. From Eq. (47), we know $\vec{n}_{d}$ is
collinear with $\left[-\sin\alpha\sin\theta,\ (1-\cos\alpha)\sin\theta,\
\sin\alpha(1-\cos\theta)\right]$, which is collinear with

$[-\sqrt{1-\lambda}\sin\alpha,\ \sqrt{1-\lambda}\,(1-\cos\alpha),\
\sqrt{\lambda}\sin\alpha].$

So $\sqrt{1-\lambda}\,n_{dz}+\sqrt{\lambda}\,n_{dx}=0$, which is Eq. (imag).

Let $\beta_{1}^{\prime\prime}=-\alpha$ and
$\beta_{2}^{\prime\prime}=\hat{f}(\beta_{1}^{\prime\prime})$. Then the
rotation axis of
$R_{\vec{n}}(\phi)=G^{\prime}(\alpha,\beta_{2}^{\prime\prime})G^{\prime}(\alpha,\beta_{1}^{\prime\prime})$
satisfy Eq. (imag) and the rotation angle is $\phi=8\phi^{\prime}$, because
the constituent two rotations have the same axis satisfying Eq. (imag), and
both have rotation angle $4\phi^{\prime}$. Similar to step 4 in the proof of
Lemma 6, from Eq. (B) of $\cos\frac{\phi}{2}$ we know that when one of the
$\beta_{i}$ is added by $2\pi$, the sign of $c_{\phi}$ would change. Thus we
can only guarantee that $(\beta_{1}^{\prime\prime},\beta_{2}^{\prime\prime})$
causes the rotation angle $\phi$ of $R_{\vec{n}}(\phi)$ to satisfy
$c_{\phi}\in\\{\cos 4\phi^{\prime},-\cos 4\phi^{\prime}\\}$. ∎

###  4.4 Lower bound of $k$

From the above three subsections, we know that there exists a continuous
function $\beta_{2}=\hat{f}(\beta_{1})$ defined on the closed interval
$[-\pi,\pi]$ such that:

  1. 1.

the pair of variable parameters $(\beta_{1},\beta_{2})$ determined by
$\hat{f}$ satisfy Eq. (imag);

  2. 2.

there exists $\beta_{1}^{\prime}$ such that the rotation angle $\phi=0$;

  3. 3.

there exists $\beta_{1}^{\prime\prime}$ such that
$\cos\frac{\phi}{2}\in\\{\cos 4\phi^{\prime},-\cos 4\phi^{\prime}\\}$.

Substitute $\beta_{2}=\hat{f}(\beta_{1})$ into Eq. (B) of
$\cos\frac{\phi}{2}$, and taking $\arccos$ on both sides, we obtain another
continuous function $\frac{\phi}{2}=g(\beta_{1})$ with range $[0,\pi]$. Let

$\phi_{0}:=\arccos|\cos 4\phi^{\prime}|\in[0,\frac{\pi}{2}].$ (39)

Then $\arccos(-|\cos 4\phi^{\prime}|)=\pi-\phi_{0}\geq\phi_{0}$, and thus
$g(\beta_{1}^{\prime\prime})\geq\phi_{0}$. Note that
$g(\beta_{1}^{\prime})=\arccos(1)=0$. Therefore, from the continuity of
function $g$, the range of $g(\beta_{1})$ must contain the interval
$[0,\phi_{0}]$ by the intermediate value theorem. Note that it may not contain
$\pi-\phi_{0}$, as Fig. 4 shows.

Figure 4:  Image of $\frac{\phi}{2}=g(\beta_{1}),\ \beta_{1}\in[-\pi,\pi]$
when $\lambda=0.2,\alpha=0.6\pi$. In this example, the range of $g$ contains
interval $[0,\phi_{0}]$ but does not contain $\pi-\phi_{0}$.

Because the range of $g(\beta_{1})$ contains $[0,\phi_{0}]$, when the number
of iterations $k$ is big enough such that

$\pi/k\leq\phi_{0},$ (40)

there exits $\beta_{1}^{\prime\prime\prime}$ such that
$\pi/k=g(\beta_{1}^{\prime\prime\prime})$. Recall that the equation obtained
from letting the real part of Eq. (32) to be zero is

$0=\sqrt{1-\lambda}\cos{(k\frac{\phi}{2})}-\sqrt{\lambda}\sin{(k\frac{\phi}{2})}\
n_{y},$ (real 1)

where $n_{y}$ satisfies

$s_{\phi}n_{y}=2\sqrt{\lambda(1-\lambda)}\Big{(}-\sin\alpha\cos\frac{\beta_{1}}{2}\sin\frac{\beta_{2}}{2}+2(1-2\lambda)\sin^{2}\frac{\alpha}{2}\sin\frac{\beta_{1}}{2}\sin\frac{\beta_{2}}{2}\Big{)},$

from Eq. (68). Substituting the two continuous function
$\beta_{2}=\hat{f}(\beta_{1})$ and $\frac{\phi}{2}=g(\beta_{1})$ into the RHS
of Eq. (real 1), we obtain a continuous function $F(\beta_{1})$ defined on the
closed interval $[-\pi,\pi]$. Note that $s_{k\phi}/s_{\phi}$ has limit $1$
when $\phi\to 0$, thus $F$ is actually continuous at $\phi=0$.

To sum up, we have

  1. 1.

$F(\beta_{1}^{\prime})=\sqrt{1-\lambda}>0$, since
$\frac{\phi}{2}=g(\beta_{1}^{\prime})=0$;

  2. 2.

$F(\beta_{1}^{\prime\prime\prime})=-\sqrt{1-\lambda}<0$, since
$\frac{\phi}{2}=g(\beta_{1}^{\prime\prime\prime})=\pi/k$.

Therefore, by the intermediate value theorem of continuous function on a
closed interval, there exists $\hat{\theta}_{1}$ such that
$F(\hat{\beta}_{1})=0$. Let $\hat{\beta}_{2}=\hat{f}(\hat{\beta}_{1})$. Then
$(\hat{\beta}_{1},\hat{\beta}_{2})$ satisfies the system of equations
$\eqref{im1},\eqref{real1}$.

It is easy to show that $\arccos|\cos x|=\big{|}x\
\mathrm{mod}[-\frac{\pi}{2},\frac{\pi}{2}]\big{|}$. Recall from Eqs. (39),
(38) that $\phi_{0}=\arccos|\cos 4\phi^{\prime}|$ where $\phi^{\prime}$
satisfies $\sin\phi^{\prime}=\sqrt{\lambda}\sin\frac{\alpha}{2}$. Therefore by
Eq. (40), whenever $k$, the number of iterations of $R_{\vec{n}}(\phi)$, is
greater than the following $k_{\mathrm{lower}}$, there exits a solution
$(\beta_{1},\beta_{2})$ to the system of equations (real), (imag). This
completes the proof of Theorem 1.

$k_{\mathrm{lower}}=\frac{\pi}{\Big{|}4\arcsin(\sqrt{\lambda}\sin\frac{\alpha}{2})\mod[-\frac{\pi}{2},\frac{\pi}{2}]\Big{|}}$
(41)

###  4.5 Differences in proof when $\beta$ is fixed

We now consider the case when $\beta$ in $G(\alpha,\beta)$ is fixed. It is
almost the same as in the previous three subsections to prove the existence of
solution $(\alpha_{1},\alpha_{2})$ to Eqs. (real), (imag), or to be more
precise, Eqs. (36), (37), when the number of iterations $k$ of
$F_{xr,\beta}=G(\alpha_{2},\beta)G(\alpha_{1},\beta)$ is greater than
$k_{\text{lower}}$ as shown in Eq. (5). Because we are treating the iteration
$F_{xr,*}$ as a whole.

However, there are at least three differences in the proof worth mentioning:

  1. 1.

In parallel to Section 4.1, we need to obtain the continuous function
$\alpha_{1}=f(\alpha_{2})$ from Eq. (imag) rather than
$\alpha_{2}=f(\alpha_{1})$. This is because in the next step corresponding to
Section 4.2, we will find a specific angle $\alpha_{2}^{\prime}$ such that
$R_{\vec{n}}(\phi)$ keeps $\ket{R}$ still. So $\alpha_{2}$ needs to be the
variable parameter of $(\alpha_{1},\alpha_{2})$ in our proof.

  2. 2.

Rather than showing that there exits a special angle $\beta_{1}^{\prime}$ such
that $R_{\vec{n}}(\phi)$ keeps $\ket{\psi_{0}}$ still, we will instead prove
that there exists an angle $\alpha_{2}^{\prime}$ such that $R_{\vec{n}}(\phi)$
keeps $\ket{R}$ still, this follows easily from Fig. 5.

  3. 3.

Parallel to Section 4.3, we will instead let
$\alpha_{2}^{\prime\prime}=-\beta$, and Eq. (38) now becomes

$\sin\phi^{\prime}=\sqrt{\lambda}\sin\frac{\beta}{2}.$ (42)

Thus, the lower bound $k_{\text{lower}}$ with $\beta$ being fixed [see Eq.
(5)] is obtained by changing $\alpha$ to $\beta$ in Eq. (41).

$A$$\ket{R}$$\ket{T}$$\ket{\psi_{0}}$$E$$E$$F(F^{\prime})$$G$$L$$C$$\alpha_{1}$$\beta$$\alpha_{2}$$\beta$
Figure 5:  Bloch sphere interpretation of the effect of
$F_{xr,\beta}=S_{r}(\beta)S_{o}(\alpha_{2})S_{r}(\beta)S_{o}(\alpha_{1})$ on
state vector $\ket{R}=[0,0,1]$. This is a view of the Bloch sphere along its
$y$-axis. $S_{o}(\alpha)$ represents a rotation about $\ket{R}$ (i.e.
$\overline{AE}$) by $\alpha$, and $S_{r}(\beta)$ represents a rotation about
$\ket{\psi_{0}}$ (i.e. $\overline{AC}$) by $\beta$. The four red arrow lines
represents trajectory
$E-\overset{\frown}{EF^{\prime}}-\overset{\frown}{F^{\prime}GF}-\overset{\frown}{FE}$
of $\ket{R}$ under operator $F_{xr,\beta}$, and shows that there exists an
angle $\alpha_{2}$ such that $F_{xr,\beta}$ keeps $\ket{R}$ still.

##  5 Conclusion

In this paper we have proposed a search framework with adjustable parameters,
in which given the phase oracle $S_{o}(\alpha)$ with an arbitrary angle
$\alpha$ or the phase rotation $S_{r}(\beta)$ with an arbitrary angle $\beta$,
we can always construct a quantum exact search algorithm without sacrificing
the quadratic speedup advantage. In technique, we have proposed the fixed-
axis-rotation (FXR) method which computes the state of a two-dimensional
system in a concise way. Two applications of the proposed search framework
have been developed. Possible future research may include extending this
framework to fixed-point or robust quantum search [21, 22], as well as looking
for more applications.

## References

  * [1] Lov K. Grover.  Quantum mechanics helps in searching for a needle in a haystack.  Phys. Rev. Lett., 79:325–328, Jul 1997.
  * [2] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp.  Quantum amplitude amplification and estimation.  AMS Contemporary Mathematics Series, 305, 06 2000.
  * [3] Peter Hoyer.  On arbitrary phases in quantum amplitude amplification.  Physical Review A, 62, 06 2000.
  * [4] G. L. Long.  Grover algorithm with zero theoretical failure rate.  Phys. Rev. A, 64:022307, Jul 2001.
  * [5] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald De Wolf.  Quantum lower bounds by polynomials.  Journal of the ACM (JACM), 48(4):778–797, 2001.
  * [6] Tanay Roy, Liang Jiang, and David I. Schuster.  Deterministic grover search with a restricted oracle.  Phys. Rev. Research, 4:L022013, Apr 2022.
  * [7] Markus Hunziker and David A. Meyer.  Quantum algorithms for highly structured search problems.  Quantum Information Processing, 1(3):145–154, Jun 2002.
  * [8] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp.  Tight bounds on quantum searching.  Fortschritte der Physik: Progress of Physics, 46(4-5):493–505, 1998\.
  * [9] Lvzhou Li, Jingquan Luo, and Yongzhen Xu.  Winning mastermind overwhelmingly on quantum computers.  arXiv:2207.09356, 2022.
  * [10] Harry Buhrman and Ronald de Wolf.  Complexity measures and decision tree complexity: a survey.  Theoretical Computer Science, 288(1):21–43, 2002.  Complexity and Logic.
  * [11] Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, and Ronald de Wolf.  Quantum algorithms for element distinctness.  SIAM Journal on Computing, 34(6):1324–1330, 2005.
  * [12] A. Ambainis.  Quantum walk algorithm for element distinctness.  In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 22–31, 2004.
  * [13] Andris Ambainis.  Quantum walk algorithm for element distinctness.  SIAM Journal on Computing, 37(1):210–239, 2007.
  * [14] Yaoyun Shi.  Quantum lower bounds for the collision and the element distinctness problems.  In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 513–519, 2002.
  * [15] Scott Aaronson and Yaoyun Shi.  Quantum lower bounds for the collision and the element distinctness problems.  J. ACM, 51(4):595–605, jul 2004.
  * [16] Andris Ambainis.  Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range.  Theory of Computing, 1(3):37–46, 2005.
  * [17] Guanzhong Li and Lvzhou Li.  Exact quantum algorithm for the element distinctness promise problem.  in preparation.
  * [18] Renato Portugal.  Element distinctness revisited.  Quantum Information Processing, 17(7):163, May 2018.
  * [19] Renato Portugal.  Element Distinctness, pages 201–221.  Springer International Publishing, Cham, 2018.
  * [20] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, 2010.
  * [21] Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang.  Fixed-point quantum search with an optimal number of queries.  Phys. Rev. Lett., 113:210501, Nov 2014.
  * [22] Yongzhen Xu, Delong Zhang, and Lvzhou Li.  Robust quantum walk search.  arXiv preprint arXiv:2111.09012 (to appear in Physical Review A), 2021.

##  Appendix A Proof of Lemma 5

Proof of Lemma 5: Suppose $S_{o}(\alpha)=e^{i\varphi}R_{\vec{n}}(\phi)$ [see
their definition in Eqs. (15),(23)], tracing (i.e. summing up diagonal
elements of) the matrix on both sides, we have
$1+e^{i\alpha}=2\cos\phi\,e^{i\varphi}$. By parallelogram rule of adding two
complex value, the left hand side (LHS) has phase angle $\alpha$ (angle
between the positive $x$-axis and a ray from the origin to the point $(x,y)$
representing complex value $z=x+iy$ in the $xy$-plane), so we can take
$\varphi=\alpha/2$. Note that $S_{o}(\alpha)$ is diagonal, so it’s obvious
that $e^{-i\alpha/2}S_{o}(\alpha)=\cos\frac{\alpha}{2}\
I-i\sin\frac{\alpha}{2}\ Z$, which by Lemma 3.(2) represents in the Bloch
sphere a rotation about $\ket{R}=[0,0,1]^{T}$ by an angle of $\alpha$.

Similarly, tracing both sides of $S_{r}(\beta)=e^{i\varphi}R_{\vec{n}}(\phi)$
[defined in Eq. (17)], we have $1+e^{-i\beta}=2\cos\phi\,e^{i\varphi}$, so
$\varphi=-\beta/2$. By comparing the two sides of equation
$R_{\vec{n}}(\phi)=e^{i\beta/2}S_{r}(\beta)$, we obtain the rotation angle
$\phi$ as follows:

$\displaystyle\cos\phi$ $\displaystyle=e^{i\beta/2}\frac{1}{2}(s_{11}+s_{22})$
$\displaystyle=e^{i\beta/2}\frac{1+e^{-i\beta}}{2}$
$\displaystyle=\cos\frac{\beta}{2},$

where $s_{ij}$ is the $(i,j)$-element of $S_{r}(\beta)$ for $i,j\in\\{1,2\\}$.
Similarly for the $z$-coordinate $n_{z}$ of the rotation axis $\vec{n}$, we
have

$\displaystyle s_{\phi}n_{z}$
$\displaystyle=e^{i\beta/2}\frac{1}{2}(s_{11}-s_{22})i$
$\displaystyle=e^{i\beta/2}\frac{-1}{2}(1-e^{-i\beta})(1-2\lambda)i$
$\displaystyle=-i\sin\frac{\beta}{2}(1-2\lambda)i$
$\displaystyle=\sin\frac{\beta}{2}\cos\theta.$

Recall that $\sqrt{\lambda}=\sin\frac{\theta}{2}$ and
$\sqrt{1-\lambda}=\cos\frac{\theta}{2}$ from Eq. (27), thus
$\cos\theta=1-2\sin^{2}\frac{\theta}{2}=1-2\lambda$ in the last equality. As
for the $x$-coordinate $n_{x}$ of the rotation axis $\vec{n}$:

$\displaystyle s_{\phi}n_{x}$
$\displaystyle=e^{i\beta/2}\frac{1}{2}(s_{12}+s_{21})i$
$\displaystyle=e^{i\beta/2}(-1)(1-e^{-i\beta})\sqrt{\lambda(1-\lambda)}\ i$
$\displaystyle=-i\sin(\frac{\beta}{2})\ 2\sqrt{\lambda(1-\lambda)}\ i$
$\displaystyle=\sin\frac{\beta}{2}\sin\theta.$

Note that in the last equality we use
$\sin\theta=2\sin\theta\cos\theta=2\sqrt{\lambda(1-\lambda)}$. Finally for the
$y$-coordinate $n_{y}$ of the rotation axis $\vec{n}$:

$s_{\phi}n_{y}=e^{i\beta/2}\frac{1}{2}(s_{21}-s_{12})=0.$

Therefore $e^{i\beta/2}S_{r}(\beta)=\cos\frac{\beta}{2}\
I-i\sin\frac{\beta}{2}(\sin\theta\ X+\cos\theta\ Z)$, which is a rotation
about $\ket{\psi_{0}}=[\sin\theta,0,\cos\theta]$ by an angle of $\beta$.
$\blacksquare$

##  Appendix B Rotation parameters of $F^{\prime}_{xr,\alpha}$ and
$F^{\prime}_{xr,\beta}$

We will calculate the rotation parameters $c_{\phi}$ and $s_{\phi}\vec{n}$ of
$F^{\prime}_{xr,\alpha}=G^{\prime}(\alpha,\beta_{2})G^{\prime}(\alpha,\beta_{1})$
and
$F^{\prime}_{xr,\beta}=G^{\prime}(\alpha_{2},\beta)G^{\prime}(\alpha_{1},\beta)$,
filling in details of the proof outline of Lemma 4.

We first calculate the effect of $G^{\prime}(\alpha,\beta)$ directly as
follows:

$\displaystyle G^{\prime}(\alpha,\beta)$
$\displaystyle=R_{\psi_{0}}(\beta)R_{R}(\alpha)$ (43)
$\displaystyle=[c_{\beta}I-i\,s_{\beta}(s_{2\theta}X+c_{2\theta}Z)]\,[c_{\alpha}I-i\,s_{\alpha}Z]$
(44)
$\displaystyle=I(c_{\beta}c_{\alpha}-s_{\beta}s_{\alpha}c_{2\theta})-iX(s_{\beta}c_{\alpha}s_{2\theta})-iY(-s_{\beta}s_{\alpha}s_{2\theta})-iZ(c_{\beta}s_{\alpha}+S_{\beta}c_{\alpha}c_{2\theta}).$
(45)

Therefore, we have

$\displaystyle c_{\phi}$
$\displaystyle=c_{\beta}c_{\alpha}-s_{\beta}s_{\alpha}c_{2\theta},$ (46)
$\displaystyle s_{\phi}\vec{n}$
$\displaystyle=(s_{\beta}c_{\alpha}s_{2\theta},\,-s_{\beta}s_{\alpha}s_{2\theta},\,c_{\beta}s_{\alpha}+s_{\beta}c_{\alpha}c_{2\theta}).$
(47)

To simplify notations, we order the trigonometric functions in each monomial
by the subscript’s order $(\alpha_{1},\alpha_{2},\beta_{1},\beta_{2})$. For
example, $ccss$ stands for
$c_{\alpha_{1}}c_{\alpha_{2}}s_{\beta_{1}}s_{\beta_{2}}$, and furthermore,
$ccs_{1+2}$ stands for $c_{\alpha_{1}}c_{\alpha_{2}}s_{\beta_{1}+\beta_{2}}$.
With this convention in mind, we first calculate the rotation angle $\phi$ of
$F^{\prime}_{xr}=G^{\prime}(\alpha_{2},\beta_{2})G^{\prime}(\alpha_{1},\beta_{1})$
using Lemma 3.(4) and Eqs. (46), (47) as follows.

$\displaystyle c_{\phi}$
$\displaystyle=(c_{\alpha_{1}}c_{\beta_{1}}-s_{\alpha_{1}}s_{\beta_{1}}c_{2\theta})(c_{\alpha_{2}}c_{\beta_{2}}-s_{\alpha_{2}}s_{\beta_{2}}c_{2\theta})$
$\displaystyle\quad-ccss\cdot s_{2\theta}^{2}-ssss\cdot
s_{2\theta}^{2}-(s_{\alpha_{1}}c_{\beta_{1}}+c_{\alpha_{1}}s_{\beta_{1}}c_{2\theta})(s_{\alpha_{2}}c_{\beta_{2}}+c_{\alpha_{2}}s_{\beta_{2}}c_{2\theta})$
(48) $\displaystyle=cccc-c_{2\theta}(scsc+cscs)+c_{2\theta}^{2}ssss$
$\displaystyle\quad-ccss-
ssss+c_{2\theta}^{2}(ccss+ssss)-(sscc+c_{2\theta}(cssc+sccs)+c_{2\theta}^{2}ccss)$
(49) $\displaystyle=(cccc-ccss-sscc-
ssss)-(1-2\lambda)(scsc+cscs+cssc+sccs)+(1-2\lambda)^{2}2ssss.$ (50)

Regrouping terms by the oder of $\lambda$, we obtain coefficient of the
constant term $\lambda^{0}=1$ as

$\displaystyle ccc_{1+2}-ssc_{1+2}-scs_{1+2}-css_{1+2}$ (51) $\displaystyle=$
$\displaystyle c_{1+2}c_{1+2}-s_{1+2}s_{1+2}$ (52) $\displaystyle=$
$\displaystyle\cos\frac{\alpha_{1}+\alpha_{2}+\beta_{1}+\beta_{2}}{2}.$ (53)

The coefficients of $\lambda$ and $\lambda^{2}$ are
$2\times(s_{1+2}s_{1+2}-4ssss)$ and $8ssss$, respectively. Therefore, for
$F^{\prime}_{xr,\alpha}=G^{\prime}(\alpha,\beta_{2})G^{\prime}(\alpha,\beta_{1})$,
its rotation angle $\phi$ satisfies

$\displaystyle c_{\phi}$
$\displaystyle=\cos(\alpha+\frac{\beta_{1}+\beta_{2}}{2})+2\lambda(\sin\alpha\sin\frac{\beta_{1}+\beta_{2}}{2}-4\sin^{2}\frac{\alpha}{2}\sin\frac{\beta_{1}}{2}\sin\frac{\beta_{2}}{2})$
$\displaystyle\quad+8\lambda^{2}\sin^{2}\frac{\alpha}{2}\sin\frac{\beta_{1}}{2}\sin\frac{\beta_{2}}{2}.$
(54)

And for
$F^{\prime}_{xr,\beta}=G^{\prime}(\alpha_{2},\beta)G^{\prime}(\alpha_{1},\beta)$,
its rotation angle $\phi$ satisfies

$\displaystyle c_{\phi}$
$\displaystyle=\cos(\frac{\alpha_{1}+\alpha_{2}}{2}+\beta)+2\lambda(\sin\frac{\alpha_{1}+\alpha_{2}}{2}\sin\beta-4\sin\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}\sin^{2}\frac{\beta}{2})$
$\displaystyle\quad+8\lambda^{2}\sin\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}\sin^{2}\frac{\beta}{2}.$
(55)

We now calculate the $x-$coordinates $n_{x}$ of $F^{\prime}_{xr}$’s rotation
axis $\vec{n}$ as follows

$\displaystyle s_{\phi}n_{x}$
$\displaystyle=c_{2}n_{1x}+c_{1}n_{2x}+n_{2y}n_{1z}-n_{1y}n_{2z}$ (56)
$\displaystyle=(c_{\alpha_{2}}c_{\beta_{2}}-s_{\alpha_{2}}s_{\beta_{2}}c_{2\theta})c_{\alpha_{1}}s_{\beta_{1}}s_{2\theta}+(c_{\alpha_{1}}c_{\beta_{1}}-s_{\alpha_{1}}s_{\beta_{1}}c_{2\theta})c_{\alpha_{2}}s_{\beta_{2}}s_{2\theta}$
$\displaystyle\quad-
s_{\beta_{2}}s_{\alpha_{2}}s_{2\theta}(s_{\alpha_{1}}c_{\beta_{1}}+c_{\alpha_{1}}s_{\beta_{1}}c_{2\theta})+s_{\beta_{1}}s_{\alpha_{1}}s_{2\theta}(s_{\alpha_{2}}c_{\beta_{2}}+c_{\alpha_{2}}s_{\beta_{2}}c_{2\theta})$
(57) $\displaystyle s_{2\theta}\times$ $\displaystyle=ccsc-csss\cdot
c_{2\theta}+cccs-scss\cdot c_{2\theta}$ $\displaystyle\quad-sscs-csss\cdot
c_{2\theta}+sssc+scss\cdot c_{2\theta}$ (58) $\displaystyle s_{2\theta}\times$
$\displaystyle=c_{1-2}sc+c_{1+2}cs-c_{2\theta}2csss$ (59)
$\displaystyle\quad\text{or:}\ ccs_{1+2}-sss_{1-2}-c_{2\theta}2csss.$ (60)

The notation ‘$s_{2\theta}\times$’ is actually on the right hand side of the
equal sign, we put it on the left to introduce less brackets. Therefore, for
$F^{\prime}_{xr,\alpha}$, we have

$s_{\phi}n_{x}=2\sqrt{\lambda(1-\lambda)}\Big{(}\sin\frac{\beta_{1}}{2}\cos\frac{\beta_{2}}{2}+\cos\alpha\cos\frac{\beta_{1}}{2}\sin\frac{\beta_{2}}{2}-(1-2\lambda)\sin\alpha\sin\frac{\beta_{1}}{2}\sin\frac{\beta_{2}}{2}\Big{)}.$
(61)

And for $F^{\prime}_{xr,\beta}$, we have

$s_{\phi}n_{x}=2\sqrt{\lambda(1-\lambda)}\Big{(}\cos\frac{\alpha_{1}}{2}\cos\frac{\alpha_{2}}{2}\sin\beta-2(1-2\lambda)\cos\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}\sin^{2}\frac{\beta}{2}\Big{)}.$
(62)

We now calculate the $y-$coordinates $n_{y}$ of $F^{\prime}_{xr}$’s rotation
axis $\vec{n}$ as follows

$\displaystyle s_{\phi}n_{y}$
$\displaystyle=c_{2}n_{1y}+c_{1}n_{2y}-n_{2x}n_{1z}+n_{1x}n_{2z}$ (63)
$\displaystyle=-(c_{\alpha_{2}}c_{\beta_{2}}-s_{\alpha_{2}}s_{\beta_{2}}c_{2\theta})s_{\beta_{1}}s_{\alpha_{1}}s_{2\theta}-(c_{\alpha_{1}}c_{\beta_{1}}-s_{\alpha_{1}}s_{\beta_{1}}c_{2\theta})s_{\beta_{2}}s_{\alpha_{2}}s_{2\theta}$
$\displaystyle\quad-
c_{\alpha_{2}}s_{\beta_{2}}s_{2\theta}(s_{\alpha_{1}}c_{\beta_{1}}+c_{\alpha_{1}}s_{\beta_{1}}c_{2\theta})+c_{\alpha_{1}}s_{\beta_{1}}s_{2\theta}(s_{\alpha_{2}}c_{\beta_{2}}+c_{\alpha_{2}}s_{\beta_{2}}c_{2\theta})$
(64) $\displaystyle s_{2\theta}\times$ $\displaystyle=-scsc+ssss\cdot
c_{2\theta}-cscs+ssss\cdot c_{2\theta}$ $\displaystyle\quad-sccs-ccss\cdot
c_{2\theta}+cssc+ccss\cdot c_{2\theta}$ (65) $\displaystyle s_{2\theta}\times$
$\displaystyle=-s_{1-2}sc-s_{1+2}cs+2c_{2\theta}ssss$ (66)
$\displaystyle\quad\text{or:}\ -scs_{1+2}+css_{1-2}+2c_{2\theta}ssss.$ (67)

Therefore, for $F^{\prime}_{xr,\alpha}$, we have

$s_{\phi}n_{y}=2\sqrt{\lambda(1-\lambda)}\Big{(}-\sin\alpha\cos\frac{\beta_{1}}{2}\sin\frac{\beta_{2}}{2}+2(1-2\lambda)\sin^{2}\frac{\alpha}{2}\sin\frac{\beta_{1}}{2}\sin\frac{\beta_{2}}{2}\Big{)}.$
(68)

And for $F^{\prime}_{xr,\beta}$, we have

$s_{\phi}n_{y}=2\sqrt{\lambda(1-\lambda)}\Big{(}-\sin\frac{\alpha_{1}}{2}\cos\frac{\alpha_{2}}{2}\sin\beta+2(1-2\lambda)\sin\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}\sin^{2}\frac{\beta}{2}\Big{)}.$
(69)

Finally, we calculate the $z-$coordinates $n_{z}$ of $F^{\prime}_{xr}$’s
rotation axis $\vec{n}$ as follows

$\displaystyle s_{\phi}n_{z}$
$\displaystyle=c_{2}n_{1z}+c_{1}n_{2z}+n_{2x}n_{1y}-n_{1x}n_{2y}$ (70)
$\displaystyle=(c_{\alpha_{2}}c_{\beta_{2}}-s_{\alpha_{2}}s_{\beta_{2}}c_{2\theta})(s_{\alpha_{1}}c_{\beta_{1}}+c_{\alpha_{1}}s_{\beta_{1}}c_{2\theta})+(c_{\alpha_{1}}c_{\beta_{1}}-s_{\alpha_{1}}s_{\beta_{1}}c_{2\theta})(s_{\alpha_{2}}c_{\beta_{2}}+c_{\alpha_{2}}s_{\beta_{2}}c_{2\theta})$
$\displaystyle\quad-c_{\alpha_{2}}s_{\beta_{2}}s_{2\theta}\cdot
s_{\beta_{1}}s_{\alpha_{1}}s_{2\theta}+c_{\alpha_{1}}s_{\beta_{1}}s_{2\theta}\cdot
s_{\beta_{2}}s_{\alpha_{2}}s_{2\theta}.$ (71)

The last line is equal to $-scss+csss+c_{2\theta}^{2}(scss-csss)$. If we
regard $c_{2\theta}$ as the pivot, and consider regrouping the terms by
$1,c_{2\theta},c_{2\theta}^{2}$, we have

$\displaystyle s_{\phi}n_{z}$ $\displaystyle=(sccc+cscc-
scss+csss)+c_{2\theta}c_{1+2}s_{1+2}-2c_{2\theta}^{2}csss.$ (72)

Therefore, for $F^{\prime}_{xr,\alpha}$, we have

$s_{\phi}n_{z}=\sin\alpha\cos\frac{\beta_{1}}{2}\cos\frac{\beta_{2}}{2}+(1-2\lambda)\cos\alpha\sin\frac{\beta_{1}+\beta_{2}}{2}-(1-2\lambda)^{2}\sin\alpha\sin\frac{\beta_{1}}{2}\sin\frac{\beta_{2}}{2}.$
(73)

And for $F^{\prime}_{xr,\beta}$, we have

$\displaystyle s_{\phi}n_{z}$
$\displaystyle=\sin\frac{\alpha_{1}}{2}\cos\frac{\alpha_{2}}{2}\cos\beta+\cos\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}$
$\displaystyle\quad+(1-2\lambda)\cos\frac{\alpha_{1}+\alpha_{2}}{2}\sin\beta-2(1-2\lambda)^{2}\cos\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}\sin^{2}\frac{\beta}{2}.$
(74)

##  Appendix C Continuity of $\beta_{2}=f(\beta_{1})$

######  Lemma 8.

When $\beta_{1}\in[-\pi,\pi]$, the function $\beta_{2}=f(\beta_{1})$ obtained
by solving Eq. (imag), or equivalently Eq. (35), as shown in Section 4.1 is
inherently continuous.

###### Proof.

We copy Eq. (2f1) in Section 4.1 here for convenience:

$t_{2}=-\frac{t_{1}\big{[}(1-2\lambda)c_{2\alpha}+2\lambda\big{]}+s_{2\alpha}}{c_{2\alpha}-t_{1}s_{2\alpha}(1-2\lambda)}.$
(2f1)

Note that Eq. (35) is equivalent to:

$s_{2}\big{[}c_{1}c_{2\alpha}-s_{1}s_{2\alpha}(1-2\lambda)\big{]}=-s_{1}c_{2}\big{[}(1-2\lambda)c_{2\alpha}+2\lambda\big{]}-c_{1}c_{2}s_{2\alpha}.$
(im 2)

The potential ‘discontinuity point’ of $f(\beta_{1})$ is the solution of the
equation $t_{1}=\frac{c_{2\alpha}}{s_{2\alpha}(1-2\lambda)}$. To avoid the
denominator of its RHS become zero, the following first two cases need to be
considered first.

  1. 1.

$\alpha=\pi$. Then $s_{2\alpha}=\sin\alpha=0,c_{2\alpha}=-1$, so Eq. (2f1)
becomes $t_{2}=-(1-4\lambda)t_{1}$, and we denote it by Eq. (2f1-1). Eq. (im
2) now also simplifies to $s_{2}c_{1}=-(1-4\lambda)s_{1}c_{2}$ (im2-1). When
$\beta_{1}\in(-\pi,\pi)$, function $\beta_{2}=f(\beta_{1})$ obtained by taking
$\arctan$ of Eq. (2f1-1) is continuous, so we only need to consider the
‘discontinuity point’ $\beta_{1}=\pm\pi$ of Eq. (2f1-1). We have
$c_{1}=0,s_{1}=1$. Substituting them into Eq. (im2-1), we have
$0=(1-4\lambda)\cos(\beta_{2}/2)$, which has solutions $\beta_{2}=\pm\pi$.
Moreover, $\beta_{2}=f(\beta_{1})\to\pm\pi$ when $\beta_{1}\to\pm\pi$.
Therefore $f$ is inherently continuous at $\beta_{1}=\pm\pi$.

  2. 2.

$\alpha\neq\pi,\lambda=\frac{1}{2}$. Then Eq. (2f1) becomes
$t_{2}=-\frac{t_{1}+\sin\alpha}{\cos\alpha}$ (2f1-2) and Eq. (im 2) becomes
$s_{2}c_{1}\cos\alpha=-s_{1}c_{2}-c_{1}s_{2}\sin\alpha$ (im2-2). Note that the
denominator of Eq. (2f1-2) is $\cos\alpha$, so we will need to discuss whether
$\alpha=\pi/2$:

    1. (a)

$\alpha=\pi/2$. Then Eq. (im2-2) becomes
$0=\sin(\frac{\beta_{1}+\beta_{2}}{2})$. Solving it produce
$\beta_{2}=f(\beta_{1})=-\beta_{1}+2l\pi$ for $l\in\mathbb{Z}$, so $f$ is
continuous.

    2. (b)

$\alpha\neq\pi/2$. Consider the ‘discontinuity point’ $\beta_{1}=\pm\pi$ of
Eq. (2f1-2). Substituting $\beta_{1}=\pm\pi$ into Eq. (im2-2), we obtain
$0=c_{2}$, so $\beta_{2}=\pm\pi$. Moreover, the function
$\beta_{2}=f(\beta_{1})$ obtained by taking $\arctan$ of Eq. (2f1-2) will
$\to\pm\pi$ when $\beta_{1}\to\pm\pi$. Therefore $f$ is inherently continuous
at $\beta_{1}=\pm\pi$.

  3. 3.

$\alpha\neq\pi,\lambda\neq\frac{1}{2}$. We first consider the ‘discontinuity
point’ which cause the denominator of Eq. (2f1) to become zero, then we have
$t_{1}=\frac{c_{2\alpha}}{s_{2\alpha}(1-2\lambda)}$ (suppose by taking
$\arctan$ of both sides, its solution is the ‘discontinuity point’
$\beta_{1}^{\prime}$), which is equivalent to
$c_{1}c_{2\alpha}-s_{1}s_{2\alpha}(1-2\lambda)=0$. Substituting it into Eq.
(im 2), we have
$0=s_{1}c_{2}\big{[}(1-2\lambda)c_{2\alpha}+2\lambda\big{]}+c_{1}c_{2}s_{2\alpha}$,
which has solution $\beta_{2}=\pm\pi$. Moreover, the function
$\beta_{2}=f(\beta_{1})$ obtained by taking $\arctan$ of Eq. (2f1) will
$\to\infty$ (so $\beta_{2}\to\pm\pi$) when $\beta_{1}\to\beta_{1}^{\prime}$.
Therefore $f$ is inherently continuous at $\beta_{1}^{\prime}$. Next, we
consider the ‘discontinuity point’ $\beta_{1}=\pm\pi$ of Eq. (2f1). Now
$c_{1}=0,s_{1}=1$. Substituting them into Eq. (im 2), we have
$s_{2}s_{2\alpha}(1-2\lambda)=c_{2}\big{[}(1-2\lambda)c_{2\alpha}+2\lambda\big{]}$,
which has solution
$t_{2}^{\prime}:=\frac{(1-2\lambda)c_{2\alpha}+2\lambda}{s_{2\alpha}(1-2\lambda)}$.
Moreover, from Eq. (2f1), $t_{2}\to t_{2}^{\prime}$ when $\beta_{1}\to\pi$, so
$f$ is also continuous at $\beta_{1}=\pm\pi$.

∎


# On statistical arc length of the Riemann $Z(t)$-curve

Jan Moser  Department of Mathematical Analysis and Numerical Mathematics,
Comenius University, Mlynska Dolina M105, 842 48 Bratislava, SLOVAKIA
<EMAIL_ADDRESS>
###### Abstract.

In this paper we study certain stochastic process that is generated by the
Riemann-Siegel formula. Further, we construct corresponding statistical model
by a way similar to those used in telecommunication. We define statistical arc
length of the Riemann $Z(t)$-curve in this model and obtain an asymptotic
formula for that length. This paper is English remake of our work of reference
[4].

###### Key words and phrases:

Riemann zeta-function

##  1\. Introduction

### 1.1.

In the paper [5] we have studied the following integral

(1.1) $\int_{T}^{T+H}\sqrt{1+\\{Z^{\prime}(t)\\}^{2}}{\rm d}t=L(T,H)=L,$

i.e. the arc length of the Riemann curve

$y=Z(t),\ t\in[T,T+H],\ T\to\infty,$

where (see [7], pp. 79, 329)

$\begin{split}&Z(t)=e^{i\vartheta(t)}\zeta\left(\frac{1}{2}+it\right),\\\
&\vartheta(t)=-\frac{t}{2}\ln\pi+\mbox{Im}\ln\Gamma\left(\frac{1}{4}+i\frac{t}{2}\right).\end{split}$

Next, we will denote the roots of the equations

$Z(t)=0,\quad Z^{\prime}(t)=0$

by the symbols

$\\{\gamma\\},\quad\\{t_{0}\\};\quad t_{0}\not=\gamma$

correspondingly.

######  Remark 1.

On the Riemann hypothesis, the points of the sequences $\\{\gamma\\}$ and
$\\{t_{0}\\}$ are separated each from other (see [2], Corollary 3), i.e. in
this case we have

$\gamma^{\prime}<t_{0}<\gamma^{\prime\prime},$

where $\gamma^{\prime},\gamma^{\prime\prime}$ are neighboring points of the
sequence $\\{\gamma\\}$. Of course, $Z(t_{0})$ is an extremal value of the
function $Z(t)$ in some neighborhood of the point $t_{0}$.

Namely, we have proved (see [5]) for integral (1.1) the following formula

(1.2) $\begin{split}&\int_{T}^{T+H}\sqrt{1+\\{Z^{\prime}(t)\\}^{2}}{\rm
d}t=2\sum_{T\leq t_{0}\leq T+H}|Z(t_{0})|+\Theta
H+\mathcal{O}\left(T^{\frac{A}{\ln\ln T}}\right),\\\ &T\to\infty,\
\Theta=\Theta(T,H)\in(0,1),\ H=T^{\epsilon}\end{split}$

for every fixed $\epsilon>0$.

The proof of the formula (1.2) was based on the following

(1.3)
$\begin{split}&Z^{\prime}(t)=-2\sum_{n<P}\frac{1}{\sqrt{n}}\ln\frac{P}{n}\sin\\{\vartheta(t)-t\ln
n\\}+\\\ &+\mathcal{O}(T^{-1/4}\ln T),\ t\in[T,T+U],\
U\in(0,\sqrt{T}],\end{split}$

that was obtained in our paper [3] as a variant of the Riemann-Siegel formula.
One sight on formulae (1.1)–(1.3) is sufficient for insight of the difficulty
of the problem about the asymptotic formula of the arc length of the Riemann
curve.

### 1.2.

In connection with formulae (1.1)–(1.3) we give the following

######  Remark 2.

The main difficulty lies probably in that we are absent of something like
famous Dirac procedure

$\sqrt{m^{2}c^{2}+p_{1}^{2}+p_{2}^{2}+p_{3}^{2}}=\alpha_{1}p_{1}+\alpha_{2}p_{2}+\alpha_{3}p_{3}+\beta,$

i.e. extracting of the square root of the operator - see [1], p. 255,
equations (5), (7). This was the way towards Dirac’s relativistic wave
equation for the electron - the fundamental law of the quantum mechanics.

### 1.3.

Next, let us remind, in connection with (1.1)–(1.3), that in our recent paper
we have proved the following result on metamorphoses: there is an infinite set
of elements

(1.4) $\\{\alpha_{0}(T),\alpha_{1}(T),\dots,\alpha_{k}(T)\\},\
T\in(T_{0},+\infty),\ T_{0}>0$

where $T_{0}$ is sufficiently big, such that

(1.5)
$\begin{split}&\prod_{r=1}^{k}\left|\sum_{n\leq\tau(\alpha_{r})}\frac{2}{\sqrt{n}}\cos\\{\vartheta(\alpha_{r})-\alpha_{r}\ln
n\\}+\mathcal{O}(\alpha_{r}^{-1/4})\right|\sim\\\
&\sim\sqrt{\frac{\Lambda}{\left|\sum_{n\leq\tau(\alpha_{0})}\frac{2}{\sqrt{n}}\cos\\{\vartheta(\alpha_{0})-\alpha_{0}\ln
n\\}+\mathcal{O}(\alpha_{0}^{-1/4})\right|}},\\\ &T\to\infty,\end{split}$

where

$\Lambda=\sqrt{2\pi}\frac{H}{H_{k}}\ln^{k}T,\ \tau(t)=\sqrt{\frac{t}{2\pi}},\
k=1,\dots,k_{0},\ k_{0}\in\mathbb{N},$

i.e. to the infinite subset

$\\{\alpha_{1}(T),\dots,\alpha_{k}(T)\\}$

an infinite set of metamorphoses of the multiform on the left-hand side of
(1.5) into quite distinct form on the right-hand side of (1.5) corresponds.

Now we rewrite the formula (1.5) in the following form

(1.6)
$\begin{split}&\sqrt{\frac{1}{\Lambda}\left|\sum_{n\leq\tau(\alpha_{0})}\frac{2}{\sqrt{n}}\cos\\{\vartheta(\alpha_{0})-\alpha_{0}\ln
n\\}+\mathcal{O}(\alpha_{0}^{-1/4})\right|}\sim\\\
&\sim\prod_{r=1}^{k}\left|\sum_{n\leq\tau(\alpha_{r})}\frac{2}{\sqrt{n}}\cos\\{\vartheta(\alpha_{r})-\alpha_{r}\ln
n\\}+\mathcal{O}(\alpha_{r}^{-1/4})\right|^{-1}.\end{split}$

######  Remark 3.

We see, in connection with (1.1)–(1.3) and the Remark 2, that the square root
of the weighted nonlinear monoform on the left-hand side of (1.6) is
asymptotically expressed as the rational function of the multiform for
infinite set of elements (1.4).

### 1.4.

In this paper, we introduce new method to study the main integral (1.1).
Namely, we use certain stochastic process generated by the formula (1.3). We
use simple properties of this process together with the Ljapunov’s central
limit theorem for a construction of an integral that we call _statistical arc
length of the Riemann $Z(t)$-curve_. Consequently, an asymptotic formula for
this integral is obtained.

##  2\. Tranformation of the formula (1.1)

In the formula (see (1.1))

$L=L(T,U)=\int_{T}^{T+U}\sqrt{1+\\{Z^{\prime}(t)\\}^{2}}{\rm d}t$

we put

$Z^{\prime}(t)=Z_{1}(t)+R_{1}(t),\ t\in[T,T+U],$

where (see (1.3))

$\begin{split}&Z_{1}(t)=2\sum_{n<P}\frac{1}{\sqrt{n}}\ln\frac{P}{n}\cos\\{\vartheta(t)-t\ln
n+\pi/2\\},\\\ &R_{1}(t)=\mathcal{O}(T^{-1/4}\ln T).\end{split}$

Since

$\ln\frac{P}{n}=\mathcal{O}(\ln P),\ \ln\frac{P}{n-1}>\ln\frac{P}{n},\ 2\leq
n<P,$

then, similarly to [7], pp. 92, 93, we obtain the following estimate

$Z_{1}(t)=\mathcal{O}(T^{1/6}\ln^{2}T),\ t\in[T,T+U].$

Hence,

$\\{Z^{\prime}(t)\\}^{2}=\\{Z_{1}(t)\\}^{2}+\mathcal{O}(T^{-1/12}\ln^{3}T),$

and

$\begin{split}&\sqrt{1+\\{Z^{\prime}(t)\\}^{2}}=\sqrt{1+\\{Z_{1}(t)\\}^{2}}\left\\{1+\mathcal{O}\left(\frac{T^{-1/12}\ln^{3}T}{1+\\{Z_{1}(t)\\}^{2}}\right)\right\\}=\\\
&=\sqrt{1+\\{Z_{1}(t)\\}^{2}}+\mathcal{O}(T^{-1/12}\ln^{3}T).\end{split}$

Consequently, we have the following

######  Lemma 1.

(2.1) $L=L(T,U)=\int_{T}^{T+U}\sqrt{1+\\{Z_{1}(t)\\}^{2}}{\rm
d}t+\mathcal{O}(T^{-1/12}\ln^{3}T),$ (2.2)
$Z_{1}(t)=2\sum_{n<P}\frac{1}{\sqrt{n}}\ln\frac{P}{n}\cos\\{\vartheta(t)-t\ln
n+\pi/2\\},\quad U\in(0,\sqrt{T}].$

##  3\. Definition of the statistical arc length of the Riemann curve and
Theorem

### 3.1.

Let

$\varphi_{n}\in[-\pi,\pi],\ n<P$

be the system of independent random variables each of them uniformly
distributed on the segment $[-\pi,\pi]$. Putting these $\varphi_{n}$ into the
arguments of cosine-functions in (2.2) one obtains the following stochastic
process

(3.1) $\begin{split}&\Phi_{1}(t)=\Phi_{1}(t,\varphi_{1},\varphi_{2},\dots)=\\\
&=2\sum_{n<P}\frac{1}{\sqrt{n}}\ln\frac{P}{n}\cos\\{a(t,n)+\varphi_{n}\\},\end{split}$

where

$\begin{split}&a(t,n)=\vartheta(t)-t\ln n+\frac{\pi}{2},\\\ &t\in[T,T+U],\
U\in(0,\sqrt{T}].\end{split}$

######  Remark 4.

The following is true: every realization

$\Phi_{1}(t,\bar{\varphi}_{1},\bar{\varphi}_{2},\dots),\ t\in[T,T+U]$

of the stochastic process (3.1) is a continuous function of the variable $t$
for every admissible vector

$\bar{\varphi}=(\bar{\varphi}_{1},\bar{\varphi}_{2},\dots)$

and. consequently, there is the Riemann integral

$\int_{T}^{T+U}\Phi_{1}(t,\bar{\varphi}){\rm d}t,\quad\forall\bar{\varphi}.$

We also use the one-dimensional Gaussian density of probability

(3.2)
$w_{\infty}(\Phi_{1})=\frac{1}{2}\frac{1}{\ln^{3/2}P}e^{-\beta(\Phi_{1})^{2}},\quad\beta=\frac{3}{4\ln^{3}P}.$

### 3.2.

Now, we define the following stochastic process

(3.3)
$\Phi_{2}=\Phi_{2}(T,U,\varphi)=\int_{T}^{T+U}\sqrt{1+\\{\Phi_{1}(t)\\}^{2}}{\rm
d}t,\ U\in(0,\sqrt{T}],$

for every sufficiently big $T$. Expectation value of this process is given by
the formula

(3.4) $E(\Phi_{2})=\int_{T}^{T+U}E(\sqrt{1+(\Phi_{1})^{2}}){\rm d}t.$

Next, we define the following asymptotic expectations

(3.5)
$E_{\infty}(\sqrt{1+(\Phi_{1})^{2}})=\int_{-\infty}^{\infty}\sqrt{1+(\Phi_{1})^{2}}w_{\infty}(\Phi_{1}){\rm
d}\Phi_{1},$

and, consequently, (see (3.3)–(3.5))

(3.6)
$E_{\infty}(\Phi_{2})=\int_{T}^{T+U}E_{\infty}(\sqrt{1+(\Phi_{1})^{2}}){\rm
d}t.$

Thus, the comparison of the formulae (2.2), (3.1) and (2.1), (3.6) leads us to
the following

######  Definition.

(3.7) $\langle L(t,U)\rangle|_{S}=E_{\infty}(\Phi_{2}),$

where

$\langle L(t,U)\rangle|_{S}$

is the statistical arc length of the Riemann $Z(t)$-curve.

Consequently, we notice that the basis of constructed statistical model lies
in the following (purely) mathematical

######  Theorem.

(3.8)
$E_{\infty}(\sqrt{1+(\Phi_{1})^{2}})\sim\frac{1}{\sqrt{6\pi}}\ln^{3/2}T,\
T\to\infty.$

Since (see (3.6), (3.8))

(3.9) $E_{\infty}(\Phi_{2})\sim\frac{1}{\sqrt{6\pi}}U\ln^{3/2}T,\ T\to\infty,$

then we obtain from (3.9) the following

######  Corollary.

$\langle L(t,U)\rangle|_{S}\sim\frac{1}{\sqrt{6\pi}}U\ln^{3/2}T,\
U\in(0,\sqrt{T}],\ T\to\infty.$

##  4\. Statistical considerations about the Gaussian distribution

### 4.1.

The following lemma holds true

######  Lemma 2.

(4.1) $E(\Phi_{1})=0,\ \operatorname{Var}(\Phi_{1})\sim\frac{2}{3}\ln^{3}P,\
T\to\infty.$

###### Proof.

We have (see (3.1))

$\Phi_{1}(t;\varphi)=\sum_{n<P}X_{n},\
X_{n}=\frac{2}{\sqrt{n}}\ln\frac{P}{n}\cos\\{\varphi_{n}+a\\}.$

Since $\varphi_{n}$ are independent and uniformly distributed then we obtain
that

$E(X_{n})=0,\ \operatorname{Var}(X_{n})=\frac{2}{n}\ln^{2}\frac{P}{n}$

and

$E(\Phi_{1})=0,\
\operatorname{Var}(\Phi_{1})=2\sum_{n<P}\frac{1}{n}\ln^{2}\frac{P}{n}.$

Next, for $\operatorname{Var}$ we use the Euler-MacLaurin summation formula
(comp. [7], p. 13) for the function

$f(x)=\frac{1}{x}\ln^{2}\frac{P}{x},\ x\in[1,P].$

Since

$f^{\prime}(x)=\mathcal{O}\left(\frac{\ln^{2}P}{x^{2}}\right),\
f(1)=\mathcal{O}(\ln^{2}P),\ f(P)=0,$

then

$\begin{split}&\sum_{n<P}f(n)=\int_{1}^{P}\ln^{2}\frac{P}{x}\frac{{\rm
d}x}{x}+\mathcal{O}\left(\ln^{2}P\int_{1}^{P}\frac{{\rm
d}x}{x^{2}}\right)+\mathcal{O}(\ln^{2}P)=\\\
&=\frac{1}{3}\ln^{3}P+\mathcal{O}(\ln^{2}P),\end{split}$

and, consequently,

$\operatorname{Var}(\Phi_{1})\sim\frac{2}{3}\ln^{3}P,\ T\to\infty.$

∎

### 4.2.

Next, we give the following

######  Lemma 3.

It is true that in our case the Ljapunov’s condition in the central limit
theorem is fulfilled.

###### Proof.

Since

$\begin{split}&E(|X_{n}-E(X_{n})|^{3})=E(|X_{n}|^{3})=\frac{8}{n^{3/2}}\ln^{3}P\frac{1}{2\pi}\int_{-\pi}^{\pi}|\cos^{3}(\varphi_{n}+a)|{\rm
d}\varphi_{n}<\\\ &<\frac{8}{n^{3/2}}\ln^{3}\frac{P}{n},\end{split}$

then we have the following estimate for the third absolute central moment

$\begin{split}&\sum_{n<P}E(|X_{n}|^{3})\leq
8\sum_{n<P}\frac{1}{n^{3/2}}\ln^{3}\frac{P}{n}<8\ln^{3}P\sum_{n=1}^{\infty}\frac{1}{n^{3/2}}=A\ln^{3}P.\end{split}$

Now, (see (4.1))

$B_{P}=\sqrt{\operatorname{Var}(\Phi_{1})}\sim\sqrt{\frac{2}{3}}\ln^{3/2}P$

and, consequently,

(4.2)
$\frac{1}{B_{P}^{3}}\sum_{n<P}E(|X_{n}|^{3})<2A\frac{\ln^{3}P}{\ln^{9/2}P}\xrightarrow{T\to\infty}0,$

i.e. the Ljapunov’s condition is fulfilled. ∎

######  Remark 5.

Our choice of the Gaussian asymptotics in (3.2) is based upon the results
(4.1) and (4.2), respectively.

##  5\. Proof of Theorem

We put (see (3.2) – (3.5))

(5.1)
$E_{\infty}(\sqrt{1+(\Phi_{1})^{2}})=\sqrt{\frac{3}{\pi}}\frac{1}{\ln^{3/2}P}F(\beta),$

where

(5.2) $F(\beta)=\int_{0}^{\infty}\sqrt{1+x^{2}}e^{-\beta x^{2}}{\rm d}x,\
\beta=\frac{3}{4\ln^{3}P}.$

We need to obtain an asymptotic formula for $F(\beta)$ for small values of
$\beta$ (i.e. for large values of $T$).

First of all, we have that

$\begin{split}&F(\beta)=\int_{0}^{\infty}\cosh^{2}te^{-\beta\sinh^{2}t}{\rm
d}t=\frac{1}{2}e^{\beta/2}\int_{0}^{\infty}(\cosh
2t+1)e^{-\frac{\beta}{2}\cosh 2t}{\rm d}t=\\\
&=\frac{1}{4}e^{\beta/2}\int_{0}^{\infty}(\cosh t+1)e^{-\frac{\beta}{2}\cosh
t}{\rm d}t.\end{split}$

Now, we use the Schläfli’s integral (see [8], p. 81)

$\int_{0}^{\infty}e^{-z\cosh t}\cosh\nu t{\rm d}t=K_{\nu}(t),\
\operatorname{Re}\\{z\\}>0,$

for the modified Bessel’s function of the second kind, and then we obtain

(5.3)
$F(\beta)=\frac{1}{4}e^{\beta/2}\left\\{K_{0}\left(\frac{\beta}{2}\right)+K_{1}\left(\frac{\beta}{2}\right)\right\\}.$

Further, we use the following representations of the $K_{\nu}$-functions (see
[8], p. 80)

$\begin{split}&K_{0}(z)=I_{0}(z)\ln\frac{z}{2}+\sum_{m=1}^{\infty}\frac{z^{2m}}{2^{m}(m!)^{2}}\psi(m+1),\\\
&K_{n}(z)=\frac{1}{2}\sum_{m=0}^{n-1}(-1)^{m}\frac{(n-m-1)!}{m!\left(\frac{z}{2}\right)^{n-2m}}+\\\
&+(-1)^{n+1}\sum_{m=0}^{\infty}\frac{\left(\frac{z}{2}\right)^{n+2m}}{m!(n+m)!}\left\\{\ln\frac{z}{2}-\frac{1}{2}\psi(m+1)-\frac{1}{2}\psi(n+m+1)\right\\},\end{split}$

where (see [8], p. 77)

$I_{0}(z)=\sum_{m=0}^{\infty}\frac{1}{(m!)^{2}}\left(\frac{z}{2}\right)^{2m},$

and (see [9], p. 241)

$\psi(x)=\frac{{\rm d}}{{\rm
d}x}\ln\Gamma(x)=-c-\sum_{k=0}^{\infty}\left(\frac{1}{k+x}-\frac{1}{k+1}\right),$

where $c$ is the Euler’s constant.

Since

$\psi(m+1),\psi(n+m+1)=\mathcal{O}(1),$

and (see (5.2))

$\begin{split}&\frac{\beta}{2}=\frac{3}{8\ln^{3}P},\
\ln\frac{\beta}{4}=-3\ln\ln P+\mathcal{O}(1),\\\
&I_{0}\left(\frac{\beta}{2}\right)=1+\mathcal{O}\left(\frac{1}{\ln^{6}P}\right),\end{split}$

then

$\begin{split}&K_{0}\left(\frac{\beta}{2}\right)=3\ln\ln P+\mathcal{O}(1),\\\
&K_{1}\left(\frac{\beta}{2}\right)=\frac{2}{\beta}+\mathcal{O}(\beta|\ln\beta|)=\frac{8}{3}\ln^{3}P+\mathcal{O}\left(\frac{\ln\ln
P}{\ln^{3}P}\right).\end{split}$

Consequently (see (5.3))

$F(\beta)=\frac{2}{3}\ln^{3}P+\mathcal{O}(\ln\ln P),$

and from this (see (5.1)) the formula (3.8) follows, of course,

$\ln^{3/2}P\sim\frac{1}{2\sqrt{2}}\ln^{3/2}T,\ T\to\infty.$

I would like to thank Michal Demetrian for helping me with the electronic
version of this work.

## References

  * [1] P.A.M. Dirac, ‘The principles of quantum mechanics‘, Oxford at the Clarendon Press, (1958).
  * [2] J. Moser, ‘Some properties of the Riemann zeta-function on the critical line‘, Acta Arith., 26, (1974), 33-39, (in Russian), arXiv: 0710.0943. (1995).
  * [3] J. Moser, ‘On the roots of the equation $Z^{\prime}(t)=0$‘, Acta. Arith., 40, (1981), 97-107, (in Russian), arXiv: 1303.0967.
  * [4] J. Moser, ‘Ljapunov theorem and the statistical length of a curve in the theory of Riemann-zeta function‘, Acta Math. Univ. Comen., 54-55 (1988), 147-163.
  * [5] J. Moser, ‘Riemann hypothesis and the arc length of the Riemann $Z(t)$-curve‘, arXiv: 1404.1717.
  * [6] J. Moser, ‘Jacob’s ladders, $\zeta$-factorization and infinite set of metamorphoses of a multiform‘, arXiv: 1501.07705.
  * [7] E. C. Titchmarsh, ‘ _The theory of the Riemann zeta-function_ ‘, Clarendon Press, Oxford, 1951.
  * [8] G.N. Watson, _A treatrise on the theory of Bessel-functions_ , Cambdridge at the University Press, 1922.
  * [9] E.T. Whittaker, G.N. Watson, _A course of modern analysis_ , Cambridge, University Press, 1927.