Talk:Bernstein–Vazirani algorithm

Overly verbose 'Implementation' section

The 'Implementation' section is one long code snippet in one of the quantum computing frameworks.

This seems much too long, not very enlightening and very biased towards a single framework. I would suggest that this section be deleted. Or replaced with a pedagogical example based on quantum circuits (which are common to all approaches to quantum algorithms).

Note that I work on a rival framework, and so may be biased. So I would appreciate other opinions.

Woottonjames (talk) 22:24, 20 December 2019 (UTC)

I agree that it seems unnecessary, and I have no bias towards any of the quantum computing languages. I'm not sure whether Wikipedia has any guidelines around this sort of thing, but pseudocode seems to be used in favor of any particular language. Note that swap test also has a Cirq implementation, so presumably that should be changed or removed as well.

Fawly (talk) 10:12, 21 December 2019 (UTC)

Someone added Qiskit code again. Personally, I don't think it's useful. Miguel M. (talk) 14:19, 12 February 2025 (UTC)

I agree that it's not useful and find that this is textbook material, not encyclopedic material. A link to code or pseudocode could be included as a footnote or weblink. It's also a kind of "original research": there is no source provided for the code. It's like proving a theorem instead of paraphrasing a proof and giving a reference for where to find it. --Qcomp (talk) 17:50, 12 February 2025 (UTC)

I've undone the changes. Worth noticing this user is doing the same across multiple pages, e.g., Simon's problem. Miguel M. (talk) 14:28, 14 February 2025 (UTC)

A mistake in the algorithm section

The exponent in the fourth term of the diagram should be $(s*x)+(x*y)$.

Missing information in Problem Statement

The problem statement gives the non-decision version of the problem. However, it's stated in the introduction that the B.-V. algorithm separates BQP and BPP, which requires some decision problem. It's not clear from the statement what this decision problem should be (to preserve the problem's hardness).

From reading the original paper it seems that the decision version follows from a significant complication of the non-decision problem. I can't quite tell what's going on from that reference, but the earlier STOC'93 version of the paper suggests to me that the reduction to a decision problem is made by the inclusion of a second random oracle (denoted $g$) that maps $k\mapsto \{0,1\}$. I'm not confident to make a change to the article without some confirmation. Miguelmurca (talk) 17:46, 16 January 2025 (UTC)

These classnotes make things clearer: there are in fact two versions of Bernstein-Vazirani, the recursive and the non-recursive forms. The current problem statement is for the non-recursive problem, but only the recursive problem is a decision problem. Furthermore, while the non-decision version has a super-exponential query complexity separation ($O(1)$ vs. $\Omega (n)$), the decision version has a superpolynomial (but not exponential) separation ($O(n)$ vs. $\Omega (n^{\log n})$). This is an important aspect that should really be included in the article, due to the relationship with Simon's Problem. As it stands, it looks like Bernstein-Vazirani provides a stronger separation between BPP and BQP than Simon's problem, when it's in fact the other way around. Miguelmurca (talk) 18:47, 16 January 2025 (UTC)

I've added some words about this in a dedicated section. Miguelmurca (talk) 10:07, 17 January 2025 (UTC)