TransWikia.com

Implementing 3-Qubit Grover Algorithm in Qiskit

Quantum Computing Asked on June 2, 2021

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?

One 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.

Correct answer by Joseph Geipel on June 2, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP