Algoritma Deutsch-Jozsa

Algoritma Deutsch mengungguli semua algoritma klasik untuk masalah query, tapi keuntungannya cukup sederhana: satu query versus dua. Algoritma Deutsch-Jozsa memperluas keuntungan ini — dan, sebenarnya, algoritma ini bisa digunakan untuk menyelesaikan beberapa masalah query yang berbeda.

Berikut deskripsi Circuit kuantum dari algoritma Deutsch-Jozsa. Langkah pemrosesan klasik tambahan, yang tidak ditampilkan dalam gambar, mungkin juga diperlukan tergantung pada masalah spesifik yang sedang diselesaikan.

Tentu saja, kita belum membahas masalah apa yang diselesaikan algoritma ini; hal itu dilakukan di dua bagian berikut.

Masalah Deutsch-Jozsa

Kita akan mulai dengan masalah query yang awalnya dimaksudkan untuk diselesaikan oleh algoritma Deutsch-Jozsa, yang dikenal sebagai masalah Deutsch-Jozsa.

Fungsi input untuk masalah ini berbentuk $f:\Sigma^n \rightarrow \Sigma$ untuk bilangan bulat positif $n$ yang sembarang. Seperti masalah Deutsch, tugasnya adalah mengeluarkan $0$ jika $f$ konstan dan $1$ jika $f$ seimbang, yang kembali berarti bahwa jumlah string input di mana fungsi mengambil nilai $0$ sama dengan jumlah string input di mana fungsi mengambil nilai $1$.

Perhatikan bahwa, ketika $n$ lebih besar dari $1,$ ada fungsi berbentuk $f:\Sigma^n \rightarrow \Sigma$ yang bukan konstan maupun seimbang. Misalnya, fungsi $f:\Sigma^2\rightarrow\Sigma$ yang didefinisikan sebagai

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

tidak termasuk dalam salah satu dari dua kategori ini. Untuk masalah Deutsch-Jozsa, kita tidak perlu khawatir tentang fungsi seperti ini — mereka dianggap sebagai input "don't care". Artinya, untuk masalah ini kita memiliki janji bahwa $f$ adalah konstan atau seimbang.

Masalah Deutsch-Jozsa

Input: sebuah fungsi $f:\{0,1\}^n\rightarrow\{0,1\}$
Janji: $f$ adalah konstan atau seimbang
Output: $0$ jika $f$ konstan, $1$ jika $f$ seimbang

Algoritma Deutsch-Jozsa, dengan satu querynya, menyelesaikan masalah ini dalam pengertian berikut: jika setiap satu dari $n$ hasil pengukuran adalah $0,$ maka fungsi $f$ adalah konstan; dan sebaliknya, jika setidaknya satu dari hasil pengukuran adalah $1,$ maka fungsi $f$ adalah seimbang. Cara lain untuk mengatakannya adalah bahwa Circuit yang dijelaskan di atas diikuti oleh langkah pemrosesan klasik di mana OR dari hasil pengukuran dihitung untuk menghasilkan output.

Analisis algoritma

Untuk menganalisis kinerja algoritma Deutsch-Jozsa untuk masalah Deutsch-Jozsa, ada baiknya kita mulai dengan memikirkan aksi dari satu lapisan Gate Hadamard. Operasi Hadamard dapat diekspresikan 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},$$

tapi kita juga bisa mengekspresikan operasi ini dalam hal aksinya pada keadaan basis standar:

$$\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 persamaan ini dapat digabungkan menjadi satu rumus 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 pilihan $a\in\Sigma.$

Sekarang misalkan alih-alih hanya satu Qubit kita punya $n$ Qubit, dan operasi Hadamard dilakukan pada masing-masing. Operasi gabungan pada $n$ Qubit dijelaskan oleh produk tensor $H\otimes \cdots \otimes H$ ($n$ kali), yang kita tulis sebagai $H^{\otimes n}$ untuk keringkasan dan kejelasan. Menggunakan rumus dari atas, dilanjutkan dengan mengekspansi kemudian menyederhanakan, kita dapat mengekspresikan aksi dari operasi gabungan ini pada keadaan basis standar dari $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, ngomong-ngomong, kita menulis string biner panjang $n$ sebagai $x_{n-1}\cdots x_0$ dan $y_{n-1}\cdots y_0,$ mengikuti konvensi pengindeksan Qiskit.

