الخوارزميات الكمية: بحث غروفر وتطبيقاته

ملاحظة

Atsushi Matsuo (10 مايو 2024)

تحميل ملف PDF للمحاضرة الأصلية. لاحظ أن بعض مقاطع الكود قد تكون قديمة لأنها صور ثابتة.

الوقت التقريبي للتشغيل على وحدة المعالجة الكمية (QPU) هو ثانيتان.

1. مقدمة إلى خوارزمية غروفر

هذا الدفتر هو الرابع في سلسلة محاضرات حول مسار الاستخدام الفعلي للحوسبة الكمية. سنتعلم في هذا الدفتر عن خوارزمية غروفر.

تُعدّ خوارزمية غروفر من أشهر الخوارزميات الكمية بسبب تسريعها التربيعي مقارنةً بأساليب البحث الكلاسيكية. في الحوسبة الكلاسيكية، يتطلب البحث في قاعدة بيانات غير مرتبة تحتوي على $N$ عنصر تعقيداً زمنياً من الرتبة $O(N)$، أي أنه في أسوأ الحالات قد يتعين فحص كل عنصر على حدة. غير أن خوارزمية غروفر تتيح تحقيق هذا البحث في زمن $O(\sqrt{N})$، مستعينةً بمبادئ ميكانيكا الكم لتحديد العنصر المستهدف بكفاءة أعلى.

تستخدم الخوارزمية تضخيم السعة (Amplitude Amplification)، وهي عملية ترفع احتمالية سعة الحالة الصحيحة في التراكب الكمي، مما يجعلها أكثر احتمالاً عند القياس. هذا التسريع يجعل خوارزمية غروفر ذات قيمة في تطبيقات عديدة تتخطى مجرد البحث في قواعد البيانات، لا سيما حين يكون حجم البيانات كبيراً. يمكن الاطلاع على شرح مفصّل للخوارزمية في دفتر خوارزمية غروفر.

البنية الأساسية لخوارزمية غروفر

تتكوّن خوارزمية غروفر من أربعة مكوّنات رئيسية:

1. التهيئة: إعداد التراكب الكمي على جميع الحالات الممكنة.
2. الأوراكل: تطبيق دالة أوراكل تُعلّم الحالة المستهدفة بقلب طورها.
3. عامل الانتشار: تطبيق سلسلة من العمليات لتضخيم احتمالية الحالة المُعلَّمة.

كل خطوة من هذه الخطوات تؤدي دوراً محورياً في جعل الخوارزمية تعمل بكفاءة. الشرح التفصيلي لكل خطوة يأتي لاحقاً.

2. تطبيق خوارزمية غروفر

2.1 الإعداد

استيراد المكتبات اللازمة وإعداد البيئة لتشغيل الدائرة الكمية.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-aer qiskit-ibm-runtime

%config InlineBackend.figure_format = 'svg' # Makes the images look nice

# importing Qiskit
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister

# import basic plot tools
from qiskit.visualization import plot_histogram

الخطوة 1: تعيين المسألة إلى دوائر وعوامل كمية

تأمّل قائمةً من 4 عناصر، وهدفنا إيجاد فهرس العنصر الذي يستوفي شرطاً محدداً. على سبيل المثال، نريد إيجاد فهرس العنصر المساوي للعدد 2. في هذا المثال، تمثّل الحالة الكمية $|01\rangle$ فهرس العنصر الذي يحقق هذا الشرط، إذ تشير إلى الموضع الذي توجد فيه القيمة 2.

الخطوة 2: التحسين لأجهزة العتاد المستهدفة

1: التهيئة

في خطوة التهيئة، نُنشئ تراكباً كمياً لجميع الحالات الممكنة. يتحقق ذلك بتطبيق بوابة هادامار على كل كيوبت في سجل من $n$ كيوبت، مما ينتج تراكباً متساوياً لـ $2^n$ حالة. رياضياً، يمكن التعبير عن ذلك كما يلي:

$$\frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle$$

حيث $N = 2^n$ هو العدد الإجمالي للحالات الممكنة. كذلك نغيّر حالة بت المساعدة (ancilla) إلى $|-\rangle$.

def initialization(circuit):
    # Initialization
    n = circuit.num_qubits
    # For input qubits
    for qubit in range(n - 1):
        circuit.h(qubit)
    # For the ancilla bit
    circuit.x(n - 1)
    circuit.h(n - 1)
    circuit.barrier()
    return circuit

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
initialization_circuit = QuantumCircuit(qr, anc)

initialization(initialization_circuit)
initialization_circuit.draw(output="mpl", idle_wires=False)

2: الأوراكل

الأوراكل هو الجزء الأساسي في خوارزمية غروفر. يُعلّم الحالة المستهدفة بتطبيق إزاحة طور، عادةً بقلب إشارة السعة المرتبطة بتلك الحالة. يكون الأوراكل في الغالب خاصاً بالمسألة المطروحة ويُبنى وفق معايير تحديد الحالة المستهدفة. رياضياً، يطبّق الأوراكل التحويل التالي:

f(x) = \begin\{cases\} 1, & \text\{if \} x = x_\{\text\{target}\} \\ 0, & \text\{otherwise\} \end\{cases\}

يتحقق قلب الطور هذا بتطبيق إشارة سالبة على سعة الحالة المستهدفة عبر آلية رفس الطور (Phase Kickback).

def oracle(circuit):
    circuit.x(1)
    circuit.ccx(0, 1, 2)
    circuit.x(1)
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
oracle_circuit = QuantumCircuit(qr, anc)

oracle(oracle_circuit)
oracle_circuit.draw(output="mpl", idle_wires=False)

