2
$\begingroup$

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 that someone could help me.

If I have an 8 bit secret of all 0s, would the oracle just be nothing? Alternatively, if it was all 1s, would my oracle CNOT each input with the output qubit?

$\endgroup$
3
$\begingroup$

Yes, this is because the initial state will be starting as $|\psi_{init} \rangle = |000\cdots0\rangle = |0\rangle^{\otimes 8} $. Then you apply a layer of Hadamard gates, follow by the Oracle operation, then another layer of Hadamard gates, then finally the state of the 8 qubits of interest. Because the secret bitstring you have in mind are all $0$s, the Oracle would be nothing since this will allow the two layer of the Hadamard gates cancel each other out and keeping the state as $|\psi \rangle = |0\rangle^{\otimes 8}$. Now, upon measurement, you will extract out this very state... which is the secret bitstring you are interested in finding.

enter image description here

If your secret bitstring is all 1's then you would want your final state to be $|\psi\rangle = |1\rangle^{\otimes 8}$. To do this, we can use something called phase kickback. The idea is simple but clever. First notice the following:

enter image description here

This tells us, that if we want all $1$s then we will apply CNOT gates to each of the 8 qubits in your state to the ancilla qubit (which is in the state $\dfrac{|0\rangle - |1\rangle}{\sqrt{2}}$, which is created by apply $X$ gate follow by Hadamard gate) between the two layers of the Hadamard gates. Thus you will have something like this:

enter image description here

Measuring this will return you the state of all 1's.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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