# Revisiting fixed-point quantum search

Guanzhong Li, Lvzhou Li
Institute of Quantum Computing and Software, School of Computer Science and
Engineering,
Sun Yat-sen University, Guangzhou 510006, China
Quantum Science Center of Guangdong-Hong Kong-Macao Greater Bay Area
(Guangdong),
Shenzhen 518045, China Email<EMAIL_ADDRESS><EMAIL_ADDRESS>(corresponding author)

###### Abstract

We revisit the fixed-point quantum search (Yoder, Low, and Chuang, 2014) that
overcomes the souffle problem while maintaining quadratic speedups. We give a
rigorous proof of the lemma regarding the explicit formula of recursive quasi-
Chebyshev polynomials. This lemma is crucial to the correctness of the fixed-
point quantum search, or more precisely the closed-form angle parameters
therein, but its proof is missing in the original paper.

##  1 Introduction

Grover’s search [1] is a fundamental algorithm in quantum computing, as it
achieves a quadratic speedup for the unstructured search problem. It can be
easily generalized to amplitude amplification [2], which has become a
ubiquitous component in designing quantum algorithms. Stimulated by its wide
application, the research on quantum search itself is never-ending and has led
to a variety of versions, such as the deterministic version in which a marked
state is obtained with certainty when the proportion is known beforehand [2,
3, 4, 5], the variable time version where the cost of each oracle query is
different [6, 7], and versions handling oracles with bounded-error [8, 9].

In this paper, we revisit versions that deal with the souffle problem, i.e.
the problem that the success probability of quantum search decreases
dramatically if the iteration time is too small or too large from the right
time. Brassard [10] pointed out this phenomenon in a figurative way: “Quantum
searching is like cooking a souffle. You put the state obtained by quantum
parallelism in a ‘quantum oven’ and let the desired answer rise slowly.
Success is almost guaranteed if you open the oven at just the right time. But
the souffle is very likely to fall—the amplitude of the correct answer drops
to zero—if you open the oven too early. Furthermore, the souffle could burn if
you overcook it; strangely, the amplitude of the desired state starts
shrinking after reaching its maximum.”

A straightforward solution to the souffle problem is to first estimate the
proportion of the marked states using amplitude estimation [2], and then
perform a quantum search based on that estimation. An alternative way is to
repeat the quantum search with exponentially increasing random iteration time,
until a marked state is obtained [11]. Grover himself has also studied the
souffle problem and proposed the $\pi/3$ method [12] with a ‘fixed-point’
property, such that the success probability monotonically increases with the
iteration times. However, the quadratic speedup is lost in this method. In
2014, Yoder, Low, and Chuang [13] proposed an innovative quantum search
algorithm that overcomes the souffle problem while maintaining the quadratic
speedup. The proposed algorithm achieves a slightly different ‘fixed-point’
property: as long as the actual proportion of marked states $\lambda^{2}$ is
greater than a predetermined lower bound $w^{2}$, a marked state is guaranteed
to be found with probability greater than $1-\delta^{2}$, using approximately
$\ln(2/\delta)/w$ oracle queries.

To achieve the goal above, the generalized Grover’s iteration
$G(\alpha,\beta)$ (see Eq. (1) below for its definition) is used, and the
sequence of angles $(\alpha_{k},\beta_{k})_{k=1}^{l}$ is given explicitly
[13]. The correctness of the algorithm relies on the explicit formula of a
recursive quasi-Chebyshev polynomial. More specifically, it was stated in Ref.
[13] that “For other values of $\gamma$, the complex, degree-$h$ polynomials
$a_{h}^{(\gamma)}(x)$ generalize the Chebyshev polynomials. In fact, it can be
shown using combinatorial arguments analogous to those in [14] that
$a_{L}^{(\gamma)}(x)=T_{L}(x/\gamma)/T_{L}(1/\gamma)$.” However, it seems
unclear how to prove this key formula, since Ref. [14] only provides the
combinatorial interpretation of Chebyshev polynomials $T_{L}(x)$ and the paper
[13] does not provide any further explanation.

Some years later, an alternative and rigorous method (see [15, Theorem 27] or
[16, Section III]) was proposed to achieve the same goal using quantum
singular value transformation (QSVT), a framework that unified many quantum
algorithms. Roughly speaking, this method consists of two steps. The first
step concerns constructing a polynomial that approximates the sign function,
and the second step concerns obtaining the sequence of angles from the
coefficient of the polynomial. However, since both steps involve much
numerical approximation, it’s unlikely to obtain closed-form angle parameters
as in Ref. [13].

The rest of this paper is organized as follows. In Section 2, we review the
fixed-point quantum search that overcomes the souffle problem, which is
summarized in Theorem 1. In Section 3, we restate the key formula of recursive
quasi-Chebyshev polynomials in Lemma 1, and then prove Theorem 1 using Lemma 1
and their relation (Lemma 2) for completeness. Section 4 is devoted to the
proof of Lemma 1, which is the main contribution of this article.

##  2 Fixed-point quantum search

We begin by defining the generalized Grover’s iteration $G(\alpha,\beta)$
which will be used later in the fixed-point quantum search.

$G(\alpha,\beta):=S_{0}(\beta)\cdot S_{M}(\alpha),$ (1)

where
$S_{0}(\beta):=e^{i\beta\ket{\psi_{0}}\bra{\psi_{0}}}=I-(1-e^{i\beta})\ket{\psi_{0}}\bra{\psi_{0}}$
multiplies a phase shift of $e^{i\beta}$ to the initial state
$\ket{\psi_{0}}$; and
$S_{M}(\alpha):=e^{i\alpha\Pi_{M}}=I-(1-e^{i\alpha})\sum_{m\in
M}\ket{m}\bra{m}$ multiplies a phase shift of $e^{i\alpha}$ to all the marked
basis states and leaves the other states unchanged. The phase oracle
$S_{M}(\alpha)$ can be implemented using twice the standard oracle
$O:\ket{x}\ket{b}\mapsto\ket{x}\ket{b\oplus\delta(x\in M)}$ that flips the
auxiliary qubit $\ket{b}$ when the basis state $x$ is marked [13].

Let’s have a quick review of Grover’s original search algorithm, which uses
the restricted iteration $G(\pi,\pi)$ with $\alpha=\beta=\pi$ in Eq. (1). The
initial state $\ket{\psi_{0}}$ is the equal-superposition of all basis states.
Each iteration
$-G(\pi,\pi)=(2\ket{\psi_{0}}\bra{\psi_{0}}-I)\cdot(I-2\sum_{m\in
M}\ket{m}\bra{m})$ can be seen as the composition of two reflections, and is
thus a rotation. The more detailed geometric interpretation is shown in Fig.
1.

$\ket{r}$$\ket{t}$$\ket{\psi_{0}}$$\ket{\psi_{l}}$$\theta$$2l\theta$ Figure 1:
Geometric interpretation of Grover’s search process, i.e.
$\ket{\psi_{l}}:=[-G(\pi,\pi)]^{l}\ket{\psi_{0}}$, in the invariant subspace
$\mathcal{H}_{0}=\text{span}\\{\ket{r},\ket{t}\\}$, where
$\ket{t}:=\Pi_{M}\ket{\psi_{0}}/\lambda$,
$\lambda:=\left\|\Pi_{M}\ket{\psi_{0}}\right\|$ and
$\ket{r}:=\Pi_{M}^{\bot}\ket{\psi_{0}}/\sqrt{1-\lambda^{2}}$,
$\Pi_{M}^{\bot}:=I-\Pi_{M}$. One iteration
$-G(\pi,\pi)=(2\ket{\psi_{0}}\bra{\psi_{0}}-I)\cdot(I-2\ket{t}\bra{t})$ is
interpreted as a reflection around $\ket{r}$ followed by a reflection around
$\ket{\psi_{0}}$, and is thus a counter-clockwise rotation by
$2\theta:=2\arcsin\lambda$.

