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 {a1,a2,a3,…,aN} and a special function g, we determine N values of the function g(a1),g(a2),g(a3),…,g(aN) 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 {a1,a2,a3,…,aN} and a function g:R→Z, we shall determine the following values {g(a1),g(a2),g(a3),…,g(aN)} 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 {a1,a2,a3,…,aN}.
We present generalization of the Bernstein-Vazirani algorithm. Suppose there are many natural numbers: a1,a2,a3,…,aN. 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:ai→ai.
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 {a1,a2,a3,…,aN}, and the function g:R→{0,1}, we shall determine the following values {g(a1),g(a2),g(a3),…,g(aN)} simultaneously. By using M parallel quantum systems, we can compute M functions g1,g2,...,gM simultaneously. The speed of determining the N×M values will be shown to outperform the classical case by a factor of N.
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.
We present a method of fast determining a homogeneous linear function f(x):=s.x=s1x1+s2x2+⋯+sNxN from {0,1,…,d−1}N with coefficients s=(s1,…,sN). Here x=(x1,…,xN) and xj∈R. Given the interpolation values (f(1),f(2),...,f(N))=y, we shall determine the unknown coefficients s=(s1(y),…,sN(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}.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlogn) and a near-matching lower bound of Ω(n). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n) upper bound.
We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n], where an algorithm may test whether xS=b for an arbitrary S∈Q and b∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set.
All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning x is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→R the ratio of the maximum value of f to the maximum (over T∈Q) standard deviation of f on a subcube whose free variables are exactly T.'
To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.