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.

Isn't this an algorithm with query complexity of O(1)?

  • 1
    $\begingroup$ Why would you think this has query complexity O(1)? Are you envisioning quantum state tomography as a magical step that will just tell you everything you need to know about the state in one go? Or how many measurements do you think quantum-state tomography takes, and how do you think it scales with $d$? (I don't mean to bash, btw - I just want to prompt you to look critically at your assumptions.) $\endgroup$ – Emilio Pisanty May 8 '17 at 18:29
  • $\begingroup$ @EmilioPisanty Sir, According to the paper that I have linked in the question, for quantum state tomography of a pure state $\psi$ weak measurement of a single observable instead of a set of observables is sufficient. Also, the post selection has to be done on a set of basis states $b_i$ to make this process efficient. But, even though the weak tomography method demands extra measurements and equipment to physically realize it at the end of the day there is only one input that is given to the oracle. $\endgroup$ – Rajath Krishna R May 8 '17 at 18:41
  • $\begingroup$ So, does this correspond to a query complexity of O(1)? I have very limited knowledge of complexity of algorithms so please correct me if I am wrong. $\endgroup$ – Rajath Krishna R May 8 '17 at 18:41
  • $\begingroup$ To be precise, as a weak value measurement has to be made for each post selected state $b_i$, the number of measurements required increases linearly with the dimension d. $\endgroup$ – Rajath Krishna R May 8 '17 at 18:47
  • $\begingroup$ I haven't read the linked issue yet, but based on your comments, in pretty sure your understanding of tomography using weak measurement is not correct. $\endgroup$ – DanielSank May 8 '17 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.