# Performance Analysis and Parameter Optimization of the Optimal Fixed-Point Quantum Search
## 2 OFPQS Algorithm Revisited  
Based on the multi-phase matching method [21; 22], the OFPQS algorithm [20] overcomes the souffle problem in the original Grover algorithm [1] as well as the loss of quadratic speedup in the original fixed-point quantum search algorithm [17].  
The initial state of the OFPQS algorithm is prepared to be \(\ket{\psi}=A\ket{0}\), where \(A\) can be an arbitrary unitary operator. Denote the equal superposition of all target and nontarget states as \(\ket{\alpha}\) and \(\ket{\beta}\), respectively, i.e.,  
\[\ket{\alpha} = \frac{1}{\sqrt{M}}\sum_{x\in f^{-1}(1)}\ket{x}, \tag{1}\] \[\ket{\beta} = \frac{1}{\sqrt{N-M}}\sum_{x\in f^{-1}(0)}\ket{x}, \tag{2}\]  
where \(M\) is the number of target items in the database of size \(N\), \(f\left(x\right)\) is a Boolean function identifying the target state(s), i.e., if \(\ket{x}\) is a target state, then \(f\left(x\right)=1\)--otherwise, \(f\left(x\right)=0\), with \(A=H^{\otimes n}\) and \(H\) being the Hadamard transform, \(\ket{\psi}\) can be written as  
\[\ket{\psi} = \sqrt{\lambda}\ket{\alpha}+\sqrt{1-\lambda}\ket{\beta}, \tag{3}\]  
where \(\lambda=M/N\) represents the fraction of target items.  
The sequence of operations performed on \(\ket{\psi}\) is given by (see also Equation (2.6) of [21])  
\[S_{L}=G\left(\phi_{l},\varphi_{l}\right)G\left(\phi_{l-1},\varphi_{l-1}\right) \cdots G\left(\phi_{1},\varphi_{1}\right), \tag{4}\]  
where \(L-1=2l\) represents the query complexity of sequence \(S_{L}\), as each generalized Grover operation \(G\left(\phi_{j},\varphi_{j}\right)\) requires two Oracle queries [20], and  
\[G\left(\phi_{j},\varphi_{j}\right) = -AS_{0}^{\phi_{j}}A^{\intercal}S_{f}^{\varphi_{j}}, \tag{5}\]  
where \(S_{0}^{\phi_{j}}\) and \(S_{f}^{\varphi_{j}}\) are the selective phase shifts (\(i=\sqrt{-1}\)) (see also Equations (1) and (2) of [13]),  
\[S_{0}^{\phi_{j}} = I-\left(1-e^{i\phi_{j}}\right)\ket{0}\bra{0}, \tag{6}\] \[S_{f}^{\varphi_{j}} = I-\left(1-e^{i\varphi_{j}}\right)\sum_{x\in f^{-1}(1)}\ket{x} \bra{x}. \tag{7}\]Under the multiphase matching condition (see also Equation (11) of [20])  
\[\phi_{j}=\varphi_{l-j+1}=-2\cot^{-1}\left(\tan\left(2\pi j/L\right)\sqrt{1-\gamma ^{2}}\right),\,1\leq j\leq l, \tag{8}\]  
the final state can be obtained as  
\[S_{L}\left|\psi\right\rangle=\sqrt{P_{L}}\left|\alpha\right\rangle+\sqrt{1-P_{ L}}\left|\beta\right\rangle, \tag{9}\]  
where \(\gamma=T_{1/L}^{-1}\left(1/\delta\right)\), \(P_{L}\) is the success probability of the algorithm (see also Equation (1) of [20]),  
\[P_{L}=1-\delta^{2}T_{L}^{2}\left[T_{1/L}\left(1/\delta\right)\sqrt{1-\lambda} \right], \tag{10}\]  
and \(T_{L}\left(x\right)\) is the \(L\)th Chebyshev polynomial of the first kind [23],  
\[T_{L}\left(x\right)=\left\{\begin{array}{ll}\cos\left(L\arccos\left(x\right) \right),&\text{if }|x|\leq 1,\\ \cosh\left(L\text{arcosh}\left(x\right)\right),&\text{if }x\geq 1,\\ \left(-1\right)^{L}\cosh\left(L\text{arcosh}\left(-x\right)\right),&\text{if }x\leq-1. \end{array}\right. \tag{11}\]  
To ensure the success probability \(P_{L}\left(\lambda\right)\) no less than a given lower bound \(1-\delta^{2}\) for any \(\delta\in\left(0,1\right]\), an approximated condition of \(L\) is given as  
\[L\geq\frac{\ln\left(2/\delta\right)}{\sqrt{\lambda}}, \tag{12}\]  
which is sufficient but not necessary, as shown below.