Ang Deutsch-Jozsa algorithm

Ang algorithm ni Deutsch ay mas mahusay kaysa sa lahat ng classical algorithm para sa isang query problem, ngunit maliit lamang ang kalamangan: isa kumpara sa dalawang query. Pinapalawig ng Deutsch-Jozsa algorithm ang kalamantang ito — at, sa katunayan, maaari itong gamitin para malutas ang ilang iba't ibang query problem.

Narito ang quantum circuit na paglalarawan ng Deutsch-Jozsa algorithm. Maaaring kailanganin din ang karagdagang classical post-processing na hakbang, na hindi ipinapakita sa figure, depende sa partikular na problemang nilulutas.

Siyempre, hindi pa natin tinalakay kung anong mga problema ang nilulutas ng algorithm na ito; gagawin ito sa dalawang seksyong susunod.

Ang Deutsch-Jozsa problem

Magsisimula tayo sa query problem na orihinal na layunin ng Deutsch-Jozsa algorithm na malutas, na kilala bilang ang Deutsch-Jozsa problem.

Ang input function para sa problemang ito ay may anyo na $f:\Sigma^n \rightarrow \Sigma$ para sa isang arbitrary na positibong integer na $n.$ Tulad ng Deutsch's problem, ang gawain ay mag-output ng $0$ kung ang $f$ ay constant at $1$ kung ang $f$ ay balanced, na nangangahulugang ang bilang ng mga input string kung saan ang function ay kumukuha ng halagang $0$ ay katumbas ng bilang ng mga input string kung saan ang function ay kumukuha ng halagang $1$.

Pansinin na, kapag ang $n$ ay mas malaki sa $1,$ mayroong mga function ng anyo $f:\Sigma^n \rightarrow \Sigma$ na hindi constant at hindi rin balanced. Halimbawa, ang function na $f:\Sigma^2\rightarrow\Sigma$ na tinukoy bilang

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

ay hindi nahuhulog sa alinman sa dalawang kategoryang ito. Para sa Deutsch-Jozsa problem, hindi na natin alalahanin ang mga ganitong function — itinuturing itong mga "don't care" na input. Ibig sabihin, para sa problemang ito mayroon tayong pangako na ang $f$ ay constant o balanced.

Deutsch-Jozsa problem

Input: isang function na $f:\{0,1\}^n\rightarrow\{0,1\}$
Pangako: ang $f$ ay constant o balanced
Output: $0$ kung ang $f$ ay constant, $1$ kung ang $f$ ay balanced

Ang Deutsch-Jozsa algorithm, sa iisang query nito, ay nilulutas ang problemang ito sa sumusunod na paraan: kung lahat ng $n$ na resulta ng pagsukat ay $0,$ kung gayon ang function na $f$ ay constant; at kung hindi, kapag hindi bababa sa isa sa mga resulta ng pagsukat ay $1,$ kung gayon ang function na $f$ ay balanced. Isa pang paraan ng pagsasabi nito ay ang circuit na inilarawan sa itaas ay sinusundan ng classical post-processing na hakbang kung saan kinukuwenta ang OR ng mga resulta ng pagsukat upang makabuo ng output.

Pagsusuri ng algorithm

Para masuri ang pagganap ng Deutsch-Jozsa algorithm para sa Deutsch-Jozsa problem, makakatulong na magsimula sa pag-iisip tungkol sa kilos ng isang layer ng mga Hadamard gate. Ang isang Hadamard na operasyon ay maaaring ipahayag bilang isang matrix sa karaniwang paraan,

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

ngunit maaari rin nating ipahayag ang operasyong ito sa pamamagitan ng kilos nito sa mga standard basis state:

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

Ang dalawang ekwasyong ito ay maaaring pagsamahin sa isang formula,

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

na totoo para sa parehong pagpipilian ng $a\in\Sigma.$

Ngayon, ipagpalagay na sa halip na isang Qubit lamang ay mayroon tayong $n$ na Qubit, at isang Hadamard na operasyon ay isinasagawa sa bawat isa. Ang pinagsama-samang operasyon sa $n$ na Qubit ay inilarawan ng tensor product na $H\otimes \cdots \otimes H$ ($n$ beses), na isinusulat natin bilang $H^{\otimes n}$ para sa kaiklian at kalinawan. Gamit ang formula mula sa itaas, sinusundan ng pagpapalawak at pagpapasimple, maaari nating ipahayag ang kilos ng pinagsama-samang operasyong ito sa mga standard basis state ng $n$ Qubit tulad nito:

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

