Algoritma Deutsch-Jozsa

Algoritma Deutsch mengatasi semua algoritma klasik untuk masalah pertanyaan, tetapi kelebihan itu agak sederhana: satu pertanyaan berbanding dua. Algoritma Deutsch-Jozsa memperluaskan kelebihan ini — malah, ia boleh digunakan untuk menyelesaikan beberapa masalah pertanyaan yang berbeza.

Berikut ialah penerangan Circuit kuantum bagi algoritma Deutsch-Jozsa. Langkah pemprosesan pasca klasik tambahan, yang tidak ditunjukkan dalam rajah, mungkin juga diperlukan bergantung pada masalah tertentu yang diselesaikan.

Sudah tentu, kita belum membincangkan masalah apa yang diselesaikan oleh algoritma ini; perkara ini dibincangkan dalam dua bahagian berikutnya.

Masalah Deutsch-Jozsa

Kita akan mulakan dengan masalah pertanyaan yang algoritma Deutsch-Jozsa pada asalnya direka untuk diselesaikan, yang dikenali sebagai masalah Deutsch-Jozsa.

Fungsi input untuk masalah ini mengambil bentuk $f:\Sigma^n \rightarrow \Sigma$ untuk integer positif $n$ yang sewenang-wenangnya. Seperti masalah Deutsch, tugasnya ialah mengeluarkan $0$ jika $f$ adalah malar dan $1$ jika $f$ adalah seimbang, yang sekali lagi bermakna bilangan rentetan input di mana fungsi mengambil nilai $0$ adalah sama dengan bilangan rentetan input di mana fungsi mengambil nilai $1$.

Perhatikan bahawa, apabila $n$ lebih besar daripada $1,$ terdapat fungsi berbentuk $f:\Sigma^n \rightarrow \Sigma$ yang bukan malar mahupun seimbang. Sebagai contoh, fungsi $f:\Sigma^2\rightarrow\Sigma$ yang ditakrifkan sebagai

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

tidak termasuk dalam mana-mana dua kategori ini. Untuk masalah Deutsch-Jozsa, kita tidak perlu risau tentang fungsi seperti ini — ia dianggap sebagai input "jangan ambil pusing". Iaitu, untuk masalah ini kita ada janji bahawa $f$ sama ada malar atau seimbang.

Masalah Deutsch-Jozsa

Input: fungsi $f:\{0,1\}^n\rightarrow\{0,1\}$
Janji: $f$ sama ada malar atau seimbang
Output: $0$ jika $f$ malar, $1$ jika $f$ seimbang

Algoritma Deutsch-Jozsa, dengan satu pertanyaannya, menyelesaikan masalah ini dalam erti kata berikut: jika setiap satu daripada $n$ hasil ukuran adalah $0,$ maka fungsi $f$ adalah malar; dan sebaliknya, jika sekurang-kurangnya satu hasil ukuran adalah $1,$ maka fungsi $f$ adalah seimbang. Cara lain untuk menyatakannya ialah Circuit yang dihuraikan di atas diikuti dengan langkah pemprosesan pasca klasik di mana OR bagi hasil ukuran dikira untuk menghasilkan output.

Analisis algoritma

Untuk menganalisis prestasi algoritma Deutsch-Jozsa bagi masalah Deutsch-Jozsa, adalah berguna untuk memulakan dengan memikirkan tindakan satu lapisan Gate Hadamard. Operasi Hadamard boleh dinyatakan sebagai matriks dengan cara biasa,

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

tetapi kita juga boleh menyatakan operasi ini dari segi tindakannya pada keadaan asas piawai:

$$\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}$$

Kedua-dua persamaan ini boleh digabungkan menjadi satu formula tunggal,

$$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,$$

yang berlaku untuk kedua-dua pilihan $a\in\Sigma.$

Sekarang andaikan bahawa bukannya hanya satu Qubit kita mempunyai $n$ Qubit, dan operasi Hadamard dilakukan pada setiap satu. Operasi gabungan pada $n$ Qubit dihuraikan oleh hasil darab tensor $H\otimes \cdots \otimes H$ ($n$ kali), yang kita tulis sebagai $H^{\otimes n}$ untuk keringkasan dan kejelasan. Menggunakan formula di atas, diikuti dengan mengembangkan dan kemudian memudahkan, kita boleh menyatakan tindakan operasi gabungan ini pada keadaan asas piawai bagi $n$ Qubit seperti ini:

