In this short contribution we present a generalization of the Bernstein-Vazirani algorithm. Givenhe set of real values $\left\{a_1,a_2,a_3,\mathrm{....}{a}_N\right\}$ and the function g: R → {0, 1}, we shall determinethe following values $\left\{g\left(a_1\right), g\left(a_2\right),g\left(a_3\right),\mathrm{.........},g\left(a_N\right)\right\}$ simultaneously. We are thus generalizing theBernstein-Vazirani algorithm. We recover the usual algorithm when $g: a_i\to a_i$ The speed ofdetermining the N values will be shown to outperform the classical case by a factor of N.PACS numbers: 03.67.Lx(Quantum computation architectures and implementations), 03.67.Ac(Quantum algorithms, protocols, and simulations).

Quantum mechanics^1-6 provides exact and frequently remarkably accurate numerical predictions, as reported for over a century. There has been a remarkable link in recent decades between the quantum theory and information theory, given rise to the rich field of quantum information theory (QIT), which novel proposals that outperform classical tasks or simply have no classical counterpart.⁶ One case that involves both quantum theory and information theory that can be found in the foundations o fthe quantum theory is the Leggett-type non-local variables theory,⁷ which has been experimentally explored.^8-17 These experiments report that quantum theory does not accept a Leggett-type non-local variables interpretation, although some controversy remains around the conclusions and interpretations of the experimental outcomes.^11-13 Applications of QIT also include the implementation of quantum algorithms. One such case is provided for stance by the Deutsch’s problem,¹⁴ first experimentally realized on a nuclear magnetic resonance proof-of principle quantum computer.¹⁵ Implementation of the Deutsch-Jozsa algorithm on an ion-trap quantum computer has also been achieved.¹⁶ There have been, as well, several other attempts to use single-photon two qubitstates for quantum computing. Oliveira et a implemented the Deutsch’s algorithm with polarization and transverse electromagnetic spatial modes as qubits.¹⁷ Other achievements also include single-photon Bell states preparation and measurement,¹⁸ a decoherence free implementation of Deutsch’s algorithm using single photon and using two logical qubits¹⁹ and, more recently,a one-way quantum computing implementation of the algorithm.²⁰ These achievements involving the Deutsch-Jozsa algorithm are very well related to the so called Bernstein-Vazirani algorithm,^21,22 which can be considered as an extended version of the previous one. After these two algorithms, Simon’s algorithm²³ was discovered, among others. There has been a experimental implementation of a quantum algorithm that solves the Bernstein-Vazirani parity problem without entanglement.²⁴ Additionally, fiber-optics implementations of the Deutsch-Jozsa and Bernstein-Vazirani quantum algorithms with three qubits have been realized.²⁵ Also, a variant of the algorithm for quantum learning being robust against noise has been introduced,²⁶ as well as a quantum algorithm for approximating the influences of Boolean functions and its applications.²⁷ The Bernstein-Vaziranial growth has been also versatile in quantum key distribution²⁸ and transport implementation with ion qubits.²⁹ In the present work we shall extend the Bernstein-Vazirani algorithm a bit further. In what follows, we present in full detail our generalization and some conclusions are drawn. Let us suppose that we are given the following sequence of real values

$a_1,a_2,a_3,\mathrm{....},a_N.$ (1)

Let us now introduce the function

$g : R\to \left\{0,1\right\}.$ (2)

Our goal is to determine the following values:

$g\left(a_1\right),g\left(a_2\right),g\left(a_3\right),\mathrm{....},g\left(a_N\right)$ (3)

Recall that in the classical case, we need N queries, that is, N separate evaluations of the function (2). In our quantum algorithm, we shall require a single query.  Suppose now that we introduce another function

$f : {\left\{0,1\right\}}^N\to \left\{0,1\right\},$ (4)

which is a function with a N-bit domain and a 1-bitrange. We construct the following function:

$f \left(x\right)=g\left(a\right) . x={\displaystyle \sum _{i=1}^{ N}g\left(a_i\right)}{x}_i\left(\mathrm{mod}2\right)$

$\begin{array}{l}=g\left(a_1\right)x_1\oplus g\left(a_2\right)x_2\oplus g\left(a_3\right)x_3 \oplus \mathrm{....}\oplus g\left(a_N\right)x_N,\\ x_i \in {\left\{0,1\right\}}^N, g\left(a_{{}_i}\right) \in \left\{0,1\right\}, a{i}_{ } \in R\end{array}$ (5)                                                           

