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)

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)