Algoritma Deutsch

Algoritma Deutsch memecahkan masalah paritas untuk kasus khusus bahwa $n = 1.$ Dalam konteks komputasi kuantum masalah ini kadang-kadang disebut sebagai masalah Deutsch, dan kita akan mengikuti nomenklatur tersebut dalam pelajaran ini.

Lebih tepatnya, inputnya diwakili oleh fungsi $f:\Sigma \rightarrow \Sigma$ dari satu bit ke satu bit. Ada empat fungsi seperti itu:

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

Fungsi pertama dan terakhir bersifat konstan dan dua yang di tengah bersifat seimbang, artinya dua nilai keluaran yang mungkin untuk fungsi tersebut terjadi dengan jumlah yang sama saat kita merentang masukan. Masalah Deutsch adalah menentukan kategori mana yang dimiliki fungsi input: konstan atau seimbang.

Masalah Deutsch

Input: fungsi $f:\{0,1\}\rightarrow\{0,1\}$
Output: $0$ jika $f$ konstan, $1$ jika $f$ seimbang

Jika kita melihat fungsi input $f$ dalam masalah Deutsch sebagai mewakili akses acak ke sebuah string, kita sedang memikirkan string dua-bit: $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}$$

Dilihat dari cara ini, masalah Deutsch adalah menghitung paritas (atau, setara, XOR eksklusif) dari dua bit.

Setiap algoritma kueri klasik yang memecahkan masalah ini dengan benar harus mengkueri kedua bit: $f(0)$ dan $f(1).$ Jika kita mengetahui bahwa $f(1) = 1,$ misalnya, jawabannya masih bisa $0$ atau $1,$ tergantung apakah $f(0) = 1$ atau $f(0) = 0,$ masing-masing. Setiap kasus lainnya serupa; mengetahui hanya satu dari dua bit tidak memberikan informasi apapun tentang paritasnya. Jadi, sirkuit Boolean yang dijelaskan di bagian sebelumnya adalah yang terbaik yang bisa kita lakukan dalam hal jumlah kueri yang diperlukan untuk memecahkan masalah ini.

Deskripsi sirkuit kuantum

Algoritma Deutsch memecahkan masalah Deutsch menggunakan satu kueri, sehingga memberikan keunggulan yang dapat diukur dari kuantum atas komputasi klasik. Ini mungkin merupakan keunggulan yang sederhana — satu kueri dibanding dua — tetapi kita harus mulai dari suatu tempat. Kemajuan ilmiah kadang-kadang memiliki asal-usul yang tampaknya sederhana.

Berikut adalah sirkuit kuantum yang mendeskripsikan algoritma Deutsch:

Analisis

Untuk menganalisis algoritma Deutsch, kita akan menelusuri aksi sirkuit di atas dan mengidentifikasi keadaan qubit pada waktu yang disarankan oleh gambar ini:

Keadaan awalnya adalah $\vert 1\rangle \vert 0 \rangle,$ dan dua operasi Hadamard di sisi kiri sirkuit mengubah keadaan ini menjadi

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

(Seperti biasa, kita mengikuti konvensi urutan qubit Qiskit, yang menempatkan qubit atas di sebelah kanan dan qubit bawah di sebelah kiri.) Mungkin terasa tidak intuitif untuk menulis keadaan produk ini sebagian didistribusikan (membiarkan keadaan qubit 1 difaktorkan keluar), tetapi ini akan membuat ekspresi kita selanjutnya lebih ringkas.

Selanjutnya, gate $U_f$ dilakukan. Sesuai definisi gate $U_f$, nilai fungsi $f$ untuk keadaan klasik qubit atas/paling kanan di-XOR ke qubit bawah/paling kiri, yang mengubah $\vert \pi_1\rangle$ menjadi keadaan

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

Kita bisa menyederhanakan ekspresi ini dengan mengamati bahwa rumus

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

berlaku untuk kedua nilai yang mungkin $a\in\Sigma.$ Lebih eksplisit, dua kasusnya adalah sebagai berikut.

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

Dengan demikian, kita bisa mengekspresikan $\vert\pi_2\rangle$ secara alternatif seperti ini:

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

Sesuatu yang menarik baru saja terjadi! Meskipun aksi gate $U_f$ pada keadaan basis standar membiarkan qubit atas/paling kanan sendirian dan meng-XOR nilai fungsi ke qubit bawah/paling kiri, di sini kita melihat bahwa keadaan qubit atas/paling kanan telah berubah (secara umum) sementara keadaan qubit bawah/paling kiri tetap sama — secara khusus berada dalam keadaan $\vert - \rangle$ sebelum dan sesudah gate $U_f$ dilakukan. Fenomena ini dikenal sebagai phase kickback, dan kita akan membahasnya lebih lanjut segera.