The souffle problem has a nice geometric explanation as shown in Fig. 1. The
success probability (i.e. projection of $\ket{\psi_{l}}$ onto $\ket{t}$)
decreases dramatically if the iteration time $l$ is too far from the optimal
time
$\lfloor(\frac{\pi}{2}-\theta)/(2\theta)\rceil=\lfloor\frac{\pi}{4\arcsin\lambda}-\frac{1}{2}\rceil$
which depends on $\lambda=\left\|\Pi_{M}\ket{\psi_{0}}\right\|$.

To solve the souffle problem, we can use the fixed-point quantum search in
Ref. [13] such that only a lower bound $w$ of
$\lambda=\left\|\Pi_{M}\ket{\psi_{0}}\right\|$ is required to be known
beforehand.

######  Theorem 1 ([13]).

For any $w\in(0,1)$ and $\delta\in(0,1)$, consider the following procedure:

$\ket{\psi_{l}}:=G(\alpha_{l},\beta_{l})\cdots
G(\alpha_{1},\beta_{1})\ket{\psi_{0}},$ (2)

where the iteration time $l\geq\ln(2/\delta)/(2w)$, and the sequence of
parameters are set according to
$\alpha_{k}=2\mathrm{arccot}\left(w\tan(\frac{2k-1}{2l+1}\pi)\right)$ and
$\beta_{k}=-2\mathrm{arccot}\left(w\tan(\frac{2k}{2l+1}\pi)\right)$ for
$k=1\sim l$. Then
$\left\|\Pi_{M}\ket{\psi_{l}}\right\|\geq\sqrt{1-\delta^{2}}$ as long as
$\left\|\Pi_{M}\ket{\psi_{0}}\right\|\geq w$.

To have an intuitive understanding of the ‘fixed-point’ property in Theorem 1,
the plot of how $\left\|\Pi_{M}|\psi_{l}\rangle\right\|$ varies with
$\left\|\Pi_{M}|\psi_{0}\rangle\right\|$ is shown in Fig 2.

Figure 2: The plot of $P(\lambda):=\left\|\Pi_{M}|\psi_{l}\rangle\right\|$ as
a function of $\lambda=\left\|\Pi_{M}|\psi_{0}\rangle\right\|$, where we let
$w=0.08$, $\delta=0.3$, and $l=\lceil\ln(2/\delta)/(2w)\rceil=12$ (cf. Theorem
1). It shows that $P(\lambda)\geq\sqrt{1-\delta^{2}}\approx 0.95$ as long as
$\lambda\geq w=0.08$. The explicit formula of $P(\lambda)$ is shown in Eq.
(20).

##  3 Proof of Theorem 1

###  3.1 The quasi-Chebyshev lemma

To prove Theorem 1, we will need the following Lemma 1 regarding the explicit
formula of a recursive quasi-Chebyshev polynomial. The main contribution of
this article is to provide an explicit and detailed proof of Lemma 1, which is
deferred to Section 4.

######  Lemma 1.

Suppose $\gamma\in(0,1]$. Consider the odd polynomial $a^{\gamma}_{L}(x)$ of
degree $L=2l+1$ defined by the following recursive relation:

$\displaystyle a^{\gamma}_{0}(x)$ $\displaystyle=1,\ a^{\gamma}_{1}(x)=x,$ (3)
$\displaystyle a^{\gamma}_{n+1}(x)$
$\displaystyle=x(1+e^{-i\phi_{n}})a^{\gamma}_{n}(x)-e^{-i\phi_{n}}a^{\gamma}_{n-1}(x),\quad
n=1\sim 2l,$ (4)

where the angles are

$\phi_{n}=2\arctan\left(\sqrt{1-\gamma^{2}}\tan(\frac{n}{L}\pi)\right),\
n=1\sim 2l.$ (5)

Then the explicit formula of $a^{\gamma}_{L}(x)$ is

$a^{\gamma}_{L}(x)=T_{L}(x/\gamma)/T_{L}(1/\gamma),$ (6)

where $T_{L}(x)\equiv\cos(L\arccos(x))\equiv\cosh(L\,\mathrm{arccosh}(x))$ is
the Chebyshev polynomial of first kind.

We provide a proof of Theorem 1 in the following two subsections for
completeness.

###  3.2 Relating failure amplitude to quasi-Chebyshev polynomials

The core of relating Theorem 1 to Lemma 1 lies in the following Lemma 2, which
may be of independent interest. Specifically, the final failing amplitude
$\left\|\Pi_{M}^{\bot}\ket{\psi_{l}}\right\|$ can be expressed as
$\left|a_{L}(x)\right|$, where $x=\left\|\Pi_{M}^{\bot}\ket{\psi_{0}}\right\|$
and $a_{L}(x)$ is a recursive quasi-Chebyshev polynomial, and that the angles
$\phi_{n}$ in the recursive relation of $a_{L}(x)$ are related to the angles
$(\alpha_{k},\beta_{k})_{k=1}^{l}$ in a simple way:

######  Lemma 2.

Let $x:=\left\|\Pi_{M}^{\bot}\ket{\psi_{0}}\right\|$ be the length of the
projection of the initial state $\ket{\psi_{0}}$ onto the subspace spanned by
unmarked states. Consider the final state
$\ket{\psi_{l}}:=G(\alpha_{l},\beta_{l})\cdots
G(\alpha_{1},\beta_{1})\ket{\psi_{0}}$ (cf. Eq. (1) for $G(\alpha,\beta)$).
Then $\left\|\Pi_{M}^{\bot}\ket{\psi_{l}}\right\|=\left|a_{L}(x)\right|$,
where the odd polynomial $a_{L}(x)$ of degree $L=2l+1$ is defined by the
recursive relation: $a_{0}(x)=1,a_{1}(x)=x$, and
$a_{n+1}(x)=x(1+e^{-i\phi_{n}})a_{n}(x)-e^{-i\phi_{n}}a_{n-1}(x)$ for $n=1\sim
2l$, and the angles $\\{\phi_{n}\\}_{n=1}^{2l}$ are related to
$(\alpha_{k},\beta_{k})_{k=1}^{l}$ by $\phi_{2k-1}=\pi-\alpha_{k}$ and
$\phi_{2k}=\beta_{k}+\pi$ for $k=1\sim l$.

###### Proof.

We will restrict ourselves to the invariant subspace
$\mathcal{H}_{0}=\text{span}\\{\ket{r},\ket{t}\\}$, where
$\ket{r}=\Pi_{M}^{\bot}\ket{\psi_{0}}/x$ and
$\ket{t}=\Pi_{M}\ket{\psi_{0}}/\sqrt{1-x^{2}}$. Then the initial state
$\ket{\psi_{0}}=x\ket{r}+\sqrt{1-x^{2}}\ket{t}$ in $\mathcal{H}_{0}$, and thus
we have $\ket{\psi_{0}}=R(x)\ket{r}$, where

