Quantum Search with Prior Knowledge

1,2]Xiaoyu He
1,2] Jialin Zhang
1,2] Xiaoming<EMAIL_ADDRESS>
[1]Institute of Computing Technology, Chinese Academy of Sciences
[2]University of Chinese Academy of Sciences

Search-base algorithms have widespread applications in different scenarios. Grover's quantum search algorithms and its generalization, amplitude amplification, provide a quadratic speedup over classical search algorithms for unstructured search. We consider the problem of searching with prior knowledge. More preciously, search for the solution among $N$ items with a prior probability distribution. This letter proposes a new generalization of Grover's search algorithm which performs better than the standard Grover algorithm in average under this setting. We prove that our new algorithm achieves the optimal expected success probability of finding the solution if the number of queries is fixed.

§ INTRODUCTION

Quantum searching is an important problem. Many computationally difficult problem, including deciphering some popular encryption scheme[1, 2], Monte Carlo tree search for game [3] and NP-hard problem[4], can be reduced to searching problem. Grover's quantum search algorithm[5, 6] shows a quadratic speed-up over classical search algorithm. The problem is represented by an oracle function, which gives the solution by flipping the sign of corresponding quantum state, among an unsorted list of size $N$.

Grover's search algorithm applies oracle and preparation of initial state  iteratively to implement the rotation on the 2-dimensional Hilbert space spanned by the initial state and target state. It rotates a fixed angle, determined by size $N$ and the number of solutions, towards the target every time and it may miss the solution when the fixed angle is not exact.  Quantum amplitude amplification[7] generalized Grover's standard algorithm to make the success probability of search reach $100\%$.
The exact query complexity of this algorithm to find one solution among $N$ items exactly is the same as Grover's algorithm, $\lceil\frac{\pi}{4\arcsin\sqrt{1/N}}-\frac{1}{2}\rceil\approx O(\sqrt{N})$, which is optimal[8].

These searching algorithms are also suitable for finding one of $M$ solutions among items of size $N$. However, the case is complicated when the number of solutions is unknown since too little iterations cannot reach the target state and too many iterations may pass by the target state. Grover's $\pi/3$-algorithm[9] and a critically damped quantum search algorithm [10] were proposed to handle this fixed point search problem. Then an amplitude amplification improvement[11] was made to achieve quadratic speed-up of query complexity.

Grover's quantum search algorithm and above generalizations consider all the items to be searched are of equal status. However, the items are rarely equally important. We note that heuristic methods are commonly used in classical searching algorithms. For practical search problems, some prior knowledge is usually known about where the solution is more likely to be located. Then a biased probability distribution can be obtained from the current problem to instruct how to prune branches or enter branches of the search tree randomly to improve the expected success probability of search algorithm. A famous modern example is Google's go AI: AlphaGo and AlphaZero[12, 13], despite the emphasis of their work is machine learning, they search for the best placement instructed by knowledge drawn from the current pattern and check if a placement is good enough by some complex calculation.

This paper focuses on how to take advantage of prior knowledge to improve the success probability of quantum search. Here we formalize the prior knowledge as a probability distribution $\textbf{p}=(p_1,p_2,\dots,p_N)$, which indicates the probability about the location of the solution. Assuming $p_1\ge p_2\ge\dots \ge p_N$, then the classical maximum expected success is obviously $\sum_{i=1}^T p_i$, which is reached by querying the item from $1$ to $T$. A naive example that shows the advantage of prior knowledge is $\textbf p=(0.25,0.25,0.25,0.25,0,0,0,0)$ with $N=8$, the success probability in one oracle query with or without this prior knowledge is $100\%$ and about $78.1\%$ respectively, while the classical success probability in one query is $25\%$.

Actually, when the distribution of the solution is uniform, repeating the iteration of Grover's algorithm can reach the maximum average success probability if the number of queries is limited to some given integer $T$.
Our result shows that by replacing the initialization and diffusion operation of Grover's algorithm with some parametric operations related to the given probability distribution, we can improve the expected success probability to optimal for any given number of oracle queries.

Montanaro[14] shows an algorithm that can find the solution with an asymptotically optimal expected number of queries. His quantum algorithm is a Las Vegas algorithm, that repeats many times until finding the solution. The expected number of oracle queries is proven a constant multiple of the optimal value.
Nevertheless, the constant of time complexity is important in some scenarios. An algorithm with asymptotically optimal running time is not good enough for time-sensitive tasks, such as game AI which must output a solution in limited time, while running time directly determines the strength of artificial intelligence.