Dito, sa pamamagitan ng paraan, isinusulat natin ang mga binary string na may haba na $n$ bilang $x_{n-1}\cdots x_0$ at $y_{n-1}\cdots y_0,$ sumusunod sa indexing convention ng Qiskit.

Ang formula na ito ay nagbibigay sa atin ng kapaki-pakinabang na kasangkapan para suriin ang quantum circuit sa itaas. Pagkatapos isagawa ang unang layer ng mga Hadamard gate, ang estado ng $n+1$ na Qubit (kasama ang pinakakaliwang/pinakamababang Qubit, na tinatrato nang hiwalay mula sa iba) ay

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

Kapag isinagawa ang operasyong $U_f$, ang estado ay nababago sa

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

sa pamamagitan ng parehong phase kick-back na penomenon na nakita natin sa pagsusuri ng algorithm ni Deutsch.

Pagkatapos ay isinasagawa ang ikalawang layer ng mga Hadamard gate, na (ayon sa formula sa itaas) ay nagbabago ng estado na ito sa

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

Medyo kumplikado ang hitsura ng ekspresyong ito, at hindi masyadong maraming masasabi tungkol sa mga probabilidad na makuha ang iba't ibang resulta ng pagsukat nang hindi alam pa ang higit pa tungkol sa function na $f.$

Sa kabutihang palad, ang kailangan lang nating malaman ay ang probabilidad na lahat ng resulta ng pagsukat ay $0$ — dahil iyon ang probabilidad na matukoy ng algorithm na ang $f$ ay constant. Ang probabilidad na ito ay may simpleng formula.

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

Sa mas detalyadong paliwanag, kung ang $f$ ay constant, kung gayon alinman ay $f(x_{n-1}\cdots x_0) = 0$ para sa bawat string na $x_{n-1}\cdots x_0,$ kung saan ang halaga ng sum ay $2^n,$ o kaya ay $f(x_{n-1}\cdots x_0) = 1$ para sa bawat string na $x_{n-1}\cdots x_0,$ kung saan ang halaga ng sum ay $-2^n.$ Sa pag-divide ng $2^n$ at pagkuha ng parisukat ng absolute value ay nakukuha natin ang $1.$

Kung, sa kabilang banda, ang $f$ ay balanced, kung gayon ang $f$ ay kumukuha ng halagang $0$ sa kalahati ng mga string na $x_{n-1}\cdots x_0$ at halagang $1$ sa kabilang kalahati, kaya ang mga $+1$ at $-1$ na termino sa sum ay nagkakansela at natitira tayo sa halagang $0.$

Napagtatanto natin na ang algorithm ay gumagana nang tama basta natutupad ang pangako.

Kahirapan sa classical

Ang Deutsch-Jozsa algorithm ay gumagana sa bawat pagkakataon, laging nagbibigay ng tamang sagot kapag natutupad ang pangako, at nangangailangan ng isang query lamang. Paano ito ikukumpara sa classical query algorithm para sa Deutsch-Jozsa problem?

Una, ang anumang deterministic na classical algorithm na wastong nalulutas ng Deutsch-Jozsa problem ay dapat gumawa ng exponential na maraming query: kailangan ang $2^{n-1} + 1$ na query sa pinakamasamang kaso. Ang dahilan ay, kung ang isang deterministic na algorithm ay nag-query sa $f$ sa $2^{n-1}$ o mas kaunting iba't ibang string, at nakakakuha ng parehong function value sa bawat pagkakataon, kung gayon parehong sagot ay posible pa rin. Ang function ay maaaring constant, o maaaring balanced ngunit sa malas ang mga query ay nagbabalik ng parehong function value.

Ang ikalawang posibilidad ay maaaring mukhang hindi malamang — ngunit para sa mga deterministic na algorithm ay walang randomness o kawalan ng katiyakan, kaya mabibigo sila nang sistematiko sa ilang mga function. Kaya naman mayroon tayong makabuluhang kalamangan ng quantum kumpara sa classical na algorithm sa aspetong ito.

Ngunit mayroon isang caveat, at iyon ay ang mga probabilistic na classical algorithm ay kayang malutas ang Deutsch-Jozsa problem nang may napakataas na probabilidad gamit ang ilang query lamang. Sa partikular, kung pipili lang tayo ng ilang iba't ibang string na may haba na $n$ nang random, at mag-query sa $f$ sa mga string na iyon, hindi malamang na makakakuha tayo ng parehong function value para sa lahat ng mga ito kapag ang $f$ ay balanced.

