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 .

  • 1
    $\begingroup$ It's probably non-linear when considered on the input $|x\rangle \otimes |y\rangle$ $\endgroup$
    – Danylo Y
    May 9, 2020 at 10:05
  • $\begingroup$ @DanyloY that is indeed the case. Do you have any intuition to see why it's nonlinear? $\endgroup$
    – glS
    May 9, 2020 at 19:17
  • 2
    $\begingroup$ @glS The reflection doesn't depend on the phase of $|x\rangle$. $\endgroup$
    – Danylo Y
    May 9, 2020 at 19:35

1 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".

  • $\begingroup$ Thank you @glS . No wonder I couldn't find a solution. I don't know if specially designed quantum systems (not necessarily standard quantum circuits) can solve the problem or whether it's possible to approximate this mapping with standard quantum circuits (or some other method). Feedback appreciated. $\endgroup$ May 9, 2020 at 19:01
  • $\begingroup$ @CristianDumitrescu the comment turned out to be too long so I added it to the answer. In summary, I don't think you can approximate this in any way: there is no way to go around the non-linearity of the operation. However, for things like Grover, you probably don't need it. The reflection operation can be implemented, you just can't have it work reliably for non-orthogonal values of $x$, but I don't think you need that $\endgroup$
    – glS
    May 9, 2020 at 19:16
  • $\begingroup$ I know there is a lot of research in nonlinear quantum gates at the moment. If this operator can be successfully implemented then an exponential speedup of Grover's algorithm is possible (as can be seen in the second link in my question), and that means that most/all practical problems (in industry, technology, etc.) of interest could be solved efficiently. Thank you for your feedback @glS $\endgroup$ May 10, 2020 at 22:57
  • $\begingroup$ @CristianDumitrescu The "nonlinearity" in the "research in nonlinear gates" you might have seen is not the same "nonlinearity" I'm talking about here. Any evolution following the rules of QM is linear, in the sense that $\Phi(\rho+\sigma)=\Phi(\rho)+\Phi(\sigma)$. There is no going around this staying within QM. However, the term "nonlinearity" is also used in the context of bosonic systems to refer to dynamics that are nonlinear in the creation/annihilation operators. E.g. a squeezing operator is "nonlinear" in this sense. These are very different notions, despite the confusing notation. $\endgroup$
    – glS
    May 10, 2020 at 23:01
  • $\begingroup$ (unless of course you are referring to research into extensions of quantum mechanics) $\endgroup$
    – glS
    May 10, 2020 at 23:05

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.