Algoritma Deutsch

Algoritma Deutsch menyelesaikan masalah pariti untuk kes khas di mana $n = 1.$ Dalam konteks pengkomputeran kuantum, masalah ini kadangkala dirujuk sebagai masalah Deutsch, dan kita akan menggunakan tatanomenklatur itu dalam pelajaran ini.

Untuk lebih tepat, input diwakili oleh fungsi $f:\Sigma \rightarrow \Sigma$ dari satu bit ke satu bit. Terdapat empat fungsi sedemikian:

$$\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 adalah malar manakala dua yang di tengah adalah seimbang, bermakna dua nilai output yang mungkin bagi fungsi tersebut muncul dengan bilangan yang sama apabila kita mengambil semua input. Masalah Deutsch adalah untuk menentukan kategori mana fungsi input tersebut tergolong: malar atau seimbang.

Masalah Deutsch

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

Jika kita melihat fungsi input $f$ dalam masalah Deutsch sebagai mewakili capaian rawak kepada rentetan, kita sedang memikirkan tentang rentetan 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}$$

Apabila dilihat dengan cara ini, masalah Deutsch adalah untuk mengira pariti (atau, secara setara, XOR eksklusif) dua bit tersebut.

Setiap algoritma pertanyaan klasik yang menyelesaikan masalah ini dengan betul mesti bertanya kedua-dua bit: $f(0)$ dan $f(1).$ Jika kita mengetahui bahawa $f(1) = 1,$ sebagai contoh, jawapannya masih boleh $0$ atau $1,$ bergantung pada sama ada $f(0) = 1$ atau $f(0) = 0,$ masing-masing. Setiap kes lain adalah serupa; mengetahui hanya satu daripada dua bit tidak memberikan sebarang maklumat tentang pariti mereka. Jadi, litar Boolean yang diterangkan dalam bahagian sebelumnya adalah yang terbaik yang boleh kita lakukan dari segi bilangan pertanyaan yang diperlukan untuk menyelesaikan masalah ini.

Penerangan litar kuantum

Algoritma Deutsch menyelesaikan masalah Deutsch menggunakan satu pertanyaan sahaja, dengan itu memberikan kelebihan yang boleh diukur bagi kuantum berbanding pengiraan klasik. Ini mungkin kelebihan yang sederhana — satu pertanyaan berbanding dua — tetapi kita perlu bermula dari suatu tempat. Kemajuan saintifik kadangkala mempunyai asal-usul yang kelihatan rendah hati.

Berikut adalah litar kuantum yang menerangkan algoritma Deutsch:

Analisis

Untuk menganalisis algoritma Deutsch, kita akan meneliti tindakan litar di atas dan mengenal pasti keadaan Qubit pada masa-masa yang dicadangkan oleh rajah ini:

Keadaan awal adalah $\vert 1\rangle \vert 0 \rangle,$ dan dua operasi Hadamard di sebelah kiri litar mengubah keadaan ini kepada

$$\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 konvensyen susunan Qubit Qiskit, yang meletakkan Qubit atas di sebelah kanan dan Qubit bawah di sebelah kiri.) Mungkin terasa tidak intuitif untuk menulis keadaan produk ini sebahagiannya dalam bentuk teragih (meninggalkan keadaan Qubit 1 dalam bentuk faktor), tetapi ini akan menjadikan ungkapan kita kemudian lebih ringkas.

Seterusnya, gerbang $U_f$ dilaksanakan. Mengikut definisi gerbang $U_f,$ nilai fungsi $f$ untuk keadaan klasik Qubit atas/paling kanan di-XOR ke atas Qubit bawah/paling kiri, yang mengubah $\vert \pi_1\rangle$ kepada 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 boleh memudahkan ungkapan ini dengan memerhatikan bahawa formula

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

berfungsi untuk kedua-dua nilai yang mungkin $a\in\Sigma.$ Secara lebih eksplisit, dua kes tersebut adalah seperti 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}$$

Oleh itu, kita boleh menyatakan $\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 berlaku! Walaupun tindakan gerbang $U_f$ pada keadaan asas standard membiarkan Qubit atas/paling kanan tidak berubah dan meng-XOR nilai fungsi ke atas Qubit bawah/paling kiri, di sini kita melihat bahawa keadaan Qubit atas/paling kanan telah berubah (secara umumnya) manakala keadaan Qubit bawah/paling kiri kekal sama — khususnya berada dalam keadaan $\vert - \rangle$ sebelum dan selepas gerbang $U_f$ dilaksanakan. Fenomena ini dikenali sebagai tendangan fasa, dan kita akan membincangkannya dengan lebih lanjut tidak lama lagi.