On the other hand, we note that on actual physical quantum devices, the fidelity of circuit decreases rapidly with the number of oracle queries increases. A three-qubit Grover search experiment on scalable quantum computing system[15] uses only one oracle query, it seems that search one solution among eight items using one oracle query performs better than using two oracle queries, although the relationship between their theoretical success probability is opposite. Our result can offer a trade-off between theoretical success probability and experimental error of circuit, which results in an algorithm with a suitable number of oracle queries to reach optimal experiment success probability.

This paper is organized as follows. We show the details of our search algorithm (Sec. II). When given a probability distribution of solution and a limited number of oracle queries, our algorithm reaches an optimal expected success probability. Then the proof of optimality of our method is shown in Appendix. We then show how quantum can speed up heuristic search of a game tree, while the probability distribution of solution can be approximated by some modern techniques such as machine learning(Sec. III). We also demonstrated our algorithm for some biased distribution of solution on IBM's quantum computing system IBMQ[16], which shows the improvement of experimental success probability on a physical device(Sec. IV).

@C=0.8em @R=1.2em

|0⟩     3A     4O_x     3A^†   1   3A       …

|0⟩     A            O_x	       A^†  	     2   A      …

⋮                           ⋮

|0⟩     A    		   O_x	       A^† 	     1 	   A      …

|1⟩     H   		   O_x	                2366.8em–   …       H        |1⟩

We provide a circuit for our quantum search algorithm in $T$ oracle queries. Here $A$ is an unitary that prepares the initial state $A\ket{0}=\sum_{i=1}^N \sqrt{q_i} |i\rangle + \sqrt{1-\sum_{i=1}^N q_i}|0\rangle$. $O_x$ is the oracle that flip an ancilla qubit, that $O_x\ket{x}\ket{b}=\ket{x}\ket{b\oplus1}$ and $O_x\ket{x^\perp}\ket{b}=\ket{x}\ket{b\oplus1}$.

§ AN OPTIMAL QUANTUM SEARCH ALGORITHM

Grover's quantum search algorithm can be described as a rotation in the space spanned by initial state and the target solution state. Given the probability distribution $\textbf p=(p_1,p_2,\dots,p_N)$ as prior knowledge about where the solution might be located, we show that by replacing the initial state with $|s\rangle=\sum_{i=1}^N \sqrt{q_i} \ket{i}+ \sqrt{1-\sum_{i=1}^N q_i}\ket{0}$, where $q_i$ are some parameters that $q_i\ge 0$ and $\sum_{i=1}^N q_i\le 1$, we can improve the expected success probability. Let $R_s=I-2\ketbra{s}{s}$, which is the reflection operation about $|s\rangle$. Consider the transformation $(R_sO_x)^T$ applied to $|s\rangle$. For a fixed solution $x$, let $|x^\perp\rangle={1}/({1-q_x})\sum_{i\neq x}\sqrt{q_i}|i\rangle$, the state after $(R_sO_x)^T$ applied to $|s\rangle$ is $\sin\left((2T+1)\arcsin\sqrt{q_x}\right)|x\rangle + \cos\left((2T+1)\arcsin\sqrt{q_x}\right) |x^{\perp}\rangle$. The success probability of getting solution $x$ is $\sin^2\left((2T+1)\arcsin\sqrt{q_x}\right)$
if we use measurement with standard basis. Hence the expected success probability of our algorithm is

\begin{equation}
\sum_{x=1}^N p_i\sin^2((2T+1)\arcsin\sqrt{q_i}).
\end{equation}

Then we have following theorem.

Given distribution $\textbf p=(p_1,p_2,\dots,p_N)$ indicating where the solution might be, for any non-negative vector $\textbf{q}=(q_1,\dots,q_N)$ that $\sum_{i=1}^N q_i\le 1$, the expected success probability of quantum search in $T$ queries can be

\begin{equation}\label{eq:optimization}
\text{\rm ESP}_T(\textbf p,\textbf{q})=\sum_{i=1}^N p_i\sin^2((2T+1)\arcsin\sqrt{q_i})
\end{equation}

Therefore we can choose $\textbf{q}$ to optimize the success probability. Note that $\sin^2((2T+1)\arcsin\sqrt{q_i})$ reaches its maximum value $1$ when $q_i=\sin^2\frac{\pi}{2(2T+1)}$ and it increases monotonously with $q_i$ in $[0,\sin^2\frac{\pi}{2(2T+1)}]$, so we can add extra constraints that $q_i\le \sin^2\frac{\pi}{2(2T+1)}$ , without  decreasing the maximum value of Eq.(<ref>). Let $\textbf{q}^*\!(\textbf p)$ denote the parameters that maximize Eq.(<ref>).