$$\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}$$

Di sini, kita menulis rentetan binari panjang $n$ sebagai $x_{n-1}\cdots x_0$ dan $y_{n-1}\cdots y_0,$ mengikut konvensyen pengindeksan Qiskit.

Formula ini memberi kita alat yang berguna untuk menganalisis Circuit kuantum di atas. Selepas lapisan Gate Hadamard pertama dilakukan, keadaan $n+1$ Qubit (termasuk Qubit paling kiri/bawah, yang dirawat secara berasingan daripada yang lain) ialah

$$\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.$$

Apabila operasi $U_f$ dilakukan, keadaan ini berubah menjadi

$$\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$$

melalui fenomena tendangan fasa yang sama seperti yang kita lihat dalam analisis algoritma Deutsch.

Kemudian lapisan Gate Hadamard kedua dilakukan, yang (melalui formula di atas) mengubah keadaan ini menjadi

$$\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.$$

Ungkapan ini kelihatan agak rumit, dan tidak banyak yang boleh disimpulkan tentang kebarangkalian mendapat hasil ukuran yang berbeza tanpa mengetahui lebih lanjut tentang fungsi $f.$

Nasib baik, yang perlu kita ketahui hanyalah kebarangkalian bahawa setiap satu hasil ukuran adalah $0$ — kerana itulah kebarangkalian algoritma menentukan bahawa $f$ adalah malar. Kebarangkalian ini mempunyai formula yang mudah.

$$\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{if $f$ is constant}\\[1mm] 0 & \text{if $f$ is balanced} \end{cases}$$

Secara lebih terperinci, jika $f$ adalah malar, maka sama ada $f(x_{n-1}\cdots x_0) = 0$ untuk setiap rentetan $x_{n-1}\cdots x_0,$ dalam kes ini nilai jumlah ialah $2^n,$ atau $f(x_{n-1}\cdots x_0) = 1$ untuk setiap rentetan $x_{n-1}\cdots x_0,$ dalam kes ini nilai jumlah ialah $-2^n.$ Membahagi dengan $2^n$ dan mengambil kuasa dua nilai mutlak menghasilkan $1.$

Sebaliknya, jika $f$ adalah seimbang, maka $f$ mengambil nilai $0$ pada separuh rentetan $x_{n-1}\cdots x_0$ dan nilai $1$ pada separuh yang lain, jadi sebutan $+1$ dan sebutan $-1$ dalam jumlah saling menghapuskan dan kita mendapat nilai $0.$

Kita menyimpulkan bahawa algoritma beroperasi dengan betul selagi janji dipenuhi.

Kesukaran klasik

Algoritma Deutsch-Jozsa berfungsi setiap masa, sentiasa memberi jawapan yang betul apabila janji dipenuhi, dan memerlukan satu pertanyaan sahaja. Bagaimana ini berbanding dengan algoritma pertanyaan klasik untuk masalah Deutsch-Jozsa?

Pertama, mana-mana algoritma klasik deterministik yang menyelesaikan masalah Deutsch-Jozsa dengan betul mesti membuat pertanyaan yang amat banyak: $2^{n-1} + 1$ pertanyaan diperlukan dalam kes terburuk. Alasannya ialah, jika algoritma deterministik membuat pertanyaan $f$ pada $2^{n-1}$ atau lebih sedikit rentetan berbeza, dan mendapat nilai fungsi yang sama setiap kali, maka kedua-dua jawapan masih mungkin. Fungsi itu mungkin malar, atau ia mungkin seimbang tetapi malangnya semua pertanyaan kebetulan mengembalikan nilai fungsi yang sama.

Kemungkinan kedua mungkin kelihatan tidak mungkin — tetapi untuk algoritma deterministik tiada kerawakan atau ketidaktentuan, jadi mereka akan gagal secara sistematik pada fungsi tertentu. Oleh itu kita mempunyai kelebihan yang ketara bagi kuantum berbanding algoritma klasik dalam hal ini.

Walau bagaimanapun, terdapat satu tangkapan, iaitu algoritma klasik kebarangkalian boleh menyelesaikan masalah Deutsch-Jozsa dengan kebarangkalian yang sangat tinggi menggunakan hanya beberapa pertanyaan sahaja. Khususnya, jika kita hanya memilih beberapa rentetan berbeza panjang $n$ secara rawak, dan membuat pertanyaan $f$ pada rentetan tersebut, tidak mungkin kita mendapat nilai fungsi yang sama untuk semua daripadanya apabila $f$ adalah seimbang.

