الخوارزميات الكمية: تقدير الطور

ملاحظة

Kento Ueda (15 May 2024)

يقدّم هذا الدفتر المفاهيم الأساسية وطريقة تنفيذ تحويل فورييه الكمي (QFT) وتقدير الطور الكمي (QPE).

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

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

1. المقدمة

تحويل فورييه الكمي (QFT)

تحويل فورييه الكمي هو النظير الكمي لتحويل فورييه المنفصل الكلاسيكي. إنه تحويل خطي يُطبَّق على الحالات الكمية، يُعيد رسم أسس الحوسبة إلى تمثيلاتها في أساس فورييه. يؤدي QFT دورًا محوريًا في كثير من الخوارزميات الكمية، إذ يوفّر طريقة فعّالة لاستخلاص معلومات الدورية من الحالات الكمية. يمكن تنفيذ QFT بعدد $O(N^2)$ من العمليات باستخدام بوابات كمية كبوابات هادامار وبوابات التحكم بالطور لـ $N$ كيوبت، مما يتيح تسريعًا أسيًا مقارنةً بتحويل فورييه الكلاسيكي.

• التطبيقات: إنه ركيزة أساسية في خوارزميات كمية مثل خوارزمية شور لتحليل الأعداد الكبيرة إلى عواملها واللوغاريتم المنفصل.

تقدير الطور الكمي (QPE)

تقدير الطور الكمي هو خوارزمية كمية تُستخدم لتقدير الطور المرتبط بمتجه ذاتي لمؤثر أحادي. تمثّل هذه الخوارزمية جسرًا بين الخصائص الرياضية المجردة للحالات الكمية وتطبيقاتها الحسابية.

• التطبيقات: يمكنها حل مسائل مثل إيجاد القيم الذاتية للمصفوفات الأحادية ومحاكاة الأنظمة الكمية.

يُشكّل كلٌّ من QFT وQPE معًا العمود الفقري لكثير من الخوارزميات الكمية التي تحل مسائل يعجز عنها الحاسوب الكلاسيكي. بنهاية هذا الدفتر، ستمتلك فهمًا واضحًا لكيفية تنفيذ هذه التقنيات.

2. أساسيات تحويل فورييه الكمي (QFT)

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

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
from qiskit.visualization import plot_histogram, plot_bloch_multivector
from qiskit.quantum_info import Statevector
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit_ibm_runtime import Sampler

from numpy import pi

بالقياس على تحويل فورييه المنفصل، يعمل QFT على الحالة الكمية $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$ لـ $N$ كيوبت ويُعيد رسمها إلى الحالة الكمية $\vert Y\rangle = \sum_{k=0}^{N-1} y_k \vert k \rangle$.

$$QFT_{N}: \vert j \rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk} \vert k \rangle$$

حيث $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$.

أو بصيغة التمثيل بالمصفوفة الأحادية:

$$U_{QFT} = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \sum_{k=0}^{N-1} \omega_N^{jk} \vert k \rangle \langle j \vert$$

2.1. الحدس

يُحوّل تحويل فورييه الكمي (QFT) بين أساسَين: أساس الحوسبة (محور Z)، وأساس فورييه. لكن ماذا يعني أساس فورييه في هذا السياق؟ على الأرجح تتذكر أن تحويل فورييه $F(\omega)$ لدالة $f(x)$ يصف تحليل $f(x)$ على دالة جيبية بتردد $\omega$. بعبارة بسيطة: تحويل فورييه هو دالة تصف مقدار كل تردد $\omega$ الذي نحتاجه لبناء دالة $f(x)$ من دوال الجيب (أو دوال الجيب تمام). للحصول على فهم أعمق لما يعنيه QFT في هذا السياق، تأمّل الصور المتدرجة أدناه التي تُظهر رقمًا مُرمَّزًا بالنظام الثنائي باستخدام أربعة كيوبتات:

في أساس الحوسبة، نخزّن الأرقام بالنظام الثنائي باستخدام الحالتين $|0\rangle$ و$|1\rangle$.

لاحظ التردد الذي تتغيّر به الكيوبتات المختلفة؛ الكيوبت الأيسر يتقلّب مع كل زيادة في الرقم، والتالي مع كل زيادتين، والثالث مع كل أربع زيادات، وهكذا.

إذا طبّقنا تحويل فورييه الكمي على هذه الحالات، نُعيد الرسم:

$$|\text{State in Computational Basis}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{State in Fourier Basis}\rangle$$ $$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$

(نُشير عادةً إلى الحالات في أساس فورييه بعلامة التلدة (~)).

