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

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

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

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

مسألة دويتش-يوزسا

سنبدأ بمسألة الاستعلام التي صُمِّمت خوارزمية دويتش-يوزسا في الأصل لحلها، والمعروفة بـمسألة دويتش-يوزسا.

الدالة المُدخَلة في هذه المسألة تأخذ الشكل $f:\Sigma^n \rightarrow \Sigma$ لعدد صحيح موجب $n$ اعتباطي. كما في مسألة دويتش، المهمة هي إخراج $0$ إذا كانت $f$ ثابتة و$1$ إذا كانت $f$ متوازنة، أي أن عدد السلاسل المُدخَلة التي تأخذ عندها الدالة القيمة $0$ يساوي عدد السلاسل التي تأخذ عندها القيمة $1$.

لاحظ أنه حين يكون $n$ أكبر من $1$، توجد دوال بالشكل $f:\Sigma^n \rightarrow \Sigma$ ليست ثابتة ولا متوازنة. مثلاً، الدالة $f:\Sigma^2\rightarrow\Sigma$ المعرَّفة كالتالي:

$$\begin{aligned} f(00) & = 0 \\ f(01) & = 0 \\ f(10) & = 0 \\ f(11) & = 1 \end{aligned}$$

لا تندرج تحت أيٍّ من الفئتين. في مسألة دويتش-يوزسا، ببساطة لا نهتم بمثل هذه الدوال — فهي تُعدّ مُدخلات "لا يهم أمرها". أي أن لدينا في هذه المسألة وعداً بأن $f$ إما ثابتة أو متوازنة.

مسألة دويتش-يوزسا

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

خوارزمية دويتش-يوزسا، باستعلامها الواحد، تحل هذه المسألة بالطريقة التالية: إذا كانت جميع نتائج القياس الـ$n$ تساوي $0$، فالدالة $f$ ثابتة؛ وإلا، إذا كانت إحدى نتائج القياس تساوي $1$، فالدالة $f$ متوازنة. طريقة أخرى للتعبير عن ذلك هي أن الدائرة الموصوفة أعلاه تتبعها خطوة معالجة كلاسيكية تحسب فيها العملية OR لنتائج القياس لإنتاج الخرج.

تحليل الخوارزمية

لتحليل أداء خوارزمية دويتش-يوزسا في مسألة دويتش-يوزسا، من المفيد أن نبدأ بالتفكير في تأثير طبقة واحدة من بوابات هادامار. يمكن التعبير عن عملية هادامار كمصفوفة بالطريقة المعتادة:

$$H = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix},$$

لكن يمكننا أيضاً التعبير عن هذه العملية من خلال تأثيرها على حالات الأساس القياسية:

$$\begin{aligned} H \vert 0\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle\\[3mm] H \vert 1\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle - \frac{1}{\sqrt{2}} \vert 1 \rangle. \end{aligned}$$

يمكن دمج هاتين المعادلتين في صيغة واحدة:

$$H \vert a \rangle = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} (-1)^a \vert 1 \rangle = \frac{1}{\sqrt{2}} \sum_{b\in\{0,1\}} (-1)^{ab} \vert b\rangle,$$

وهذا صحيح لكلتا قيمتَي $a\in\Sigma$.

لنفترض الآن أنه بدلاً من كيوبت واحد لدينا $n$ كيوبت، وتُجرى عملية هادامار على كل منها. العملية المشتركة على الكيوبتات الـ$n$ يصفها الجداء التنسوري $H\otimes \cdots \otimes H$ ($n$ مرة)، الذي نكتبه اختصاراً $H^{\otimes n}$. باستخدام الصيغة أعلاه ثم التوسيع والتبسيط، يمكننا التعبير عن تأثير هذه العملية المشتركة على حالات الأساس القياسية لـ$n$ كيوبت كالتالي:

$$\begin{aligned} & H^{\otimes n} \vert x_{n-1} \cdots x_1 x_0 \rangle \\ & \qquad = \bigl(H \vert x_{n-1} \rangle \bigr) \otimes \cdots \otimes \bigl(H \vert x_{0} \rangle \bigr) \\ & \qquad = \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{n-1}\in\Sigma} (-1)^{x_{n-1} y_{n-1}} \vert y_{n-1} \rangle \Biggr) \otimes \cdots \otimes \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{0}\in\Sigma} (-1)^{x_{0} y_{0}} \vert y_{0} \rangle \Biggr) \\ & \qquad = \frac{1}{\sqrt{2^n}} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle. \end{aligned}$$