Rumus ini memberi kita alat yang berguna untuk menganalisis Circuit kuantum di atas. Setelah lapisan pertama Gate Hadamard dilakukan, keadaan $n+1$ Qubit (termasuk Qubit paling kiri/bawah, yang diperlakukan secara terpisah dari yang lain) adalah

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

Ketika operasi $U_f$ dilakukan, keadaan ini diubah 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 phase kick-back yang persis sama seperti yang kita lihat dalam analisis algoritma Deutsch.

Kemudian lapisan kedua Gate Hadamard dilakukan, yang (berdasarkan rumus 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.$$

Ekspresi ini terlihat agak rumit, dan tidak banyak yang bisa disimpulkan tentang probabilitas untuk mendapatkan hasil pengukuran yang berbeda tanpa mengetahui lebih banyak tentang fungsi $f.$

Untungnya, yang perlu kita ketahui hanyalah probabilitas bahwa setiap satu dari hasil pengukuran adalah $0$ — karena itulah probabilitas bahwa algoritma menentukan bahwa $f$ adalah konstan. Probabilitas ini memiliki rumus sederhana.

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

Lebih rinci, jika $f$ konstan, maka entah $f(x_{n-1}\cdots x_0) = 0$ untuk setiap string $x_{n-1}\cdots x_0,$ dalam hal ini nilai jumlahnya adalah $2^n,$ atau $f(x_{n-1}\cdots x_0) = 1$ untuk setiap string $x_{n-1}\cdots x_0,$ dalam hal ini nilai jumlahnya adalah $-2^n.$ Membagi dengan $2^n$ dan mengambil kuadrat dari nilai absolut menghasilkan $1.$

Di sisi lain, jika $f$ seimbang, maka $f$ mengambil nilai $0$ pada setengah dari string $x_{n-1}\cdots x_0$ dan nilai $1$ pada setengah lainnya, sehingga suku-suku $+1$ dan $-1$ dalam jumlah saling menghilangkan dan kita mendapat nilai $0.$

Kita menyimpulkan bahwa algoritma beroperasi dengan benar asalkan janji terpenuhi.

Kesulitan klasik

Algoritma Deutsch-Jozsa bekerja setiap saat, selalu memberi kita jawaban yang benar ketika janji terpenuhi, dan hanya membutuhkan satu query. Bagaimana ini dibandingkan dengan algoritma query klasik untuk masalah Deutsch-Jozsa?

Pertama, algoritma klasik deterministik mana pun yang dengan benar menyelesaikan masalah Deutsch-Jozsa harus membuat query dalam jumlah eksponensial: $2^{n-1} + 1$ query diperlukan dalam kasus terburuk. Alasannya adalah bahwa, jika sebuah algoritma deterministik melakukan query $f$ pada $2^{n-1}$ atau lebih sedikit string yang berbeda, dan mendapatkan nilai fungsi yang sama setiap saat, maka kedua jawaban masih mungkin. Fungsinya mungkin konstan, atau mungkin seimbang tetapi karena kemalangan, query-query tersebut semuanya mengembalikan nilai fungsi yang sama.

Kemungkinan kedua mungkin tampak tidak mungkin — tetapi untuk algoritma deterministik tidak ada keacakan atau ketidakpastian, sehingga mereka akan gagal secara sistematis pada fungsi-fungsi tertentu. Oleh karena itu kita memiliki keuntungan yang signifikan dari algoritma kuantum dibandingkan algoritma klasik dalam hal ini.

Namun ada kendala, yaitu algoritma klasik probabilistik dapat menyelesaikan masalah Deutsch-Jozsa dengan probabilitas sangat tinggi hanya menggunakan beberapa query. Khususnya, jika kita hanya memilih beberapa string berbeda panjang $n$ secara acak, dan melakukan query $f$ pada string-string tersebut, tidak mungkin kita mendapatkan nilai fungsi yang sama untuk semuanya ketika $f$ seimbang.

Lebih spesifik, jika kita memilih $k$ string input $x^1,\ldots,x^k \in \Sigma^n$ secara seragam secara acak, mengevaluasi $f(x^1),\ldots,f(x^k),$ dan menjawab $0$ jika nilai fungsinya semua sama, dan $1$ jika tidak, maka kita akan selalu benar ketika $f$ konstan, dan salah dalam kasus bahwa $f$ seimbang dengan probabilitas hanya $2^{-k + 1}.$ Jika kita mengambil $k = 11,$ misalnya, algoritma ini akan menjawab dengan benar dengan probabilitas lebih besar dari $99.9$%.

Karena alasan ini, kita tetap memiliki keuntungan yang cukup sederhana dari kuantum dibandingkan algoritma klasik — tetapi tetap saja merupakan keuntungan yang dapat dikuantifikasi yang mewakili peningkatan atas 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 mengimplementasikan algoritma Deutsch-Jozsa di Qiskit, kita akan mulai dengan mendefinisikan fungsi dj_query yang menghasilkan Circuit kuantum yang mengimplementasikan Gate query, untuk fungsi yang dipilih secara acak yang memenuhi janji untuk masalah Deutsch-Jozsa. Dengan peluang 50%, fungsinya konstan, dan dengan peluang 50% fungsinya seimbang. Untuk masing-masing dari dua kemungkinan tersebut, fungsinya dipilih secara seragam dari fungsi-fungsi dengan tipe tersebut. Argumennya adalah jumlah bit input dari 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 dapat menampilkan implementasi Circuit kuantum dari Gate query menggunakan metode draw seperti biasa.

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

Selanjutnya kita mendefinisikan fungsi yang membuat Circuit Deutsch-Jozsa, dengan mengambil implementasi Circuit kuantum dari Gate query 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

Terakhir, sebuah fungsi yang menjalankan Circuit Deutsch-Jozsa sekali didefinisikan.

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 dapat menguji implementasi kita dengan memilih fungsi secara acak, menampilkan implementasi Circuit kuantum dari Gate query untuk fungsi ini, lalu menjalankan algoritma Deutsch-Jozsa pada fungsi tersebut.

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

'balanced'

Masalah Bernstein-Vazirani

Selanjutnya, kita akan membahas masalah yang dikenal sebagai masalah Bernstein-Vazirani. Ini juga disebut masalah Fourier sampling, meskipun ada formulasi yang lebih umum dari masalah ini yang juga menggunakan nama tersebut.

Pertama, mari kita perkenalkan beberapa notasi. Untuk dua string biner $x = x_{n-1} \cdots x_0$ dan $y = y_{n-1}\cdots y_0$ dengan panjang $n,$ kita mendefinisikan

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

Kita akan menyebut operasi ini sebagai produk titik biner. Cara alternatif untuk mendefinisikannya adalah seperti ini.

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

Perhatikan bahwa ini adalah operasi simetris, artinya hasilnya tidak berubah jika kita menukar $x$ dan $y,$ jadi kita bebas melakukan itu kapan saja ketika itu nyaman. Terkadang berguna untuk memikirkan produk titik biner $x \cdot y$ sebagai paritas bit dari $x$ di posisi di mana string $y$ memiliki $1,$ atau secara ekivalen, paritas bit dari $y$ di posisi di mana string $x$ memiliki $1.$

Dengan notasi ini di tangan, kita sekarang dapat mendefinisikan masalah Bernstein-Vazirani.

Masalah Bernstein-Vazirani

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

Kita sebenarnya tidak membutuhkan algoritma kuantum baru untuk masalah ini; algoritma Deutsch-Jozsa menyelesaikannya. Demi kejelasan, mari kita sebut Circuit kuantum dari atas, yang tidak mencakup langkah pemrosesan klasik berupa komputasi OR, sebagai Circuit Deutsch-Jozsa.

Analisis algoritma

Untuk menganalisis bagaimana Circuit Deutsch-Jozsa bekerja untuk fungsi yang memenuhi janji untuk masalah Bernstein-Vazirani, kita akan mulai dengan pengamatan singkat. Menggunakan produk titik biner, kita dapat secara alternatif mendeskripsikan aksi dari $n$ Gate Hadamard pada keadaan basis standar dari $n$ Qubit sebagai berikut.

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

Mirip dengan yang kita lihat ketika menganalisis algoritma Deutsch, ini karena nilai $(-1)^k$ untuk bilangan bulat $k$ apa pun hanya bergantung pada apakah $k$ genap atau ganjil.

Beralih ke Circuit Deutsch-Jozsa, setelah 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 query kemudian dilakukan, yang (melalui fenomena phase kickback) mengubah keadaan menjadi

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

Menggunakan rumus kita untuk aksi dari lapisan Gate Hadamard, kita melihat bahwa lapisan kedua Gate Hadamard kemudian mengubah keadaan ini menjadi

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

Sekarang kita dapat membuat beberapa penyederhanaan, dalam eksponen $-1$ di dalam jumlah. Kita dijanjikan bahwa $f(x) = s\cdot x$ untuk suatu string $s = s_{n-1} \cdots s_0,$ jadi kita dapat mengekspresikan 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.$$

Karena $s\cdot x$ dan $x\cdot y$ adalah nilai biner, kita dapat mengganti penjumlahan dengan eksklusif-OR — kembali karena satu-satunya hal yang penting untuk bilangan bulat dalam eksponen $-1$ adalah apakah itu genap atau ganjil. Memanfaatkan simetri produk titik biner, kita mendapatkan ekspresi berikut untuk keadaan:

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

(Tanda kurung telah ditambahkan untuk kejelasan, meskipun sebenarnya tidak diperlukan karena konvensinya adalah memperlakukan produk titik biner sebagai memiliki prioritas lebih tinggi dari eksklusif-OR.)

Pada titik ini kita akan memanfaatkan rumus berikut.

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

Kita dapat memperoleh rumus ini melalui rumus serupa untuk bit,

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

bersama dengan ekspansi produk titik biner 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 memungkinkan kita untuk mengekspresikan keadaan Circuit tepat 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 memanfaatkan satu rumus lagi, yang berlaku untuk setiap string biner $z = z_{n-1}\cdots z_0.$

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

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

Cara sederhana untuk menunjukkan bahwa rumus ini berlaku adalah dengan mempertimbangkan dua kasus secara terpisah. Jika $z = 0^n,$ maka $z\cdot x = 0$ untuk setiap string $x\in\Sigma^n,$ sehingga nilai setiap suku dalam jumlah adalah $1,$ dan kita mendapatkan $1$ dengan menjumlahkan dan membagi dengan $2^n.$ Di sisi lain, jika salah satu bit dari $z$ sama dengan $1,$ maka produk titik biner $z\cdot x$ sama dengan $0$ untuk tepat setengah dari kemungkinan pilihan $x\in\Sigma^n$ dan $1$ untuk setengah lainnya — karena nilai produk titik biner $z\cdot x$ berbalik (dari $0$ ke $1$ atau dari $1$ ke $0$) jika kita membalik bit apa pun dari $x$ di posisi di mana $z$ memiliki $1.$

Jika kita sekarang menerapkan rumus ini untuk menyederhanakan keadaan Circuit sebelum pengukuran, kita mendapatkan

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

karena $s\oplus y = 0^n$ jika dan hanya jika $y = s.$ Dengan demikian, pengukuran mengungkapkan tepat string $s$ yang kita cari.

Kesulitan klasik

Sementara Circuit Deutsch-Jozsa menyelesaikan masalah Bernstein-Vazirani dengan satu query, algoritma query klasik mana pun harus membuat setidaknya $n$ query untuk menyelesaikan masalah ini.

Hal ini dapat dibuktikan melalui argumen yang disebut information theoretic, yang sangat sederhana dalam kasus ini. Setiap query klasik mengungkapkan satu bit informasi tentang solusi, dan ada $n$ bit informasi yang perlu diungkap — sehingga setidaknya $n$ query diperlukan.

Sebenarnya, memang mungkin untuk menyelesaikan masalah Bernstein-Vazirani secara klasik dengan melakukan query fungsi pada masing-masing dari $n$ string yang memiliki satu $1,$ di setiap posisi yang mungkin, dan $0$ untuk semua bit lainnya, yang mengungkapkan bit-bit dari $s$ satu per satu. Oleh karena itu, keuntungan kuantum dibandingkan algoritma klasik untuk masalah ini adalah $1$ query versus $n$ query.

Bernstein-Vazirani dengan Qiskit

Kita sudah mengimplementasikan Circuit Deutsch-Jozsa di atas, dan di sini kita akan menggunakannya untuk menyelesaikan masalah Bernstein-Vazirani. Pertama kita akan mendefinisikan fungsi yang mengimplementasikan Gate query untuk masalah Bernstein-Vazirani untuk string biner $s$ apa pun.

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"))

Sekarang kita dapat membuat fungsi yang menjalankan Circuit Deutsch-Jozsa pada fungsi tersebut, menggunakan fungsi compile_circuit yang telah didefinisikan sebelumnya.

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 nomenklatur

Dalam konteks masalah Bernstein-Vazirani, umum bahwa algoritma Deutsch-Jozsa disebut sebagai "algoritma Bernstein-Vazirani." Ini sedikit menyesatkan, karena algoritmanya adalah algoritma Deutsch-Jozsa, seperti yang sangat jelas dikatakan oleh Bernstein dan Vazirani dalam karya mereka.

Yang Bernstein dan Vazirani lakukan setelah menunjukkan bahwa algoritma Deutsch-Jozsa menyelesaikan masalah Bernstein-Vazirani (seperti yang dinyatakan di atas) adalah mendefinisikan masalah yang jauh lebih rumit, yang dikenal sebagai masalah recursive Fourier sampling. Ini adalah masalah yang sangat dibuat-buat di mana solusi untuk instance yang berbeda dari masalah tersebut secara efektif membuka level baru dari masalah yang disusun dalam struktur seperti pohon. Masalah Bernstein-Vazirani pada dasarnya hanyalah kasus dasar dari masalah yang lebih rumit ini.

Masalah recursive Fourier sampling adalah contoh pertama yang diketahui dari masalah query di mana algoritma kuantum memiliki keuntungan yang disebut super-polinomial atas algoritma probabilistik, sehingga melampaui keuntungan kuantum dibandingkan klasik yang ditawarkan oleh algoritma Deutsch-Jozsa. Secara intuitif, versi rekursif dari masalah ini memperkuat keuntungan $1$ versus $n$ dari algoritma kuantum menjadi sesuatu yang jauh lebih besar.

Aspek paling menantang dari analisis matematika yang menetapkan keuntungan ini adalah menunjukkan bahwa algoritma query klasik tidak dapat menyelesaikan masalah tanpa membuat banyak query. Ini sangat khas; untuk banyak masalah bisa sangat sulit untuk mengecualikan pendekatan klasik yang kreatif yang menyelesaikannya secara efisien.

Masalah Simon, dan algoritma untuk itu yang dijelaskan di bagian berikutnya, memang memberikan contoh yang jauh lebih sederhana dari keuntungan super-polinomial (dan, sebenarnya, eksponensial) kuantum dibandingkan algoritma klasik, dan karena alasan ini masalah recursive Fourier sampling lebih jarang dibahas. Namun demikian, ini adalah masalah komputasi yang menarik dengan sendirinya.