Dengan satu pemudahan terakhir, iaitu mengeluarkan faktor $(-1)^{f(0)}$ ke luar jumlah, kita memperoleh ungkapan 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{jika $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{jika $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

Perhatikan bahawa dalam ungkapan ini, kita mempunyai $f(0) \oplus f(1)$ dalam eksponen $-1$ berbanding $f(1) - f(0),$ yang mungkin kita jangkakan dari sudut pandang aljabar semata-mata, tetapi kita mendapat hasil yang sama dalam kedua-dua cara. Ini kerana nilai $(-1)^k$ untuk sebarang integer $k$ hanya bergantung pada sama ada $k$ adalah genap atau ganjil.

Menggunakan gerbang Hadamard terakhir pada Qubit atas meninggalkan kita dengan keadaan

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

yang membawa kepada hasil yang betul dengan kebarangkalian $1$ apabila Qubit kanan/paling atas diukur.

Catatan lanjut tentang tendangan fasa

Sebelum meneruskan, mari kita lihat analisis di atas dari sudut yang sedikit berbeza yang mungkin dapat menjelaskan fenomena tendangan fasa.

Pertama, perhatikan bahawa formula berikut berfungsi untuk semua pilihan bit $b,c\in\Sigma.$

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

Ini boleh disahkan dengan menyemaknya untuk dua nilai $c = 0$ dan $c = 1$ yang mungkin:

$$\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 formula ini, kita melihat bahawa

$$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.$ Kerana formula ini benar untuk $b=0$ dan $b=1,$ kita melihat melalui kelinearan bahawa

$$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 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 menjadikan ini berfungsi ialah $X\vert - \rangle = - \vert - \rangle.$ Dalam istilah matematik, vektor $\vert - \rangle$ adalah vektor eigen bagi matriks $X$ yang mempunyai nilai eigen $-1.$

Kita akan membincangkan vektor eigen dan nilai eigen dengan lebih terperinci dalam pelajaran akan datang tentang Anggaran fasa dan pemfaktoran, di mana fenomena tendangan fasa digeneralisasikan kepada operasi uniter lain.

Dengan mengingat bahawa skalar bergerak bebas melalui hasil tensor, kita menemui cara alternatif untuk memikirkan bagaimana operasi $U_f$ mengubah $\vert \pi_1\rangle$ kepada $\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}$$

Pelaksanaan dalam Qiskit

Sekarang mari kita lihat bagaimana kita boleh melaksanakan algoritma Deutsch dalam Qiskit. Kita akan bermula dengan semakan versi dan kemudian melakukan import yang diperlukan khusus untuk pelaksanaan ini. Untuk pelaksanaan algoritma lain yang berikut, kita akan melakukan import yang diperlukan secara berasingan demi modulariti yang lebih baik.

# 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 litar kuantum yang melaksanakan gerbang pertanyaan untuk salah satu daripada empat fungsi $f_1,$ $f_2,$ $f_3,$ atau $f_4$ dari satu bit ke satu bit yang diterangkan sebelumnya. Seperti yang telah kita sebutkan, pelaksanaan gerbang pertanyaan sebenarnya bukan sebahagian daripada algoritma Deutsch itu sendiri; di sini kita pada asasnya hanya menunjukkan satu cara untuk menyediakan input, dalam bentuk pelaksanaan litar gerbang pertanyaan.

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 boleh melihat rupa setiap litar menggunakan kaedah draw. Berikut adalah litar untuk fungsi $f_3.$

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

Seterusnya kita akan mencipta litar kuantum sebenar untuk algoritma Deutsch, menggantikan gerbang pertanyaan dengan pelaksanaan litar kuantum yang diberikan sebagai argumen. Tidak lama lagi kita akan memasukkan salah satu daripada empat litar yang ditakrifkan oleh fungsi deutsch_function yang kita takrifkan sebelumnya. Penghalang disertakan untuk menunjukkan pemisahan visual antara pelaksanaan gerbang pertanyaan dan bahagian lain litar.

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 boleh melihat rupa litar menggunakan kaedah draw.

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

Akhirnya, kita akan mencipta fungsi yang menjalankan litar yang ditakrifkan sebelumnya sekali dan mengeluarkan hasil yang sesuai: "malar" atau "seimbang."

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 kini boleh menjalankan algoritma Deutsch pada mana-mana satu daripada empat fungsi yang ditakrifkan di atas.

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

'balanced'