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.