Para maging tiyak, kung pipiliin natin ang $k$ na input string na $x^1,\ldots,x^k \in \Sigma^n$ nang uniformly at random, suriin ang $f(x^1),\ldots,f(x^k),$ at sumagot ng $0$ kung pareho ang lahat ng function value, at $1$ kung hindi, palagi tayong magiging tama kapag ang $f$ ay constant, at maling sagot sa kaso ng balanced na $f$ na may probabilidad na $2^{-k + 1}$ lamang. Kung kukuha tayo ng $k = 11,$ halimbawa, ang algorithm na ito ay sasagot nang tama nang may probabilidad na mas malaki sa $99.9$%.

Dahil dito, mayroon pa rin tayong medyo maliit na kalamangan ng quantum kumpara sa classical na algorithm — ngunit ito ay isang nasusukat na kalamangan na kumakatawan sa pagpapabuti kumpara sa algorithm ni Deutsch.

Deutsch-Jozsa gamit ang 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

Para ipatupad ang Deutsch-Jozsa algorithm sa Qiskit, magsisimula tayo sa pamamagitan ng pagtukoy ng function na dj_query na gumagawa ng quantum circuit na nagpapatupad ng query gate, para sa isang random na piniling function na nakakatugon sa pangako para sa Deutsch-Jozsa problem. Sa 50% na tsansa, ang function ay constant, at sa 50% na tsansa ang function ay balanced. Para sa bawat isa sa dalawang posibilidad na iyon, ang function ay pinipili nang uniformly mula sa mga function ng ganoong uri. Ang argument ay ang bilang ng input bits ng function.

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

Maaari nating ipakita ang quantum circuit na implementasyon ng query gate gamit ang draw na paraan tulad ng dati.

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

Susunod na tutukuyin natin ang isang function na gumagawa ng Deutsch-Jozsa circuit, na tumatanggap ng quantum circuit na implementasyon ng query gate bilang argument.

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

Sa wakas, isang function na nagpapatakbo ng Deutsch-Jozsa circuit nang isang beses ay tinukoy.

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"

Maaari nating subukan ang ating implementasyon sa pamamagitan ng random na pagpili ng function, pagpapakita ng quantum circuit na implementasyon ng query gate para sa function na ito, at pagpapatakbo ng Deutsch-Jozsa algorithm sa function na iyon.

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

'balanced'

Ang Bernstein-Vazirani problem

Susunod, tatalakayin natin ang isang problem na kilala bilang ang Bernstein-Vazirani problem. Tinatawag din itong Fourier sampling problem, kahit mayroon pa ring mas pangkalahatang mga formulation ng problemang ito na tinatawag rin sa pangalang iyon.

Una, ipakilala natin ang ilang notasyon. Para sa anumang dalawang binary string na $x = x_{n-1} \cdots x_0$ at $y = y_{n-1}\cdots y_0$ na may haba na $n,$ tinutukoy natin ang

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

Tatawagin natin ang operasyong ito bilang ang binary dot product. Isang alternatibong paraan ng pagtukoy nito ay ganito.

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

Pansinin na ito ay isang symmetric na operasyon, ibig sabihin, ang resulta ay hindi nagbabago kung i-swap natin ang $x$ at $y,$ kaya malaya tayong gawin ito anumang oras na maginhawa. Minsan ay kapaki-pakinabang na isipin ang binary dot product na $x \cdot y$ bilang ang parity ng mga bit ng $x$ sa mga posisyon kung saan ang string na $y$ ay may $1,$ o katumbas nito, ang parity ng mga bit ng $y$ sa mga posisyon kung saan ang string na $x$ ay may $1.$

Sa notasyong ito, maaari na nating tukuyin ang Bernstein-Vazirani problem.

Bernstein-Vazirani problem

Input: isang function na $f:\{0,1\}^n\rightarrow\{0,1\}$
Pangako: mayroon isang binary string na $s = s_{n-1} \cdots s_0$ kung saan ang $f(x) = s\cdot x$ para sa lahat ng $x\in\Sigma^n$
Output: ang string na $s$

Hindi na natin kailangan ng bagong quantum algorithm para sa problemang ito; nilulutas ito ng Deutsch-Jozsa algorithm. Para sa kalinawan, tukuyin natin ang quantum circuit mula sa itaas, na hindi kasama ang classical post-processing na hakbang ng pagkuwenta ng OR, bilang ang Deutsch-Jozsa circuit.

Pagsusuri ng algorithm

Para masuri kung paano gumagana ang Deutsch-Jozsa circuit para sa isang function na nakakatugon sa pangako para sa Bernstein-Vazirani problem, magsisimula tayo sa isang mabilis na obserbasyon. Gamit ang binary dot product, maaari nating alternatibong ilarawan ang kilos ng $n$ na Hadamard gate sa mga standard basis state ng $n$ Qubit tulad ng sumusunod.

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

Katulad ng nakita natin nang sinusuri ang algorithm ni Deutsch, ito ay dahil ang halagang $(-1)^k$ para sa anumang integer na $k$ ay nakasalalay lamang sa kung ang $k$ ay even o odd.

Bumabalik sa Deutsch–Jozsa circuit, pagkatapos isagawa ang unang layer ng mga Hadamard gate, ang estado ng $n+1$ na Qubit ay

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

Ang query gate ay isinasagawa pagkatapos, na (sa pamamagitan ng phase kickback phenomenon) ay nagbabago ng estado sa

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

Gamit ang ating formula para sa kilos ng isang layer ng mga Hadamard gate, nakikita natin na ang ikalawang layer ng mga Hadamard gate ay nagbabago ng estado na ito sa

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

Ngayon ay maaari tayong gumawa ng ilang simplipikasyon, sa exponent ng $-1$ sa loob ng sum. Pinangako sa atin na ang $f(x) = s\cdot x$ para sa ilang string na $s = s_{n-1} \cdots s_0,$ kaya maaari nating ipahayag ang estado bilang

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

Dahil ang $s\cdot x$ at $x\cdot y$ ay mga binary na halaga, maaari nating palitan ang addition ng exclusive-OR — muli dahil ang tanging mahalaga para sa isang integer sa exponent ng $-1$ ay kung ito ay even o odd. Gamit ang symmetry ng binary dot product, makukuha natin ang ekspresyong ito para sa estado:

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

(Ang mga panaklong ay idinagdag para sa kalinawan, kahit hindi talaga kailangan dahil kaugalian na tratuhin ang binary dot product na may mas mataas na precedence kaysa sa exclusive-OR.)

Sa puntong ito gagamitin natin ang sumusunod na formula.

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

Maaari nating makuha ang formula sa pamamagitan ng katulad na formula para sa mga bit,

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

kasama ang pagpapalawak ng binary dot product at bitwise exclusive-OR:

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

Ito ay nagpapahintulot sa atin na ipahayag ang estado ng circuit bago pa ang mga pagsukat tulad nito:

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

Ang huling hakbang ay gamitin ang isa pang formula, na gumagana para sa bawat binary string na $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}$$

Dito gumagamit tayo ng simpleng notasyon para sa mga string na gagamitin natin ng ilang beses pa sa aralin: ang $0^n$ ay ang all-zero string na may haba na $n.$

Isang simpleng paraan para ipakita na gumagana ang formula na ito ay ang isaalang-alang ang dalawang kaso nang hiwalay. Kung ang $z = 0^n,$ kung gayon ang $z\cdot x = 0$ para sa bawat string na $x\in\Sigma^n,$ kaya ang halaga ng bawat termino sa sum ay $1,$ at nakakakuha tayo ng $1$ sa pamamagitan ng pagdaragdag at pag-divide ng $2^n.$ Sa kabilang banda, kung ang alinman sa mga bit ng $z$ ay katumbas ng $1,$ kung gayon ang binary dot product na $z\cdot x$ ay katumbas ng $0$ para sa eksakto sa kalahati ng mga posibleng pagpipilian para sa $x\in\Sigma^n$ at $1$ para sa kabilang kalahati — dahil ang halaga ng binary dot product na $z\cdot x$ ay nagbabago (mula $0$ hanggang $1$ o mula $1$ hanggang $0$) kung i-flip natin ang anumang bit ng $x$ sa isang posisyon kung saan ang $z$ ay may $1.$

Kung ilalapat natin ang formula na ito para pasimplehin ang estado ng circuit bago ang mga pagsukat, makukuha natin ang

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

dahil sa katotohanang ang $s\oplus y = 0^n$ kung at kung ang $y = s.$ Kaya, ang mga pagsukat ay nagpapakita ng eksakto ang string na $s$ na hinahanap natin.

Kahirapan sa classical

Habang nilulutas ng Deutsch-Jozsa circuit ang Bernstein-Vazirani problem gamit ang isang query, ang anumang classical query algorithm ay kailangang gumawa ng hindi bababa sa $n$ na query para malutas ang problemang ito.

Maaari itong ipaliwanag sa pamamagitan ng tinatawag na information theoretic na argumento, na napakasimple sa kasong ito. Ang bawat classical query ay nagbubunyag ng isang bit ng impormasyon tungkol sa solusyon, at mayroon $n$ na bit ng impormasyon na kailangang matuklasan — kaya kailangan ng hindi bababa sa $n$ na query.

Sa katunayan, posible na malutas ang Bernstein-Vazirani problem nang klasikal sa pamamagitan ng pag-query sa function sa bawat isa sa $n$ na string na may isang $1,$ sa bawat posibleng posisyon, at $0$ para sa lahat ng iba pang bit, na nagbubunyag ng mga bit ng $s$ nang isa-isa. Kaya naman, ang kalamangan ng quantum kumpara sa classical na algorithm para sa problemang ito ay $1$ query kumpara sa $n$ na query.

Bernstein-Vazirani gamit ang Qiskit

Naipatupad na natin ang Deutsch-Jozsa circuit sa itaas, at dito gagamitin natin ito para malutas ang Bernstein-Vazirani problem. Una, tutukuyin natin ang isang function na nagpapatupad ng query gate para sa Bernstein-Vazirani problem para sa anumang binary string na $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"))

Ngayon ay maaari tayong lumikha ng isang function na nagpapatakbo ng Deutsch-Jozsa circuit sa function, gamit ang compile_circuit na function na tinukoy nang mas maaga.

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'

Puna sa nomenclature

Sa konteksto ng Bernstein-Vazirani problem, karaniwang tinutukoy ang Deutsch-Jozsa algorithm bilang "Bernstein-Vazirani algorithm." Ito ay bahagyang nakakalito, dahil ang algorithm ay ang Deutsch-Jozsa algorithm, gaya ng malinaw na itinakda nina Bernstein at Vazirani sa kanilang gawain.

Ang ginawa nina Bernstein at Vazirani pagkatapos ipakita na nilulutas ng Deutsch-Jozsa algorithm ang Bernstein-Vazirani problem (tulad ng nakasaad sa itaas) ay tumukoy ng mas kumplikadong problema, na kilala bilang ang recursive Fourier sampling problem. Ito ay isang lubhang contrived na problema kung saan ang mga solusyon sa iba't ibang instance ng problema ay epektibong nagbubukas ng mga bagong antas ng problema na nakaayos sa isang tree-like na istraktura. Ang Bernstein-Vazirani problem ay mahalagang base case lamang ng mas kumplikadong problemang ito.

Ang recursive Fourier sampling problem ay ang unang kilalang halimbawa ng isang query problem kung saan ang mga quantum algorithm ay may tinatawag na super-polynomial na kalamangan kumpara sa mga probabilistic na algorithm, na lumagpas sa kalamangan ng quantum kumpara sa classical na inaalok ng Deutsch-Jozsa algorithm. Sa intuitive na pagsasalita, ang recursive na bersyon ng problema ay nagpapalaki ng $1$ kumpara sa $n$ na kalamangan ng mga quantum algorithm sa mas malaking bagay.

Ang pinaka-mapaghamong aspeto ng mathematical analysis na nagtatag ng kalamantang ito ay ang pagpapakita na ang mga classical query algorithm ay hindi makakalutas ng problema nang hindi gumagawa ng maraming query. Ito ay napaka-tipikal; para sa maraming problema maaaring maging napakahirap na ibukod ang mga malikhaing classical na diskarte na naglulutas sa kanila nang mahusay.

Ang Simon's problem, at ang algorithm para dito na inilarawan sa susunod na seksyon, ay nagbibigay ng mas simpleng halimbawa ng isang super-polynomial (at, sa katunayan, exponential) na kalamangan ng quantum kumpara sa classical na algorithm, at sa kadahilanang ito ang recursive Fourier sampling problem ay hindi gaanong madalas na tinalakay. Ito ay, gayunpaman, isang kawili-wiling computational problem sa sarili nitong karapatan.