$R(x):=\begin{bmatrix}x&\sqrt{1-x^{2}}\\\ \sqrt{1-x^{2}}&-x\end{bmatrix}.$ (7)

Recall
$G(\alpha,\beta)=\left(I-(1-e^{i\beta})\ket{\psi_{0}}\bra{\psi_{0}}\right)\cdot\left(I-(1-e^{i\alpha})\sum_{m\in
M}\ket{m}\bra{m}\right)$ from Eq. (1). Thus we can write the expression of
$G(\alpha,\beta)$ in $\mathcal{H}_{0}$ as

$\displaystyle G(\alpha,\beta)$
$\displaystyle=R(x)\cdot\left(I-(1-e^{i\beta})\ket{r}\bra{r}\right)\cdot
R(x)\cdot\left(I-(1-e^{i\alpha})\ket{t}\bra{t}\right)$ (8)
$\displaystyle=e^{i\beta}R(x)\cdot M_{t}(\beta)\cdot R(x)\cdot
M_{t}(-\alpha),$ (9)

where

$M_{t}(\phi):=\begin{bmatrix}1&0\\\ 0&e^{-i\phi}\end{bmatrix}.$ (10)

Let

$\displaystyle A(\phi)$ $\displaystyle:=R(x)\cdot M_{t}(\phi)$ (11)
$\displaystyle=\begin{bmatrix}x&e^{-i\phi}\sqrt{1-x^{2}}\\\
\sqrt{1-x^{2}}&-xe^{-i\phi}\end{bmatrix}.$ (12)

We can then write the expression of the final state
$\ket{\psi_{l}}=G(\alpha_{l},\beta_{l})\cdots
G(\alpha_{1},\beta_{1})\ket{\psi_{0}}$ in $\mathcal{H}_{0}$ as

$\ket{\psi_{l}}=\exp(i\sum_{n=1}^{l}\beta_{n})\cdot A(\phi_{2l}^{\prime})\cdot
A(\phi_{2l-1}^{\prime})\cdots A(\phi_{2}^{\prime})\cdot
A(\phi_{1}^{\prime})\cdot A(\phi_{0}^{\prime})\ket{r},$ (13)

where the angles $\phi_{n}^{\prime}$ are defined by $\phi_{0}^{\prime}=0$,
$\phi_{2k-1}^{\prime}=-\alpha_{k}$, and $\phi_{2k}^{\prime}=\beta_{k}$, for
$k=1\sim l$.

Consider $a_{n}(x)$ and $b_{n}(x)$ defined by

$[a_{n}(x),\ \sqrt{1-x^{2}}b_{n}(x)]^{T}:=A(\phi_{n-1}^{\prime})\cdots
A(\phi_{0}^{\prime})\ket{r},\ n=1\sim L.$ (14)

Combining Eq. (13) and Eq. (14), we know
$\left|\braket{r}{\psi_{l}}\right|=\left|a_{L}(x)\right|$. Note that
$\left\|\Pi_{M}^{\bot}\ket{\psi_{l}}\right\|=\left|\braket{r}{\psi_{l}}\right|$
in $\mathcal{H}_{0}$. Thus it remains to show that $a_{L}(x)$ can be also
defined by the desired recursive relation as shown in Lemma 2.

From the matrix expression of $A(\phi)$ (Eq. (12)) and Eq. (14), we have the
following coupled recursive relation of $a_{n}(x)$ and $b_{n}(x)$ for $n=0\sim
2l$:

$\displaystyle a_{n+1}(x)$
$\displaystyle=xa_{n}(x)+e^{-i\phi_{n}^{\prime}}(1-x^{2})b_{n}(x),$ (15)
$\displaystyle b_{n+1}(x)$
$\displaystyle=a_{n}(x)-xe^{-i\phi_{n}^{\prime}}b_{n}(x),$ (16)

where $a_{0}(x):=1,b_{0}(x):=0$. To decouple this recursive relation, we first
obtain $b_{n}(x)=\left(a_{n-1}(x)-xa_{n}(x)\right)/(1-x^{2})$ using “(15) $+$
(16) $\times\frac{1-x^{2}}{x}$” and $n\mapsto(n-1)$, and then plug $b_{n}(x)$
into Eq. (15), resulting in:

$a_{n+1}(x)=x(1-e^{-i\phi_{n}^{\prime}})a_{n}(x)+e^{-i\phi_{n}^{\prime}}a_{n-1}(x),\quad
n=1\sim 2l,$ (17)

and $a_{0}(x)=1,a_{1}(x)=x$. We now let $\phi_{n}:=\phi_{n}^{\prime}+\pi$.
Then $\phi_{2k-1}=\pi-\alpha_{k}$ and $\phi_{2k}=\beta_{k}+\pi$ for $k=1\sim
l$, and $a_{n+1}(x)=x(1+e^{-i\phi_{n}})a_{n}(x)-e^{-i\phi_{n}}a_{n-1}(x)$ for
$n=1\sim 2l$ from Eq. (17), which is the desired result. ∎

###  3.3 Finishing the proof of Theorem 1

Using Lemma 2 and Lemma 1, we can now prove Theorem 1 as follows.

Recall the parameter setting of $(\alpha_{k},\beta_{k})_{k=1}^{l}$ in Theorem
1:

$\begin{cases}\alpha_{k}=2\mathrm{arccot}\left(w\tan(\frac{2k-1}{2l+1}\pi)\right),\\\
\beta_{k}=-2\mathrm{arccot}\left(w\tan(\frac{2k}{2l+1}\pi)\right).\end{cases}$
(18)

Using Lemma 2, we know
$\left\|\Pi_{M}^{\bot}\ket{\psi_{l}}\right\|=\left|a_{L}(x)\right|$ where
$x:=\left\|\Pi_{M}^{\bot}\ket{\psi_{0}}\right\|$, and the odd polynomial
$a_{L}(x)$ of degree $L=2l+1$ is defined by the recursive relation:
$a_{0}(x)=1,a_{1}(x)=x$, and
$a_{n+1}(x)=x(1+e^{-i\phi_{n}})a_{n}(x)-e^{-i\phi_{n}}a_{n-1}(x)$ for $n=1\sim
2l$, and the angles the angles $\\{\phi_{n}\\}_{n=1}^{2l}$ are:

$\begin{cases}\phi_{2k-1}=\pi-\alpha_{k}=2\arctan\left(w\tan(\frac{2k-1}{L}\pi)\right),\\\
\phi_{2k}=\beta_{k}+\pi=2\arctan\left(w\tan(\frac{2k}{L}\pi)\right),\end{cases}$
(19)

for $k=1\sim l$, where we used Eq. (18) in the second equality.

Let $\gamma:=\sqrt{1-w^{2}}$, then
$\phi_{n}=2\arctan\left(\sqrt{1-\gamma^{2}}\tan(\frac{n}{L}\pi)\right)$ for
$n=1\sim 2l$ by Eq. (19), which coincides with Eq. (5). Thus by Lemma 1 we
know $a_{L}(x)=T_{L}(x/\gamma)/T_{L}(1/\gamma)$.

In addition, using the fact that
$\left\|\Pi_{M}\ket{\varphi}\right\|=\sqrt{1-\left\|\Pi_{M}^{\bot}\ket{\varphi}\right\|^{2}}$
for any quantum state $\ket{\varphi}$, we obtain the (earlier mentioned, cf.
Fig. 2) explicit formula of $P(\lambda)=\left\|\Pi_{M}\ket{\psi_{l}}\right\|$
about $\lambda=\left\|\Pi_{M}\ket{\psi_{0}}\right\|$ as:

$P(\lambda)=\sqrt{1-\frac{T_{L}^{2}(\sqrt{1-\lambda^{2}}/\sqrt{1-w^{2}})}{T_{L}^{2}(1/\sqrt{1-w^{2}})}}.$
(20)

From the assumption $l\geq\ln(2/\delta)/(2w)$ in Theorem 1, we have
$L\geq{\ln(2/\delta)}/{w}$. We now show that it implies
$1/T_{L}(1/\gamma)\leq\delta$. Using the definition
$T_{L}(x)\equiv\cosh(L\,\mathrm{arccosh}(x))$, we have

$\displaystyle 1/T_{L}(1/\gamma)\leq\delta$ (21)
$\displaystyle\Leftrightarrow\ $
$\displaystyle\cosh\left(L\,\mathrm{arccosh}(1/\gamma)\right)\geq 1/\delta$
(22) $\displaystyle\Leftrightarrow\ $ $\displaystyle
L\geq\frac{\mathrm{arccosh}(1/\delta)}{\mathrm{arccosh}(1/\gamma)}.$ (23)

Thus it suffices to show that the RHS of Eq. (23) is not greater than
${\ln(2/\delta)}/{w}$. From $\gamma=\sqrt{1-w^{2}}$ and the definition
$\mathrm{arccosh}(x)=\ln(x+\sqrt{x^{2}-1})$, we have

$\displaystyle\frac{\mathrm{arccosh}(1/\delta)}{\mathrm{arccosh}(1/\gamma)}$
$\displaystyle=\frac{\ln\left(\frac{1}{\delta}+\sqrt{\frac{1}{\delta^{2}}-1}\right)}{\ln\left(\frac{1}{\sqrt{1-w^{2}}}+\sqrt{\frac{1}{1-w^{2}}-1}\right)}$
(24)
$\displaystyle=\frac{\ln\big{[}\left(1+\sqrt{1-\delta^{2}}\right)/\delta\big{]}}{\ln\big{[}(1+w)/\sqrt{1-w^{2}}\big{]}}$
(25)
$\displaystyle\leq\frac{\ln(2/\delta)}{\ln\sqrt{\frac{1+w}{1-w}}}\leq\frac{\ln(2/\delta)}{w},$
(26)

where the last line follows from $\ln\left(\frac{1+w}{1-w}\right)\geq 2w$,
which can be shown by taking derivative on both sides and observing that
$\frac{2}{1-w^{2}}\geq 2$ holds for $w\in[0,1)$.

Finally, combining
$\left\|\Pi_{M}^{\bot}\ket{\psi_{l}}\right\|=\left|a_{L}(x)\right|$, and
$a_{L}(x)=T_{L}(x/\gamma)/T_{L}(1/\gamma)$, and $1/T_{L}(1/\gamma)\leq\delta$,
and the fact that $|T_{L}(x)|\leq 1$ as long as $|x|\leq 1$, we have:
$\left\|\Pi_{M}^{\bot}\ket{\psi_{l}}\right\|\leq\delta$ as long as
$|x|\leq\gamma$. Recall that $x=\left\|\Pi_{M}^{\bot}\ket{\psi_{0}}\right\|$
and $\gamma=\sqrt{1-w^{2}}$. Therefore,
$\|\Pi_{M}\ket{\psi_{l}}\|\geq\sqrt{1-\delta^{2}}$ as long as
$\|\Pi_{M}\ket{\psi_{0}}\|\geq w$, which completes the proof of Theorem 1.

##  4 Proof of Lemma 1

We copy Lemma 1 in the following for convenience.

######  Lemma 3 (Copy of Lemma 1).

Suppose $\gamma\in(0,1]$. Consider the odd polynomial $a^{\gamma}_{L}(x)$ of
degree $L=2l+1$ defined by the following recursive relation:

$\displaystyle a^{\gamma}_{0}(x)$ $\displaystyle=1,\ a^{\gamma}_{1}(x)=x,$
(27) $\displaystyle a^{\gamma}_{n+1}(x)$
$\displaystyle=x(1+e^{-i\phi_{n}})a^{\gamma}_{n}(x)-e^{-i\phi_{n}}a^{\gamma}_{n-1}(x),\quad
n=1\sim 2l,$ (28) $\displaystyle\phi_{n}$
$\displaystyle=2\arctan\left(\sqrt{1-\gamma^{2}}\tan(\frac{n}{L}\pi)\right),\
n=1\sim 2l.$ (29)

Then $a^{\gamma}_{L}(x)=T_{L}(x/\gamma)/T_{L}(1/\gamma)$, where
$T_{L}(x)\equiv\cos(L\arccos(x))\equiv\cosh(L\,\mathrm{arccosh}(x))$ is the
Chebyshev polynomial of first kind.

###  4.1 Reducing to Eq. (39)

To show $a_{L}^{\gamma}(x)=T_{L}(x/\gamma)/T_{L}(1/\gamma)$, we will separate
$a_{L}^{\gamma}(x)$ into two parts to match the RHS:
$a_{L}^{\gamma}(x)=N_{L}^{\gamma}(x)/D_{L}(\gamma)$. Lemma 4 below shows that
$D_{L}(\gamma)=\gamma^{L}T_{L}(1/\gamma)$, and thus it suffices to show
$N_{L}^{\gamma}(x)=\gamma^{L}T_{L}(x/\gamma)$ (Eq. (39)) to prove Lemma 3.

Denote $t(n):=\tan(\frac{n}{L}\pi)$, $t_{n}:=\sqrt{1-\gamma^{2}}\cdot
t(n):=\tan{\theta_{n}}$. Then $\phi_{n}=2\theta_{n}$ by Eq. (29). We expand
$e^{-i\phi_{n}}$ into expressions regarding $t_{n}$ as follows:

$\displaystyle e^{-i\phi_{n}}$
$\displaystyle=e^{i2\theta_{n}}=\cos(2\theta_{n})-i\sin(2\theta_{n})$ (30)
$\displaystyle=\frac{\cos^{2}\theta_{n}-\sin^{2}\theta_{n}}{\cos^{2}\theta_{n}+\sin^{2}\theta_{n}}-i\frac{2\cos\theta_{n}\sin\theta_{n}}{\cos^{2}\theta_{n}+\sin^{2}\theta_{n}}$
(31)
$\displaystyle=\frac{1-\tan^{2}\theta_{n}}{1+\tan^{2}\theta_{n}}-i\frac{2\tan\theta_{n}}{1+\tan^{2}\theta_{n}}$
(32) $\displaystyle=\frac{(1-it_{n})^{2}}{(1-it_{n})(1+it_{n})}$ (33)
$\displaystyle=\frac{1-it_{n}}{1+it_{n}}.$ (34)

Therefore, the recursive relation of $a^{\gamma}_{n}(x)$ shown by Eq. (28) can
be written as

$a^{\gamma}_{n+1}(x)=\frac{2x}{1+it_{n}}a^{\gamma}_{n}(x)-\frac{1-it_{n}}{1+it_{n}}a^{\gamma}_{n-1}(x),\quad
n=1\sim 2l.$ (35)

