Generalization of the Bernstein-Vazirani Algorithm

Koji Nagata, Tadao Nakamura

Published Aug 1, 2016• 3 citations

Abstract

We present generalization of the Bernstein-Vazirani algorithm. Suppose there are many natural numbers: $a_1,a_2,a_3,\ldots,a_N$. Here, we introduce a function: $ g:{\bf N}\rightarrow \{0,1\}. $ Our goal is to determine the following values simultaneously: $ g(a_1),g(a_2),g(a_3),\ldots, g(a_N). $ The speed to determine $N$ values improves by a factor of $N$ by comparing the classical case. We obtain the Bernstein-Vazirani algorithm when $g:a_i\rightarrow a_i$.

Related papers

Generalization of the Bernstein-Vazirani Algorithm Beyond Qubit Systems

Koji Nagata, Tadao Nakamura, Shahrokh Heidari +2 more

Sep 1, 20180 citations

The Generalized Bernstein-Vazirani Algorithm for Determining an Integer String

Koji Nagata, Tadao Nakamura, Han J.F. Geurdes +3 more

Mar 1, 20180 citations

A Method of Computing Many Functions Simultaneously by Using Many Parallel Quantum Systems

Koji Nagata, Germano Resconi, Tadao Nakamura +4 more

Apr 1, 20171 citation

A Generalization of Bernstein-Vazirani Algorithm to Qudit Systems

R Narayanan Krishna, Vishesh Makwana, Ananda Padhmanabhan Suresh

arXiv:1609.03185Sep 11, 20165 citations

Quantum Algorithm Determining a Homogeneous Linear Function

Koji Nagata, Tadao Nakamura, Han J.F. Geurdes +4 more

Sep 1, 20170 citations

New Method of Calculating a Multiplication by using the Generalized Bernstein-Vazirani Algorithm

Koji Nagata, Tadao Nakamura, Han J.F. Geurdes +3 more

International Journal of Theoretical PhysicsFeb 12, 20186 citations

Generalization of the Bernstein-Vazirani Algorithm

Koji Nagata, Tadao Nakamura

Published Aug 1, 2016• 3 citations

OpenAlex

Abstract

We present generalization of the Bernstein-Vazirani algorithm. Suppose there are many natural numbers:

a_1,a_2,a_3,\ldots,a_N

. Here, we introduce a function:

g:{\bf N}\rightarrow \{0,1\}.

Our goal is to determine the following values simultaneously:

g(a_1),g(a_2),g(a_3),\ldots, g(a_N).

The speed to determine

N

values improves by a factor of

N

by comparing the classical case. We obtain the Bernstein-Vazirani algorithm when

g:a_i\rightarrow a_i

Related papers

Generalization of the Bernstein-Vazirani Algorithm Beyond Qubit Systems

Koji Nagata, Tadao Nakamura, Shahrokh Heidari +2 more

First, we review the Bernstein-Vazirani algorithm for determining a bit string. Next, we discuss the generalized Bernstein-Vazirani algorithm for determining a natural number string. Finally, we discuss the generalized Bernstein-Vazirani algorithm for determining an integer string. All of the generalized algorithms presented here have the following structure. Given the set of real values $\{a_1,a_2,a_3,\ldots,a_N\}$ and a special function $g$ , we determine $N$ values of the function $g(a_1),g(a_2),g(a_3),\ldots, g(a_N)$ simultaneously. The speed of determining the strings is shown to outperform the best classical case by a factor of $N$ in every case.First, we review the Bernstein-Vazirani algorithm for determining a bit string. Next, we discuss the generalized Bernstein-Vazirani algorithm for determining a natural number string. Finally, we discuss the generalized Bernstein-Vazirani algorithm for determining an integer string. All of the generalized algorithms presented here have the following structure. Given the set of real values $\{a_1,a_2,a_3,\ldots,a_N\}$ and a special function $g$, we determine $N$ values of the function $g(a_1),g(a_2),g(a_3),\ldots, g(a_N)$ simultaneously. The speed of determining the strings is shown to outperform the best classical case by a factor of $N$ in every case.

