# 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 inverting the result? That would mean this encodes the secret 1111, correct?

Is this a valid instance? What function would you say the oracle is implementing, just an inversion?

• where did you get that from? if you read out the measurement result on the input qubits, you will see that they are all $|0\rangle$. This is because the two layers of Hadamard gate will cancel each other out... so this circuit really encodes the secret bitstring 0000. However, I am not sure why you have two $X$ gates at the bottom tho... Maybe you meant to put a Hadamard for the second $X$ gate? Apr 28, 2021 at 4:33
• Admittedly this is an example from a worksheet. It's an exercise where we are exploring whether a given circuit is or isn't a valid Bernstein-Vazirani circuit. So the X gate is intended, it just might not be "valid". Apr 28, 2021 at 6:38
• @KAJ226 Well, I don't know what secret it's intended to encode. I've just been given the circuit and have to say if it's a valid instance or not and why. Apr 30, 2021 at 1:43

A circuit (or oracle) is an instance of the Bernstein-Vazirani problem if it is equivalent to a circuit that only contains Controlled-Not operations and Not operations where all of the Controlled-Nots use one common specified qubit (the "output" qubit) as their target.

The goal of the problem is to figure out which qubits (other than the output qubit) are being used as the control of a Controlled-Not.

• I still don't really get it. It seems to me that X gate on b is going to make it as if this encoded the secret 1111. Is that correct? If so, then that secret could be trivially encoded with only CNOT gates and removing the X gate on b. May 2, 2021 at 0:52
• The goal is to figure out the cnots. The not gates are just distractions that make it a bit harder. The secret in your example is 0000 because there are no cnots. May 2, 2021 at 1:59
• But since the not gate flips the result, wouldn't the example actually be 1111? May 2, 2021 at 6:22
• @QuantumLearner No. The not gates are irrelevant. It's 0000. May 2, 2021 at 9:05
• @QuantumLearner Yes it's a valid instance. The not gate doesn't affect the solution but it does cause minor trouble for the classical solver. May 3, 2021 at 7:43

With this problem I found these two resources helpful:

Especially in this picture

one can see the concept of what is happening in your posted circuit.

The qubit b0 has the task to invert the other qubits, but it's just an auxiliary qubit, so it doesn't need to be measured.

To your question if this is a valid BV-problem.

My answer would be, that it is valid, but it's not minimized. the X(b0) in the middle section is as unnecessary as to measure b0 in the end. But as already answered by KAJ226 this is encoding 0000.

Hope this helps a little. I am quite new to this too, so I hope I didn't mess up anything.