Lebih spesifik, jika kita memilih $k$ rentetan input $x^1,\ldots,x^k \in \Sigma^n$ secara seragam rawak, menilai $f(x^1),\ldots,f(x^k),$ dan menjawab $0$ jika nilai fungsi semuanya sama, dan $1$ jika tidak, maka kita akan sentiasa betul apabila $f$ adalah malar, dan salah dalam kes $f$ seimbang dengan kebarangkalian hanya $2^{-k + 1}.$ Jika kita ambil $k = 11,$ sebagai contoh, algoritma ini akan menjawab dengan betul dengan kebarangkalian lebih daripada $99.9$%.

Atas sebab ini, kita masih mempunyai kelebihan yang agak sederhana bagi kuantum berbanding algoritma klasik — tetapi ia tetap merupakan kelebihan yang boleh diukur yang menunjukkan peningkatan berbanding algoritma Deutsch.

Deutsch-Jozsa dengan 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

Untuk melaksanakan algoritma Deutsch-Jozsa dalam Qiskit, kita akan mulakan dengan mentakrifkan fungsi dj_query yang menjana Circuit kuantum yang melaksanakan Gate pertanyaan, untuk fungsi yang dipilih secara rawak yang memenuhi janji untuk masalah Deutsch-Jozsa. Dengan kebarangkalian 50%, fungsi adalah malar, dan dengan kebarangkalian 50% fungsi adalah seimbang. Untuk setiap dua kemungkinan tersebut, fungsi dipilih secara seragam daripada fungsi-fungsi jenis itu. Argumen ialah bilangan bit input bagi fungsi.

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

Kita boleh menunjukkan pelaksanaan Circuit kuantum bagi Gate pertanyaan menggunakan kaedah draw seperti biasa.

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

Seterusnya kita takrifkan fungsi yang mencipta Circuit Deutsch-Jozsa, mengambil pelaksanaan Circuit kuantum bagi Gate pertanyaan sebagai argumen.

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

Akhirnya, fungsi yang menjalankan Circuit Deutsch-Jozsa sekali ditakrifkan.

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"

Kita boleh menguji pelaksanaan kita dengan memilih fungsi secara rawak, memaparkan pelaksanaan Circuit kuantum bagi Gate pertanyaan untuk fungsi ini, dan kemudian menjalankan algoritma Deutsch-Jozsa pada fungsi tersebut.

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

'balanced'

Masalah Bernstein-Vazirani

Seterusnya, kita akan bincangkan satu masalah yang dikenali sebagai masalah Bernstein-Vazirani. Ia juga dipanggil masalah pensampelan Fourier, walaupun terdapat rumusan yang lebih umum bagi masalah ini yang turut menggunakan nama tersebut.

Pertama, mari kita perkenalkan sedikit notasi. Untuk mana-mana dua rentetan binari $x = x_{n-1} \cdots x_0$ dan $y = y_{n-1}\cdots y_0$ dengan panjang $n,$ kita takrifkan

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

Kita akan merujuk operasi ini sebagai hasil darab titik binari. Cara alternatif untuk mentakrifkannya adalah seperti berikut.

$$x \cdot y = \begin{cases} 1 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ adalah ganjil}\\[0.5mm] 0 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ adalah genap} \end{cases}$$

Perhatikan bahawa ini adalah operasi simetri, bermakna hasilnya tidak berubah jika kita tukarkan $x$ dan $y,$ jadi kita bebas berbuat demikian bila-bila masa perlu. Kadang-kadang berguna untuk memikirkan hasil darab titik binari $x \cdot y$ sebagai pariti bit-bit dalam $x$ pada kedudukan di mana rentetan $y$ mempunyai $1,$ atau secara setara, pariti bit-bit dalam $y$ pada kedudukan di mana rentetan $x$ mempunyai $1.$

Dengan notasi ini, kita kini boleh mentakrifkan masalah Bernstein-Vazirani.

Masalah Bernstein-Vazirani

Input: suatu fungsi $f:\{0,1\}^n\rightarrow\{0,1\}$
Janji: wujud rentetan binari $s = s_{n-1} \cdots s_0$ di mana $f(x) = s\cdot x$ untuk semua $x\in\Sigma^n$
Output: rentetan $s$

