This question was inspired by the following reference:

Reference paper

We use the usual notation.  $N = 2^n$ ,  the number of all possible n-bit strings . The oracle  $U_\omega$ can be put in the form  

$U_\omega=I - 2  (\vert\omega\rangle\langle\omega \vert )$

$U_\omega$ is a reflection of any vector on the hyperplane orthogonal to $\vert\omega\rangle$

The vector $\vert s \rangle $ and operator $U_s$ are introduced. 

$\vert s \rangle = H^{\otimes n} \vert 0 \rangle^{\otimes n}$ , where $H^{\otimes n}$ is the n-qubit Hadamard transform. 

Operator $U_s$ reflects any vector with respect to $\vert s \rangle$

$U_s = 2\vert s \rangle \langle s \vert - I$    

The Grover iteration is $U_{Grover} = U_s U_\omega$

$U_{Grover}$ rotates (at every iteration) the initial vector $\vert s \rangle$ towards the desired vector $\vert\omega\rangle$ by the angle $2\theta$, where $sin\theta =  \frac{1}{\sqrt{N}}$

We note that a reflection is expressed by a unitary matrix. That means that the operator defined below is represented by a unitary matrix, therefore a quantum circuit can be designed in order to implement this operator (Edit. This statement was proven false by the answer to this question). 

We define the operator:

$U(\vert x \rangle , \vert y \rangle  ) = ( \vert x \rangle , U_x \vert y \rangle) $  , where  $U_x \vert y \rangle$ represents the reflection of $\vert y \rangle$  with respect to $\vert x \rangle$

In the following relations the vectors  $\vert \xi_i \rangle$ are implicitly defined based on the action of the operator U.

We consider the following sequence of transformations (based on the definition of the operator U):

$U(\vert s \rangle ,  U_\omega\vert  s \rangle  ) = (\vert s \rangle ,  U_sU_\omega \vert s \rangle) = (\vert s \rangle , \vert \xi_1 \rangle )$

$U(\vert \xi_1 \rangle ,  U_\omega\vert  s \rangle  ) = (\vert \xi_1 \rangle ,  U_{\xi_1}U_\omega \vert s \rangle) = (\vert \xi_1 \rangle , \vert \xi_2 \rangle )$

$U(\vert \xi_2 \rangle ,  U_\omega\vert  s \rangle  ) = (\vert \xi_2 \rangle ,  U_{\xi_2}U_\omega \vert s \rangle) = (\vert \xi_2 \rangle , \vert \xi_3 \rangle )$

.......................and so on..........................

$U(\vert \xi_{n-1} \rangle ,  U_\omega\vert  s \rangle  ) = (\vert \xi_{n-1} \rangle ,  U_{\xi_{n-1}}U_\omega \vert s \rangle) = (\vert \xi_{n-1} \rangle , \vert \xi_n \rangle )$

In other words, the vector to be reflected is fixed but the reflection axis is variable (in the original Grover algorithm it's the other way around ).

At every step  K of the algorithm above  the initial vector $\vert s \rangle$ is rotated towards the desired vector $\vert\omega\rangle$ by an angle which is at about $2^K\theta$ (as order of magnitude ), where $sin\theta =  \frac{1}{\sqrt{N}}$.  That means that this algorithm will only need about  $log_2 N$ (as order of magnitude ) steps  to reach the target.

Question 1. Can a quantum circuit be designed, that implements this algorithm, in principle ?

Question 2. Does this algorithm present an exponential speedup,  when compared to Grover's algorithm?

Edit. Unfortunately nothing from what I tried seems to work. You need a quantum circuit that takes as input the vector to be reflected and the vector that represents the reflection axis. The output of the quantum circuit must contain the reflected vector. That does not seem possible, as far as I understand. This reflection implementation problem, if ever solved, would lead to an exponential speedup of Grover's algorithm.

Related question


1 Answer 1


TLDR: your operation $U$ does not exist (so the answer to question 2 is irrelevant, and I haven't thought about it).

You can show that $U$ does not exist in a very similar way to the way that you cloning is impossible. I'll give the very crude sketch here. There are mathematically more robust versions.

It suffices to show that the transformation is not unitary, provided we include an ancilla in the operation (any CP map can be described by a unitary operator on a sufficiently extended system). So, we want a transformation $$ |0\rangle|\psi\rangle|r\rangle\mapsto |0\rangle(I-2|0\rangle\langle 0|)|\psi\rangle|s\rangle $$ and a second one $$ |\phi\rangle|\psi\rangle|r\rangle\mapsto |\phi\rangle(I-2|\phi\rangle\langle \phi|)|\psi\rangle|s'\rangle. $$ Let's consider the inner products. Before the transformation, we have $\langle\phi|0\rangle$, which we'll assume to be non-zero. After the transformation, we have $$ \langle\phi|0\rangle \langle\psi|(I-2|\phi\rangle\langle\phi|)(I-2|0\rangle\langle 0|)|\psi\rangle\langle s'|s\rangle. $$ The two can only be equal (as required for a unitary) if $|s\rangle=|s'\rangle$ and $$ \langle\psi|(I-2|\phi\rangle\langle\phi|)(I-2|0\rangle\langle 0|)|\psi\rangle=1-2|\langle\phi|\psi\rangle|^2-2|\langle0|\psi\rangle|^2+4\langle\psi|\phi\rangle\langle\phi|0\rangle\langle0|\psi\rangle=1. $$ It's easy to find a counter-example to this. For example, $|\psi\rangle=|0\rangle$ and and $|\phi\rangle=\cos\theta|0\rangle+\sin\theta|1\rangle$ provided $0<\theta<\pi/2$.

  • $\begingroup$ Thank you @DaftWullie The $\xi_i$ can be calculated recursively, for $i=1,2,....n$, so one can build in advance all the quantum circuits implementing the operators $U_{\xi_i} = 2\vert \xi_i \rangle\langle \xi_i \vert - I$ which are unitary , and run the algorithm (quite a lot of them for large n). I was trying to avoid all that by considering only one quantum circuit implementing U, but it' looks like it's not unitary. $\endgroup$ Commented May 7, 2020 at 15:33
  • $\begingroup$ But surely you can only precompute them if you know in advance what you’re searching for? (also, I guess it’s hard for a classical computer to perform that precomputation) $\endgroup$
    – DaftWullie
    Commented May 7, 2020 at 16:18
  • $\begingroup$ "........if you know in advance what you're searching for". Understood, I see the problem, thanks. $\endgroup$ Commented May 9, 2020 at 7:15
  • $\begingroup$ You assume that the program states are not orthogonal. That's the key. Please have a look at this: quantumcomputing.stackexchange.com/q/12071/10110 Feedback appreciated @DaftWullie $\endgroup$ Commented May 18, 2020 at 23:48
  • $\begingroup$ No, I’m just assuming that your program has to be able to act on non-orthogonal states, which it does if it’s a quantum computer. $\endgroup$
    – DaftWullie
    Commented May 19, 2020 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.