Questions tagged [bernstein-vazirani-algorithm]

For questions on the Bernstein-Vazirani algorithm.

Filter by
Sorted by
Tagged with
2 votes
1 answer
61 views

Recursive Bernstein-Vazirani algorithm

Recently I've found the recursive Bernstein-Vazirani algorithm which is explained quite good in this paper CSE 599d - Quantum Computing The Recursive and Nonrecursive Bernstein-Vazirani Algorithm of ...
aghin00's user avatar
  • 129
2 votes
1 answer
117 views

Why is Bernstein-Vazirani guessing considered a one guess?

In Bernstein-Vazirani algorithm, we can see the application of $CX$ gates from each qubit that represents the bit in state 1, onto the $|-\rangle$ state. It seems clear to me that the $CX$ will apply ...
user10420480's user avatar
1 vote
1 answer
277 views

The difference between the Deutsch-Jozsa Algorithm and the Bernstein-Vazirani Algorithm

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 ...
Hamideh's user avatar
  • 269
2 votes
1 answer
156 views

Why can't Bernstein-Vazirani algorithm be classicaly computed in one try?

Instead of using n inputs (000...01, 000...10, ..., 100...00) and multiplying each one with the hidden number x, why can't we just try one input: 111...11 ? I can't think of an example of a binary ...
Confused engineer's user avatar
7 votes
1 answer
272 views

Were quantum computers conjectured to factor large numbers before Shor developed his algorithm?

Peter Shor has given wonderful accounts of the development of his algorithm, with a lot of detail on the activity in the field at around the early-mid 90's. He's been very free about emphasizing that ...
Mark Spinelli's user avatar
1 vote
1 answer
229 views

Understanding the Bernstein-Vazirani implementation from the qiskit website

My question is with regards to the implementation from the Qiskit textbook. From my understanding the algorithm is for finding out what an unknown bit-string is which in the classical case requires N ...
timmy1691's user avatar
0 votes
1 answer
77 views

Bernstein-Vazirani algorithm to find whether the secret has a one at a specific location

In the Bernstein- Vazirani Algorithm, we check whether the secret number has a '1' at a specific index of the number. If it's 1, we apply a CNOT gate, and then the algorithm gives the accurate value ...
Gandalf73's user avatar
  • 133
1 vote
1 answer
422 views

What Adding Modulo To Register Means

I was reading about the Jordan gradient algorithm(https://arxiv.org/pdf/quant-ph/0405146.pdf) and I am a bit confused about one of the phrases: Next, use the blackbox to compute f and add it modulo $...
MeltedStatementRecognizing's user avatar
0 votes
2 answers
127 views

Why are we getting secret number $50\%$ of time even if there is no negative phase in last qubit?

In Bernstein-Vazirani Algorithm, the role of the last qubit (here, $q_7$) is simply to dish out negative relative phases to each qubit representing a $1$ through the use of $\text{CNOT}$s. But if we ...
Vinay Sharma's user avatar
3 votes
1 answer
155 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 ...
user avatar
2 votes
1 answer
107 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?
Random's user avatar
  • 43
5 votes
2 answers
249 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 ...
user20364's user avatar
1 vote
1 answer
112 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.
n22's user avatar
  • 183
3 votes
1 answer
222 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 ...
stopper's user avatar
  • 443
1 vote
2 answers
125 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 ...
Chetan Waghela's user avatar
1 vote
1 answer
69 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?
QuantumLearner's user avatar
3 votes
2 answers
231 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/...
Doug's user avatar
  • 45
2 votes
2 answers
209 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 ...
QuantumLearner's user avatar
3 votes
1 answer
790 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? ...
QuantumLearner's user avatar
3 votes
2 answers
394 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 ...
QuantumLearner's user avatar
5 votes
2 answers
331 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 ...
David Fulton's user avatar
2 votes
1 answer
226 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 ...
GRT's user avatar
  • 21
1 vote
2 answers
172 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-...
soderpop's user avatar
3 votes
1 answer
337 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 ...
KAJ226's user avatar
  • 13.8k
1 vote
2 answers
201 views

Bernstein-Vazirani IBMQ error due to probably measurements

I'm using the following piece of python code: ...
silgon's user avatar
  • 167
-4 votes
1 answer
139 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?
吉川 喜次's user avatar
10 votes
1 answer
307 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 ...
BlackHat18's user avatar
  • 1,313
5 votes
2 answers
281 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 ...
Joery's user avatar
  • 173
4 votes
1 answer
302 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 ...
Labo's user avatar
  • 181
4 votes
1 answer
484 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 ...
Jay S's user avatar
  • 43