Algoritmo ni Deutsch

Ang algoritmo ni Deutsch ay naglulutas ng parity problem para sa espesyal na kaso na $n = 1.$ Sa konteksto ng quantum computing, ang problemang ito ay tinutukoy minsan bilang Deutsch's problem, at susundin natin ang nomenclature na iyon sa araling ito.

Upang maging tumpak, ang input ay kinakatawan ng isang function na $f:\Sigma \rightarrow \Sigma$ mula sa isang bit patungo sa isang bit. May apat na ganyang function:

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

Ang una at huli sa mga function na ito ay constant at ang dalawa sa gitna ay balanced, ibig sabihin, ang dalawang posibleng output value ng function ay parehong dalas habang inuulit natin ang mga input. Ang Deutsch's problem ay ang tukuyin kung alin sa dalawang kategoryang ito ang kinabibilangan ng input function: constant o balanced.

Deutsch's problem

Input: a function $f:\{0,1\}\rightarrow\{0,1\}$
Output: $0$ if $f$ is constant, $1$ if $f$ is balanced

Kung titingnan natin ang input function na $f$ sa Deutsch's problem bilang random access sa isang string, iniisip natin ang isang two-bit string: $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}$$

Kapag tiningnan sa ganitong paraan, ang Deutsch's problem ay ang komputahin ang parity (o, katumbas nito, ang exclusive-OR) ng dalawang bit.

Ang bawat classical query algorithm na tama ang paglutas sa problemang ito ay kailangang i-query ang parehong bit: $f(0)$ at $f(1).$ Halimbawa, kung nalaman natin na $f(1) = 1,$ ang sagot ay maaari pa ring $0$ o $1,$ depende kung $f(0) = 1$ o $f(0) = 0,$ ayon sa pagkakasunod. Katulad nito ang bawat ibang kaso; ang pagkaalam ng isa lang sa dalawang bit ay walang anumang impormasyon tungkol sa kanilang parity. Kaya, ang Boolean circuit na inilarawan sa nakaraang seksyon ang pinakamainam na magagawa natin sa bilang ng mga query na kailangan para malutas ang problemang ito.

Paglalarawan ng quantum circuit

Ang algoritmo ni Deutsch ay naglulutas ng Deutsch's problem gamit ang isang query, kaya nagbibigay ito ng mapapanukalang kalamangan ng quantum kumpara sa classical na computation. Maaaring humble ang kalamangan na ito — isang query kumpara sa dalawa — ngunit kailangan naming magsimula sa isang lugar. Ang mga pag-unlad sa agham ay minsan may tila hamak na pinagmulan.

Narito ang isang quantum circuit na naglalarawan ng algoritmo ni Deutsch:

Pagsusuri

Para suriin ang algoritmo ni Deutsch, susubaybayan natin ang aksyon ng circuit sa itaas at tutukuyin ang mga estado ng mga qubit sa mga oras na iminumungkahi ng figure na ito:

Ang paunang estado ay $\vert 1\rangle \vert 0 \rangle,$ at ang dalawang Hadamard operation sa kaliwang bahagi ng circuit ay nagbabago ng estadong ito sa

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

(Tulad ng lagi, sinusunod natin ang qubit ordering convention ng Qiskit, na naglalagay ng pinakamataas na qubit sa kanan at ang pinakamababang qubit sa kaliwa.) Maaaring hindi natural ang pagsusulat ng product state na ito nang bahagyang ipinagkalat (na iniiwan ang mga estado ng qubit 1 na naka-factor out), ngunit gagawin nitong mas maayos ang ating mga susunod na expression.

Susunod, isasagawa ang gate na $U_f$. Ayon sa kahulugan ng gate na $U_f$, ang halaga ng function na $f$ para sa classical state ng pinakamataas/pinakakanang qubit ay XOR-ed sa pinakamababa/pinakakaliwang qubit, na nagbabago ng $\vert \pi_1\rangle$ sa estado

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

Maaari nating pasimplehin ang expression na ito sa pamamagitan ng pagmamasid na ang formula

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

ay gumagana para sa parehong posibleng halaga na $a\in\Sigma.$ Mas malinaw, ang dalawang kaso ay ang mga sumusunod.

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

Kaya, maaari nating ilarawan ang $\vert\pi_2\rangle$ nang ganito:

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

May nangyaring kagiliw-giliw na bagay! Bagama't ang aksyon ng gate na $U_f$ sa standard basis states ay nag-iiwan ng pinakamataas/pinakakanang qubit nang walang pagbabago at XOR-s ang halaga ng function sa pinakamababa/pinakakaliwang qubit, makikita natin dito na nagbago ang estado ng pinakamataas/pinakakanang qubit (sa pangkalahatan) habang nananatiling pareho ang estado ng pinakamababa/pinakakaliwang qubit — lalo na nasa estado $\vert - \rangle$ bago at pagkatapos na isagawa ang gate na $U_f$. Ang penomenong ito ay kilala bilang phase kickback, at magkakaroon pa tayo ng mas maraming sasabihin tungkol dito sa lalong madaling panahon.