If we let $N^{\gamma}_{n}(x):=a^{\gamma}_{n}(x)\cdot D_{n}(\gamma)$, where
$D_{n}(\gamma):=\prod_{k=0}^{n-1}(1+it_{k})$ for $n=1\sim L$ and
$D_{0}(\gamma):=1$, then Eq. (35) can be written as

$\frac{N^{\gamma}_{n+1}(x)}{D_{n+1}(\gamma)}=\frac{2x}{1+it_{n}}\frac{N^{\gamma}_{n}(x)}{D_{n}(\gamma)}-\frac{1-it_{n}}{1+it_{n}}\cdot\frac{1+it_{n-1}}{1+it_{n-1}}\frac{N^{\gamma}_{n-1}(x)}{D_{n-1}(\gamma)},\quad
n=1\sim 2l.$ (36)

Multiplying both sides of Eq. (36) by $D_{n+1}(\gamma)$, we obtain the
recursive definition of $N^{\gamma}_{L}(x)$ as follows

$\displaystyle N^{\gamma}_{n+1}(x)$
$\displaystyle=2xN^{\gamma}_{n}(x)-(1-it_{n})(1+it_{n-1})N^{\gamma}_{n-1}(x),\quad
n=1\sim 2l,$ (37) $\displaystyle N^{\gamma}_{0}(x)$
$\displaystyle=1,N^{\gamma}_{1}(x)=x.$ (38)

From Lemma 4 shown below, we know $D_{L}(\gamma)=\gamma^{L}T_{L}(1/\gamma)$.
We will later show in Section 4.2 that $N^{\gamma}_{L}(x)$ has the following
explicit formula:

$N^{\gamma}_{L}(x)=\gamma^{L}T_{L}(x/\gamma).$ (39)

Thus
$a^{\gamma}_{n}(x)=N^{\gamma}_{L}(x)/D_{L}(\gamma)=T_{L}(x/\gamma)/T_{L}(1/\gamma)$,
completing the proof of Lemma 3.

######  Lemma 4.

Suppose $L=2l+1$ is odd. Consider the degree-$2l$ polynomial $D_{L}(\gamma)$
defined by $D_{L}(\gamma)=\prod_{n=0}^{2l}(1+it_{n})$, where
$t_{n}=\sqrt{1-\gamma^{2}}\cdot t(n)$ and $t(n)=\tan(\frac{n}{L}\pi)$. Then

$D_{L}(\gamma)=\gamma^{L}T_{L}(1/\gamma),$ (40)

where $T_{L}(x)=\cos(L\,\arccos x)$ is the Chebyshev polynomial of the first
kind.

######  Remark 1.

Eq. (40) is actually a special case of Eq. (39) with $x=1$. Therefore,
assuming Eq. (39) holds, we only need to show
$D_{L}(\gamma)=N^{\gamma}_{L}(1)$ to prove Lemma 4. The equality
$D_{L}(\gamma)=N^{\gamma}_{L}(1)$ holds because (1)
$D_{n}(\gamma)=\prod_{k=0}^{n-1}(1+it_{k})$ satisfies the recursive relation
of $N^{\gamma}_{n}(x)$ when $x=1$ (cf. Eq. (37)), since
$D_{n+1}(\gamma)=2D_{n}(\gamma)-(1-it_{n})(1+it_{n-1})D_{n-1}(\gamma)$, and
(2) the initial terms also coincide, since $D_{0}(\gamma)=1=N^{\gamma}_{0}(1)$
and $D_{1}(\gamma)=1=N^{\gamma}_{1}(1)$.

###### Proof of Lemma 4.

We now prove this lemma without assuming Eq. (39). Note that $t_{0}=0$ and
$t_{L-n}=-t_{n}$, thus

$\displaystyle D_{L}(\gamma)$
$\displaystyle=\prod_{n=1}^{l}\left(1+i\sqrt{1-\gamma^{2}}\cdot
t(n)\right)\left(1-i\sqrt{1-\gamma^{2}}\cdot t(n)\right)$ (41)
$\displaystyle=\prod_{n=1}^{l}\left(1+(1-\gamma^{2})\cdot t(n)^{2}\right).$
(42)

Let $\gamma\mapsto 1/\gamma$, then Eq. (40) becomes
$\gamma^{L}D_{L}(1/\gamma)=T_{L}(\gamma)$, where the LHS by Eq. (42) equals to

$p(\gamma):=\gamma\prod_{n=1}^{l}(\gamma^{2}+(\gamma^{2}-1)\cdot t(n)^{2}).$
(43)

Thus it suffices to prove $p(\gamma)=T_{L}(\gamma)$. Note that
$p(1)=T_{L}(1)$, and the degree-$L$ odd polynomial
$T_{L}(\gamma)=\cos(L\,\arccos\gamma)$ has $L$ zeros: $0$ and

$\displaystyle\pm\left\\{\cos\left(\frac{n+1/2}{L}\pi\right)\right\\}_{n=0}^{l-1}$
$\displaystyle=\pm\left\\{\sin\left(\frac{L/2-(n+1/2)}{L}\pi\right)\right\\}_{n=0}^{l-1}$
(44)
$\displaystyle=\pm\left\\{\sin\left(\frac{l-n}{L}\pi\right)\right\\}_{n=0}^{l-1}$
(45)
$\displaystyle=\pm\left\\{\sin\left(\frac{n}{L}\pi\right)\right\\}_{n=1}^{l},$
(46)

which coincide with the zeros of $p(\gamma)$, since
$\gamma=\pm\sin\left(\frac{n}{L}\pi\right)$ is the zeros of
$\gamma^{2}+(\gamma^{2}-1)\cdot t(n)^{2}=0$. As $p(\gamma)$ and
$T_{L}(\gamma)$ are both degree-$L$ polynomials, $p(\gamma)=T_{L}(\gamma)$. ∎

###  4.2 Proof of Eq. (39)

In this subsection, we will compare the combinatorial interpretations of
$2N^{\gamma}_{L}(x)$ and $2\gamma^{L}T_{L}(x/\gamma)$ to prove
$2N^{\gamma}_{L}(x)=2\gamma^{L}T_{L}(x/\gamma)$, from which Eq. (39) holds.

####  4.2.1 Combinatorial interpretation of $2N^{\gamma}_{L}(x)$

Similar to Ref. [14, Theorem 4], we will show that $2N^{\gamma}_{L}(x)$ (cf.
Eq. (37) for the recursive definition of $N^{\gamma}_{L}(x)$) can be regarded
as counting weights of tilings on the $L$-star in Lemma 5 below. As a
preliminary, we first introduce some combinatorial objects.

The ‘$L$-star’ consists of $L$ positions $\braket{0,1,\cdots,L-1}$ modular $L$
equally distributed on a circle. To form a ‘tiling’ on the $L$-star, we need
to cover all the $L$ positions using either ‘square’ with weight $2x$ on any
single position, or ‘domino’ with weight $-(1-it_{n})(1+it_{n-1})$ on two
consecutive positions $\braket{n,n-1}$. Recall that
$t_{n}=\sqrt{1-\gamma^{2}}\cdot t(n)$ and $t(n)=\tan(\frac{n}{L}\pi)$. Thus
$t_{n+L}=t_{n}$, which coincides with the fact that the positions on the
$L$-star are modular $L$. The weight of a tiling is the product of the weights
of all its squares and dominos. For example, a tiling on the $5$-star
consisting of $1$ square and $2$ dominos is shown in Fig. 3.

