In this short contribution we present a generalization of the Bernstein-Vazirani algorithm. Givenhe set of real values
and the function g: R → {0, 1}, we shall determinethe following values
simultaneously. We are thus generalizing theBernstein-Vazirani algorithm. We recover the usual algorithm when
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 mechanics1-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.6 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,7 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,14 first experimentally realized on a nuclear magnetic resonance proof-of principle quantum computer.15 Implementation of the Deutsch-Jozsa algorithm on an ion-trap quantum computer has also been achieved.16 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.17 Other achievements also include single-photon Bell states preparation and measurement,18 a decoherence free implementation of Deutsch’s algorithm using single photon and using two logical qubits19 and, more recently,a one-way quantum computing implementation of the algorithm.20 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 algorithm23 was discovered, among others. There has been a experimental implementation of a quantum algorithm that solves the Bernstein-Vazirani parity problem without entanglement.24 Additionally, fiber-optics implementations of the Deutsch-Jozsa and Bernstein-Vazirani quantum algorithms with three qubits have been realized.25 Also, a variant of the algorithm for quantum learning being robust against noise has been introduced,26 as well as a quantum algorithm for approximating the influences of Boolean functions and its applications.27 The Bernstein-Vaziranial growth has been also versatile in quantum key distribution28 and transport implementation with ion qubits.29 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
(1)
Let us now introduce the function
(2)
Our goal is to determine the following values:
(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
(4)
which is a function with a N-bit domain and a 1-bitrange. We construct the following function:
(5)
where ai is a real value. Here
symbolizes
(6)
Let us follow the quantum states through the algorithm. The input state is
(7)
After the Hadamard transform on the state, we have
(8)
Next, the function f is evaluated using
(9)
Givening
(10)
After the Hadamard transform, using the previous equation and (10) we can now evaluate
(11)
Thus,
(12)
(13)
Thus,
(14)
from which
(15)
can be obtained. That is to say, if we measure
then we can retrieve the following values
(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
In the present work we have presented a generalization of the Bernstein-Vazirani algorithm. The advantage that is promised over its classical counterpart is
, much like in the vein of quantum parallelism, where the N coefficients of a pure state
can be known in one single quantum query.