Kita sebenarnya tidak memerlukan algoritma kuantum baharu untuk masalah ini; algoritma Deutsch-Jozsa menyelesaikannya. Demi kejelasan, mari kita rujuk Circuit kuantum di atas, yang tidak merangkumi langkah pasca-pemprosesan klasik untuk mengira OR, sebagai Circuit Deutsch-Jozsa.

Analisis algoritma

Untuk menganalisis cara Circuit Deutsch-Jozsa berfungsi bagi fungsi yang memenuhi janji masalah Bernstein-Vazirani, kita akan mulakan dengan satu pemerhatian ringkas. Menggunakan hasil darab titik binari, kita boleh menerangkan secara alternatif tindakan $n$ Gate Hadamard ke atas keadaan asas piawai bagi $n$ Qubit seperti berikut.

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

Serupa dengan apa yang kita lihat semasa menganalisis algoritma Deutsch, ini kerana nilai $(-1)^k$ untuk mana-mana integer $k$ hanya bergantung pada sama ada $k$ genap atau ganjil.

Beralih kepada Circuit Deutsch–Jozsa, selepas lapisan pertama Gate Hadamard dilakukan, keadaan $n+1$ Qubit adalah

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

Gate kueri kemudian dilakukan, yang (melalui fenomena tendangan fasa) mengubah keadaan kepada

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

Menggunakan rumus kita untuk tindakan lapisan Gate Hadamard, kita dapati bahawa lapisan kedua Gate Hadamard kemudian mengubah keadaan ini kepada

$$\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.$$

Kini kita boleh membuat beberapa penyederhanaan pada eksponen $-1$ di dalam jumlah. Kita dijanjikan bahawa $f(x) = s\cdot x$ untuk rentetan tertentu $s = s_{n-1} \cdots s_0,$ jadi kita boleh ungkapkan keadaan sebagai

$$\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.$$

Kerana $s\cdot x$ dan $x\cdot y$ adalah nilai binari, kita boleh menggantikan penambahan dengan eksklusif-OR — sekali lagi kerana satu-satunya perkara yang penting bagi integer dalam eksponen $-1$ adalah sama ada ia genap atau ganjil. Menggunakan simetri hasil darab titik binari, kita memperoleh ungkapan ini untuk keadaan tersebut:

$$\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.$$

(Kurungan telah ditambah untuk kejelasan, walaupun ia tidak benar-benar diperlukan kerana adalah konvensional untuk memperlakukan hasil darab titik binari sebagai mempunyai keutamaan lebih tinggi daripada eksklusif-OR.)

Pada ketika ini kita akan menggunakan rumus berikut.

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

Kita boleh memperoleh rumus ini melalui rumus serupa untuk bit,

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

bersama-sama dengan pengembangan hasil darab titik binari dan eksklusif-OR bitwise:

$$\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}$$

Ini membolehkan kita mengungkapkan keadaan Circuit sejurus sebelum pengukuran seperti ini:

$$\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.$$

Langkah terakhir adalah menggunakan satu lagi rumus, yang berlaku untuk setiap rentetan binari $z = z_{n-1}\cdots z_0.$

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

Di sini kita menggunakan notasi ringkas untuk rentetan yang akan kita gunakan beberapa kali lagi dalam pelajaran ini: $0^n$ adalah rentetan semua-sifar dengan panjang $n.$

Cara mudah untuk membuktikan bahawa rumus ini betul adalah dengan mempertimbangkan dua kes secara berasingan. Jika $z = 0^n,$ maka $z\cdot x = 0$ untuk setiap rentetan $x\in\Sigma^n,$ jadi nilai setiap sebutan dalam jumlah adalah $1,$ dan kita mendapat $1$ selepas menjumlah dan membahagi dengan $2^n.$ Sebaliknya, jika mana-mana satu bit dalam $z$ adalah sama dengan $1,$ maka hasil darab titik binari $z\cdot x$ adalah sama dengan $0$ untuk tepat separuh daripada pilihan yang mungkin bagi $x\in\Sigma^n$ dan $1$ untuk separuh yang lain — kerana nilai hasil darab titik binari $z\cdot x$ bertukar (dari $0$ ke $1$ atau dari $1$ ke $0$) jika kita tukarkan mana-mana bit dalam $x$ pada kedudukan di mana $z$ mempunyai $1.$

Jika kita kini menerapkan rumus ini untuk menyederhanakan keadaan Circuit sebelum pengukuran, kita peroleh

$$\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,$$