هنا نكتب السلاسل الثنائية ذات الطول $n$ على شكل $x_{n-1}\cdots x_0$ و$y_{n-1}\cdots y_0$، وذلك باتباع اصطلاح ترقيم Qiskit.

تمنحنا هذه الصيغة أداة مفيدة لتحليل الدائرة الكمومية أعلاه. بعد تنفيذ الطبقة الأولى من بوابات هادامار، تكون حالة الكيوبتات الـ$n+1$ (بما فيها الكيوبت الأيسر/السفلي الذي يُعامَل بصورة منفصلة عن البقية):

$$\bigl( H \vert 1 \rangle \bigr) \bigl( H^{\otimes n} \vert 0 \cdots 0 \rangle \bigr) = \vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \vert x_{n-1} \cdots x_0 \rangle.$$

عند تنفيذ العملية $U_f$، تتحوّل هذه الحالة إلى:

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \vert x_{n-1} \cdots x_0 \rangle$$

وذلك من خلال ظاهرة الركل الطوري نفسها التي رأيناها في تحليل خوارزمية دويتش.

ثم تُنفَّذ الطبقة الثانية من بوابات هادامار، التي تحوّل هذه الحالة (بالصيغة أعلاه) إلى:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0) + x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle.$$

يبدو هذا التعبير معقداً نوعاً ما، ولا يمكن استنتاج الكثير عن احتمالات الحصول على نتائج قياس مختلفة دون معرفة المزيد عن الدالة $f$.

لحسن الحظ، كل ما نحتاج معرفته هو احتمال أن تكون جميع نتائج القياس $0$ — لأن ذلك هو احتمال أن تقرر الخوارزمية أن $f$ ثابتة. هذا الاحتمال له صيغة بسيطة:

$$\Biggl\vert \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \Biggr\vert^2 = \begin{cases} 1 & \text{إذا كانت $f$ ثابتة}\\[1mm] 0 & \text{إذا كانت $f$ متوازنة} \end{cases}$$

بمزيد من التفصيل: إذا كانت $f$ ثابتة، فإما أن $f(x_{n-1}\cdots x_0) = 0$ لكل سلسلة $x_{n-1}\cdots x_0$، وعندئذٍ تكون قيمة المجموع $2^n$، أو $f(x_{n-1}\cdots x_0) = 1$ لكل سلسلة $x_{n-1}\cdots x_0$، وعندئذٍ تكون قيمة المجموع $-2^n$. القسمة على $2^n$ وأخذ مربع القيمة المطلقة يعطيان $1$.

أما إذا كانت $f$ متوازنة، فإنها تأخذ القيمة $0$ على نصف السلاسل $x_{n-1}\cdots x_0$ والقيمة $1$ على النصف الآخر، فتتلاشى حدود $+1$ و$-1$ في المجموع وتبقى القيمة $0$.

نستنتج أن الخوارزمية تعمل بصورة صحيحة متى تحقق الوعد.

الصعوبة الكلاسيكية

خوارزمية دويتش-يوزسا تعمل في جميع الأحوال، وتعطينا دائماً الإجابة الصحيحة حين يُستوفى الوعد، وتحتاج استعلاماً واحداً فحسب. كيف يقارن ذلك بالخوارزميات الكلاسيكية لمسألة دويتش-يوزسا؟

أولاً، أي خوارزمية كلاسيكية حتمية تحل مسألة دويتش-يوزسا بصورة صحيحة يجب أن تجري عدداً أسياً من الاستعلامات: يُحتاج في أسوأ الحالات إلى $2^{n-1} + 1$ استعلاماً. السبب هو أنه إذا استعلمت خوارزمية حتمية $f$ عند $2^{n-1}$ سلسلة مختلفة أو أقل، وحصلت على نفس قيمة الدالة في كل مرة، فكلا الجوابين لا يزالان ممكنَين. قد تكون الدالة ثابتة، أو قد تكون متوازنة لكن بحظ سيء تعيد جميع الاستعلامات نفس قيمة الدالة.

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

غير أن هناك استثناءً، وهو أن الخوارزميات الكلاسيكية الاحتمالية يمكنها حل مسألة دويتش-يوزسا باحتمالية عالية جداً باستخدام استعلامات قليلة. بالتحديد، إذا اخترنا عشوائياً عدداً قليلاً من السلاسل ذات الطول $n$، واستعلمنا $f$ عند تلك السلاسل، فمن غير المرجح أن نحصل على نفس قيمة الدالة لجميعها حين تكون $f$ متوازنة.