\begin{align}\label{eq:extra}
\textbf{q}^*\!(\textbf p)=\mathop{\arg\max}_{\textbf{q}}&\sum_{i=1}^np_i\sin^2((2T+1)\arcsin\sqrt{q_i})\\
\mbox{s.t. }&\sum_{i=1}^n q_i\le 1,\\
&\forall i:\ 0\le q_i\le\sin^2\frac{\pi}{2(2T+1)}.
\end{align}

Since $\sin^2((2T+1)\arcsin\sqrt{q_i})$ is concave when $q_i\in[0,\sin^2\frac{\pi}{2(2T+1)}]$, $\sum_{i=1}^np_i\sin^2((2T+1)\arcsin\sqrt{q_i})$ is a concave function about $(q_1,\dots,q_N)$. Eq <ref> is a concave optimization with linear constraints, which can be solved as a convex optimization problem by Lagrange multiplier method, gradient descent or some other contemporary methods.

The perturbation of $\textbf p$ is robust to $\textbf{q}^*\!(\textbf p)$. If we have an estimation of distribution $\hat{\textbf p}$ that the $L_1$ distance $d_1(\textbf p,\hat{\textbf p})=\sum_{i=1}^N |p_i-\hat{p}_i|\le\epsilon$, the expected success probability using $\textbf{q}^*\!(\hat{\textbf p})$ is

\begin{align*}
&\text{ESP}_T(\textbf p,\textbf{q}^*\!(\hat{\textbf p}))\\
=&\text{ESP}_T(\hat{\textbf p},\textbf{q}^*\!(\hat{\textbf p}))+\text{ESP}_T(\textbf p-\hat{\textbf p},\textbf{q}^*\!(\hat{\textbf p}))\\
\ge&\text{ESP}_T(\hat{\textbf p},\textbf{q}^*\!(\textbf p))+\text{ESP}_T(\textbf p-\hat{\textbf p},\textbf{q}^*\!(\hat{\textbf p}))\\
=&\text{ESP}_T(\textbf p,\textbf{q}^*\!(\textbf p))+\text{ESP}_T(\hat{\textbf p}-\textbf p,\textbf{q}^*\!(\textbf p))+\text{ESP}_T(\textbf p-\hat{\textbf p},\textbf{q}^*\!(\hat{\textbf p}))\\
\ge&\text{ESP}_T(\hat{\textbf p},\textbf{q}^*\!(\textbf p))-\sum_{i=1}^N|p_i-\hat{p}_i|\\
\ge&\text{ESP}_T(\hat{\textbf p},\textbf{q}^*\!(\textbf p))-\epsilon,
\end{align*}

which means a good estimation of the precise distribution can approach the optimal expected success probability well.

Our quantum search algorithm is a variation of Grover's quantum search algorithm. Our algorithm starts with initial state $|s\rangle=\sum_i^N \sqrt{q_i^*}|i\rangle$ and applies $(R_s O_x)^T$ to $|s\rangle$, where $R_s=I-2|s\rangle\langle s|$. We claim that our algorithm is optimal, which means the maximum expected success probability in $T$ queries can be reached by our algorithm. The proof of the optimality is given in Appendix.

The maximum expected success probability by $T$ classical query can be achieved by quantum algorithm using only $\lceil\sqrt{T}\rceil$ oracle queries. Let $q_i=\sin^2\frac{1}{2\lceil\sqrt{T}\rceil+1}$ if $i\le\lceil\sqrt{T}\rceil$, $q_i=0$ otherwise. Then $\text{ESP}_{\lceil \sqrt{T}\rceil}(\textbf{p},\textbf{q})\ge\sum_{i=1}^T p_i$, which means quantum has at least quadratic speed-up over classical when given probability distribution of the solution.

§ APPLICATION TO GAME TREE SEARCH

Solving a game is an important application of search algorithm. Ambainis[17] proposed a quantum algorithm that can solve $2$-player game quadratically faster than the classical deterministic algorithm. On the other hand many heuristic methods are applied to classical search algorithms such as $k$-SAT[18], which can quadratically speed up by [19]. Combining heuristic methods and quantum search algorithms is of great interest. Different from those algorithms above that search for a solution at leaf nodes, solving a game decides which child of root node is optimal. We show a framework of solving game by calling our algorithm recursively and give some evidence that our algorithm would perform well.

We call a choice good if a player will win the game eventually after taking it, no matter how his adversary acts afterwards. In a probabilistic search tree with edge suggesting which choice is more likely to be good, such as Monte Carlo tree after trained, we can obtain some knowledge formed as a probability distribution about each node to be good.

