خوارزمية دوتش

تحل خوارزمية دوتش مسألة التكافؤ في الحالة الخاصة $n = 1$. في سياق الحوسبة الكمومية تُعرف هذه المسألة أحيانًا بـمسألة دوتش، وسنتبع هذا التسمية في هذا الدرس.

بدقة أكبر، يُمثَّل المدخل بدالة $f:\Sigma \rightarrow \Sigma$ من بت إلى بت. توجد أربع دوال من هذا النوع:

$$\rule[-10mm]{0mm}{10mm} \begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}$$

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

مسألة دوتش

المدخل: دالة $f:\{0,1\}\rightarrow\{0,1\}$
المخرج: $0$ إذا كانت $f$ ثابتة، $1$ إذا كانت $f$ متوازنة

إذا نظرنا إلى الدالة المدخلة $f$ في مسألة دوتش باعتبارها تمثيلًا للوصول العشوائي إلى سلسلة نصية، فنحن نفكر في سلسلة من بتين: $f(0)f(1)$.

$$\begin{array}{cc} \mathsf{function} & \mathsf{string}\\ \hline f_1 & 00 \\ f_2 & 01 \\ f_3 & 10 \\ f_4 & 11 \end{array}$$

بهذه الطريقة، تصبح مسألة دوتش حساب التكافؤ (أو ما يعادله OR الحصري XOR) للبتين.

كل خوارزمية استعلام كلاسيكية تحل هذه المسألة بشكل صحيح يجب أن تستعلم عن كلا البتين: $f(0)$ و$f(1)$. إذا علمنا أن $f(1) = 1$ مثلًا، فقد تكون الإجابة لا تزال $0$ أو $1$ اعتمادًا على ما إذا كانت $f(0) = 1$ أو $f(0) = 0$ على التوالي. كل حالة أخرى مشابهة؛ معرفة بت واحد فقط من اثنين لا تُقدِّم أي معلومة عن تكافؤهما. لذلك، الدائرة المنطقية الموضحة في القسم السابق هي الأفضل من حيث عدد الاستعلامات اللازمة لحل هذه المسألة.

وصف الدائرة الكمومية

تحل خوارزمية دوتش مسألة دوتش باستخدام استعلام واحد فقط، مما يوفر ميزة قابلة للقياس للحوسبة الكمومية على الكلاسيكية. قد تبدو هذه الميزة متواضعة — استعلام واحد مقابل اثنين — لكن علينا أن نبدأ من مكان ما. التقدم العلمي يبدأ أحيانًا بأصول متواضعة الظاهر.

فيما يلي الدائرة الكمومية التي تصف خوارزمية دوتش:

التحليل

لتحليل خوارزمية دوتش، سنتتبع تأثير الدائرة أعلاه ونُحدِّد حالات الكيوبتات في اللحظات التي يقترحها هذا الشكل:

الحالة الابتدائية هي $\vert 1\rangle \vert 0 \rangle$، وتحوِّل عمليتا هادامار على الجانب الأيسر من الدائرة هذه الحالة إلى

$$\vert \pi_1 \rangle = \vert - \rangle \vert + \rangle = \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 0\rangle + \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 1\rangle.$$

(كالعادة، نتبع اتفاقية Qiskit لترتيب الكيوبتات التي تضع الكيوبت العلوي على اليمين والكيوبت السفلي على اليسار.) قد يبدو كتابة هذه الحالة المنتجة بهذه الصورة الموزَّعة جزئيًا غير حدسي، لكن هذا سيجعل التعبيرات اللاحقة أكثر إيجازًا.

بعد ذلك، تُنفَّذ بوابة $U_f$. وفقًا لتعريف بوابة $U_f$، تُطبَّق عملية XOR لقيمة الدالة $f$ للحالة الكلاسيكية للكيوبت العلوي/الأيمن على الكيوبت السفلي/الأيسر، مما يحوِّل $\vert \pi_1\rangle$ إلى الحالة

$$\vert \pi_2 \rangle = \frac{1}{2} \bigl( \vert 0 \oplus f(0) \rangle - \vert 1 \oplus f(0) \rangle \bigr) \vert 0 \rangle + \frac{1}{2} \bigl( \vert 0 \oplus f(1) \rangle - \vert 1 \oplus f(1) \rangle \bigr) \vert 1 \rangle.$$