Sep 1, 20180 citations

The Generalized Bernstein-Vazirani Algorithm for Determining an Integer String

Koji Nagata, Tadao Nakamura, Han J.F. Geurdes +3 more

We present the generalized Bernstein-Vazirani algorithm for determining a restricted integer string. Given the set of real values $\{a_1,a_2,a_3,\ldots,a_N\}$ and a function $g:{\bf R}\rightarrow {\bf Z}$ , 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$ . The method determines the maximum of and the minimum of the function $g$ that the finite domain is $\{a_1,a_2,a_3,\ldots,a_N\}$ .We present the generalized Bernstein-Vazirani algorithm for determining a restricted integer string. Given the set of real values $\{a_1,a_2,a_3,\ldots,a_N\}$ and a function $g:{\bf R}\rightarrow {\bf Z}$, 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$. The method determines the maximum of and the minimum of the function $g$ that the finite domain is $\{a_1,a_2,a_3,\ldots,a_N\}$.

Mar 1, 20180 citations

A Method of Computing Many Functions Simultaneously by Using Many Parallel Quantum Systems

Koji Nagata, Germano Resconi, Tadao Nakamura +4 more

We suggest a method of computing many functions in the same time by using many parallel quantum systems. We use the Bernstein-Vazirani algorithm. Given the set of real values $\{a_1,a_2,a_3,\ldots,a_N\}$ , and the function $g:{\bf R}\rightarrow \{0,1\}$ , we shall determine the following values $\{g(a_1),g(a_2),g(a_3),\ldots, g(a_N)\}$ simultaneously. By using $M$ parallel quantum systems, we can compute $M$ functions $g^1,g^2,...,g^M$ simultaneously. The speed of determining the $N\times M$ values will be shown to outperform the classical case by a factor of $N$ .We suggest a method of computing many functions in the same time by using many parallel quantum systems. We use the Bernstein-Vazirani algorithm. Given the set of real values $\{a_1,a_2,a_3,\ldots,a_N\}$, and the function $g:{\bf R}\rightarrow \{0,1\}$, we shall determine the following values $\{g(a_1),g(a_2),g(a_3),\ldots, g(a_N)\}$ simultaneously. By using $M$ parallel quantum systems, we can compute $M$ functions $g^1,g^2,...,g^M$ simultaneously. The speed of determining the $N\times M$ values will be shown to outperform the classical case by a factor of $N$.

Apr 1, 20171 citation

A Generalization of Bernstein-Vazirani Algorithm to Qudit Systems

R Narayanan Krishna, Vishesh Makwana, Ananda Padhmanabhan Suresh

A quantum algorithm to solve the parity problem is better than its most efficient classical counter- part with a separation that is polynomial in the number of queries. This was shown by E. Bernstein and U. Vazirani and was one of the earliest indications that the quantum information processing can outperform the classical one by a significant margin. The problem and its solution both is usually stated for a 2-level system since we generally work with bits/qubits. However, many works have been done generalizing known quantum computing techniques to higher level systems. Following this, we look at a generalization of the Bernstein-Vazirani algorithm implemented on a general qudit system.A quantum algorithm to solve the parity problem is better than its most efficient classical counter- part with a separation that is polynomial in the number of queries. This was shown by E. Bernstein and U. Vazirani and was one of the earliest indications that the quantum information processing can outperform the classical one by a significant margin. The problem and its solution both is usually stated for a 2-level system since we generally work with bits/qubits. However, many works have been done generalizing known quantum computing techniques to higher level systems. Following this, we look at a generalization of the Bernstein-Vazirani algorithm implemented on a general qudit system.

arXiv:1609.03185Sep 11, 20165 citations

Quantum Algorithm Determining a Homogeneous Linear Function

Koji Nagata, Tadao Nakamura, Han J.F. Geurdes +4 more