3: عامل الانتشار

تضخيم السعة هو ما يُميّز خوارزمية غروفر عن البحث الكلاسيكي. بعد أن يُعلّم الأوراكل الحالة المستهدفة، نطبّق سلسلة من العمليات التي ترفع سعة هذه الحالة المُعلَّمة، مما يجعل احتمال قياسها أعلى. يتحقق ذلك عبر عامل الانتشار، الذي يُنفّذ فعلياً انعكاساً حول متوسط السعة. العملية الرياضية هي:

$D = 2|\psi\rangle\langle\psi| - I$

حيث $D$ هو عامل الانتشار، و$I$ هي مصفوفة الوحدة، و$|\psi\rangle$ هي حالة التراكب المتساوي. يُطبَّق تركيب الأوراكل وعامل الانتشار تقريباً $\sqrt{N}$ مرة لتحقيق أقصى احتمال لقياس الحالة المُعلَّمة.

def diffusion(circuit):
    input_qubits = circuit.num_qubits - 1
    circuit.h(range(0, input_qubits))
    circuit.x(range(0, input_qubits))
    circuit.h(input_qubits - 1)
    circuit.mcx([i for i in range(0, input_qubits - 1)], input_qubits - 1)
    circuit.h(input_qubits - 1)
    circuit.x(range(0, input_qubits))
    circuit.h(range(0, input_qubits))
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
diffusion_circuit = QuantumCircuit(qr, anc)

diffusion(diffusion_circuit)
diffusion_circuit.draw(output="mpl", idle_wires=False)

2.2 مثال على بحث غروفر بكيوبتين

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
meas = ClassicalRegister(3, "meas")
grover_circuit = QuantumCircuit(qr, anc, meas)

# the number of iterations
num_iterations = 1

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)
grover_circuit.measure_all(add_bits=False)

grover_circuit.draw(output="mpl", idle_wires=False)

2.3 التجربة على المحاكيات

الخطوة 3: تنفيذ الدائرة

from qiskit_aer import AerSimulator
from qiskit_ibm_runtime import Sampler
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(mode=backend)
job = sampler.run([isa_qc])
result = job.result()

الخطوة 4: معالجة النتائج

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

حصلنا على الإجابة الصحيحة $|01\rangle$. انتبه إلى ترتيب الكيوبتات.

3. التجربة على الأجهزة الحقيقية

الخطوة 2: التحسين لأجهزة العتاد المستهدفة

from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService()
real_backend = service.backend("ENTER-QPU-NAME-HERE")

# You can also identify the least busy device

real_backend = service.least_busy(simulator=False, operational=True)
print("The least busy device is ", real_backend)

# Transpile the circuit into basis gates executable on the hardware
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

pm = generate_preset_pass_manager(backend=real_backend, optimization_level=1)
target_circuit = pm.run(grover_circuit)

target_circuit.draw(output="mpl", idle_wires=False)

من خلال ترجمة الدائرة (Transpilation)، تحوّلت إلى دائرة تستخدم البوابات الأساسية الأصيلة للجهاز.

الخطوة 3: تنفيذ الدائرة

sampler = Sampler(real_backend)
job_real = sampler.run([target_circuit])
job_id = job_real.job_id()
print("job id:", job_id)

job id: cw69csv19rzg0080yfkg

# Check the job status
job_real.status()

'QUEUED'

# If the Notebook session got disconnected you can also check your job status by running the following code
job_real = service.job(job_id)  # Input your job-id between the quotations
job_real.status()

'DONE'

# Execute after job has successfully run
result_real = job_real.result()
print(result_real[0].data.meas.get_counts())

{'101': 540, '001': 2253, '011': 476, '000': 251, '110': 105, '100': 100, '010': 168, '111': 203}

الخطوة 4: معالجة النتائج

plot_histogram(result_real[0].data.meas.get_counts())

4. بحث غروفر بثلاثة كيوبتات

لنجرّب الآن مثالاً على بحث غروفر بثلاثة كيوبتات.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancilla")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 2

def oracle(circuit):
    circuit.mcx([0, 1, 2], 3)
    circuit.barrier()

هذه المرة، الحالة "الجيدة" هي $|111\rangle$.

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0111': 977, '0100': 11, '0001': 8, '0000': 8, '0011': 5, '0010': 12, '0110': 3}

تُلاحَظ الحالة $|0111\rangle$ بأعلى احتمالية كما هو متوقع. لاحظ أن تكرارَين هو العدد الأمثل في هذه الحالة. بيد أن احتمالية الحصول على الإجابة الصحيحة ليست 100%، وهذا أمر معتاد في بحث غروفر.

ماذا يحدث إذا كرّرنا العملية 3 مرات؟

لنجرّب الآن التكرار 3 مرات.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 3

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0010': 88, '0001': 103, '0000': 94, '0111': 334, '0100': 112, '0110': 106, '0101': 99, '0011': 88}

لا تزال الحالة $|0111\rangle$ تُلاحَظ بأعلى احتمالية، غير أن احتمالية الحصول على الإجابة الصحيحة انخفضت قليلاً.

وماذا عن 4 مرات؟

لنجرّب الآن التكرار 4 مرات.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 4

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc])
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0110': 127, '0000': 135, '0001': 150, '0101': 164, '0010': 153, '0011': 131, '0100': 150, '0111': 14}

تُلاحَظ الحالة $|0111\rangle$ بأدنى احتمالية، وقد انخفض احتمال الحصول على الإجابة الصحيحة بشكل أكبر. يُبيّن ذلك أهمية اختيار العدد الأمثل من التكرارات في خوارزمية غروفر للحصول على أفضل النتائج.

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'