# Solve sudoku using Grover's algorithm

The Qiskit tutorial shows the application of Grover's Algorithm to solve a 2x2 sudoku. However, I don't understand how why its diffuser works as intended. Precisely, why the control bit is on a "variable" qubit (labeled as "v") rather than on the auxiliary qubit (labeled as "out_0")?

var_qubits = QuantumRegister(4, name='v')
clause_qubits = QuantumRegister(4, name='c')
output_qubit = QuantumRegister(1, name='out')
cbits = ClassicalRegister(4, name='cbits')
qc = QuantumCircuit(var_qubits, clause_qubits, output_qubit, cbits)

def sudoku_oracle(qc, clause_list, clause_qubits):
# Compute clauses
i = 0
for clause in clause_list:
XOR(qc, clause[0], clause[1], clause_qubits[I])
i += 1

# Flip 'output' bit if all clauses are satisfied
qc.mct(clause_qubits, output_qubit)

# Uncompute clauses to reset clause-checking bits to 0
i = 0
for clause in clause_list:
XOR(qc, clause[0], clause[1], clause_qubits[I])
i += 1

sudoku_oracle(qc, clause_list, clause_qubits)
qc.draw()

Define difusser:
def diffuser(nqubits):
qc = QuantumCircuit(nqubits)
# Apply transformation |s> -> |00..0> (H-gates)
for qubit in range(nqubits):
qc.h(qubit)
# Apply transformation |00..0> -> |11..1> (X-gates)
for qubit in range(nqubits):
qc.x(qubit)
# Do multi-controlled-Z gate
qc.h(nqubits-1)
qc.mct(list(range(nqubits-1)), nqubits-1)  # multi-controlled-toffoli
qc.h(nqubits-1)
# Apply transformation |11..1> -> |00..0>
for qubit in range(nqubits):
qc.x(qubit)
# Apply transformation |00..0> -> |s>
for qubit in range(nqubits):
qc.h(qubit)
# We will return the diffuser as a gate
U_s = qc.to_gate()
U_s.name = "U$$_s$$"
return U_s

#Put everything together
# Initialize 'out0' in state |->
qc.initialize([1, -1]/np.sqrt(2), output_qubit)

# Initialize qubits in state |s>
qc.h(var_qubits)
qc.barrier()  # for visual separation

## First Iteration
# Apply our oracle
sudoku_oracle(qc, clause_list, clause_qubits)
qc.barrier()  # for visual separation
# Apply our diffuser
qc.append(diffuser(4), [0,1,2,3])

## Second Iteration
sudoku_oracle(qc, clause_list, clause_qubits)
qc.barrier()  # for visual separation
# Apply our diffuser
qc.append(diffuser(4), [0,1,2,3])

# Measure the variable qubits
qc.measure(var_qubits, cbits)

qc.draw(fold=-1)


The whole circuit looks like this:

The diffuser (U_s) looks like this:

Two important things to notice:

1. Notice that the multi-controlled Toffoli has its target qubit surrounded by H gates. This means we actually have a multi-controlled Z gate..

2. A multi-controlled Z gate has the unusual property that it doesn't distinguish between its target qubit and its control qubits. If you look at:

circ = QuantumCircuit(2)
circ.cz(0, 1)
circ.draw('latex')


you'd see the printed circuit doesn't even bother distinguishing between the control and the target.

The net effect of the control Z is that it maps $$|1111\rangle$$ to $$-|1111\rangle$$.

Since the entire control-Z is surrounded by a wall of X's on both sides, the total effect of both is that $$|0000\rangle$$ is mapped to $$-|0000\rangle$$

Update:

I confirmed that Qiskit also prints multi-control Z gates the same way it handles single-control Z gates: no qubit is distinguished as the target.

circ = QuantumCircuit(4)
circ.append(ZGate().control(3), [0, 1, 2, 3])
x = circ.draw('text')

q_0: ─■─
│
q_1: ─■─
│
q_2: ─■─
│
q_3: ─■─



Your confusion is from the fact that the text chose to implement the controlled-Z gate by way of a controlled-X gate. One of the qubits had to be picked, arbitrarily, to be the target.