scale = 1, transform shape, thick,
every node/.style = draw, circle, minimum size = 6mm,
grow = down,
level 1/.style = sibling distance=4cm,
level 2/.style = sibling distance=2cm,
level distance = 1.2cm
[shape = circle, draw, line width = 1pt,
minimum size = 6mm, inner sep = 0mm, font = ,] (Start)
child    node [fill=gray!30] (A) 0
child  node [color=white] (B) 00
child  node [color=white] (C) 01

child    node [fill=gray!30] (D) 1
child  node [color=white] (E) 10
child  node [color=white] (F) 11

[nodes = draw = none]
(Start) – (A) node [near start, left]  $0.4$;
(A)     – (B) node [near start, left]  $0.8$;
(A)     – (C) node [near start, right] $0.2$;

(Start) – (D) node [near start, right] $0.6$;
(D)     – (E) node [near start, left]  $0.5$;
(D)     – (F) node [near start, right] $0.5$;
at (B) $\cdots$;
at (C) $\cdots$;
at (E) $\cdots$;
at (F) $\cdots$;

A probabilistic game tree where the value on the edge indicating  the probability of the choice to be good enough.

The classical search strategy at step $t$ can be formed as a probability distribution $\textbf{g}_t(s_1\dots s_t)$, where $\textbf{g}_t(s_1\dots s_t)_i$ is the probability that entering branch $i$ at pattern $s_1s_2\dots s_{t}$ for next step. These strategies can be obtained from domain expert knowledge or by machine learning. Taking cheese game as an example, when $s_1\dots s_{t}$ represents the first $t$ placement positions that two players alternately played, $\textbf{g}_t(s_1\dots s_t)_i$ is the probability that $i$ might be the best placement.  Actually, $\textbf{g}_t(s_1\dots s_{t})$ can be seen as an approximation of the real optimal solution. When the number of queries is limited to $T$, the first $T$ nodes with the highest probability can be evaluated in classical algorithm, while directly using Grover's algorithm after ranking the probabilities implies a traverse over $\Theta(T^2)$ most likely choices. Our algorithm is better than directly calling Grover's algorithm after ranking, as shown in Fig.<ref>.

Comparison of the expected success probability between classical, ranking method and our algorithm for probability distributions of size 512 which are generated uniformly randomly, with $100$ samples of probability distributions for every number of queries.

Since the strategy $\textbf{g}_t$ can be calculated efficiently by classical computer, the quantum operator that generate state $\sum_i\sqrt{\textbf{q}^*(\textbf{g}(s_1\dots s_t))_i}\ket{i}$ can be implemented efficiently, as shown in Fig.<ref>.

@C=0.8em @R=1.5em
/    4G_t     5Q^*   4G_t^†

|s_1⟩    /     G_t     Q^*   G_t^†       |s_1⟩

|s_2⟩     /    G_t     Q^*   G_t^†        |s_2⟩

⋮                            ⋮

|s_t⟩    /     G_t     Q^*    G_t^†       |s_t⟩

|0⟩    /        Q^*          ∑_i√(q^*(g(s_1…s_t))_i)|i⟩

We provide a circuit for generating the optimal initial state of quantum search corresponding to distribution $\textbf{g}(s_1\dots s_t)$. $G_t$ calculate the probability distribution $\textbf{g}(s_1\dots s_t)$ as classical algorithm and store it to ancillae qubits. $Q^*$ calculate $\textbf{q}^*(\textbf{g}(s_1\dots s_t))$ and then generate the corresponding quantum state. Then ancillae qubits are recovered by reversing the circuit.

Note that when Alice plays a game with Bob, to determine whether a choice $i$ is good for Alice, Alice only needs to predict whether Bob can take a good choice after Alice takes choice $i$. This means that the oracle determines whether a choice $i$ is good for Alice can be implemented by searching for a good choice for Bob at the pattern after Alice takes choice $i$. Hence we can call our search algorithm recursively, search to a certain depth in the game tree, and then use “approximated oracle” such as neural network or rule-based evaluation. This implies a quantum algorithm framework similar to practical classical game tree search, which can speed up the game tree search. Our algorithm is optimal at each level of the tree locally, we believe it would perform well globally as well.

Quantum search using a single oracle query, for finding one solution among $8$ items on $3$ qubits of IMB's $5$-qubit computing system ibmqx2. (a) Comparison of the theoretical maximum expected success probability and  the experiment result of expected success probability. (b)Comparison of the growth rate of maximum expected success probability than quantum search without prior knowledge and the experimental growth rate of expected success probability than result without prior knowledge. The growth rate here is the ratio of the expected success rate with prior knowledge to the success rate without prior knowledge, then minus $1$.

