BHT algorithm implementation

Question

Summary of Method

Amplitude Amplification Summary

The BHT algorithm uses amplitude amplification, a nice generalisation of Grover's algorithm, where there is a subset $G\subset X$ of good elements in the orthonormal basis $X$. Below is a brief summary of the results to define notation and give the background for the question.

Let:

$$\begin{align}&|S\rangle\equiv\frac{1}{\sqrt{\left|S\right|}}\sum_{|x\rangle\in S}|x\rangle,&I_S|x\rangle\equiv\begin{cases}-|x\rangle,&|x\rangle\in S\\\phantom{-}|x\rangle,&|x\rangle\not\in S\end{cases}&\end{align}$$

where $S$ is a set of orthonormal kets. It is easy enough to show using the modified Grover operator $Q\equiv-I_{\left\{|X\rangle\right\}}I_G$ that:

$$\left|\langle G|Q^m|X\rangle\right|^2\ge P_0\equiv\cos^2\left(2\sin^{-1}\sqrt{\frac{\left|G\right|}{\left|X\right|}}\right)=1-\mathcal O\left(\frac{\left|G\right|}{\left|X\right|}\right)$$

where $m$ is the nearest integer to $\dfrac{\pi}{4}\sqrt{\frac{\left|X\right|}{\left|G\right|}}$ and so a good element can be found from $G$ with probability of at least $P_0$ using only $m=\mathcal O\left(\sqrt{\frac{\left|X\right|}{\left|G\right|}}\right)$ applications of $Q$. Finally, substituting in $\left|G\right|=1$ yields the standard results of Grover's algorithm.

BHT algorithm

For Grover's algorithm, we can construct the operator $I_G$ by using an oracle $U_H$ for the function $H:X\to\mathcal B_1$ such that $H\left(x\right)=1$ if and only if $|x\rangle\in G$; where $\mathcal B_n$ is the set of all $n$-bit strings. Thus, using one ancilla line $U_H|x\rangle|-\rangle=I_G|x\rangle|-\rangle$. However, in the case of the BHT algorithm there is an oracle $U_F$ that implements the two-to-one function $F:X\to Y$ and we wish to find two values of $x_0,x_1\in X$ such that $F\left(x_0\right)=F\left(x_1\right)$ - a collision. The algorithm is as follows:

Collision$\left(F,k\right)$

1. Pick an arbitrary subset $K\subseteq X$ of cardinality $k$. Construct a table $L$ of size $k$ where each item in $L$ holds a distinct pair $\left(x,F\left(x\right)\right)$ with $x\in K$.
2. Sort $L$ according to the second entry in each item of $L$.
3. Check if $L$ contains a collision, that is, check if there exist distinct elements $\left(x_0, F\left(x_0\right)\right),\left(x_1, F\left(x_1\right)\right)\in L$ for which $F\left(x_0\right)=F\left(x_1\right)$. If so, goto step 6.
4. Compute $x_1=\operatorname{Grover}\left(H, 1\right)$ where $H:X\to\left\{0, 1\right\}$ denotes the function defined by $H\left(x\right)=1$ if and only if there exists $x_0\in K$ so that $\left(x_0, F\left(x\right)\right)\in L$ but $x\ne x_0$. (Note that $x_0$ is unique if it exists since we already checked that there are no collisions in $L$.)
5. Find $\left(x_0, F\left(x_1\right)\right)\in L$.
6. Output the collision $\left\{x_0, x_1\right\}$.

page 4 - Quantum Algorithm for the Collision Problem (the BHT algorithm)

My implementation of $H$

The paper doesn't mention the implementation of $H$ apart from stating that $H$ can be implemented with only one query to $F$. However, implementing a general $H$ seems like it would give rise to a large complexity cost. Below is the best implementation of general $H$ I could think of:

where $h_{ij}$ denotes the $j^\text{th}$ bit of the $n$-bit string $h_i$

If we denote the action of the above circuit by $U_H|F\left(x\right)\rangle|y\rangle=|F\left(x\right)\rangle|y\oplus H\left(x\right)\rangle$ then:

As a Toffoli gate can be implemented with 15 1,2-qubit gates and an $n$-bit controlled $X$ gate requires $2n$ Toffoli gates and an $X$ gate then $U_H$ is implemented by $\left(32n+1\right)k$ 1,2-qubit gates. Clearly not all the $X$ gates in $U_H$ are required as if $h_{ij}=0$ then the corresponding two $X$ gates can be removed. In addition, $X^2=I$ so the $\left\{h_i\right\}$ could be ordered to take advantage of this. But still, we can upper bound the complexity of $U_H$ as $\mathcal O\left(nk\right)$.

Thus, it takes $k$ initial evaluations of $U_F$ to generate $L$. Next with this definition of $H$ we can skip the sorting. Then both $U_F$ and $U_H$ are evaluated $\mathcal O\left(\sqrt{\frac{N-k}{k}}\right)=\mathcal O\left(\sqrt{\frac{N}{k}}\right)$ times before measuring and checking the answer with one more evaluation of $U_F$. Hence, the complexity is:

$$\mathcal O\left(\left(k+\sqrt{\frac{N}{k}}\right)T+\sqrt{Nk}\log N\right)$$

which is not the complexity given in the paper of:

$$\mathcal O\left(\left(k+\sqrt{\frac{N}{k}}\right)\left(T+\log k\right)\right)$$

Question

So presumably there is a better implementation of $U_H$ than I have given as the paper has better time complexity. My question is what is this implementation of $U_H$?

---

Edit

I managed to lower bound the complexity of $U_H$ in my answer below. Any answer from now on will be accepted and gain the bounty if it explains the remaining discrepancy in my complexity and explains why sorting is helpful. Any more elegant proofs than my own will also be considered for the bounty and being accepted. I shall not accept my own answer. Thank you for your interest.

Answer 1

Disclaimer

This answer to my own question does not completely answer the question but does cover some it the relevant points and hopefully can help anyone still considering answering or is interested in the problem I posed. Any answer from now on will be accepted and gain the bounty if it explains the remaining discrepancy in my complexity and explains why sorting is helpful.

I have come up with a proof that the best complexity with which $U_H$ can be implemented is $\mathcal O\left(nk\right)$ and so my implementation of $U_H$ is optimum up to a constant factor in complexity.

Proof

The output $|y\oplus H\left(x\right)\rangle$ must depend on each $F\left(x_i\right)$ in $L$ and in turn each bit in $F\left(x_i\right)$ so we must perform at least $nk$ comparisons with 2-qubit gates minimum. One might attempt to argue if we pre-sort $L$ then we can use some classical optimisation such as a binary search where if-then-else statements are used to reduce the number of operations taken to compare the input to the elements in $L$; but in a unitary operation, such flow controls are implemented by controlled gates where both the controlled gate for the then and else are still carried out because in general the condition for if is a state in superposition and thus we still compare all $nk$ bits. If we wished to cut out the gates from the then or else executions we would first need to measure which would then prevent the circuit from being unitary and we require $U_H$ to be unitary for Grovers algorithm. Therefore, this imposes a lower bound on the complexity of $\mathcal O\left(nk\right)$.