Quantum algorithm for determining a complex number string (Q2010995)

In the paper under reviewing the authors studied the generalized Bernstein-Vazirani algorithm for determining a complex number string, which can then be generalized to the case of a matrix string. Let \(a_1,\dots.a_N\) be a sequence of complex numbers, \(g: \mathbf C \to \mathbf C\) be a complex-valued function. The problem is to determine the string \(g(a_1), \dots, g(a_N)\). In the classical case, one need at least N queries. One can consider the 2 sequences of all the real parts \(\Re(a_1),\dots, \Re(a_N)\) and the imaginary parts \(\Im(a_1),\dots,\Im(a_N)\) as 2 bounded sequences of real numbers \(-d < l(a_1) < \dots < l(a_N) < d\) and a linear functional \(f(x) = l(a_1)x_1 + \dots + l(a_N)x_N\). The author proposed a quantum algorithm by: 1) taking the initial state \(|\psi_0\rangle = |0\rangle^{\otimes N} |\phi\rangle\) for some \(|\phi\rangle =\int_{[0,d)} dj \frac{\omega^{d-j}|j\rangle}{\sqrt{d}} \) that is a quantum state in an infinite-dimensional space, \( \omega = e^{i2\pi/d}\). The transform \(|x_1,\dots,x_N\rangle = \int_{-d}^d dz_1\dots \int_{-d}^ddz_N \frac{\omega^{z.x}|z\rangle}{\sqrt{(2d)^N}}\), by using multi-index notation \(x=(x_n,\dots,x_N), z=(z_1,\dots, z_N), x.z := x_1z_1+\dots x_Nz_N\). The generalized Laplace transformation \[G: |\psi_0\rangle \mapsto |\psi_1\rangle= \int_{-d}^d dz_1\dots \int_{-d}^ddz_N \frac{\omega^{z.x}|z\rangle}{\sqrt{(2d)^N}};\] 2) The authors then apply the phase kick-back operation \[O_{f(x)}|x\rangle|\phi\rangle = \omega^{f(x)}|x\rangle |\phi\rangle,\quad O_{f(x)}|\psi_1\rangle =|\psi_2\rangle = \omega^{f(x)}\int_{(-d,d)^N} \frac{\omega^{f(x)}|x\rangle}{\sqrt{(2d)^N}} |\phi\rangle;\] 3) Finally, measure the state \[|\psi_3\rangle = \int_{(-d,d)^N}dz \int_{(-d,d)^N}dx \frac{\omega^{x.z+l(a).x}|x\rangle}{\sqrt{(2d)^N}} |\phi\rangle = |-(l(a_1)l(a_2),\dots, l(a_N))\rangle |\phi\rangle,\] because of the relation \(\int_{(-d,d)^N}dx\; \omega^{x.(z+l(a))} = (2d)^N \delta_{z,-l(a)},\) to have the strings of real or imaginary parts. From this mathematical essence the authors formulated the formal algorithm.