بالتحديد، إذا اخترنا $k$ سلاسل مُدخَلة $x^1,\ldots,x^k \in \Sigma^n$ بصورة عشوائية موحدة، وحسبنا $f(x^1),\ldots,f(x^k)$، وأجبنا بـ$0$ إذا كانت القيم جميعها متساوية وبـ$1$ إذا لم تكن، فسنكون دائماً على صواب حين تكون $f$ ثابتة، وسنخطئ حين تكون $f$ متوازنة باحتمالية $2^{-k + 1}$ فحسب. إذا أخذنا $k = 11$ مثلاً، ستُجيب هذه الخوارزمية بصواب باحتمالية أكبر من $99.9$%.

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

دويتش-يوزسا مع Qiskit

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

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

لتطبيق خوارزمية دويتش-يوزسا في Qiskit، سنبدأ بتعريف دالة dj_query تُنشئ دائرة كمومية تُنفِّذ بوابة استعلام، لدالة مُختارة عشوائياً تستوفي الوعد لمسألة دويتش-يوزسا. باحتمال 50%، تكون الدالة ثابتة، وباحتمال 50% تكون متوازنة. في كلتا الحالتين، تُختار الدالة بصورة موحدة من بين دوال ذلك النوع. المُعامِل هو عدد بتات المُدخَل للدالة.

def dj_query(num_qubits):
    # Create a circuit implementing for a query gate for a random function
    # satisfying the promise for the Deutsch-Jozsa problem.

    qc = QuantumCircuit(num_qubits + 1)

    if np.random.randint(0, 2):
        # Flip output qubit with 50% chance
        qc.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance
        return qc

    # Choose half the possible input strings
    on_states = np.random.choice(
        range(2**num_qubits),  # numbers to sample from
        2**num_qubits // 2,  # number of samples
        replace=False,  # makes sure states are only sampled once
    )

    def add_cx(qc, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc.x(qubit)
        return qc

    for state in on_states:
        qc.barrier()  # Barriers are added to help visualize how the functions are created.
        qc = add_cx(qc, f"{state:0b}")
        qc.mcx(list(range(num_qubits)), num_qubits)
        qc = add_cx(qc, f"{state:0b}")

    qc.barrier()

    return qc

يمكننا عرض تطبيق الدائرة الكمومية لبوابة الاستعلام باستخدام دالة draw كالمعتاد.

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

بعد ذلك نُعرِّف دالة تُنشئ دائرة دويتش-يوزسا، آخذةً تطبيق الدائرة الكمومية لبوابة الاستعلام كمعامل.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in the Deutsch-Jozsa algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)
    qc.h(range(n + 1))
    qc.compose(function, inplace=True)
    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

أخيراً، نُعرِّف دالة تُشغِّل دائرة دويتش-يوزسا مرة واحدة.

def dj_algorithm(function: QuantumCircuit):
    # Determine if a function is constant or balanced.

    qc = compile_circuit(function)

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

يمكننا اختبار تطبيقنا باختيار دالة عشوائياً، وعرض تطبيق الدائرة الكمومية لبوابة الاستعلام لتلك الدالة، ثم تشغيل خوارزمية دويتش-يوزسا عليها.

f = dj_query(3)
display(f.draw("mpl"))
display(dj_algorithm(f))

'balanced'

مسألة برنشتاين-فازيراني

بعد ذلك، سنناقش مسألة تُعرف بـمسألة برنشتاين-فازيراني. وتُسمى أيضاً مسألة أخذ عينات فورييه، وإن كانت هناك صياغات أعم لهذه المسألة تحمل الاسم ذاته.

أولاً، لنُدخل بعض الرموز. لأي سلسلتَين ثنائيتَين $x = x_{n-1} \cdots x_0$ و$y = y_{n-1}\cdots y_0$ ذواتَي الطول $n$، نُعرِّف:

$$x \cdot y = x_{n-1} y_{n-1} \oplus \cdots \oplus x_0 y_0.$$

سنسمي هذه العملية الضرب الداخلي الثنائي. طريقة بديلة لتعريفه هي كالتالي:

$$x \cdot y = \begin{cases} 1 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ فردي}\\[0.5mm] 0 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ زوجي} \end{cases}$$

لاحظ أن هذه عملية متماثلة، أي أن النتيجة لا تتغير إذا استبدلنا $x$ بـ$y$، فيمكننا فعل ذلك متى أردنا. أحياناً يكون من المفيد التفكير في الضرب الداخلي الثنائي $x \cdot y$ باعتباره تعادل (parity) بتات $x$ في المواضع التي تحتوي $y$ على $1$، أو بالتكافؤ، تعادل بتات $y$ في المواضع التي تحتوي $x$ على $1$.

بهذه الرموز، يمكننا الآن تعريف مسألة برنشتاين-فازيراني.

