# Exponential speedup of Grover's algorithm?

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

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$$.
• 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. May 7 '20 at 15:33