Questions tagged [bernstein-vazirani-algorithm]
For questions on the Bernstein-Vazirani algorithm.
21
questions
2
votes
1
answer
92
views
Applicability of the Bernstein-Vazirani to different modulus
The Bernstein Vazirani can solve s for f(x) = s(dot product) x mod 2. My question is if its possible to modify this to work for mod 3,4 etc. Is this even possible?
Edit: Whats the probability of the ...
1
vote
1
answer
67
views
Can the Bernstein-Vazirani algorithm be applied to a remote classical function?
Can the Bernstein-Vazirani algorithm be applied to a remote classical function? As in, a function we are not able to set up an oracle for and is completely classical?
4
votes
2
answers
93
views
How are Deutsch-Jozsa and Bernstein-Vazirani algorithms a fair comparison to classical ones
In both of these example algorithms, the Classical one is restricted to a single bit of output, while the Quantum one is allowed to use information exposed from multiple bits. There is no question ...
1
vote
1
answer
57
views
In the Bernstein-Vazirani algorithm, what is the use of the second Hadamard gate?
In the Bernstein-Vazirani algorithm, what is the use of the second Hadamard gate? What happens if I remove it? Would the algorithm works fine? I read something about it closing the interference.
3
votes
1
answer
179
views
What are quantum algorithms with only one possible outcome with probability equal to one?
I would like to study circuits with only one possible outcome. Quantum phase estimation, Bernstein-Vazirani, and in part Deutsch-Jozsa (for constant functions) come to mind - do you know any other ...
1
vote
2
answers
67
views
Can there be different gate implementations of same oracle implementation?
I have been reading about Bernstein-Vazirani Algorithm, and it uses what is known as a phase oracle. Basically, it is CNOT gate with several controls attached to the ancilla qubit $|-\rangle$ (it is ...
1
vote
1
answer
49
views
Worst Case Asymptotic Complexity of Berstein-Vazirani
How would one determine the worst-case asymptotic complexity ($\theta$) of a Bernstein-Vazirani circuit encoding the secret 1111?
3
votes
2
answers
76
views
Bernstein Vazirani Algorithm widget (bv_widget) in the Qiskit documentation
I'm new to quantum computing and Qiskit, so please be patient with me. I'm going through the info on Bernstein Vazirani. Here is the link to the section: https://qiskit.org/textbook/ch-algorithms/...
2
votes
2
answers
140
views
What does it mean for a circuit to be a valid instance of the Bernstein-Vazirani problem?
What does it mean for a circuit to be a valid instance of the Bernstein-Vazirani problem? It's not clear to me in the above circuit what the X gate is doing on the $b$ qubit. I guess it's just ...
2
votes
1
answer
236
views
How do I construct the oracle for a general Bernstein-Vazirani circuit?
Say I have a secret of length $n$, $s = |x_{n-1}x_{n-2}...x_0 \rangle$. If I want to construct an oracle for this problem would I just insert a CNOT gate on every qubit where the secret's value is 1? ...
3
votes
2
answers
172
views
In the Bernstein-Vazirani circuit, if the secret is all 0s, would the oracle just be nothing?
I'm self-studying quantum computing and have gone through the Wikipedia article on the Berstein-Vazirani algorithm and believe that I understand it. I'm looking to verify my understanding and hope ...
4
votes
2
answers
162
views
Worked example of Bernstein-Vazirani - understanding bitwise product
From chapter 3.3 or the Qiskit Textbook, I'm trying to follow the worked example of the quantum solution for Bernstein-Vazirani.
I'm having trouble with what I think should be a trivial bit of ...
2
votes
1
answer
143
views
Bernstein-Vazirani Gate IBM Q Noise
When running the attached Bernstein-Vazirani gate on IBM Q, with 1024 shots on ibmq_16_melbourne, I receive the expected result of "00110" with 26.563% success. I notice that there is a lot ...
1
vote
2
answers
144
views
Does anyone know of Qiskit source code for a Bernstein Vazirani grover's algorithm for N bits? If so please share
I'm just getting started in the space of quantum computing, I've built a 5 qubit program for Bernstein-Vazirani, but am trying to figure out how to go about building an N bit version of Bernstein-...
3
votes
1
answer
179
views
Speed up in Bernstein-Vazirani algorithm and Gottesman-Knill theorem
The Bernstein-Vazirani problem:
Let $f$ be a function from bit strings of length $n$ to a single bit,
$$f: \{ 0, 1\}^n \to \{0, 1\} $$
thus all input bit strings $x \in \{0,1\}^n$. There exists a ...
1
vote
2
answers
142
views
Bernstein-Vazirani IBMQ error due to probably measurements
I'm using the following piece of python code:
...
-4
votes
1
answer
123
views
Bernstein-Vazirani algorithm in IBM Q Experience [closed]
I have composed the gate with IBM Q Experience, but I do not know how to set the answer.
Please tell me how to set it?
10
votes
1
answer
265
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 ...
4
votes
2
answers
197
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 ...
4
votes
1
answer
231
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 ...
4
votes
1
answer
355
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 ...