We present a method of fast determining a homogeneous linear function $f(x):= s.x=s_1x_1+ s_2x_2+\dots+s_Nx_N$ from $\{0,1,\dots,d-1\}^N$ with coefficients $s=(s_1,\dots,s_N)$ . Here $x=(x_1,\dots,x_N)$ and $x_j\in{\bf R}$ . Given the interpolation values $(f(1), f(2),...,f(N))=\vec{y}$ , we shall determine the unknown coefficients $s = (s_1(\vec{y}),\dots, s_N(\vec{y}))$ of the linear function, simultaneously. The speed of determining the values is shown to outperform the classical case by a factor of $N$ . Our method is based on the generalized Bernstein-Vazirani algorithm \cite{BVG} to qudit systems \cite{BVD}.We present a method of fast determining a homogeneous linear function $f(x):= s.x=s_1x_1+ s_2x_2+\dots+s_Nx_N$ from $\{0,1,\dots,d-1\}^N$ with coefficients $s=(s_1,\dots,s_N)$. Here $x=(x_1,\dots,x_N)$ and $x_j\in{\bf R}$. Given the interpolation values $(f(1), f(2),...,f(N))=\vec{y}$, we shall determine the unknown coefficients $s = (s_1(\vec{y}),\dots, s_N(\vec{y}))$ of the linear function, simultaneously. The speed of determining the values is shown to outperform the classical case by a factor of $N$. Our method is based on the generalized Bernstein-Vazirani algorithm \cite{BVG} to qudit systems \cite{BVD}.

Sep 1, 20170 citations

New Method of Calculating a Multiplication by using the Generalized Bernstein-Vazirani Algorithm

Koji Nagata, Tadao Nakamura, Han J.F. Geurdes +3 more

International Journal of Theoretical PhysicsFeb 12, 20186 citations

We present generalization of the Bernstein-Vazirani algorithm. Suppose there are many natural numbers:

a_1,a_2,a_3,\ldots,a_N

. Here, we introduce a function:

g:{\bf N}\rightarrow \{0,1\}.

Our goal is to determine the following values simultaneously:

g(a_1),g(a_2),g(a_3),\ldots, g(a_N).

The speed to determine

N

values improves by a factor of

N

by comparing the classical case. We obtain the Bernstein-Vazirani algorithm when

g:a_i\rightarrow a_i

\{a_1,a_2,a_3,\ldots,a_N\}

and a special function

g

, we determine

N

values of the function

g(a_1),g(a_2),g(a_3),\ldots, g(a_N)

simultaneously. The speed of determining the strings is shown to outperform the best classical case by a factor of

N

in every case.

We present the generalized Bernstein-Vazirani algorithm for determining a restricted integer string. Given the set of real values

\{a_1,a_2,a_3,\ldots,a_N\}

and a function

g:{\bf R}\rightarrow {\bf Z}

, 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

. The method determines the maximum of and the minimum of the function

g

that the finite domain is

\{a_1,a_2,a_3,\ldots,a_N\}

We suggest a method of computing many functions in the same time by using many parallel quantum systems. We use the Bernstein-Vazirani algorithm. Given the set of real values

\{a_1,a_2,a_3,\ldots,a_N\}

, and the function

g:{\bf R}\rightarrow \{0,1\}

, we shall determine the following values

\{g(a_1),g(a_2),g(a_3),\ldots, g(a_N)\}

simultaneously. By using

M

parallel quantum systems, we can compute

M

functions

g^1,g^2,...,g^M

simultaneously. The speed of determining the

N\times M

values will be shown to outperform the classical case by a factor of

N

We present a method of fast determining a homogeneous linear function

f(x):= s.x=s_1x_1+ s_2x_2+\dots+s_Nx_N

from

\{0,1,\dots,d-1\}^N

with coefficients

s=(s_1,\dots,s_N)

. Here

x=(x_1,\dots,x_N)

and

x_j\in{\bf R}

. Given the interpolation values

(f(1), f(2),...,f(N))=\vec{y}

, we shall determine the unknown coefficients

s = (s_1(\vec{y}),\dots, s_N(\vec{y}))

of the linear function, simultaneously. The speed of determining the values is shown to outperform the classical case by a factor of

N

. Our method is based on the generalized Bernstein-Vazirani algorithm \cite{BVG} to qudit systems \cite{BVD}.