Abstract
We present a new method of more speedily calculating a multiplication by using the generalized Bernstein-Vazirani algorithm and many parallel quantum systems. Given the set of real values \(\{a_{1},a_{2},a_{3},\ldots ,a_{N}\}\) and a function \(g:\textbf {R}\rightarrow \{0,1\}\), we shall determine the following values \(\{g(a_{1}),g(a_{2}),g(a_{3}),\ldots , g(a_{N})\}\) simultaneously. The speed of determining the values is shown to outperform the classical case by a factor of \(N\). Next, we consider it as a number in binary representation; M1 = (g(a1),g(a2),g(a3),…,g(a N )). By using \(M\) parallel quantum systems, we have \(M\) numbers in binary representation, simultaneously. The speed of obtaining the \(M\) numbers is shown to outperform the classical case by a factor of \(M\). Finally, we calculate the product; \( M_{1}\times M_{2}\times \cdots \times M_{M}. \) The speed of obtaining the product is shown to outperform the classical case by a factor of N × M.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Introduction
As for applications of the quantum theory, implementation of a quantum algorithm to solve Deutsch’s problem [1,2,3] on a nuclear magnetic resonance quantum computer is reported firstly [4]. An implementation of the Deutsch-Jozsa algorithm on an ion-trap quantum computer is also reported [5]. There are several attempts to use single-photon two-qubit states for quantum computing. Oliveira et al. implements Deutsch’s algorithm with polarization and transverse spatial modes of the electromagnetic field as qubits [6]. Single-photon Bell states are prepared and measured [7]. Also the decoherence-free implementation of Deutsch’s algorithm is reported by using such a single-photon and by using two logical qubits [8]. More recently, a one-way based experimental implementation of Deutsch’s algorithm is reported [9].
In 1993, the Bernstein-Vazirani algorithm was reported [10, 11]. It can be considered as an extended Deutsch-Jozsa algorithm. In 1994, Simon’s algorithm was reported [12]. Implementation of a quantum algorithm to solve the Bernstein-Vazirani parity problem without entanglement on an ensemble quantum computer is reported [13]. Fiber-optics implementation of the Deutsch-Jozsa and Bernstein-Vazirani quantum algorithms with three qubits is discussed [14]. Quantum learning robust against noise is studied [15]. A quantum algorithm for approximating the influences of Boolean functions and its applications are recently reported [16]. Quantum computation with coherent spin states and the close Hadamard problem are also discussed [17]. Transport implementation of the Bernstein-Vazirani algorithm with ion qubits is more recently reported [18]. Quantum Gauss-Jordan elimination and simulation of accounting principles on quantum computers are discussed [19]. We mention that the dynamical analysis of Grover’s search algorithm in arbitrarily high-dimensional search spaces is studied [20]. A method of computing many functions simultaneously by using many parallel quantum systems is reported [21].
On the other hand, the earliest quantum algorithm, the Deutsch-Jozsa algorithm, is representative to show that quantum computation is faster than the classical counterpart with a magnitude that grows exponentially with the number of qubits. In 2015, it was discussed that the Deutsch-Jozsa algorithm can be used for quantum key distribution [22]. In 2017, it was discussed that secure quantum key distribution based on Deutsch’s algorithm using an entangled state [23]. Subsequently, a highly speedy secure quantum cryptography based on the Deutsch-Jozsa algorithm is proposed [24].
In this work we present a new method of more speedily calculating a multiplication by using the generalized Bernstein-Vazirani algorithm and many parallel quantum systems. Given the set of real values \(\{a_{1},a_{2},a_{3},\ldots ,a_{N}\}\) and a function \(g:\textbf {R}\rightarrow \{0,1\}\), we shall determine the following values \(\{g(a_{1}),g(a_{2}),g(a_{3}),\ldots , g(a_{N})\}\) simultaneously. The speed of determining the values is shown to outperform the classical case by a factor of \(N\). Next, we consider it as a number in binary representation; M1 = (g(a1),g(a2),g(a3),…,g(a N )). By using \(M\) parallel quantum systems, we have \(M\) numbers in binary representation, simultaneously. The speed of obtaining the \(M\) numbers is shown to outperform the classical case by a factor of \(M\). Finally, we calculate the product; \( M_{1}\times M_{2}\times \cdots \times M_{M}. \) The speed of obtaining the product is shown to outperform the classical case by a factor of N × M.
2 The Generalized Bernstein-Vazirani Algorithm
Let us suppose that we are given the following sequence of real values
Let us now introduce the function
One step is of determining the following values
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
which is a function with a \(N\)-bit domain and a 1-bit range. We construct the following function
where \(a_{i}\) is a real value. Here \(g(a)\) symbolizes
Let us follow the quantum states through the algorithm. The input state is
where \(|0\rangle ^{\otimes N} =\overbrace {|0\rangle \otimes |0\rangle \otimes ...\otimes |0\rangle }^{N}\). After the componentwise Hadamard transforms on the state (7)
we have
Next, the function \(f\) is evaluated using
giving
Here \(y\oplus f(x)\) is the bitwise XOR (exclusive OR) of \(y\) and \(f(x)\). By checking the cases \(x = 0\) and \(x = 1\) separately, we see that for a single qubit
Thus
This can be summarized more succinctly in the very useful equation
where \(x\cdot z\) is the bitwise inner product of \(x\) and \(z\), modulo 2. Using the (14) and (11), we can now evaluate H⊗N|ψ2〉 = |ψ3〉
Thus
Because we have
we can see that
Therefore, the sum is zero if \(z\neq g(a)\) and is \(2^{N}\) if \(z= g(a)\). Thus
from which
can be obtained. That is to say, if we measure \(|g(a_{1})g(a_{2})\cdots g(a_{N})\rangle \) then we can retrieve the following values
using a single query. All we have to do is of performing one quantum measurement.
The speed of determining \(N\) values improves by a factor of \(N\) as compared to the classical counterpart. Notice that we recover the Bernstein-Vazirani algorithm when \(g:a_{i}\rightarrow a_{i}\).
3 Calculating a Multiplication by using the Generalized Bernstein-Vazirani Algorithm
We present a new method of more speedy calculating a multiplication by using many parallel quantum systems. By using \(M\) parallel quantum systems, we can compute \(M\) functions \(g^{1},g^{2},...,g^{M}\) simultaneously.
Let us suppose that we are given the following another sequence of real values
Let us now introduce the function
We can determine the following values by using the generalized Bernstein-Vazirani algorithm
By using \(M\) parallel quantum systems, we can retrieve the following values
In the case, we measure the following quantum state
All we have to do is of performing one quantum measurement.
We consider them as numbers in binary representation
Therefore, by using \(M\) parallel quantum systems, we have \(M\) numbers in binary representation, simultaneously. The speed of obtaining the \(M\) numbers is shown to outperform the classical case by a factor of \(M\). Finally, we calculate the product; M1 × M2 ×⋯ × M M . The speed of obtaining the product is shown to outperform the classical case by a factor of \(N\times M\).
As an example, if \(N = 2\) and \(M = 3\), we may have
and we have
An experimental evidence is very interesting and it is a further investigation.
4 Conclusions
In conclusion, we have presented a new method of more speedily calculating a multiplication by using the generalized Bernstein-Vazirani algorithm and many parallel quantum systems. Given the set of real values \(\{a_{1},a_{2},a_{3},\ldots ,a_{N}\}\) and a function \(g:\textbf {R}\rightarrow \{0,1\}\), we shall have determined the following values \(\{g(a_{1}),g(a_{2}),g(a_{3}),\ldots , g(a_{N})\}\) simultaneously. The speed of determining the values has been shown to outperform the classical case by a factor of \(N\). Next, we have considered it as a number in binary representation; M1 = (g(a1),g(a2),g(a3),…,g(a N )). By using \(M\) parallel quantum systems, we have had \(M\) numbers in binary representation, simultaneously. The speed of obtaining the \(M\) numbers has been shown to outperform the classical case by a factor of \(M\). Finally, we have calculated the product; \( M_{1}\times M_{2}\times \cdots \times M_{M}. \) The speed of obtaining the product has been shown to outperform the classical case by a factor of \(N\times M\).
References
Deutsch, D.: Proc. Roy. Soc. London Ser. A 400, 97 (1985)
Deutsch, D., Jozsa, R.: Proc. Roy. Soc. London Ser. A 439, 553 (1992)
Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Proc. Roy. Soc. London Ser. A 454, 339 (1998)
Jones, J. A., Mosca, M.: J. Chem. Phys. 109, 1648 (1998)
Gulde, S., Riebe, M., Lancaster, G. P. T., Becher, C., Eschner, J., Häffner, H., Schmidt-Kaler, F., Chuang, I. L., Blatt, R.: Nature (London) 421, 48 (2003)
de Oliveira, A. N., Walborn, S. P., Monken, C. H.: J. Opt. B: Quantum Semiclass. Opt. 7, 288–292 (2005)
Kim, Y. -H.: Phys. Rev. A 67, 040301(R) (2003)
Mohseni, M., Lundeen, J. S., Resch, K. J., Steinberg, A. M.: Phys. Rev. Lett. 91, 187903 (2003)
Tame, M. S., Prevedel, R., Paternostro, M., Böhi, P., Kim, M. S., Zeilinger, A.: Phys. Rev. Lett. 98, 140501 (2007)
Bernstein, E., Vazirani, U: In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC ’93), pp. 11–20 (1993). https://doi.org/10.1145/167088.167097
Bernstein, E., Vazirani, U.: SIAM J. Comput. 26–5, 1411–1473 (1997)
Simon, D. R.: Foundations of computer science. In: 35th Annual Symposium on Proceedings, pp. 116–123, retrieved 2011-06-06 (1994)
Du, J., Shi, M., Zhou, X., Fan, Y., Ye, B. J., Han, R., Wu, J.: Phys. Rev. A 64, 042306 (2001)
Brainis, E., Lamoureux, L. -P., Cerf, N. J., Emplit, P. h., Haelterman, M., Massar, S.: Phys. Rev. Lett. 90, 157902 (2003)
Cross, A. W., Smith, G., Smolin, J. A.: Phys. Rev. A 92, 012327 (2015)
Li, H., Yang, L.: Quantum Inf. Process. 14, 1787 (2015)
Adcock, M. R. A., Hoyer, P., Sanders, B. C.: Quantum Inf. Process. 15, 1361 (2016)
Fallek, S. D., Herold, C. D., McMahon, B. J., Maller, K. M., Brown, K. R., Amini, J. M.: J. Phys. 18, 083030 (2016)
Diep, D. N., Giang, D. H., Van Minh, N.: Int. J. Theor. Phys. 56, 1948 (2017). https://doi.org/10.1007/s10773-017-3340-8
Jin, W.: Quantum Inf. Process. 15, 65 (2016)
Nagata, K., Resconi, G., Nakamura, T., Batle, J., Abdalla, S., Farouk, A., Geurdes, H.: Asian J. Math. Phys. 1(1), 1–4 (2017)
Nagata, K., Nakamura, T.: Open Access Library J. 2, e1798 (2015). https://doi.org/10.4236/oalib.1101798
Nagata, K., Nakamura, T.: Int. J. Theor. Phys. 56, 2086 (2017). https://doi.org/10.1007/s10773-017-3352-4
Nagata, K., Nakamura, T., Farouk, A.: Int. J. Theor. Phys. 56, 2887 (2017). https://doi.org/10.1007/s10773-017-3456-x
Acknowledgements
All authors are grateful to the anonymous referees who provided a great insight into the completion of the final manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Nagata, K., Nakamura, T., Geurdes, H. et al. New Method of Calculating a Multiplication by using the Generalized Bernstein-Vazirani Algorithm. Int J Theor Phys 57, 1605–1611 (2018). https://doi.org/10.1007/s10773-018-3687-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10773-018-3687-5