في أساس فورييه، نخزّن الأرقام باستخدام دورانات مختلفة حول محور Z:

IFRAME

الرقم الذي نريد تخزينه يُحدّد الزاوية التي يدور عندها كل كيوبت حول محور Z. في الحالة $|\widetilde{0}\rangle$، تكون جميع الكيوبتات في الحالة $|{+}\rangle$. كما يتضح من المثال أعلاه، لترميز الحالة $|\widetilde{5}\rangle$ على 4 كيوبتات، دوّرنا الكيوبت الأيسر بمقدار $\tfrac{5}{2^n} = \tfrac{5}{16}$ دورة كاملة ($\tfrac{5}{16}\times 2\pi$ راديان). الكيوبت التالي يُدار بضعف هذا المقدار ($\tfrac{10}{16}\times 2\pi$ راديان، أو $10/16$ دورة كاملة)، ثم تتضاعف هذه الزاوية للكيوبت الذي يليه، وهكذا.

مجددًا، لاحظ التردد الذي يتغيّر به كل كيوبت. الكيوبت الأيسر (qubit 0) في هذه الحالة يمتلك أدنى تردد، بينما الكيوبت الأيمن يمتلك أعلاه.

2.2 مثال: QFT لكيوبت واحد

لنتأمل حالة $N = 2^1 = 2$.

يمكن كتابة المصفوفة الأحادية على النحو:

$$\begin{aligned} U_{QFT} & = \frac{1}{\sqrt{2}} \sum_{j=0}^{1} \sum_{k=0}^{1} \omega_2^{jk} \vert k \rangle \langle j \vert \\ & = \frac{1}{\sqrt{2}} (\omega_2^{0} \vert 0 \rangle \langle 0 \vert + \omega_2^{0} \vert 0 \rangle \langle 1 \vert + \omega_2^{0} \vert 1 \rangle \langle 0 \vert + \omega_2^{1} \vert 1 \rangle \langle 1 \vert) \\ & = \frac{1}{\sqrt{2}} (\vert 0 \rangle \langle 0 \vert + \vert 0 \rangle \langle 1 \vert + \vert 1 \rangle \langle 0 \vert - \vert 1 \rangle \langle 1 \vert) \\ & = H \end{aligned}$$

هذه العملية هي نتيجة تطبيق بوابة هادامار ($H$).

2.3 التمثيل الضربي لـ QFT

لنُعمّم التحويل لـ $N = 2^n$، حيث يعمل $QFT_{N}$ على الحالة $\vert x \rangle = \vert x_1\ldots x_n \rangle$.

$$\begin{aligned} QFT_N\vert x \rangle & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1}\omega_N^{xy} \vert y \rangle \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i xy / 2^n} \vert y \rangle ~\text{since}\: \omega_N^{xy} = e^{2\pi i \frac{xy}{N}} \:\text{and}\: N = 2^n \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i \left(\sum_{k=1}^n y_k/2^k\right) x} \vert y_1 \ldots y_n \rangle \:\text{rewriting in fractional binary notation}\: y = y_1\ldots y_n, y/2^n = \sum_{k=1}^n y_k/2^k \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \prod_{k=1}^n e^{2 \pi i x y_k/2^k } \vert y_1 \ldots y_n \rangle \:\text{after expanding the exponential of a sum to a product of exponentials,} \\ & = \frac{1}{\sqrt{N}} \bigotimes_{k=1}^n \left(\vert0\rangle + e^{2 \pi i x /2^k } \vert1\rangle \right) \:\text{after rearranging the sum and products, and expanding} \sum_{y=0}^{N-1} = \sum_{y_1=0}^{1}\sum_{y_2=0}^{1}\ldots\sum_{y_n=0}^{1} \\ & = \frac{1}{\sqrt{N}} \left(\vert0\rangle + e^{\frac{2\pi i}{2}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^2}x} \vert1\rangle\right) \otimes \ldots \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^{n-1}}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^n}x} \vert1\rangle\right) \end{aligned}$$

2.4 مثال: بناء دائرة تحويل فورييه الكمي لـ 3 كيوبتات

من الوصف أعلاه، قد لا يكون من الواضح كيفية بناء دائرة QFT. في الوقت الحالي، لاحظ فقط أننا نتوقع أن تمر الطورات في الثلاثة كيوبتات بمعدلات تطور مختلفة. فهم كيفية ترجمة ذلك إلى دائرة متروك كتمرين للقارئ. تتوفر مخططات وأمثلة متعددة في ملف PDF للمحاضرة. تشمل الموارد الإضافية هذا الدرس من دورة أساسيات الخوارزميات الكمية.