$0$$1$$2$$3$$4$$(1+it_{4})$$-(1-it_{0})$$(1+it_{1})$$-(1-it_{2})$$2x$ Figure
3: A tiling on the $5$-star with positions $\braket{0,1,2,3,4}$. It has one
square with weight $2x$ on position $\braket{3}$, one domino with weight
$-(1-it_{2})(1+it_{1})$ on positions $\braket{2,1}$, and one domino with
weight $-(1-it_{0})(1+it_{4})$ on positions $\braket{0,4}$. The weight of this
tiling is thus $2x(1-it_{2})(1+it_{1})(1-it_{0})(1+it_{4})$.

######  Lemma 5.

$2N^{\gamma}_{L}(x)$ equals the sum of the weights of all the possible tilings
on the $L$-star.

We first consider the combinatorial interpretation of $N^{\gamma}_{L}(x)$ and
have the following Lemma 6.

######  Lemma 6.

$N^{\gamma}_{L}(x)$ equals the sum of the weights of all the possible
‘modified’ tilings on the $L$-star. A ‘modified’ tiling means that the dominos
are not allowed to cover positions $\braket{0,L-1}$ and a square has weight
$x$ instead of $2x$ when covering position $\braket{0}$.

###### Proof.

In other words, we can cut the $L$-star between positions $\braket{0,L-1}$ to
form a $L$-line with positions $\braket{L-1,\cdots,0}$. Thus it suffices to
show the following claim.

Claim: $N^{\gamma}_{L}(x)$ counts the weights of all the possible tilings on a
$L$-line. Specifically, a tiling has all the positions covered by either
square with weight $x$ at $\braket{0}$ or weight $2x$ at $\braket{n}$ for
$n=1\sim(L-1)$, or domino with weight $-(1-it_{n})(1+it_{n-1})$ at
$\braket{n,n-1}$ for $n=1\sim(L-1)$.

Observe that any tiling on a $(n+1)$-line has either a square with weight $2x$
at $\braket{n}$, or a domino with weight $-(1-it_{n})(1+it_{n-1})$ at
$\braket{n,n-1}$. Thus assuming the claim holds for $N^{\gamma}_{n}(x)$ and
$N^{\gamma}_{n-1}(x)$, the recursive relation
$N^{\gamma}_{n+1}(x)=2xN^{\gamma}_{n}(x)-(1-it_{n})(1+it_{n-1})N^{\gamma}_{n-1}(x)$
implies that $N^{\gamma}_{n+1}(x)$ counts the weights of all the possible
tilings on a $(n+1)$-line, so the claim also holds for $N^{\gamma}_{n+1}(x)$.
Finally, combing with $N^{\gamma}_{0}(x)=1$ and $N^{\gamma}_{1}(x)=x$, the
claim holds by induction. ∎

We can now prove Lemma 5 by multiplying the weight of each modified tiling in
Lemma 6 by $2$.

###### Proof of Lemma 5.

From the combinatorial interpretation of $N^{\gamma}_{L}(x)$ as shown in Lemma
6, we first divide all the possible modified tilings on the $L$-star into the
following two types.

  1. A.

Position $\braket{0}$ is covered by a square with weight $x$.

  2. B.

Positions $\braket{0,1}$ are covered by a domino.

If a modified tiling $T\in A$, then multiplying its weight by $2$ can be
regarded as simply changing the weight of the square on position $\braket{0}$
from $x$ to $2x$. Denote by $f(T)$ the obtained tiling on the $L$-star.

If a modified tiling $T\in B$, then $T$ is already a tiling on the $L$-star,
and thus we cannot use the same technique as in $T\in A$. Instead, we will add
a new tiling $g(T)$ on the $L$-star, where $g$ is a reflection across the
horizontal line passing position $\braket{0}$. Specifically, $g$ reflects all
the consisting squares and dominos of $T$ as follows: it moves the square on
position $\braket{n\neq 0}$ with weight $2x$ to position $\braket{L-n}$, and
moves the domino on positions $\braket{n,n-1}$ with weight
$-(1-it_{n})(1+it_{n-1})=-(1+it_{L-n})(1-it_{L-n+1})$ to positions
$\braket{L-n,L-n+1}$, where we’ve used $t_{L-n}=-t_{n}$. Note that the $g(T)$
is a valid tiling on the $L$-star, and that $g(T)$ has the same weight as $T$.
Also, reflecting twice maps $T$ back to itself, thus $g^{2}=I$.

Denote by $C$ the set of all possible tilings on the $L$-star. The above
process shows that $f(A)\cup B\cup g(B)\subseteq C$. The other direction of
inclusion can be seen by the fact that any tiling $T\in C$ belongs to one and
only one of the following three cases:

  1. 1.

Position $\braket{0}$ of $T$ is covered by a square with weight $2x$, then we
can simply change the square’s weight to $x$ and obtain a modified tiling
$T^{\prime}\in A$. Thus $T=f(T^{\prime})\in f(A)$.

  2. 2.

Positions $\braket{1,0}$ of $T$ are covered by a domino, then $T\in B$.

  3. 3.

Positions $\braket{0,L-1}$ of $T$ are covered by a domino, then $g(T)\in B$.
By $g^{2}=I$ we have $T\in g(B)$.

Therefore, $f(A)\cup B\cup g(B)=C$. It remains to show that the tilings in
$f(A)$, $B$, and $g(B)$ are distinct. First, these three sets do not intersect
with each other because they consist of three different types of tilings as
shown above. Second, tilings in $f(A)$ and $g(B)$ are all distinct, since the
invertible maps $f$ and $g$ are bijections and the modified tilings in $A$ and
$B$ are distinct. ∎

####  4.2.2 Combinatorial interpretation of $2\gamma^{L}T_{L}(x/\gamma)$

######  Lemma 7.

$2\gamma^{L}T_{L}(x/\gamma)$ has almost the same combinatorial interpretation
of $2N^{\gamma}_{L}(x)$ as shown in Lemma 5, and the only difference is that
the weight of dominos change from $-(1-it_{n})(1+it_{n-1})$ to $-\gamma^{2}$.

###### Proof.

The Chebyshev polynomial of the first kind $T_{n}(x)=\cos(n\arccos x)$ has the
following recursive relation:

$\displaystyle T_{0}(x)$ $\displaystyle=1,T_{1}(x)=x,$ (47) $\displaystyle
T_{n+1}(x)$ $\displaystyle=2xT_{n}(x)-T_{n+1}(x).$ (48)

Comparing Eq. (48) with the recursive definition of $N^{\gamma}_{L}(x)$ in Eq.
(37), and recalling that $t_{n}=\sqrt{1-\gamma^{2}}\cdot t(n)$, we know
$T_{L}(x)$ is a special case of $N^{\gamma}_{L}(x)$ with $\gamma=1$. Thus
$2T_{L}(x)$ has almost the same combinatorial interpretation of
$2N^{\gamma}_{L}(x)$ as shown in Lemma 5, except that the weight of dominos
change from $-(1-it_{n})(1+it_{n-1})$ to $-1$. Then by multiplying each of the
$L$ positions in every tiling by $\gamma$ and substituting $x\mapsto
x/\gamma$, we obtain the desired combinatorial interpretation of
$2\gamma^{L}T_{L}(x/\gamma)$. ∎

####  4.2.3 Comparing the coefficients

