אלגוריתמים קוונטיים: חיפוש גרובר ויישומים

הערה

Atsushi Matsuo (מאי 10, 2024)

הורד את ה-PDF של ההרצאה המקורית. שים לב שחלק מקטעי הקוד עשויים להיות מיושנים מכיוון שמדובר בתמונות סטטיות.

זמן QPU משוער להרצת הניסוי הוא 2 שניות.

1. מבוא לאלגוריתם גרובר

מחברת זו היא הרביעית בסדרת הרצאות על הדרך לשימוש קוונטי מעשי. במחברת זו נלמד על אלגוריתם גרובר.

אלגוריתם גרובר הוא אחד האלגוריתמים הקוונטיים המפורסמים ביותר בזכות ההאצה הריבועית שלו לעומת שיטות חיפוש קלאסיות. בעיבוד קלאסי, חיפוש במסד נתונים לא ממוין של $N$ פריטים דורש סיבוכיות זמן $O(N)$, כלומר במקרה הגרוע ביותר ייתכן שיהיה צורך לבחון כל פריט בנפרד. אולם, אלגוריתם גרובר מאפשר לבצע חיפוש זה בזמן $O(\sqrt{N})$, תוך מינוף עקרונות המכניקה הקוונטית לזיהוי הפריט המטרה ביעילות רבה יותר.

האלגוריתם משתמש בהגברת אמפליטודה — תהליך שמגדיל את אמפליטודת ההסתברות של מצב התשובה הנכונה בסופרפוזיציה קוונטית, מה שמאפשר למדוד אותו בהסתברות גבוהה יותר. האצה זו הופכת את אלגוריתם גרובר לבעל ערך ביישומים שונים מעבר לחיפוש פשוט במסד נתונים, בעיקר כשגודל מערך הנתונים גדול. הסברים מפורטים של האלגוריתם מסופקים במחברת אלגוריתם גרובר.

המבנה הבסיסי של אלגוריתם גרובר

אלגוריתם גרובר מורכב מארבעה מרכיבים עיקריים:

1. אתחול: הגדרת הסופרפוזיציה על פני כל המצבים האפשריים.
2. אורקל: הפעלת פונקציית אורקל שמסמנת את המצב המטרה על ידי היפוך הפאזה שלו.
3. אופרטור הדיפוזיה: הפעלת סדרת פעולות להגברת ההסתברות של המצב המסומן.

כל אחד מהשלבים הללו ממלא תפקיד קריטי בהפעלה יעילה של האלגוריתם. הסברים מפורטים לכל שלב מסופקים בהמשך.

2. מימוש אלגוריתם גרובר

2.1 הכנה

ייבוא הספריות הנדרשות והגדרת הסביבה להרצת ה-Circuit הקוונטי.

# 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: מיפוי הבעיה ל-Circuits ואופרטורים קוונטיים

נניח רשימה של 4 אלמנטים, כאשר המטרה שלנו היא לזהות את האינדקס של אלמנט העומד בתנאי מסוים. לדוגמה, אנו רוצים למצוא את האינדקס של האלמנט השווה ל-2. בדוגמה זו, המצב הקוונטי $|01\rangle$ מייצג את האינדקס של האלמנט המקיים תנאי זה, מכיוון שהוא מצביע על המיקום שבו נמצא הערך 2.

שלב 2: אופטימיזציה לחומרת המטרה

1: אתחול

בשלב האתחול, אנו יוצרים סופרפוזיציה של כל המצבים האפשריים. הדבר מושג על ידי הפעלת Gate של האדמר על כל Qubit ברגיסטר של n-Qubit, מה שיוצר סופרפוזיציה שווה של $2^n$ מצבים. מתמטית, ניתן לייצג זאת כ:

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

כאשר $N = 2^n$ הוא המספר הכולל של המצבים האפשריים. כמו כן, אנו משנים את מצב ביט העזר ל-$|-\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 דוגמת חיפוש גרובר עם 2 Qubits.

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: הרצת ה-Circuit.

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$. שים לב לסדר ה-Qubits

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)

על ידי transpiling ה-Circuit, הוא הומר ל-Circuit המשתמש ב-Gate בסיס הנייטיבי של המכשיר.

שלב 3: הרצת ה-Circuit.

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. חיפוש גרובר עם 3 Qubits

עכשיו, בוא ננסה דוגמה של חיפוש גרובר עם 3 Qubits.

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'