يمكننا تبسيط هذا التعبير بملاحظة أن الصيغة

$$\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)$$

تنطبق على كلتا القيمتين الممكنتين $a\in\Sigma$. الحالتان بصورة أكثر صراحة هما:

$$\begin{aligned} \vert 0 \oplus 0\rangle - \vert 1 \oplus 0\rangle & = \vert 0 \rangle - \vert 1 \rangle = (-1)^0 \bigl( \vert 0\rangle - \vert 1\rangle \bigr)\\ \vert 0 \oplus 1\rangle - \vert 1 \oplus 1\rangle & = \vert 1 \rangle - \vert 0\rangle = (-1)^1 \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \end{aligned}$$

وهكذا يمكننا التعبير عن $\vert\pi_2\rangle$ بصيغة بديلة:

$$\begin{aligned} \vert\pi_2\rangle & = \frac{1}{2} (-1)^{f(0)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 0 \rangle + \frac{1}{2} (-1)^{f(1)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 1 \rangle \\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

حدث شيء مثير للاهتمام! رغم أن تأثير بوابة $U_f$ على حالات الأساس القياسية يُبقي الكيوبت العلوي/الأيمن دون تغيير ويطبق XOR لقيمة الدالة على الكيوبت السفلي/الأيسر، نرى هنا أن حالة الكيوبت العلوي/الأيمن قد تغيرت (بصفة عامة) بينما بقيت حالة الكيوبت السفلي/الأيسر على ما هي عليه — وتحديدًا في الحالة $\vert - \rangle$ قبل بوابة $U_f$ وبعدها. هذه الظاهرة تُعرف بـانعكاس الطور (phase kickback)، وسنتحدث عنها أكثر قريبًا.

مع تبسيط أخير يتمثل في سحب عامل $(-1)^{f(0)}$ خارج المجموع، نحصل على هذا التعبير للحالة $\vert\pi_2\rangle$:

$$\begin{aligned} \vert\pi_2\rangle & = (-1)^{f(0)} \vert - \rangle \biggl( \frac{\vert 0\rangle + (-1)^{f(0) \oplus f(1)} \vert 1\rangle}{\sqrt{2}}\biggr) \\ & = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert + \rangle & \text{إذا كان $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{إذا كان $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

لاحظ أن في هذا التعبير لدينا $f(0) \oplus f(1)$ في أس $-1$ بدلًا من $f(1) - f(0)$، وهو ما قد نتوقعه من منظور جبري صرف، لكننا نحصل على النتيجة ذاتها في الحالتين. وذلك لأن قيمة $(-1)^k$ لأي عدد صحيح $k$ تعتمد فقط على ما إذا كان $k$ زوجيًا أم فرديًا.

تطبيق بوابة هادامار الأخيرة على الكيوبت العلوي يُعطينا الحالة

$$\vert \pi_3 \rangle = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert 0 \rangle & \text{إذا كان $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert 1 \rangle & \text{إذا كان $f(0) \oplus f(1) = 1$}, \end{cases}$$

مما يؤدي إلى النتيجة الصحيحة باحتمالية $1$ عند قياس الكيوبت الأيمن/العلوي.

ملاحظات إضافية حول انعكاس الطور

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

أولًا، لاحظ أن الصيغة التالية تنطبق على كل اختيار للبتين $b,c\in\Sigma$:

$$\vert b \oplus c\rangle = X^c \vert b \rangle$$

يمكن التحقق من ذلك بفحص القيمتين الممكنتين $c = 0$ و$c = 1$:

$$\begin{aligned} \vert b \oplus 0 \rangle & = \vert b\rangle = \mathbb{I} \vert b \rangle = X^0 \vert b \rangle\\ \vert b \oplus 1 \rangle & = \vert \neg b\rangle = X \vert b \rangle = X^1 \vert b \rangle. \end{aligned}$$

باستخدام هذه الصيغة نرى أن

$$U_f \bigl(\vert b\rangle \vert a \rangle\bigr) = \vert b \oplus f(a) \rangle \vert a \rangle = \bigl(X^{f(a)}\vert b \rangle\bigr) \vert a \rangle$$

لكل اختيار للبتين $a,b\in\Sigma$. لأن هذه الصيغة صحيحة من أجل $b=0$ و$b=1$، نرى بالخطية أن

$$U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle$$

لجميع متجهات الحالة الكمومية $\vert \psi\rangle$، وبالتالي

$$U_f \bigl( \vert - \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)} \vert - \rangle \bigr) \vert a \rangle = (-1)^{f(a)} \vert - \rangle \vert a \rangle.$$

المفتاح الذي يُجعل هذا ممكنًا هو أن $X\vert - \rangle = - \vert - \rangle$. بالمصطلحات الرياضية، المتجه $\vert - \rangle$ هو متجه ذاتي للمصفوفة $X$ بـقيمة ذاتية $-1$.

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

مع الأخذ بعين الاعتبار أن الكميات القياسية تتحرك بحرية عبر الجداء التنسوري، نجد طريقة بديلة للاستدلال على كيفية تحويل العملية $U_f$ للحالة $\vert \pi_1\rangle$ إلى $\vert \pi_2\rangle$ في التحليل أعلاه:

$$\begin{aligned} \vert \pi_2 \rangle & = U_f \bigl( \vert - \rangle \vert + \rangle \bigr)\\ & = \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 0\rangle \bigr) + \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 1\rangle \bigr)\\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

التطبيق في Qiskit

لنرَ الآن كيف يمكننا تطبيق خوارزمية دوتش في Qiskit. سنبدأ بفحص الإصدار ثم نُجري الاستيرادات اللازمة لهذا التطبيق تحديدًا. في تطبيقات الخوارزميات الأخرى التي ستلي، سنُجري الاستيرادات اللازمة بصورة منفصلة لمزيد من الوحدودية.

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

from qiskit import __version__

print(__version__)

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

أولًا، سنعرِّف دائرة كمومية تُطبِّق بوابة استعلام لإحدى الدوال الأربع $f_1,$ $f_2,$ $f_3,$ أو $f_4$ من بت إلى بت كما وردت سابقًا. كما أشرنا، تطبيق بوابات الاستعلام ليس جزءًا أصيلًا من خوارزمية دوتش في حد ذاتها؛ هنا نُظهر في الأساس إحدى طرق إعداد المدخل على هيئة دائرة كمومية لبوابة الاستعلام.

def deutsch_function(case: int):
    # This function generates a quantum circuit for one of the 4 functions
    # from one bit to one bit

    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")

    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f

يمكننا رؤية شكل كل دائرة باستخدام طريقة draw. هذه هي الدائرة للدالة $f_3$.

display(deutsch_function(3).draw(output="mpl"))

بعد ذلك سننشئ الدائرة الكمومية الفعلية لخوارزمية دوتش، مُستبدِلين بوابة الاستعلام بتطبيق دائرة كمومية يُعطى كحجة. بعد قليل سنضع إحدى الدوائر الأربع المعرَّفة بالدالة deutsch_function التي عرَّفناها سابقًا. تُضمَّن الحواجز لإظهار الفصل المرئي بين تطبيق بوابة الاستعلام وبقية الدائرة.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in Deutsch's algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)

    qc.x(n)
    qc.h(range(n + 1))

    qc.barrier()
    qc.compose(function, inplace=True)
    qc.barrier()

    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc

مجددًا يمكننا رؤية شكل الدائرة باستخدام طريقة draw.

display(compile_circuit(deutsch_function(3)).draw(output="mpl"))

أخيرًا، سننشئ دالة تُشغِّل الدائرة المعرَّفة مسبقًا مرة واحدة وتُخرج النتيجة المناسبة: "constant" (ثابتة) أو "balanced" (متوازنة).

def deutsch_algorithm(function: QuantumCircuit):
    # Determine if a one-bit function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if measurements[0] == "0":
        return "constant"
    return "balanced"

يمكننا الآن تشغيل خوارزمية دوتش على أي من الدوال الأربع المعرَّفة أعلاه.

f = deutsch_function(3)
display(deutsch_algorithm(f))

'balanced'