kerana $s\oplus y = 0^n$ jika dan hanya jika $y = s.$ Oleh itu, pengukuran mendedahkan tepat rentetan $s$ yang kita cari.

Kesukaran klasik

Walaupun Circuit Deutsch-Jozsa menyelesaikan masalah Bernstein-Vazirani dengan satu kueri, mana-mana algoritma kueri klasik mesti membuat sekurang-kurangnya $n$ kueri untuk menyelesaikan masalah ini.

Ini boleh dibuktikan melalui hujah yang dipanggil teori maklumat, yang sangat mudah dalam kes ini. Setiap kueri klasik mendedahkan satu bit maklumat tentang penyelesaian, dan terdapat $n$ bit maklumat yang perlu diungkap — jadi sekurang-kurangnya $n$ kueri diperlukan.

Malah, adalah mungkin untuk menyelesaikan masalah Bernstein-Vazirani secara klasik dengan membuat kueri terhadap fungsi pada setiap $n$ rentetan yang mempunyai satu $1$ sahaja, pada setiap kedudukan yang mungkin, dan $0$ untuk semua bit lain, yang mendedahkan bit-bit dalam $s$ satu demi satu. Oleh itu, kelebihan kuantum berbanding algoritma klasik untuk masalah ini adalah $1$ kueri berbanding $n$ kueri.

Bernstein-Vazirani dengan Qiskit

Kita telah pun melaksanakan Circuit Deutsch-Jozsa di atas, dan di sini kita akan menggunakannya untuk menyelesaikan masalah Bernstein-Vazirani. Pertama, kita akan takrifkan fungsi yang melaksanakan Gate kueri untuk masalah Bernstein-Vazirani bagi mana-mana rentetan binari $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"))

Kini kita boleh mencipta fungsi yang menjalankan Circuit Deutsch-Jozsa ke atas fungsi tersebut, menggunakan fungsi compile_circuit yang telah ditakrifkan sebelum ini.

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'

Catatan tentang penamaan

Dalam konteks masalah Bernstein-Vazirani, adalah lazim bahawa algoritma Deutsch-Jozsa dirujuk sebagai "algoritma Bernstein-Vazirani." Ini sedikit mengelirukan, kerana algoritmanya memang algoritma Deutsch-Jozsa, seperti yang dinyatakan dengan jelas oleh Bernstein dan Vazirani dalam karya mereka.

Apa yang Bernstein dan Vazirani lakukan setelah menunjukkan bahawa algoritma Deutsch-Jozsa menyelesaikan masalah Bernstein-Vazirani (seperti yang dinyatakan di atas) adalah mentakrifkan satu masalah yang jauh lebih rumit, dikenali sebagai masalah pensampelan Fourier rekursif. Ini adalah masalah yang sangat direka-bentuk di mana penyelesaian kepada contoh-contoh masalah yang berbeza secara efektif membuka tahap-tahap baharu masalah yang disusun dalam struktur seperti pokok. Masalah Bernstein-Vazirani pada dasarnya hanyalah kes asas bagi masalah yang lebih rumit ini.

Masalah pensampelan Fourier rekursif adalah contoh pertama yang diketahui bagi masalah kueri di mana algoritma kuantum mempunyai kelebihan yang dipanggil super-polinomial berbanding algoritma probabilistik, dengan itu melampaui kelebihan kuantum berbanding klasik yang ditawarkan oleh algoritma Deutsch-Jozsa. Secara intuitif, versi rekursif masalah ini memperkuatkan kelebihan $1$ berbanding $n$ bagi algoritma kuantum kepada sesuatu yang jauh lebih besar.

Aspek paling mencabar dalam analisis matematik yang membuktikan kelebihan ini adalah menunjukkan bahawa algoritma kueri klasik tidak dapat menyelesaikan masalah tersebut tanpa membuat banyak kueri. Ini cukup tipikal; untuk banyak masalah, boleh jadi sangat sukar untuk menolak pendekatan klasik yang kreatif yang menyelesaikannya dengan cekap.

Masalah Simon, dan algoritma untuknya yang diterangkan dalam bahagian seterusnya, memang memberikan contoh yang jauh lebih mudah tentang kelebihan super-polinomial (dan, sebenarnya, eksponen) kuantum berbanding algoritma klasik, dan atas sebab ini masalah pensampelan Fourier rekursif kurang kerap dibincangkan. Ia tetap merupakan masalah pengiraan yang menarik dengan sendirinya.