To prove $2N^{\gamma}_{L}(x)=2\gamma^{L}T_{L}(x/\gamma)$, it suffices to show
that the coefficients of $x^{n_{s}}$ where $n_{s}\in\\{L,L-2,\cdots,1\\}$ are
the same for polynomials $2N^{\gamma}_{L}(x)$ and
$2\gamma^{L}T_{L}(x/\gamma)$. Comparing their combinatorial interpretations as
shown by Lemma 5 and Lemma 7, we let $w=\sqrt{1-\gamma^{2}}$, and thus the
weight of domino on positions $\braket{n,n-1}$ in $2N^{\gamma}_{L}(x)$ becomes
$-(1-it(n)w)(1+it(n-1)w)$, where $t(n)=\tan(\frac{n}{L}\pi)$. And the weight
of domino in $2\gamma^{L}T_{L}(x/\gamma)$ becomes $-\gamma^{2}=-(1-w)(1+w)$.
The weight of squares in both interpretations remains $2x$. Comparing the
total weights of tilings with $n_{s}$ squares (contributing to the coefficient
of $x^{n_{s}}$), it suffices to show the following Lemma 8.

######  Lemma 8.

The following two types of tilings on the $L$-star have the same total
weights. In both types of tilings, the weight of any square is $1$, and the
number of dominos is $n_{d}=(L-n_{s})/2\in\\{0,1,\cdots,l\\}$.

  1. A.

The domino has weight $(1-it(n)w)(1+it(n-1)w)$ on positions $\braket{n,n-1}$.

  2. B.

The domino has weight $(1-w)(1+w)$.

###### Proof.

To show the total weights of tilings of type A and type B are the same, we
will compare the coefficient of $w^{k}$ for $k\in\\{1,2,\cdots,L\\}$. The
coefficients of $w^{0}$, or the constant terms, are the same for both types
and are both equal to the number of all possible tilings on the $L$-star with
$n_{d}$ dominos.

The tilings of type A or type B can be categorized into groups of size $L$,
where tilings in each group have the same distribution of dominos (or squares)
up to rotations. Specifically, for a tiling $T\in A$, denote by $T(j)\in A$
the new tiling obtained from shifting all the squares and dominos of $T$ by
$j\in[L]:=\\{0,1,\cdots,L-1\\}$ positions, and updating the weights of shifted
dominos correspondingly so that $T(j)\in A$. The group to which tiling $T\in
A$ belongs is $\\{T(j):j\in[L]\\}\subseteq A$, since $T(0)=T$. Denote by
$T^{\prime}\in B$ the counterpart of $T\in A$ obtained by changing the weights
of dominos of $T$ from $(1-it(n)w)(1+it(n-1)w)$ to $(1-w)(1+w)$, and
$T^{\prime}(j)\in B$ the tiling obtained by rotating $T^{\prime}$ by $j$
positions. Then, the group $\\{T^{\prime}(j):j\in[L]\\}\subseteq B$ is a
counterpart of $\\{T(j):j\in[L]\\}\subseteq A$.

The coefficient of $w^{k}$ in the total weights of a $L$-sized group
$\\{T(j):j\in[L]\\}\subseteq A$ can be divided into different $L$-sized sets
of terms ($L$-terms for short). Specifically, if the coefficient of $w^{k}$
contains the term $\prod_{m=1}^{k}(-1)^{d_{m}}it(l_{m})$ when calculating the
weight of $T\in\\{T(j):j\in[L]\\}$, where $\\{l_{m}\\}_{m=1}^{k}\subseteq[L]$
and $d_{m}\in\\{0,1\\}$ depends on the distribution of dominos in $T$, then
the coefficient of $w^{k}$ will contain
$\prod_{m=1}^{k}(-1)^{d_{m}}it(l_{m}+j)$ for $j\in[L]$, by the definition of
$T(j)$.

We will later prove in Lemma 9 that each $L$-terms sum up to either $L$ or
zero depending on whether $k$ is even or odd:

$\sum_{j\in[L]}\prod_{m=1}^{k}it(l_{m}+j)=\delta(2|k)L,$ (49)

where $\delta(2|k)=1$ if $k$ is even, and $\delta(2|k)=0$ if $k$ is odd.

When $k$ is even, note that when $\prod_{m=1}^{k}(-1)^{d_{m}}it(l_{m}+j)$
appears in the coefficient of $w^{k}$ in $T(j)$, the corresponding term
$\prod_{m=1}^{k}(-1)^{d_{m}}$ appears in the coefficient of $w^{k}$ in the
counterpart $T^{\prime}(j)$. Equation (49) then implies
$\sum_{j\in[L]}\prod_{m=1}^{k}(-1)^{d_{m}}it(l_{m}+j)=L\prod_{m=1}^{k}(-1)^{d_{m}}$,
saying that the sum of these $L$-terms in $\\{T(j):j\in[L]\\}$ is the same as
the sum of corresponding $L$-terms in $\\{T^{\prime}(j):j\in[L]\\}$. Since the
coefficient of $w^{k}$ in $\\{T(j):j\in[L]\\}$ or
$\\{T^{\prime}(j):j\in[L]\\}$ consists of different such $L$-terms, the
coefficient of $w^{k}$ in $\\{T(j):j\in[L]\\}\subseteq A$ is the same as that
in $\\{T^{\prime}(j):j\in[L]\\}\subseteq B$. Since the tilings of type A or
type B can be categorized into different such groups of size $L$, the
coefficient of $w^{k}$ in the total weights of tilings of type A is the same
as type B.

When $k$ is odd, Eq. (49) implies that the coefficient of $w^{k}$ in any
$L$-sized group $\\{T(j):j\in[L]\\}\subseteq A$ is zero, since the coefficient
of $w^{k}$ in $\\{T(j):j\in[L]\\}$ consists of different such $L$-terms that
sum up to zero. Thus the coefficient of $w^{k}$ in the total weights of
tilings of type A is zero, since the tilings of type A can be categorized into
different such groups of size $L$. The coefficient of $w^{k}$ in the total
weights of tilings of type B is also zero, because the weight of any tiling of
type B does not contain odd powers of $w$, which follows from the fact that
its dominos have weight $(1-w^{2})$. ∎

The following lemma regards a specific sum of products of tangents, which may
be of independent interest.

######  Lemma 9.

Assume integer $L\geq 3$ is odd. Denote $t(n):=\tan(n\pi/L)$. Note that
$t(n)=t(n\,\text{mod}\,L)$. For $k\in\\{1,\cdots,L\\}$, consider any $k$-sized
subset $\\{l_{m}\\}_{m=1}^{k}\subseteq[L]:=\\{0,1,\cdots,L-1\\}$, then

$\sum_{j\in[L]}\prod_{m=1}^{k}it(l_{m}+j)=\delta(2|k)L,$ (50)

where $\delta(2|k)\in\\{0,1\\}$ indicates whether $k$ is odd or even.

###### Proof.

We will prove Lemma 9 by induction.

Base case I. When $k=L$, we have $\prod_{m=1}^{L}t(l_{m}+j)=0$, since
$\\{(l_{m}+j)\,\text{mod}\,L\\}_{m=1}^{L}=[L]$ for any $j\in[L]$ and $t(0)=0$.
Thus Eq. (50) holds since $L$ is odd.

