Implementing 3-Qubit Grover Algorithm in Qiskit

Question

The Qiskit tutorial on Grover's Algorithm shows an example of finding two marked solutions out of 8 items, produced by 3 qubits. Using the general diffuser code it provides, however, I realize that the algorithm fails to properly find the solution if the oracle is set to mark single item.
Specifically, the oracle in the example marks two items:
qc = QuantumCircuit(3)
qc.cz(0, 2)
qc.cz(1, 2)
oracle_ex3 = qc.to_gate()
oracle_ex3.name = "U$_omega$"

I've changed it to mark just one:
qc = QuantumCircuit(3)
qc.cz(0, 2)
oracle_ex3 = qc.to_gate()
oracle_ex3.name = "U$_omega$"

Now that there is only one solution and 8 possibilities, we should iterate the Grover oracle + diffuser twice, for which I did:
n = 3
grover_circuit = QuantumCircuit(n)
grover_circuit = initialize_s(grover_circuit, [0,1,2])
grover_circuit.append(oracle_ex3, [0,1,2])
grover_circuit.append(diffuser(n), [0,1,2])
grover_circuit.append(oracle_ex3, [0,1,2])
grover_circuit.append(diffuser(n), [0,1,2])
grover_circuit.measure_all()

And here is the measurement outcome plot:

As far as I expect the plot should show the state $|101⟩$ with nearly 100% probability. I tried iterating it 3 and 4 times, but the result is still messy. Is there something that I'm missing here?

Joseph Geipel · Accepted Answer

Number of states marked isn't a strict correspondence with number of CZ gates: your new oracle still marks two states, but, rather than $left|101right>$ and $left|110right>$, it marks $left|101right>$ and $left|111right>$. To see this, remember a $Z$ gate flips the sign of a $left|1right>$: if the $Z$ gate is applied to a 1 and the control is a 1, the sign is flipped, so, in your new circuit the first and last qubit have to be 1 but the other could be 0 or 1 and still be flipped, so either situation ends up marked. The original circuit doesn't have $left|111right>$ as an option since it makes both $Z$ gates flip the sign which cancels out, meaning that one but not both of the control qubits have to be 1. If you only apply the Grover Diffuser once in either the original circuit or your new one, it will be a superposition of the two marked states and will work correctly.
If you want to implement a marking of one state in an intuitively simple fashion, use a CCZ gate and flank each qubit that needs to be a 0 with $X$ gates. If you do this, it will get the answer with high probability after 2 Grover Diffusions as expected.

Implementing 3-Qubit Grover Algorithm in Qiskit

One Answer

Add your own answers!

Ask a Question