where ai is a real value. Here $g\left(a\right)$ symbolizes

$g\left(a_1\right)g\left(a_2\right)\mathrm{....}g\left(a_N\right).$ (6)

Let us follow the quantum states through the algorithm. The input state is

${\psi }_1 =\rangle {\oplus }^N|1\rangle$ (7)

After the Hadamard transform on the state, we have

$\psi {}_1\rangle ={\displaystyle \sum _{x\in {\left\{0,1\right\}}^N}\frac{|x\rangle }{{\sqrt{2}}^N}}\left[\frac{|0\rangle -|1\rangle }{\sqrt{2}}\right]$ (8)

Next, the function f is evaluated using

$Uf:|x,y\rangle \to |x,y\oplus f\left(x\right)\rangle$ (9)

Givening

$|\psi {}_{{}_{{}_2}}\rangle =\pm {\displaystyle \sum _x\frac{{\left(-1\right)}^{f\left(x\right)}|x\rangle }{{\sqrt{2}}^N}}\left[{\frac{|0\rangle -|1\rangle }{\sqrt{2}}}^{}\right]$ (10)

After the Hadamard transform, using the previous equation and (10) we can now evaluate $|\psi {}_3\rangle$

$|\psi {}_{{}_3}\rangle =\pm {\displaystyle \sum _z{\displaystyle \sum _x\frac{{\left(-1\right)}^{{}^{x.z+f\left(x\right)}}|z\rangle }{2^N}}}\left[\frac{|0\rangle -|1\rangle }{\sqrt{2}}\right]$ (11)

Thus,

$|\psi {}_{{}_{{}_3}}\rangle =\pm {\displaystyle \sum _z{\displaystyle \sum _x\frac{{\left(-1\right)}^{{}^{x.z+g\left(a\right).x}}|z\rangle }{2^N}}}\left[\frac{|0\rangle -|1\rangle }{\sqrt{2}}\right]$ (12)

${{\displaystyle \sum _x\left(-1\right)}}^{x.z}{}^{+g\left(a\right).x}=2^N{\delta }_g{}_{\left(a\right),z.}$ (13)   

Thus,

$|\psi {}_{{}_{{}_3}}\rangle =\pm {\displaystyle \sum _z{\displaystyle \sum _x\frac{{\left(-1\right)}^{{}^{x.z+g\left(a\right).x}}|z\rangle }{2^N}}}\left[\frac{|0\rangle -|1\rangle }{\sqrt{2}}\right]$

$=\pm {\displaystyle \sum _z\frac{{}^{2N\delta }g\left(a\right),z^{|z\rangle }}{2^N}}\left[\frac{|0\rangle -|1\rangle }{\sqrt{2}}\right]$

$=\pm |g\left(a\right)\rangle \left[\frac{|0\rangle -|1\rangle }{\sqrt{2}}\right]$

$=\pm |g\left(a_1\right)g\left(a_2\right)\mathrm{...}g\left(a_N\right)\rangle \left[\frac{|0\rangle -|1\rangle }{\sqrt{2}}\right]$ (14)

from which

$g\left(a_1\right),g\left(a_2\right)\mathrm{...}g\left(a_N\right)\rangle$ (15)

can be obtained. That is to say, if we measure $g\left(a_1\right),g\left(a_2\right)\mathrm{...}g\left(a_N\right)\rangle$ then we can retrieve the following values

$g\left(a_1\right),g\left(a_2\right),g\left(a_3\right),\mathrm{...}g\left(a_N\right)$ (16)

Using a single query. All we have to do is to perform one quantum measurement. The speed to determine N values improves by a factor of N as compared to the classical counterpart. Notice that we receive the Bernstein-Vazirani algorithm when $g:ai\to ai$

In the present work we have presented a generalization of the Bernstein-Vazirani algorithm. The advantage that is promised over its classical counterpart is $O\left(N\right)$ , much like in the vein of quantum parallelism, where the N coefficients of a pure state $\psi N\rangle$ can be known in one single quantum query.

J. Batle acknowledges fruitful discussions with J. Rossell´o, Maria del Mar Batle and Regina Batle.

