2
$\begingroup$

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 the $X$ gate if control qubit is in state $|1\rangle$, which basically sounds like querying the black box.

If we have $N$ bits to guess, then we are applying $N$ number of $CX$ gates, which are queries to the black box.

How come is this considered only one guess, then? I thought of the possibility that follows the logic of gates being multiplied together to form one "generalized" guess, but I am not sure whether that's correct logic to follow.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The black box (oracle) in this problem has $N{+}1$ inputs and outputs. It is guaranteed to be computationally equivalent to a sequence of CX gates acting on the last bit and controlled by other bits, but it isn't guaranteed to be implemented that way. It doesn't matter how it's implemented, because you aren't allowed to look inside the box. You can't see the application of CX gates onto the $|{-}\rangle$ state, even if they exist in there.

The number of queries of the oracle is by definition the number of times you incorporate this monolithic $N{+}1$-qubit gate into your computation.

It works that way because Bernstein and Vazirani chose to make it work that way. Their goal was to prove that there exists a problem that can be solved more efficiently by a quantum computer than a classical computer. Your clear-box problem, while fine as a problem, wouldn't have worked to prove this result.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.