# What is the query complexity of the following quantum search algorithm?

Problem statement: The search space A involves elements $|0\rangle$, $|2\rangle$... $|d-1\rangle$. An oracle is provided for the function $f(x)$ where

\begin{align} f(x)&=1 \quad x=x^{'}\in A \\ f(x)&=0 \quad x \neq x^{'} \end{align}

The aim is to find $x^{'}$. We have an oracle U corresponding to $f(x)$ whose action is the following $$|x\rangle |y\rangle \rightarrow |x\rangle |y \oplus f(x)\rangle$$ We can consider the search space as the states of a d-level quantum system. If we input the superposition

$$\frac{1}{\sqrt{d}}\sum_{x=0}^{d-1} |x\rangle \otimes |\phi\rangle$$ where $|\phi\rangle=\omega^d|0\rangle+\omega^{d-1}|1\rangle+\cdots + \omega|d-1\rangle$, $\omega=e^{\frac{2\pi i}{d}}$ is the $d^{th}$ root of unity into the oracle corresponding to $f(x)$, using phase kickback we can create the superposition

$$|\Psi\rangle=\frac{1}{\sqrt{d}}\sum_{x=0}^{d-1} \omega^{f(x)}|x\rangle.$$

Let us write $|\Psi\rangle$ as $$|\Psi\rangle=\sum_{x=0}^{d-1} c_x|x\rangle$$ where $c_x=\frac{1}{\sqrt{d}}\omega^{f(x)}$.

We can use quantum state tomography (for example using weak value measurements as described in this paper) to find the coefficients $c_x$. The $|x\rangle$ corresponding to $c_x=\frac{\omega}{\sqrt{d}}$ is the required search result.

But, quantum tomography requires an ensemble of the unknown quantum state so as to reduce the statistical error.

Suppose $M_0$ is the required size of the ensemble such that the error in the measurement is small enough to determine the search result $x^{'}$. This requires $M_0$ identical copies of $|\Psi\rangle$. But, as the state $|\Psi\rangle$ is unknown according to No-Cloning theorem we cannot make copies of $|\Psi\rangle$ using $|\Psi\rangle$ alone. Hence, the ensemble has to be made by querying the oracle $M_0$ times with the uniform superposition (4). But, note that $M_0$ is decided on the basis of the acceptable amount of error in the tomography process and hence it does not scale with the size of the search space A.

From this can I conclude that the query complexity of this algorithm is O(1)?

• It's very hard to tell what parts of this are the question you're trying to answer, and what parts are your answer. Using blockquote markup (> at the beginning of lines) would make this clearer. It also seems that you're essentially saying, "Here's my solution to an exercise I've been set. Is it correct?" That's a job for your TA or professor. Grading homework really isn't interesting to anybody except the person who did the homework, so questions of this kind are very unlikely to be useful to anybody in the future. If that's not what you're asking, could you clarify what your question is? – David Richerby May 10 '17 at 10:37
• @DavidRicherby Sir, I am sorry for the confusion. I would like to clarify that this is not a homework problem that was assigned to me.I was reading about Grover's algorithm and its query complexity. That made me think about whether it is possible to come up with quantum search algorithms which are efficient like Grover's. – Rajath Krishna R May 10 '17 at 10:43
• The above is a search problem and a quantum algorithm for the same that I thought of which could be implemented using quantum tomography. Based on my analysis I am getting the query complexity of the algorithm to be O(1) which indicates some error in my analysis as there is already a proof for the fact that Grover's algorithm is optimal. So, I was trying to ask whether I have made any mistake in my deduction that the query complexity of the above algorithm is O(1). – Rajath Krishna R May 10 '17 at 10:46
• OK. But the question is fundamentally, "Here's an exercise and here's my answer to it. Please grade it for me." As I said, that's not going to be interesting to anybody but you, unless somebody in the future wonders the exact same thing and comes up with the exact same solution attempt. – David Richerby May 10 '17 at 10:49
• @DavidRicherby Sir, I tried to tackle quantum search problem in a different way. In the question, I explained how I think the problem could be tackled writing down the whole algorithm that I think might work. But, my own analysis of the query complexity of the algorithm is driving to a contradiction to the already existing result that no search algorithm can be better than Grover's indicating an error in my analysis. – Rajath Krishna R May 10 '17 at 11:00