§ IMPLEMENTATION ON QUANTUM COMPUTING SYSTEM

We note that there are many works focusing on implementing Grover's algorithm on quantum computers[15, 20, 21], they show great techniques decreasing the depth and size of circuit for Grover's algorithm and then obtain great success on the fidelity of experiment circuit. We implement our search algorithm simply since the key of this paper is to make use of prior knowledge, instead of optimizing circuit for search algorithm. We implement our algorithm on a five-qubit quantum computer provided by IBMQ[16]. We consider search among items of size $8$ with one solution. The probability distribution of the solution is a simple biased distribution formed as $(\frac{1}{8}+\sigma,\frac{1}{8}+\sigma,\frac{1}{8}+\sigma,\frac{1}{8}+\sigma,\frac{1}{8}-\sigma,\frac{1}{8}-\sigma,\frac{1}{8}-\sigma,\frac{1}{8}-\sigma)$, for $\sigma\in\{\frac{1}{80},\frac{2}{80},\frac{3}{80},\frac{4}{80},\frac{5}{80},\frac{6}{80},\frac{7}{80},\frac{8}{80}\}$.

The circuit implementation of our algorithm is shown in Figure <ref>, the corresponding parameter $\theta$ for different distribution is provided in  Appendix.

@C=0.7em @R=0.75em
|0⟩         H     2O_x      H      X     2      X      H

|0⟩         H      O_x      H      X     1      X      H

|0⟩         R_y(θ)    O_x      R_y(-θ)       X     Z      X      R_y(θ)

A 3-qubit circuit for a 'half-half' distribution in $1$ oracle query. Here $\theta$ depends on the deviation of distribution.

The eight oracles for different solution is implemented directly as shown in Table <ref>, directly constructed from textbook[22].
The results are output by measurement on standard basis.
For eight biased and one uniform distribution, eight different oracles, we run our algorithm on IBMQ[16] with 'ibmqx2' backend, $8192$ shots for each. We conclude the experiment results in FIG. <ref> and FIG. <ref>. It shows that the experimental success probability is lower than theoretical, which is caused by the noise of the device. However, in respect of the growth rate of success probability caused by prior knowledge, the experiment result agrees with the theory well.

Oracle for different solution

Solution    Oracle    Solution     Oracle

@C=0.7em @R=1em
|q_0⟩       X      2    X

|q_1⟩       X      1    X

|q_2⟩       X      Z       X

@C=0.7em @R=1em
|q_0⟩       X      2    X

|q_1⟩       X      1    X

|q_2⟩           Z

@C=0.7em @R=1em
|q_0⟩            2

|q_1⟩       X      1    X

|q_2⟩       X      Z       X

@C=0.7em @R=1em
|q_0⟩            2

|q_1⟩       X      1    X

|q_2⟩           Z

@C=0.7em @R=1em
|q_0⟩       X      2    X

|q_1⟩            1

|q_2⟩       X      Z       X

@C=0.7em @R=1em
|q_0⟩       X      2    X

|q_1⟩            1

|q_2⟩           Z

@C=0.7em @R=1em
|q_0⟩            2

|q_1⟩            1

|q_2⟩       X      Z       X

@C=0.7em @R=1em
|q_0⟩            2

|q_1⟩            1

|q_2⟩           Z

§ CONCLUSION

We consider quantum search with prior knowledge. We provide an optimal quantum search algorithm that achieves the maximum expected success probability with a given number of queries when the probability of solution is given. We show a mathematical proof of the optimality of our algorithm. In particular, the quantum advantage of our algorithm increase as the distribution of solution becomes more biased. We also provide a framework showing how to reduce classical heuristic search algorithm for game tree to our quantum search algorithm.
Since the advantage of our algorithm has been shown by implementation on state-of-the-art device, search problem of larger size and practical search problem, such as searching a game tree, can be implemented hopefully in the future with the development of physical devices.

[1]
Michael J Wiener.
Efficient DES key search.
School of Computer Science, Carleton Univ., 1994.

[2]
Joan Daemen and Vincent Rijmen.
Aes proposal: Rijndael.

[3]
Rémi Coulom.
Efficient selectivity and backup operators in monte-carlo tree
In International conference on computers and games, pages
72–83. Springer, 2006.

[4]
Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani.
Strengths and weaknesses of quantum computing.
SIAM journal on Computing, 26(5):1510–1523, 1997.

