Questions tagged [bernstein-vazirani-algorithm]
For questions on the Bernstein-Vazirani algorithm.
4
questions
7
votes
0answers
89 views
What are examples of non-oracular versions of famous oracular problems?
Most quantum algorithms proposed, including Deutsch-Jozsa, Simon's, Bernstein-Vazirani etc, involve querying an oracle. If I understand correctly, the speedups depend on the oracle being efficiently ...
3
votes
2answers
72 views
Is the intuition of quantum parallelism always correct?
I recently read in Section 7.5.2 of Quantum Computing: A Gentle Introduction by Eleanor Rieffel and Wolfgang Polak a section in which they criticize the view of quantum parallelism in quantum ...
3
votes
1answer
63 views
Deutsch-Jozsa algorithm as a generalization of Bernstein-Vazirani
It is known that both algorithms use the same gates: $H^{\oplus n}U_fH^{\oplus n}$.
After the circuit, the qubits are in the state $\sum_y \left( \sum_x (-1)^{f(x)+xy} \right) |y\rangle $.
In DJ's ...
3
votes
1answer
120 views
Is the Bernstein-Vazirani algorithm dependent on the specific behavior of the oracle?
My understanding of the Bernstein-Vazirani algorithm is as follows:
We have a black box oracle with secret string $s$. The black box does
$$f(x) =s\cdot{x}=(\sum_1^n s_i\cdot{x_i})$$
We run each ...
