I am reading a book section about the difference between the Deutsch-Jozsa and the Bernstein-Vazirani Algorithm and here is the text:

As with DJ, the goal of BV is also to ascertain the nature of a black-box Boolean function. While it is true that DJ demonstrates an advantage of quantum over classical computing, if we allow for a small error rate, then the advantage disappears: both classical and quantum approaches are in the order of O(1) time complexity [176].

BV was the first algorithm developed that shows a clear separation between quantum and classical computing even allowing for error, i.e., a true nondeterministic speedup.

Reference: Quantum Computing: An Applied Approach, Second Edition by Jack D. Hidary, page 110

[176] M. Loceff. A Course in Quantum Computing. 2015.

How do you explain this difference? Why and how the BV algorithm allows for a small error rate?


1 Answer 1


What (I suspect) this book means by "small error rate" is "if we allow for some non-zero probability of failure in the outcome", not "there's some noise in the system".

For example, in Deutsch-Jozsa, you're looking at whether a function with $n$ bits of input is constant or balanced. With a quantum computer, you can determine the outcome with certainly after exactly 1 oracle call. With a classical computer, to guarantee that you can identify the different require $2^{n-1}+1$ calls. But you could run a classical version of the algorithm making (for example) 50 oracle calls. If all answers are the same, you say the function is constant, otherwise you say it's balanced. You can only make a mistake if the function is balanced but you claim it's constant. That happens with a probability $1/2^{49}$ assuming your inputs are randomly distributed. Most people could probably accept this level of failure (or some fixed level of failure), in which case you can use a constant number of oracle calls in the classical case as well. So, in that sense, Deutsch-Jozsa does not allow a change in the scaling.

On the other hand, Bernstein-Vazirani shows a scaling improvement even if you allow the classical algorithm to have some probability of failure. To see this, recall the problem: find the $s$ for which $f(x)=f(x\oplus s)$. The quantum algorithm, again, takes exactly 1 step. On the other hand, imagine we make $k$ samples of the classical oracle. This gives us the opportunity to compare $\binom{k}{2}$ different pairs of strings to see if any make a collision. Each (if everything is selected with sufficient uniformity) has a probability of $1/(2^n-1)$ of finding a collision. Hence, the success probability is no better than $$ \frac{\binom{k}{2}}{2^n}<\frac{k^2}{2^n}. $$ For the success probability to not be exponentially small in $n$, you need $k\sim 2^{n/2}$. So, we get this big, exponential, separation between the deterministic quantum algorithm, and the bounded error classical algorithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.