Dengan satu penyederhanaan akhir, yaitu menarik faktor $(-1)^{f(0)}$ ke luar dari jumlahan, kita mendapatkan ekspresi keadaan $\vert\pi_2\rangle$ ini:

$$\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{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{if $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

Perhatikan bahwa dalam ekspresi ini, kita memiliki $f(0) \oplus f(1)$ di eksponen $-1$ bukan $f(1) - f(0),$ yang mungkin kita harapkan dari sudut pandang aljabar murni, tetapi kita mendapatkan hasil yang sama dengan cara manapun. Ini karena nilai $(-1)^k$ untuk bilangan bulat $k$ manapun hanya bergantung pada apakah $k$ genap atau ganjil.

Menerapkan gate Hadamard akhir ke qubit atas meninggalkan kita dengan keadaan

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

yang mengarah ke hasil yang benar dengan probabilitas $1$ ketika qubit kanan/paling atas diukur.

Catatan lebih lanjut tentang phase kickback

Sebelum melanjutkan, mari kita lihat analisis di atas dari sudut yang sedikit berbeda yang mungkin memberikan pencerahan tentang fenomena phase kickback.

Pertama, perhatikan bahwa rumus berikut berlaku untuk semua pilihan bit $b,c\in\Sigma.$

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

Ini bisa diverifikasi dengan memeriksa untuk dua nilai yang mungkin $c = 0$ dan $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}$$

Menggunakan rumus ini, kita melihat bahwa

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

untuk setiap pilihan bit $a,b\in\Sigma.$ Karena rumus ini benar untuk $b=0$ dan $b=1,$ kita lihat dengan linearitas bahwa

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

untuk semua vektor keadaan qubit $\vert \psi\rangle,$ dan oleh karena itu

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

Kunci yang membuat ini bekerja adalah bahwa $X\vert - \rangle = - \vert - \rangle.$ Dalam istilah matematis, vektor $\vert - \rangle$ adalah eigenvector dari matriks $X$ yang memiliki eigenvalue $-1.$

Kita akan membahas eigenvector dan eigenvalue secara lebih rinci dalam pelajaran mendatang tentang Estimasi fase dan faktorisasi, di mana fenomena phase kickback digeneralisasikan ke operasi uniter lainnya.

Mengingat bahwa skalar mengalir bebas melalui produk tensor, kita menemukan cara alternatif untuk menalar bagaimana operasi $U_f$ mengubah $\vert \pi_1\rangle$ menjadi $\vert \pi_2\rangle$ dalam analisis di atas:

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

Implementasi dalam Qiskit

Sekarang mari kita lihat bagaimana kita bisa mengimplementasikan algoritma Deutsch dalam Qiskit. Kita akan mulai dengan pemeriksaan versi kemudian melakukan impor yang diperlukan khusus untuk implementasi ini. Untuk implementasi algoritma lain yang mengikuti, kita akan melakukan impor yang diperlukan secara terpisah demi modularitas yang lebih besar.

# 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

Pertama kita akan mendefinisikan sirkuit kuantum yang mengimplementasikan gate kueri untuk salah satu dari empat fungsi $f_1,$ $f_2,$ $f_3,$ atau $f_4$ dari satu bit ke satu bit yang dijelaskan sebelumnya. Seperti yang sudah disebutkan, implementasi gate kueri sebenarnya bukan bagian dari algoritma Deutsch itu sendiri; di sini kita pada dasarnya hanya menunjukkan satu cara untuk mempersiapkan input, dalam bentuk implementasi sirkuit dari gate kueri.

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

Kita bisa melihat seperti apa setiap sirkuit menggunakan metode draw. Berikut adalah sirkuit untuk fungsi $f_3.$

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

Selanjutnya kita akan membuat sirkuit kuantum aktual untuk algoritma Deutsch, menggantikan gate kueri dengan implementasi sirkuit kuantum yang diberikan sebagai argumen. Sebentar lagi kita akan memasukkan salah satu dari empat sirkuit yang didefinisikan oleh fungsi deutsch_function yang kita definisikan sebelumnya. Barrier disertakan untuk menunjukkan pemisahan visual antara implementasi gate kueri dan sisa sirkuit.

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

Sekali lagi kita bisa melihat seperti apa sirkuit menggunakan metode draw.

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

Akhirnya, kita akan membuat fungsi yang menjalankan sirkuit yang sebelumnya didefinisikan satu kali dan mengeluarkan hasil yang sesuai: "constant" atau "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"

Kita sekarang bisa menjalankan algoritma Deutsch pada salah satu dari empat fungsi yang didefinisikan di atas.

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

'balanced'