مسألة برنشتاين-فازيراني

المُدخَل: دالة $f:\{0,1\}^n\rightarrow\{0,1\}$
الوعد: توجد سلسلة ثنائية $s = s_{n-1} \cdots s_0$ بحيث $f(x) = s\cdot x$ لكل $x\in\Sigma^n$
المُخرَج: السلسلة $s$

لا نحتاج في الواقع إلى خوارزمية كمومية جديدة لهذه المسألة؛ فخوارزمية دويتش-يوزسا تحلها. من أجل الوضوح، لنُشر إلى الدائرة الكمومية الواردة أعلاه، التي لا تتضمن خطوة المعالجة الكلاسيكية لحساب OR، باسم دائرة دويتش-يوزسا.

تحليل الخوارزمية

لتحليل كيفية عمل دائرة دويتش-يوزسا مع دالة تستوفي وعد مسألة برنشتاين-فازيراني، سنبدأ بملاحظة سريعة. باستخدام الضرب الداخلي الثنائي، يمكننا وصف تأثير $n$ بوابة هادامار على حالات الأساس القياسية لـ$n$ كيوبت بالصيغة التالية:

$$H^{\otimes n} \vert x \rangle = \frac{1}{\sqrt{2^n}} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert y\rangle$$

وذلك مماثل لما رأيناه في تحليل خوارزمية دويتش، لأن قيمة $(-1)^k$ لأي عدد صحيح $k$ تعتمد فقط على ما إذا كان $k$ فردياً أم زوجياً.

بالعودة إلى دائرة دويتش-يوزسا، بعد تنفيذ الطبقة الأولى من بوابات هادامار، تكون حالة الكيوبتات الـ$n+1$:

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} \vert x \rangle.$$

ثم تُنفَّذ بوابة الاستعلام، التي (من خلال ظاهرة الركل الطوري) تحوّل الحالة إلى:

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} (-1)^{f(x)} \vert x \rangle.$$

باستخدام صيغتنا لتأثير طبقة بوابات هادامار، نرى أن الطبقة الثانية من بوابات هادامار تحوّل هذه الحالة إلى:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{f(x) + x \cdot y} \vert y \rangle.$$

الآن يمكننا إجراء بعض التبسيطات في أس $-1$ داخل المجموع. وُعِدنا بأن $f(x) = s\cdot x$ لسلسلة ما $s = s_{n-1} \cdots s_0$، فيمكننا كتابة الحالة:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{s\cdot x + x \cdot y} \vert y \rangle.$$

بما أن $s\cdot x$ و$x\cdot y$ قيم ثنائية، يمكننا استبدال الجمع بالـXOR — مرة أخرى لأن الشيء الوحيد المهم لعدد صحيح في أس $-1$ هو ما إذا كان فردياً أم زوجياً. باستخدام تماثل الضرب الداخلي الثنائي، نحصل على التعبير التالي للحالة:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\cdot x) \oplus (y \cdot x)} \vert y \rangle.$$

(أُضيفت الأقواس للوضوح، وإن لم تكن ضرورية حقاً لأن العرف يجعل الضرب الداخلي الثنائي أعلى أولوية من الـXOR.)

عند هذه النقطة سنستخدم الصيغة التالية:

$$(s\cdot x) \oplus (y \cdot x) = (s \oplus y) \cdot x$$

يمكننا الحصول على هذه الصيغة من خلال صيغة مماثلة للبتات،

$$(a c) \oplus (b c) = (a \oplus b) c,$$

مع توسيع الضرب الداخلي الثنائي وXOR البتية:

$$\begin{aligned} (s\cdot x) \oplus (y \cdot x) & = (s_{n-1} x_{n-1}) \oplus \cdots \oplus (s_{0} x_{0}) \oplus (y_{n-1} x_{n-1}) \oplus \cdots \oplus (y_{0} x_{0}) \\ & = (s_{n-1} \oplus y_{n-1}) x_{n-1} \oplus \cdots \oplus (s_{0} \oplus y_{0}) x_{0} \\ & = (s \oplus y) \cdot x \end{aligned}$$

هذا يتيح لنا التعبير عن حالة الدائرة قبيل القياسات مباشرةً كالتالي:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle.$$

الخطوة الأخيرة هي استخدام صيغة أخرى، تصح لكل سلسلة ثنائية $z = z_{n-1}\cdots z_0$:

$$\frac{1}{2^n} \sum_{x \in \Sigma^n} (-1)^{z \cdot x} = \begin{cases} 1 & \text{إذا كان $z = 0^n$}\\ 0 & \text{إذا كان $z\neq 0^n$} \end{cases}$$