[5]
Lov K Grover.
Quantum mechanics helps in searching for a needle in a haystack.
Physical Review Letters, 79(2):325, 1997.

[6]
Lov K Grover.
Quantum computers can search rapidly by using almost any
Physical Review Letters, 80(19):4329, 1998.

[7]
Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp.
Quantum amplitude amplification and estimation.
Contemporary Mathematics, 305:53–74, 2002.

[8]
Christof Zalka.
Grover’s quantum searching algorithm is optimal.
Physical Review A, 60(4):2746, 1999.

[9]
Lov K Grover.
Fixed-point quantum search.
Physical Review Letters, 95(15):150501, 2005.

[10]
Ari Mizel.
Critically damped quantum search.
Physical Review Letters, 102(15):150501, 2009.

[11]
Theodore J Yoder, Guang Hao Low, and Isaac L Chuang.
Fixed-point quantum search with an optimal number of queries.
Physical Review Letters, 113(21):210501, 2014.

[12]
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja
Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton,
et al.
Mastering the game of go without human knowledge.
nature, 550(7676):354–359, 2017.

[13]
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew
Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore
Graepel, et al.
A general reinforcement learning algorithm that masters chess, shogi,
and go through self-play.
Science, 362(6419):1140–1144, 2018.

[14]
Ashley Montanaro.
Quantum search with advice.
In Conference on Quantum Computation, Communication, and
Cryptography, pages 77–93. Springer, 2010.

[15]
Caroline Figgatt, Dmitri Maslov, KA Landsman, Norbert Matthias Linke, Shantanu
Debnath, and C Monroe.
Complete 3-qubit grover search on a programmable quantum computer.
Nature communications, 8(1):1–9, 2017.

[16]
Andrew Cross.
The ibm q experience and qiskit open-source quantum computing
APS, 2018:L58–003, 2018.

[17]
Andris Ambainis and Martins Kokainis.
Quantum algorithm for tree size estimation, with applications to
backtracking and 2-player games.
In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory
of Computing, pages 989–1002, 2017.

[18]
Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick.
Faster k-sat algorithms using biased-ppsz.
In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing, pages 578–589, 2019.

[19]
Evgeny Dantsin, Vladik Kreinovich, and Alexander Wolpert.
On quantum versions of record-breaking algorithms for sat.
ACM SIGACT News, 36(4):103–108, 2005.

[20]
K-A Brickman, PC Haljan, PJ Lee, M Acton, L Deslauriers, and C Monroe.
Implementation of grover’s quantum search algorithm in a scalable
Physical Review A, 72(5):050306, 2005.

[21]
Hai-Long Shi, Si-Yuan Liu, Xiao-Hui Wang, Wen-Li Yang, Zhan-Ying Yang, and Heng
Coherence depletion in the grover quantum search algorithm.
Physical Review A, 95(3):032307, 2017.

[22]
Michael A Nielsen and Isaac Chuang.
Quantum computation and quantum information, 2002.

§ HOW TO CALCULATE $\TEXTBF{Q}*$

Here we show how to find the optimal parameters $\textbf{q}^*=(q_1^*,\dots,q_N^*)$  by Lagrange multiplier method when $T=1$.

Note that $\sin^2((2T+1)\arcsin\sqrt{q_i})$ is a polynomial of degree $2T+1$ with respect to $q_i$. When $T=1$, the optimization function is $\sum_{i=1}^N p_i \sin^2(3\arcsin\sqrt{q_i})=\sum_{i=1}^N p_i q_i(3-4q_i)^2$. Note that the when $n\le 4$, the success probability can reach $1$. When $n>4$, Eq <ref> always reaches its maximum value when $\sum_{i=1}^N q_i=1$ since the function increases monotonously with increase of $q_i$.  The Lagrangian function

\begin{equation}
\mathcal{L} (\bf{q},\lambda)=\sum_{i=1}^N p_i q_i(3-4q_i)^2-\lambda(1-\sum_{i=1}^N q_i)
\end{equation}

By $\nabla\mathcal{L}(\bf{q},\lambda)=0$, we get

