# Grover's 3-qubits tutorial: Why we need the last X gates

I'm following the tutorial in Grover's Algorithm - Example 3 qubits

I'm trying to understand the amplitude amplification using the reflection. But I cannot understand if we really need the step 3d (apply X gates to the 3 qubits).

As described in the tutorial, the state before and after are the same (and I have checked using the 'statevector_simulator'

Why do we need this step?

This is my code (doubt in line DO WE REALLY NEED?!?)

def oracle(qc: QuantumCircuit, qr: QuantumRegister):
# Combined: Negate |101> and |110>
qc.cz(qr[0],qr[2]) # Negate |101> and |111>
qc.cz(qr[1], qr[2]) # Negate |110> and |111>

qc.barrier(qr[0]) # stetic only

# Perform the reflection around the average amplitude
def diffuser(qc: QuantumCircuit, qr: QuantumRegister):
# |𝜓3𝑎⟩=1/2(|000⟩+|011⟩+|100⟩−|111⟩)
qc.h(qr)

# |𝜓3𝑏⟩=1/2(−|000⟩+|011⟩+|100⟩+|111⟩)
qc.x(qr)

# |𝜓3𝑐⟩=1/2(−|000⟩+|011⟩+|100⟩−|111⟩)
# Do controlled-Z
qc.barrier(qr[0])
qc.barrier(qr[1])
qc.h(2)
qc.ccx(0,1,2)
qc.barrier(qr[0])
qc.barrier(qr[1])
qc.h(2)

# DO WE REALLY NEED?!?
# |𝜓3𝑑⟩=1/2(−|000⟩+|011⟩+|100⟩−|111⟩)
# qc.x(qr)

# |𝜓3𝑒⟩=1/√2(−|101⟩−|110⟩)
qc.h(qr)

# endregion oracles/checkers

# 3 Qubits circuit
n = 3
qr = QuantumRegister(n)
qc = QuantumCircuit(qr)

# for qubit in range(n):
#     grover_circuit.h(qubit)
# Initialize: All inputs in uniform superposition
# |𝜓1⟩=1/√8(|000⟩+|001⟩+|010⟩+|011⟩+|100⟩+|101⟩+|110⟩+|111⟩)
qc.h(qr)
# Apply oracle
# |𝜓2⟩=1/√8(|000⟩+|001⟩+|010⟩+|011⟩+|100⟩−|101⟩−|110⟩+|111⟩)
oracle(qc, qr)
# Apply augmentation
diffuser(qc, qr)

# Plot circuit
qc.draw('mpl')
plt.show()

# Get state vector (simulated one run)
backend_sv = Aer.get_backend('statevector_simulator')
job_sv = execute(qc, backend_sv)
statevec = job_sv.result().get_statevector()
print('Qiskit statevector')
for cn in statevec:
rcn = complex(round(cn.real, 8), round(cn.imag, 8))
print(f'{rcn:+.2g}')

# Get unitary (simulated one run)
backend_uni = Aer.get_backend('unitary_simulator')
job_uni = execute(qc, backend_uni)
unitary = job_uni.result().get_unitary()
print('Qiskit unitary')
print(unitary)

qc.measure_all()
backend_sim = Aer.get_backend('qasm_simulator')
shots = 1024
results = execute(qc, backend=backend_sim, shots=shots).result()
plt.show()


In this specific case it appears that you do not need the X-gates, however the diffuser is supposed to be general and removing the X-gates gives incorrect results for other oracles. Take an oracle that marks the state $$|101\rangle$$:

def oracle(qc: QuantumCircuit, qr: QuantumRegister):
# Negate |101>
qc.h(2)
qc.x(1)
qc.ccx(0,1,2)
qc.h(2)
qc.x(1)


Two Grover iterations should give you a 94.5% chance of measuring $$|101\rangle$$, but if you comment out the qc.x(qr) line you won't see this.

### Explanation:

To perform Grover's algorithm, we need the diffuser to do a reflection around $$|s\rangle$$. It is obvious how we can do a reflection around $$|111\dots1\rangle$$: a multiple controlled-Z gate ($$MCZ$$). To achieve a reflection around the state $$|s\rangle$$, we wrap this gate in the transformations $$|s\rangle \rightarrow |111\dots1\rangle$$ and $$|111\dots1\rangle \rightarrow |s\rangle$$, i.e

$$U_s = H^{\otimes n}X^{\otimes n}(MCZ) X^{\otimes n}H^{\otimes n}$$

If you remove the X-gates, you no longer have $$U_s$$, and instead something else that may work in specific cases but is not guaranteed to work generally.

• Thank you very much! Indeed I didn't understand that diffuser / reflection was generic (I thought it was oracle depending). And, Is this reflection circuit valid for any number of qubits? I have checked that the result is the same that the indicated in tutorial 2|𝑠⟩⟨𝑠|−𝟙, but in the same tutoria, for 2 qubits doesn't use this formula. Aug 24, 2020 at 17:12
• It's okay. Yes this circuit ($U_s = H^{\otimes n}X^{\otimes n}(MCZ) X^{\otimes n}H^{\otimes n}$) should work for any number of qubits (try proving it yourself!) Although it is not the only way to create $U_s$ as you have seen. Aug 24, 2020 at 21:36