Sa isang huling pagpapasimple, na ang pag-alis ng factor na $(-1)^{f(0)}$ mula sa loob ng sum, makukuha natin ang expression na ito ng estado $\vert\pi_2\rangle$:

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

Pansinin na sa expression na ito, mayroon tayong $f(0) \oplus f(1)$ sa exponent ng $-1$ kumpara sa $f(1) - f(0),$ na maaaring inaasahan natin mula sa isang purong algebraic na pananaw, ngunit pareho ang resulta sa dalawang paraan. Ito ay dahil ang halaga ng $(-1)^k$ para sa anumang integer na $k$ ay nakasalalay lamang sa kung ang $k$ ay even o odd.

Ang pagsasagawa ng huling Hadamard gate sa pinakamataas na qubit ay nagbibigay sa atin ng estado

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

na nagdudulot ng tamang resulta na may probabilidad na $1$ kapag sinukat ang kanan/pinakamataas na qubit.

Karagdagang puna tungkol sa phase kickback

Bago magpatuloy, tingnan natin ang pagsusuri sa itaas mula sa bahagyang ibang anggulo na maaaring magbigay-liwanag sa penomenon ng phase kickback.

Una, pansinin na ang sumusunod na formula ay gumagana para sa lahat ng pagpili ng mga bit na $b,c\in\Sigma.$

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

Maaari itong mapatunayan sa pamamagitan ng pagsusuri nito para sa dalawang posibleng halaga na $c = 0$ at $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}$$

Gamit ang formula na ito, makikita natin na

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

para sa bawat pagpili ng mga bit na $a,b\in\Sigma.$ Dahil tama ang formula na ito para sa $b=0$ at $b=1,$ makikita natin sa pamamagitan ng linearity na

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

para sa lahat ng qubit state vector na $\vert \psi\rangle,$ at samakatuwid

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

Ang susi na gumagana rito ay ang $X\vert - \rangle = - \vert - \rangle.$ Sa mga mathematical na termino, ang vector na $\vert - \rangle$ ay isang eigenvector ng matrix na $X$ na may eigenvalue na $-1.$

Tatalakayin natin ang mga eigenvector at eigenvalue nang mas detalyado sa susunod na aralin tungkol sa Phase estimation and factoring, kung saan ang penomenon ng phase kickback ay ginagawang mas pangkalahatan para sa iba pang unitary operation.

Tandaan na ang mga scalar ay malaya na lumipat sa pamamagitan ng tensor product, makikita natin ang alternatibong paraan ng pag-iisip kung paano binabago ng operasyon $U_f$ ang $\vert \pi_1\rangle$ sa $\vert \pi_2\rangle$ sa pagsusuri sa itaas:

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

Implementasyon sa Qiskit

Tingnan natin ngayon kung paano natin maipapatupad ang algoritmo ni Deutsch sa Qiskit. Magsisimula tayo sa isang version check at pagkatapos ay gagawin ang mga import na kailangan para sa implementasyong ito. Para sa mga implementasyon ng iba pang mga algorithm na susunod, gagawin natin ang mga kinakailangang import nang hiwalay para sa mas malaking modularity.

# 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

Una, magtatakda tayo ng isang quantum circuit na nagpapatupad ng query gate para sa isa sa apat na function na $f_1,$ $f_2,$ $f_3,$ o $f_4$ mula sa isang bit patungo sa isang bit na inilarawan kanina. Tulad ng nabanggit na natin, ang implementasyon ng mga query gate ay hindi talaga bahagi ng algoritmo ni Deutsch mismo; dito ay nagpapakita lang tayo ng isang paraan para ihanda ang input, sa anyo ng isang circuit implementation ng isang query gate.

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

Maaari nating makita kung ano ang hitsura ng bawat circuit gamit ang draw method. Narito ang circuit para sa function na $f_3.$

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

Susunod, lilikha tayo ng aktwal na quantum circuit para sa algoritmo ni Deutsch, na pinalitan ang query gate ng isang quantum circuit implementation na ibinibigay bilang argumento. Sa lalong madaling panahon ay ipa-plug natin ang isa sa apat na circuit na tinukoy ng function na deutsch_function na tinukoy natin kanina. Ang mga barrier ay kasama upang ipakita ang visual na paghihiwalay sa pagitan ng query gate implementation at ng natitirang bahagi ng circuit.

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

Muli, maaari nating makita kung ano ang hitsura ng circuit gamit ang draw method.

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

Sa wakas, lilikha tayo ng isang function na nagpapatakbo ng circuit na dati nating tinukoy nang isang beses at naglalabas ng naaangkop na resulta: "constant" o "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"

Maaari na nating patakbuhin ang algoritmo ni Deutsch sa anumang isa sa apat na function na tinukoy sa itaas.

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

'balanced'