سنوضّح تحويل QFT باستخدام المحاكيات فقط، وبالتالي لن نستخدم إطار أنماط Qiskit حتى ننتقل إلى تقدير الطور الكمي.

# Prepare for 3 qubits circuit
qr = QuantumRegister(3)
cr = ClassicalRegister(3)
qc = QuantumCircuit(qr, cr)

qc.h(2)
qc.cp(pi / 2, 1, 2)  # Controlled-phase gate from qubit 1 to qubit 2
qc.cp(pi / 4, 0, 2)  # Controlled-phase gate from qubit 0 to qubit 2
qc.draw(output="mpl")

qc.h(1)
qc.cp(pi / 2, 0, 1)  # Controlled-phase gate from qubit 0 to qubit 1

qc.draw(output="mpl")

qc.h(0)

qc.draw(output="mpl")

qc.swap(0, 2)

qc.draw(output="mpl")

نحاول تطبيق QFT على $|5\rangle$ كمثال.

أولاً، نتحقق من التمثيل الثنائي للعدد الصحيح 5 وننشئ الدائرة التي تشفّر الحالة 5:

bin(5)

'0b101'

qc = QuantumCircuit(3)

qc.x(0)
qc.x(2)
qc.draw(output="mpl")

نتحقق من الحالات الكمية باستخدام محاكي Aer:

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

أخيراً، نضيف QFT ونعرض الحالة النهائية لكيوباتنا:

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

يمكننا أن نرى أن دالة QFT عملت بشكل صحيح. لقد دُوِّر الكيوبت 0 بمقدار $\tfrac{5}{8}$ من دورة كاملة، والكيوبت 1 بمقدار $\tfrac{10}{8}$ دورات كاملة (ما يعادل $\tfrac{1}{4}$ من دورة كاملة)، والكيوبت 2 بمقدار $\tfrac{20}{8}$ دورات كاملة (ما يعادل $\tfrac{1}{2}$ من دورة كاملة).

2.5 تمرين: تحويل فورييه الكمي

(1) نفّذ تحويل QFT لـ 4 كيوبتات.

##your code goes here##

(2) طبّق QFT على $|14\rangle$، وشغّل المحاكاة، ثم ارسم متجه الحالة باستخدام كرة بلوخ.

##your code goes here##

حل التمرين: QFT

(1)

qr = QuantumRegister(4)
cr = ClassicalRegister(4)
qc = QuantumCircuit(qr, cr)

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

(2)

bin(14)

'0b1110'

qc = QuantumCircuit(4)

qc.x(1)
qc.x(2)
qc.x(3)
qc.draw("mpl")

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)
qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

3. أساسيات تقدير الطور الكمي (QPE)

بالنظر إلى عملية أحادية $U$، يُقدّر القياس الطوري الكمي QPE قيمة $\theta$ في المعادلة $U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$، وبما أن $U$ عملية أحادية فإن جميع قيمها الذاتية تمتلك قيمة مطلقة تساوي 1.

3.1 الإجراء

1. الإعداد

يقع $\vert\psi\rangle$ في مجموعة من سجلات الكيوبتات. أما مجموعة إضافية مكوّنة من $n$ كيوبت فتُشكّل سجل العدّ الذي سنخزّن فيه القيمة $2^n\theta$:

$$|\psi_0\rangle = \lvert 0 \rangle^{\otimes n} \lvert \psi \rangle$$

2. التراكب

نطبّق عملية بوابة هادامارد ذات $n$ بت $H^{\otimes n}$ على سجل العدّ:

$$|\psi_1\rangle = {\frac {1}{2^{\frac {n}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes n} \lvert \psi \rangle$$

3. العمليات الأحادية المتحكَّم بها

نحتاج إلى تقديم العملية الأحادية المتحكَّم بها $CU$ التي تُطبّق المؤثر الأحادي $U$ على السجل الهدف فقط إذا كان بت التحكم المقابل له هو $|1\rangle$. ولأن $U$ مؤثر أحادي يمتلك متجه ذاتي $|\psi\rangle$ بحيث $U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$، فهذا يعني:

$$U^{2^{j}}|\psi \rangle =U^{2^{j}-1}U|\psi \rangle =U^{2^{j}-1}e^{2\pi i\theta }|\psi \rangle =\cdots =e^{2\pi i2^{j}\theta }|\psi \rangle$$

3.2 مثال: QPE لبوابة T

لنستخدم بوابة $T$ كمثال على QPE ونُقدّر طورها $\theta$.

$$T|1\rangle = \begin{pmatrix} 1 & 0\\ 0 & e^\frac{i\pi}{4}\\ \end{pmatrix} \begin{pmatrix} 0\\ 1\\ \end{pmatrix} = e^\frac{i\pi}{4}|1\rangle$$

نتوقع أن نجد:

$$\theta = \frac{1}{8}$$

حيث

$$T|1\rangle = e^{2i\pi\theta}|1\rangle$$

qpe = QuantumCircuit(4, 3)
qpe.x(3)
qpe.draw(output="mpl")

بعد ذلك، نطبّق بوابات هادامار على كيوبتات العدّ:

for qubit in range(3):
    qpe.h(qubit)
qpe.draw(output="mpl")

ننفّذ عمليات الوحدة الأحادية المتحكَّم بها:

repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.draw(output="mpl")

نطبّق تحويل فورييه الكمي العكسي لتحويل حالة سجل العدّ، ثم نقيس سجل العدّ:

from qiskit.circuit.library import QFT

# Apply inverse QFT
qpe.append(QFT(3, inverse=True), [0, 1, 2])
qpe.draw(output="mpl")

for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

يمكننا المحاكاة باستخدام محاكي Aer:

aer_sim = AerSimulator()
shots = 2048

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

نلاحظ أننا نحصل على نتيجة واحدة (001) بيقين تام، وهي تقابل العدد العشري: 1. نحتاج الآن إلى قسمة نتيجتنا (1) على $2^n$ للحصول على $\theta$:

$$\theta = \frac{1}{2^3} = \frac{1}{8}$$

تتيح لنا خوارزمية شور تحليل عدد إلى عوامله عبر بناء دائرة كمومية تكون فيها $\theta$ مجهولة، ثم الحصول على قيمة $\theta$.

3.3 تمرين

قدِّر $\theta = 1/3$ باستخدام 3 كيوبتات للعدّ وكيوبت واحد لمتجه القيم الذاتية.

$P|1\rangle = e^{i\lambda}|1\rangle$. بما أننا نريد تطبيق $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$، علينا ضبط $\lambda = \tfrac{2 \pi}{3}$.

##your code goes here##

حل التمرين: $\theta = 1/3$

# Create and set up circuit
qpe = QuantumCircuit(4, 3)

# Apply H-Gates to counting qubits:
for qubit in range(3):
    qpe.h(qubit)

# Prepare our eigenstate |psi>:
qpe.x(3)

# Do the controlled-U operations:
angle = 2 * pi / 3
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(angle, counting_qubit, 3)
    repetitions *= 2

# Do the inverse QFT:
qpe.append(QFT(3, inverse=True), [0, 1, 2])

for n in range(3):
    qpe.measure(n, n)

qpe.draw(output="mpl")

aer_sim = AerSimulator()
shots = 4096

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

4. التنفيذ باستخدام أداة Sampler البدائية في Qiskit Runtime

سنُجري تقدير الطور الكمومي (QPE) باستخدام جهاز كمومي حقيقي، وسنتبع الخطوات الأربع لأنماط Qiskit.

1. تعيين المسألة إلى تنسيق كمومي أصلي
2. تحسين الدوائر
3. تنفيذ الدائرة المستهدفة
4. معالجة النتائج

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler

# Loading your IBM Quantum® account(s)

service = QiskitRuntimeService()

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

qpe = QuantumCircuit(4, 3)
qpe.x(3)
for qubit in range(3):
    qpe.h(qubit)
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.append(QFT(3, inverse=True), [0, 1, 2])
for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

backend = service.least_busy(simulator=False, operational=True, min_num_qubits=4)

print(backend)

<IBMBackend('ibm_strasbourg')>

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

# Transpile the circuit into basis gates executable on the hardware
pm = generate_preset_pass_manager(backend=backend, optimization_level=2)
qc_compiled = pm.run(qpe)

qc_compiled.draw("mpl", idle_wires=False)

4.3 الخطوة 3: التنفيذ على العتاد المستهدف

real_sampler = Sampler(mode=backend)
job = real_sampler.run([qc_compiled], shots=1024)
job_id = job.job_id()
print("job id:", job_id)

job id: d13p4zb5z6q00087ag00

job = service.job(job_id)  # Input your job-id between the quotations
job.status()

'DONE'

result_real = job.result()
print(result_real)

PrimitiveResult([SamplerPubResult(data=DataBin(c=BitArray(<shape=(), num_shots=1024, num_bits=3>)), metadata={'circuit_metadata': {}})], metadata={'execution': {'execution_spans': ExecutionSpans([DoubleSliceSpan(<start='2025-06-09 22:39:00', stop='2025-06-09 22:39:00', size=1024>)])}, 'version': 2})

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

from qiskit.visualization import plot_histogram

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

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'