The author declares no conflict of interest.

1. Von Neumann J. Mathematical foundations of quantum mechanics. Princeton, New Jersey: Princeton University Press; 1995.
2. Feynman RP, Leighton RB, Sands M. Lectures on physics. Quantum mechanics. 3; 1965.
3. Redhead M. Incompleteness, no locality, and realism. 2nd ed. Clarendon Press, Canada: Oxford; 1989.
4. Peres A. Quantum theory: concepts and methods. Dordrecht, The Netherlands: Kluwer Academic; 1995.
5. Sakurai JJ. Modern quantum mechanics. Addison–wesley publishing company; 1995.
6. Nielsen MA, Chuang IL. Quantum computation and quantum information. Cambridge University Press; 2000.
7. Leggett J. Found. Phys. 2003;33:1469.
8. Groblacher S, Paterek T, Kaltenbaek R, et al. A physical basis for entanglement in a non–local hidden variable theory. Nature(London). 2007;446:871.
9. Paterek T, Fedrizzi A, Groblacher S, et al. Experimental test of nonlocal realistic theories without the rotational symmetry assumption. Phys Rev Lett. 2007;99(21–23):210406.
10. Branciard C, Ling A, Gisin N, et al. Experimental falsification of leggett’s nonlocal variable model. Phys Rev Lett. 2007;99(21–23):210407.
11. Suarez A. Nonlocal “Realistic” leggett models can be considered refuted by the before–before experiment. Found Phys. 2008;38(6):583–589.
12. Zukowski M. Comment on: nonlocal “Realistic” leggett models can be considered refuted by the before–before experiment. Found Phys. 2008;38(11):1070–1071.
13. A Suarez. On Bell, Suarez–Scarani, and leggett experiments: reply to a comment by marek Żukowski. Found Phys. 2009;39(2):156–159.
14. Deutsch D. Quantum theory, the church–turing principle and the universal quantum computer. Proc Roy Soc London Ser A. 1985;400(1818):97.
15. Jones JA, Mosca M. Implementation of a quantum algorithm on a nuclear magnetic resonance quantum computer. Chem Phys. 1998;109:1648
16. Gulde S, Riebe M, Lancaster GPT, et al. Quantum information processing with trapped Ca+ ions. Nature. 2003;421:48.
17. De Oliveira N, Walborn SP, Monken CH. Opt. B: Quantum Semi class. Opt. 2005;7:288–292.
18. Kim YH. Experimental entanglement concentration and universal Bell–state synthesizer. Physical Review A. 2003;67:040301(R).
19. Mohseni M, Lundeen JS, Resch KJ, et al. Experimental application of Decoherence–free subspaces in an optical quantum–computing algorithm. Phys. Rev. Lett.2003;91(18):187903.
20. Tame MS, Prevedel R, Paternostro M, et al. Experimental realization of a quantum game on a one–way quantum computer. Phys Rev Lett. 2007;98:140501.
21. Bernstein E, Vazirani U. Proceedings of the twenty–fifth annual ACM symposium on theory of computing (STOC ’93). 1993;11–20.
22. Bernstein E, Vazirani U. Quantum complexity theory. SIAM J 1997;26(5):1411–1473.
23. Simon DR. On the power of quantum computation. Foundations of computer science proceedings 35th annual symposium on foundations of computer science. 1994;116–123.
24. Du J, Shi M, Zhou X, Fan Y, Ye BJ, et al. Phys Rev. 2001;64: 042306.
25. Brainis E, Lamoureux LP, Cerf NC, et al. Phys Rev Lett. 2003;90:157902.
26. Cross W, Smith G, Smolin JA. Quantum learning robust to noise. Phys. Rev. 2015;92:012327.
27. Li H, Yang L. A quantum algorithm for approximating the influences of Boolean functions and its applications. Quantum Inf Process. 2015;14(6):1787–1797.
28. Nagata K, Nakamura T. The Deutsch–Jozsa Algorithm Can Be Used for Quantum Key Distribution. Open Access Library Journal. 2015; p. 1–6.
29. Fallek SD, Herold CD, McMahon BJ, et al. Transport implementation of the Bernstein–Vazirani algorithm with ion qubits. New J. Phys. 2016;18:083030.