1
$\begingroup$

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:enter image description here

The diffuser (U_s) looks like this:enter image description here

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

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