نستخدم هنا ترميزاً بسيطاً للسلاسل سنوظِّفه عدة مرات أخرى في الدرس: $0^n$ هي السلسلة الصفرية الكاملة ذات الطول $n$.

طريقة بسيطة للتحقق من صحة هذه الصيغة هي النظر في الحالتين بصورة منفصلة. إذا كان $z = 0^n$، فإن $z\cdot x = 0$ لكل سلسلة $x\in\Sigma^n$، وعندئذٍ قيمة كل حد في المجموع هي $1$، ونحصل على $1$ بعد الجمع والقسمة على $2^n$. أما إذا كان أي بت من بتات $z$ يساوي $1$، فإن الضرب الداخلي الثنائي $z\cdot x$ يساوي $0$ لنصف الاختيارات الممكنة لـ$x\in\Sigma^n$ بالضبط و$1$ للنصف الآخر — لأن قيمة الضرب الداخلي الثنائي $z\cdot x$ تنقلب (من $0$ إلى $1$ أو من $1$ إلى $0$) إذا قلبنا أي بت من بتات $x$ في موضع يحتوي $z$ على $1$.

إذا طبقنا هذه الصيغة لتبسيط حالة الدائرة قبل القياسات، نحصل على:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle = \vert - \rangle \otimes \vert s \rangle,$$

استناداً إلى أن $s\oplus y = 0^n$ إذا وفقط إذا كان $y = s$. وهكذا تكشف القياسات تماماً السلسلة $s$ التي نبحث عنها.

الصعوبة الكلاسيكية

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

يمكن إثبات ذلك من خلال حجة تُعرف بـنظرية المعلومات، وهي بسيطة جداً في هذه الحالة. كل استعلام كلاسيكي يكشف بتاً واحداً من المعلومات عن الحل، وهناك $n$ بت من المعلومات التي تحتاج إلى اكتشافها — لذا تلزم على الأقل $n$ استعلامات.

في الواقع، يمكن حل مسألة برنشتاين-فازيراني كلاسيكياً باستعلام الدالة على كل من السلاسل الـ$n$ التي تحتوي على $1$ واحد في كل موضع ممكن و$0$ في جميع البتات الأخرى، مما يكشف بتات $s$ واحدة تلو الأخرى. لذا فإن ميزة الخوارزميات الكمومية على الكلاسيكية في هذه المسألة هي استعلام واحد مقابل $n$ استعلاماً.

برنشتاين-فازيراني مع Qiskit

لقد طبّقنا بالفعل دائرة دويتش-يوزسا أعلاه، وسنستخدمها هنا لحل مسألة برنشتاين-فازيراني. أولاً سنُعرِّف دالة تُطبِّق بوابة استعلام لمسألة برنشتاين-فازيراني لأي سلسلة ثنائية $s$.

def bv_query(s):
    # Create a quantum circuit implementing a query gate for the
    # Bernstein-Vazirani problem.

    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_query("1011").draw(output="mpl"))

الآن يمكننا إنشاء دالة تشغّل دائرة دويتش-يوزسا على الدالة، باستخدام دالة compile_circuit المُعرَّفة سابقاً.

def bv_algorithm(function: QuantumCircuit):
    qc = compile_circuit(function)
    result = AerSimulator().run(qc, shots=1, memory=True).result()
    return result.get_memory()[0]

display(bv_algorithm(bv_query("1011")))

'1011'

ملاحظة حول التسمية

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

ما فعله برنشتاين وفازيراني بعد إثبات أن خوارزمية دويتش-يوزسا تحل مسألة برنشتاين-فازيراني (كما صِيغت أعلاه) هو تعريف مسألة أكثر تعقيداً بكثير، تُعرف بـمسألة أخذ عينات فورييه التكرارية. هذه مسألة مُصطنعة للغاية حيث تُطلق حلول حالات مختلفة من المسألة مستويات جديدة من المسألة مرتّبة في هيكل شجري. مسألة برنشتاين-فازيراني هي في جوهرها الحالة الأساسية لهذه المسألة الأكثر تعقيداً.

كانت مسألة أخذ عينات فورييه التكرارية أول مثال معروف على مسألة استعلام تتمتع فيها الخوارزميات الكمومية بميزة فوق-متعددة الحدود على الخوارزميات الاحتمالية، متجاوزةً بذلك ميزة الكم على الكلاسيكية التي تقدمها خوارزمية دويتش-يوزسا. بشكل حدسي، تُضخِّم النسخة التكرارية من المسألة ميزة $1$ مقابل $n$ للخوارزميات الكمومية إلى شيء أكبر بكثير.

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

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