Base case II. When $k=L-1$, suppose
$\\{l_{m}\\}_{m=1}^{L-1}=[L]\setminus\\{l_{0}\\}$, then
$\\{(l_{m}+j)\,\text{mod}\,L\\}_{m=1}^{L}=[L]\setminus\\{(j+l_{0})\,\text{mod}\,L\\}$.
Note that $\\{(j+l_{0})\,\text{mod}\,L\\}_{j\in[L]}=[L]$, thus Eq. (50)
becomes:

$\sum_{\\{d_{m}\\}\subset[L]\atop|\\{d_{m}\\}|=L-1}\prod_{m=1}^{k}it(d_{m})=\delta(2|k)L,$
(51)

which is a special case of the following equality with $k=L-1$.

$\sum_{\\{d_{m}\\}\subset[L]\atop|\\{d_{m}\\}|=k}\prod_{m=1}^{k}it(d_{m})=\delta(2|k)\binom{L}{k}.$
(52)

We now prove Eq. (52). Using Euler’s formula $e^{ix}=\cos{x}+i\sin{x}$, we
have $e^{iLx}=(e^{ix})^{L}=\big{(}1+i\tan{x}\big{)}^{L}/\cos^{L}{x}$.
Expanding the latter binomial, we have:

$\cos^{L}(x)e^{iLx}=\sum_{k=0}^{L}\binom{L}{k}(i\tan x)^{k}$ (53)

When $x\in\\{\frac{n}{L}\pi\\}_{n=0}^{L-1}$, the imaginary part of
$e^{iLx}=e^{in\pi}$ is zero, and the imaginary part of $(i\tan(x))^{k}$ can be
written as $\delta(2|k)(it(n))^{k}$. Thus Eq. (53) implies:

$0=\sum_{k=0}^{L}\delta(2|k)\binom{L}{k}(it(n))^{k}.$ (54)

Therefore, the polynomial $\sum_{k=0}^{L}\delta(2|k)\binom{L}{k}x^{k}$ has $L$
different zeros $\\{it(n)\\}_{n=0}^{L-1}$. Using Vieta’s Theorem or zero-
coefficient relationship, we obtain Eq. (52).

Induction step. Assume Eq. (50) holds for $k+2,k+1$, we now show that Eq. (50)
also holds for $k\leq L-2$.

For any subset $\\{l_{m}\\}_{m=1}^{k}\subseteq[L]$ of size $k$, since $k\leq
L-2$, we can find two different
$l_{k+1},l_{k+2}\in[L]\setminus\\{l_{m}\\}_{m=1}^{k}$ such that
$\\{l_{m}\\}_{m=1}^{k+2}\subseteq[L]$. Since subsets
$\\{l_{m}\\}_{m=1}^{k}\cup\\{l_{k+1}\\}$ and
$\\{l_{m}\\}_{m=1}^{k}\cup\\{l_{k+2}\\}$ are both of size $k+1$, using the
induction of hypothesis for $k+2$, we have:

$\displaystyle 0$
$\displaystyle=\sum_{j\in[L]}it(l_{k+2}+j)\prod_{m=1}^{k}it(l_{m}+j)-\sum_{j\in[L]}it(l_{k+1}+j)\prod_{m=1}^{k}it(l_{m}+j)$
(55)
$\displaystyle=\sum_{j\in[L]}i\big{(}t(l_{k+2}+j)-t(l_{k+1}+j)\big{)}\prod_{m=1}^{k}it(l_{m}+j)$
(56)
$\displaystyle=it(l_{k+2}-l_{k+1})\sum_{j\in[L]}\big{(}1-it(l_{k+2}+j)\cdot
it(l_{k+1}+j)\big{)}\prod_{m=1}^{k}it(l_{m}+j),$ (57)

where we used the trigonometric identity
$\tan(x)-\tan(y)=\tan(x-y)\left(1+\tan(x)\tan(y)\right)$ in Eq. (57). Since
$l_{k+2}-l_{k+1}\neq 0$, the fact that Eq. (57) equals zero implies:

$\displaystyle\sum_{j\in[L]}\prod_{m=1}^{k}it(l_{m}+j)$
$\displaystyle=\sum_{j\in[L]}\prod_{m=1}^{k+2}it(l_{m}+j)$ (58)
$\displaystyle=\delta(2|k+2)L$ (59) $\displaystyle=\delta(2|k)L,$ (60)

where we used the induction of hypothesis for $k+1$ in Eq. (59), and the fact
that $k+2$ has the same parity as $k$ in Eq. (60). Thus Eq. (50) also holds
for $k$. ∎

##  5 Conclusions

In this article, we have reviewed the fixed-point quantum search that
overcomes the souffle problem while maintaining quadratic speedups. We have
provided a detailed and rigorous proof of its key lemma regarding the explicit
formula of a recursive quasi-Chebyshev polynomial. However, the proof is very
complicated, and it is natural to wonder how the authors found the closed-form
angle parameters in the first place, or what kind of inspiration led to it.

## Acknowledgement

This work was supported by the National Natural Science Foundation of China
(Grant No. 62272492), and the Guangdong Provincial Quantum Science Strategic
Initiative (Grant No. GDZX2303007).

## References

  * [1] Lov K. Grover.  “A fast quantum mechanical algorithm for database search”.  In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing.  Page 212–219.  STOC ’96New York, NY, USA (1996). Association for Computing Machinery.
  * [2] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp.  “Quantum amplitude amplification and estimation”.  AMS Contemporary Mathematics Series305 (2000).
  * [3] Peter Hoyer.  “On arbitrary phases in quantum amplitude amplification”.  Physical Review A62 (2000).
  * [4] G. L. Long.  “Grover algorithm with zero theoretical failure rate”.  Phys. Rev. A 64, 022307 (2001).
  * [5] Guanzhong Li and Lvzhou Li.  “Deterministic quantum search with adjustable parameters: Implementations and applications”.  Information and Computation 292, 105042 (2023).
  * [6] Andris Ambainis.  “Quantum search with variable times”.  Theory of Computing Systems 47, 786–807 (2010).
  * [7] Andris Ambainis, Martins Kokainis, and Jevgēnijs Vihrovs.  “Improved Algorithm and Lower Bound for Variable Time Quantum Search”.  In Omar Fawzi and Michael Walter, editors, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023).  Volume 266 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1–7:18.  Dagstuhl, Germany (2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [8] Peter Høyer, Michele Mosca, and Ronald de Wolf.  “Quantum search on bounded-error inputs”.  In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, Automata, Languages and Programming.  Pages 291–299.  Berlin, Heidelberg (2003). Springer Berlin Heidelberg.
  * [9] Ansis Rosmanis.  “Quantum search with noisy oracle” (2023).  arXiv:2309.14944.
  * [10] Gilles Brassard.  “Searching a quantum phone book”.  Science 275, 627–628 (1997).
  * [11] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp.  “Tight bounds on quantum searching”.  Fortschritte der Physik 46, 493–505 (1998).
  * [12] Lov K. Grover.  “Fixed-point quantum search”.  Phys. Rev. Lett. 95, 150501 (2005).
  * [13] 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 (2014).
  * [14] Arthur T. Benjamin and Daniel Walton.  “Counting on chebyshev polynomials”.  Mathematics Magazine 82, 117–126 (2009).
  * [15] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.  “Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics”.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing.  Page 193–204.  STOC 2019New York, NY, USA (2019). Association for Computing Machinery.
  * [16] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang.  “Grand unification of quantum algorithms”.  PRX Quantum 2, 040203 (2021).