We consider  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 ). It can be proved that this operator is nonlinear in the first argument, and in general is not unitary.  So no chances of implementing this operator with a quantum circuit, in complete generality.

However, In the reference linked in my question Programmable quantum gate arrays it is proved that a deterministic programmable gate array must have as many Hilbert dimensions in the program register as programs are implemented (consequence of the orthogonality requirement of the program states). If each program is given as input on n qubits, then n programs would require the array to have $n^2$ qubits in the program register, but in principle possible. In our case $\vert x \rangle$ is the program, the reflection axis. So we can implement all the operators $U_{\xi_k}$ described below  for $k=1.2.3......n$

And that means that these operators allow an implementation (with one quantum circuit with $n^2$  input "program" qubits ) as long as the program states are orthogonal (as explained above ). 

And that means that the Grover-Sysoev algorithm can be implemented. This consists in the following $n$ steps: $$|\xi_1\rangle = U_s U_\omega |s\rangle, \quad \vert \xi_2 \rangle = U_{\xi_1} U_\omega \vert s \rangle, \quad \cdots \quad \vert \xi_n \rangle = U_{\xi_{n-1}} U_\omega \vert s \rangle, $$ where $U_\omega\equiv I - 2  (\vert\omega\rangle\langle\omega \vert )$ and $U_s \equiv 2\vert s \rangle \langle s \vert - I$.

This algorithm finds a solution exponentially faster than Grover's. In other words, for a fixed large $n$ we can actually build this complex quantum circuit that would solve problems of practical interest efficiently.

The difference between this and the original Grover algorithm is that we perform an inversion about the previous state vector of the algorithm, rather than about the mean, at each step.

Note that the optimality proof in Grover 's original paper doesn't include operators with "program"  registers as input. 

Question  1. Is this algorithm  possible to implement,  in principle?

Question 2. Is this algorithm exponentially faster that Grover, for a fixed, chosen n?

The way "exponentially faster" is defined implies considering arbitrarily large values of n, but the meaning of this question is clear from the context.

My calculations indicate that both questions allow "yes" answers, but I could be wrong.

Another related question I asked previously can be found here.

  • $\begingroup$ I am interested in a quantum system that can solve efficiently NP complete problems for a large fixed n (practical interest), not in a universal quantum computer. $\endgroup$ May 19, 2020 at 13:40
  • 1
    $\begingroup$ There are 2 main difficulties I have in understanding this question - the first is that the answer to 'related question 2' is that this algorithm is impossible, so you can't speed something up using something that's not possible. The second difficulty in understanding this is that you're asking about a speed-up for a fixed n - this is confusing as the complexity is generally defined in terms of n, (e.g. exponential algorithm is $O(e^n)$ - if you have an 'exponential speed-up', this becomes polynomial), so if you set n to be constant, the complexity is constant, so speed-up is impossible $\endgroup$
    – Mithrandir24601
    May 19, 2020 at 23:36
  • $\begingroup$ a general comment: to maximise your chances of getting good answers, you should have your questions as specific and laser-focused as possible. A good rule of thumb is: can you come out with a title that actually describes the question you are asking? If not, that's a red flag. Another big red flag is that you are explicitly asking more than one question. Each post should contain one and only one question. $\endgroup$
    – glS
    May 19, 2020 at 23:48
  • $\begingroup$ I edited the question in an effort to make it clearer. If you don't agree with some of the edits feel free to revert it. Still, I don't quite understand why you think the impossibility proof in the linked answer doesn't rule out the algorithm altogether. It's also unclear how the algorithm works. You are applying different unitaries to the same state $|s\rangle$? I guess there is a typo somewhere? $\endgroup$
    – glS
    May 20, 2020 at 0:04
  • $\begingroup$ The quantum circuit C will have a data register with n qubits and a program register with $n^2$ qubits, so it can implement all the operators $U_{\xi_k}$ , the inversion about $\xi_k$. Let's consider the relation $\vert \xi_k \rangle = U_{\xi_{k-1}} U_\omega \vert s \rangle $. Then $U_\omega$ performs the phase inversion and passes the resulting vector $U_\omega \vert s \rangle$ to C in its data register. $\endgroup$ May 20, 2020 at 6:28