-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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.