-2
$\begingroup$

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)


# Add measure and simulate
qc.measure_all()
backend_sim = Aer.get_backend('qasm_simulator')
shots = 1024
results = execute(qc, backend=backend_sim, shots=shots).result()
answer = results.get_counts()
plot_histogram(answer)
plt.show()
$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Sourcerer
    Aug 24, 2020 at 17:12
  • $\begingroup$ 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. $\endgroup$
    – Frank
    Aug 24, 2020 at 21:36

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.