\begin{equation}
\left\{
\begin{aligned}
\sum_{i=1}^Nq_i=1.
\end{aligned}
\right.
\end{equation}

which can be simplified to

\begin{equation}\label{eq:lambda}
\sum_{i=1}^N\frac{1}{2}-\sqrt{\frac{1}{16}-\frac{\lambda}{48p_i}}=1
\end{equation}

\begin{equation}
\end{equation}

Eq <ref> can be solved efficiently by binary search of $\lambda$ since the left side is a monotone function of $x$.

§ PROOF OF THE OPTIMALITY

Given distribution $p=(p_1,p_2,\dots,p_N)$ indicating where the solution might be, the expected success probability of quantum algorithm in $T$ oracle queries is upper bounded by

\begin{align}
\max_{\textbf{r}}&\sum_{i=1}^N r_i\sin^2((2T+1)\arcsin\sqrt{r_i})\\
\text{\rm{s.t. }} &\sum_{i=1}^N r_i\le 1,\\
&\forall i:\ 0\le r_i.
\end{align}

Any quantum algorithm in $T$ queries is formed as a  transformation $U_TO_xU_{T-1}\dots U_1O_xU_0$ applied to $|0\rangle$ and measurement $\{M_i\}$, $i\in\{1,2,\dots,N\}$.

Let $\phi^x_t=U_TO_xU_{T-1}\dots O_xU_{t}U_{t-1}\dots U_0|0\rangle$.

\begin{equation}
\begin{aligned}
&\sin x,&0\le x\le \pi/2,\\
&1, &\pi/2<x.
\end{aligned}\right.
\end{equation}

For unit vectors $|a\rangle,|b\rangle,|c\rangle$, let $\langle a,c\rangle=2\arcsin(|a-c|)$ denotes the angle between $a$ and $c$, then $\langle a-c|a-c\rangle=4\sin^2(\langle a,c\rangle/2)$. Since $\langle a,c\rangle\le\langle a,b\rangle+\langle b,c\rangle$ by triangle inequality,

=&2\sin(\langle a,c\rangle/2)\\
\le&2\sin(\min(|\langle a,b\rangle/2+\langle b,c\rangle/2,\pi/2))\\
=&2f(|\langle a,b\rangle/2+\langle b,c\rangle/2)
\end{aligned}$$

Quantum states are unit vectors in Hilbert space. Note that $\phi^x_t$ is unit vector for all $t$ and $\phi^x_0=(\phi^x_0-\phi^x_1)+(\phi^x_1-\phi^x_2)+\dots +(\phi^x_{T-1}-\phi^x_T)+\phi^x_T$, $M_x$ is the measurement which outputs $x$. We have

\begin{align*}
=&\langle\phi_0^x|M_x M_x|\phi_T^x\rangle+\langle\phi_0^x|(I-M_x)(I-M_x)|\phi_T^x\rangle\\
\le&|M_x|\phi_0^x\rangle| |M_x|\phi_T^x\rangle|+\sqrt{1-|M_x|\phi_0^x\rangle|^2} \sqrt{|M_x|\phi_T^x\rangle|^2}\\
\end{align*}

\begin{align*}
\le &\langle\phi^x_0,\phi^x_T\rangle\\
\le &\langle\phi^x_0,\phi^x_1\rangle+\langle\phi^x_2,\phi^x_2\rangle+\dots+\langle\phi^x_{T-1},\phi^x_T\rangle\\
= &2\arcsin(|\phi^x_0-\phi^x_{1}|/2)+\dots+2\arcsin(|\phi^x_{T-1}-\phi^x_{T}|/2).
\end{align*}

Hence the the probability of outputting $x$ with input solution $x$ is

\begin{align*}
&|M_x \phi_0^x|^2\\
\le&f^2(\arcsin(|M_x\phi_T^x|)+\sum_{t=1}^T 2\arcsin(|\phi^x_{t-1}-\phi^x_{t}|/2)).
\end{align*}

On the other hand

\begin{align*}
=&\langle 0|U_0^\dagger\dots U_{t}^\dagger (O_x-I)U_{t+1}^\dagger O_x\dots O_xU_T^\dagger |\\
&U_TO_xU_{T-1}\dots O_xU_{t+1}(O_x-I)U_{t}\dots U_0|0\rangle\\
=&\langle 0|U_0^\dagger\dots U_{t}^\dagger (2|x\rangle\langle x|)(2|x\rangle\langle x|)U_{t}\dots U_0|0\rangle\\
=&4|\langle x|U_{t}\dots U_0|0\rangle|^2.
\end{align*}

Let $u_{t,x}=|\langle x|U_{t}\dots U_0\rangle|^2$, we have

\begin{align*}
\le &f^2(\arcsin(|M_x\phi_T^x|)
+\sum_{t=1}^T 2\arcsin(|\phi^x_{t-1}-\phi^x_{1}|/2))\\
=&f^2( \arcsin\sqrt{q_{T,x}}+2\sum_{t=0}^{T-1}\arcsin\sqrt{u_{0,x}}).
\end{align*}

So the expected success probability is upper bounded by

\begin{align}\label{eq:optimzationq}
\max_{q_{t,x}}&\sum_{x=1}^N p_xf^2( \arcsin\sqrt{u_{T,x}}+2\sum_{t=0}^{T-1}\arcsin\sqrt{u_{0,x}}),\\
\label{eq:le}
\text{s.t. }&\forall t:\sum_{x=1}^N u_{t,x}\le 1,\\
&\forall t,x: u_{t,x}\ge0.
\end{align}

The optimization function Eq <ref> increases monotonously with $u_{t,x}$, so we can replace the $\le1$ with $=1$ in constraints Eq <ref> without changing the maximum value. By Lemma <ref>, the function can reach its maximum when $u_{t,x}=u_{0,x}$, which matches Theorem <ref>.

The following optimization problem

\begin{aligned}
\max_{\{u_{t,x}\}}&\sum_{x=1}^N p_xf^2(\sum_{t=1}^m\arcsin\sqrt{u_{t,x}}),\\
\text{\rm s.t. }&\forall t:\sum_{x=1}^N u_{t,x}= 1,\\
&\forall t,x: u_{t,x}\ge0.
\end{aligned}

can reach the maximum when $\forall x,t:u_{t,x}=u_{0,x}$.

Let the function reach its maximum value with the sum of variance

\begin{equation}\label{eq:var}
\sum_{t=1}^m\sum_{x=1}^N\left(u_{t,x}-\sum_{x=1}^N u_{t,x}/n\right)^2
\end{equation}
minimized at the same time. If there exists $x,t$ that $u_{t,x}\neq u_{0,x}$,
assuming $u_{0,1}<u_{1,1}, u_{0,2}>u_{1,2}$ without loss of generality.

Firstly if $u_{0,1}+u_{1,1}\ge 1$, we can update $u_{0,1}$ and $u_{1,1}$ to $u_{0,1}+\delta$ and $u_{1,1}-\delta$ without decreasing the maximum value when $\delta\le|u_{0,1}-u_{1,1}|/2$,
since $\arcsin\sqrt{u_{0,1}+\delta}+\arcsin\sqrt{u_{1,1}-\delta}\ge\pi/2$.

Secondly if $u_{0,1}+u_{1,1}< 1$, we have differentials

\begin{align}
&\mathrm{d}\arcsin\sqrt{u_{0,1}}=1/\sqrt{(1-u_{0,1})u_{0,1}}\mathrm{d } u_{0,1},\\
&\mathrm{d}\arcsin\sqrt{u_{1,1}}=1/\sqrt{(1-u_{1,1})u_{1,1}} \mathrm{d } u_{1,1},
\end{align}

\begin{equation}
\end{equation}

when $u_{0,1}+u_{1,1}<1, u_{0,1}<u_{1,1}$.    So when $\delta\le|u_{0,1}-u_{1,1}|/2$

\begin{align*}
\arcsin\sqrt{u_{0,1}+\delta}+\arcsin\sqrt{u_{1,1}-\delta}\\
\ge\arcsin\sqrt{u_{0,1}}+\arcsin\sqrt{u_{1,1}}.
\end{align*}

Similarly, when $\delta\le|u_{0,2}-u_{1,2}|/2$

\begin{align*}
\arcsin\sqrt{u_{0,2}-\delta}+\arcsin\sqrt{u_{1,2}+\delta}\\
\ge\arcsin\sqrt{u_{0,2}}+\arcsin\sqrt{u_{1,2}}.
\end{align*}

So we can choose suitable $\delta$ to update
$u_{0,1}$ and $u_{1,1}$ or $u_{0,2}$ and $u_{1,2}$ to their average without decreasing the maximum value.

Then the maximum can be obtained with a smaller summation of variance in Eq.(<ref>), which contradicts the assumption!

Hence the maximum value of the optimization function can be obtained when $\forall x,t:u_{t,x}=u_{0,x}$.

§ OPTIMAL PARAMETERS $\THETA$ FOR 'HALF-HALF' DISTRIBUTION WITH DIFFERENT DEVIATION $\SIGMA$

Parameter $\theta$ for distribution with different deviation $\sigma$

$\sigma$     $\theta$        $\sigma$     $\theta$

$\frac{1}{80}$    $1.48725065$        $\frac{5}{80}$    $1.12383265$

$\frac{2}{80}$    $1.40239865$        $\frac{6}{80}$    $1.01471265$

$\frac{3}{80}$    $1.31480465$        $\frac{7}{80}$    $0.88979265$

$\frac{4}{80}$    $1.22272065$        $\frac{8}{80}$    $0.73831265$