Understanding Grover’s Oracle for 3-SAT

Question

First of all I'm very new to the quantum computing world so this might seem trivial to you, but it's a hump I was unable to get over for days now.

So I'm talking about the version that Qiskit has implemented for their 3-SAT example

Their example clauses look like this:

I recreated their code and printed the circuit to get an understanding of how the oracle works:

Obviously the first 3 Qubits represent the variables, the 5 Qubits labelled c seem to be simple booleans that indicate wether a clause is satisfied, the one labelled o is some sort of output and the remaining 3 are some sort of ancillaries.

What happens in the first 3 Qubits seems obvious as well (not 100% confident though), it just transforms the given clauses into binary values on the qubits.

After the modification of the qubits there is an OR-Circuit that checks wether any one of the qubits satisfies the given clause. If that is the case, it flips the Qubit representing the corresponding clause (c0 for the first clause). I think it also flips the a0 Qubit, but I am unsure as to what the purpose of this is.

This is repeated for every clause, until an AND-Circuit finally checks if all clauses are satisfied. I fail to understand what it does to the ancillary Qubits though.

After that the entire Circuit apart from the AND-Circuit is repeated to get back to the initial state.

I am confused as to how the output of this oracle actually looks. In other examples of Grover's Oracle it just flips the correct combinations but in this case that does not seem to make sense. Also I am confused as to where the measurement is actually taken, is it the ancilliary qubits?

I am sorry for presenting such a broad and vague question, but I don't know how to explain the issue I have any further.

For completeness sake I will also add the entire algorithm to hopefully clear up some confusion:

The Grover's algorithm in this case can be described as this circuit:

Where the Grover Operator Q is equal to:

Answer 1

If the output qubit ($state_8$ in the full circuit) is the one that indicates wether all clauses are satisfied, how is the circuit of importance if it is seemingly never involved in changing the values of the first 3 qubits which I assume are the ones measured at the end?

To clear this, I borrowed the code from this link (same as the one I included in my first comment) and played around with it. To get a small example, I set exactly_1_3_sat_formula = [[-1, -2, -3]]. This produces the following circuit:

I also includes some barriers to help me distinguish between the different parts of the circuit. The gates before the first barrier just sets the initial input state for Grover's algorithm. The gates after the first barrier are the black box function, and the ones after this take care of inversion about the average. Then, this two last sections are repeated and finally we measure the first register.

Now, how does the information from the ancilla register get into the first register. Note the $CX$ gates between $q946_0$ and $q945_0$ in the circuit above. Also note that $q945_0$ doesn't get reversed like the ancillary qubits (register $q946$).

How does this have any effect on the $q944$ register if they don't even interact directly? Well, notice that before the $CX(q946_0, q945_0)$, the qubits in the $q944$ and $q946$ registers become entangled because of the Hadamard gates at the beggining of the circuit and the $CX$ gates from the black box. Since the $CX(q946_0, q945_0)$ gate is applied while the two registers are entangled, qubit $q945_0$ has an effect on register $q944$. After the $CX$ gate, the $q944$ and $q946$ registers are un-entangled by reversing the operations, but the entanglement between $q945_0$ and the $q944$ has already been made and is not reversed since the gate that established it is not reversed.

This effect is adding a small negative amplitude to the configuration of the first three qubits that satisfies the clauses, which in this example is only one, with exactly 1 variable set to true (remember that this example uses Exact-1 3-SAT instead of normal 3-SAT). This happens because the $CX$ gate will only have an effect when $q946_0$ is in the $|1\rangle$ state. And $q946_0$ will only be in that state for states of $q944$ that satisfy the conditions for Exact-1 3-SAT.

Therefore, the $CX(q946_0, q945_0)$ gate adds a small negative amplitude to the states of $q944$ that satisfy the clauses. Then, this negative amplitude is inverted about the average and that's how we get our result.

For cases with more clauses, the procedure is the same but more Controlled-$X$ gates with more control qubits are involved. For example, again using the code from the link I provided but setting exactly_1_3_sat_formula = [[1, -2, 3], [-1, -2, -3], [-1, 2, 3]]. We get the following circuit:

As you can see, now we have a $CCX(q1033_3, q1033_2, q1032_0)$. But the main concept remains the same.

In your circuit, this Controlled-$X$ gate is inside the sixth black box from left to right; notice that it's the only one involving qubit $o_0$ and it's just between the entanglement and un-entanglement.