Can a circuit map $|x,y\rangle$ to the reflection of $|y\rangle$ with respect to $|x\rangle$?

Question

Statement of the problem.

I want to consider/design a quantum circuit that takes as input two vectors $\vert x \rangle$  and $\vert y \rangle$. The output of this quantum circuit must contain the reflected vector of   $\vert y \rangle$  with respect to  $\vert x \rangle$  (and whatever else that is irrelevant to the purpose ) . I can't find a solution to this problem.  I am not sure if this reference might give a clue towards a solution (programmable quantum gate arrays?). We work in a Hilbert space of fixed (but large) dimension.

Question.  Does such a quantum circuit exist?

Note that a solution for this problem is important,  because if such a quantum circuit exists, then an exponential speedup of Grover's algorithm would become a possibility (relevant for practical problems ),  as can be seen in this question .

Answer 1

Such an operation would not be linear in the $|x\rangle$ input.

Consider the simplest example with $|x\rangle$ and $|y\rangle$ two qubits. We want an operation implementing the following transformation: $$|x\rangle\otimes |y\rangle\to |\psi_{x,y}\rangle\otimes(-|y\rangle + 2|x\rangle\langle x|y\rangle),\tag1$$ for some output qubit $|\psi_{x,y}\rangle$. Consider how this would work on the computational basis: $$\begin{align} |0,0\rangle&\to \phantom{-}|\psi_{00},0\rangle, \\ |0,1\rangle&\to -|\psi_{01},1\rangle, \\ |1,0\rangle&\to -|\psi_{10},0\rangle, \\ |1,1\rangle&\to \phantom{-}|\psi_{11},1\rangle. \end{align}$$ Now consider the action of this map on $|+,0\rangle$. Eq. (1) would tell us that $$|+,0\rangle\to -|0\rangle+2\frac{1}{\sqrt2}|+\rangle = |1\rangle.$$ At the same time, linearity would imply $$|+,0\rangle\to (|\psi_{00}\rangle-|\psi_{10}\rangle)\otimes|0\rangle,$$ which is clearly not how the reflection operation should behave.

The fact that the operation is non-linear (rather than just non-unitary) tells you that there is no way of using additional ancillary degrees of freedom to implement it: there is no quantum channel achieving this operation. At the same time, for every $x$, the action on $y$ is linear (and if this wasn't the case, that would be a rather big problem for anything Grover-related).

This means that $x$ needs to be part of the specification of $\Phi$, which is how it usually appears when discussing Grover (the projections are essentially unitaries parametrised by an $x$). Now, this might appear contradictory: after all, if I "enlarge enough the black box", at some point I must be able to describe the choice of $x$ as input to some operation. If I were to guess, the solution to this conundrum is that this reflection operation is possible, as long as you don't require it to work on all $x$. In other words, it's fine to have this operation, provided you restrict the possible choices of $x$ to an orthogonal set of vectors (e.g. $|0\rangle$ and $|1\rangle$ in this case). Note how this is exactly the same situation you have for the "cloning operation".