2
$\begingroup$

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 number x which we couldn't discover by multiplying it with only 111...11. I assume I don't understand the problem correctly, but it is how I perceived it after watching Qiskit videos on Youtube.

$\endgroup$

1 Answer 1

4
$\begingroup$

If you input $1111\ldots 1$ to the oracle for the Bernstein-Vazirani problem, you get a 1 bit output which just evaluates $111\ldots 1\cdot s$ (where you're trying to learn $s$). In other words, you only learn whether the number of 1s in $s$ is even or odd. That is nowhere near enough to reconstruct the whole of $s$.

Indeed, this is the start of the argument for the classical lower bound: to learn $s$ I need to find out $n$ bits of information. Each use of the oracle can give me at most 1 bit. Thus, I must use the oracle at least $n$ times.

$\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.