Algoritmul Deutsch-Jozsa

Algoritmul lui Deutsch depășește toți algoritmii clasici pentru o problemă de interogare, însă avantajul este destul de modest: o interogare față de două. Algoritmul Deutsch-Jozsa extinde acest avantaj — și, de fapt, poate fi folosit pentru a rezolva câteva probleme de interogare diferite.

Iată o descriere în circuit cuantic a algoritmului Deutsch-Jozsa. Un pas suplimentar de post-procesare clasică, neprezentat în figură, poate fi de asemenea necesar în funcție de problema specifică rezolvată.

Desigur, nu am discutat încă ce probleme rezolvă acest algoritm; acest lucru este tratat în cele două secțiuni care urmează.

Problema Deutsch-Jozsa

Vom începe cu problema de interogare pe care algoritmul Deutsch-Jozsa a fost inițial conceput să o rezolve, cunoscută sub numele de problema Deutsch-Jozsa.

Funcția de intrare pentru această problemă are forma $f:\Sigma^n \rightarrow \Sigma$ pentru un număr întreg pozitiv arbitrar $n.$ La fel ca în cazul problemei lui Deutsch, sarcina este să returnezi $0$ dacă $f$ este constantă și $1$ dacă $f$ este echilibrată, ceea ce înseamnă din nou că numărul șirurilor de intrare pentru care funcția ia valoarea $0$ este egal cu numărul șirurilor de intrare pentru care funcția ia valoarea $1$.

Observă că, atunci când $n$ este mai mare decât $1,$ există funcții de forma $f:\Sigma^n \rightarrow \Sigma$ care nu sunt nici constante, nici echilibrate. De exemplu, funcția $f:\Sigma^2\rightarrow\Sigma$ definită ca

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

nu se încadrează în niciuna dintre aceste două categorii. Pentru problema Deutsch-Jozsa, pur și simplu nu ne preocupăm de astfel de funcții — ele sunt considerate intrări de tip „nu contează". Adică, pentru această problemă avem o promisiune că $f$ este fie constantă, fie echilibrată.

Problema Deutsch-Jozsa

Intrare: o funcție $f:\{0,1\}^n\rightarrow\{0,1\}$
Promisiune: $f$ este fie constantă, fie echilibrată
Ieșire: $0$ dacă $f$ este constantă, $1$ dacă $f$ este echilibrată

Algoritmul Deutsch-Jozsa, cu o singură interogare, rezolvă această problemă în sensul următor: dacă fiecare dintre cele $n$ rezultate ale măsurătorii este $0,$ atunci funcția $f$ este constantă; iar în caz contrar, dacă cel puțin unul dintre rezultatele măsurătorii este $1,$ atunci funcția $f$ este echilibrată. O altă modalitate de a spune acest lucru este că circuitul descris mai sus este urmat de un pas de post-procesare clasică în care se calculează SAU logic al rezultatelor măsurătorii pentru a produce ieșirea.

Analiza algoritmului

Pentru a analiza performanța algoritmului Deutsch-Jozsa pentru problema Deutsch-Jozsa, este util să începem prin a gândi la acțiunea unui singur strat de porți Hadamard. O operație Hadamard poate fi exprimată ca o matrice în modul obișnuit,

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

dar putem exprima această operație și în termenii acțiunii sale asupra stărilor bazei standard:

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

Aceste două ecuații pot fi combinate într-o singură formulă,

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

care este adevărată pentru ambele alegeri ale lui $a\in\Sigma.$

Să presupunem acum că, în loc de un singur Qubit, avem $n$ Qubiți, și o operație Hadamard este efectuată pe fiecare. Operația combinată pe cei $n$ Qubiți este descrisă de produsul tensorial $H\otimes \cdots \otimes H$ ($n$ ori), pe care îl scriem ca $H^{\otimes n}$ pentru concizie și claritate. Folosind formula de mai sus, urmată de extindere și simplificare, putem exprima acțiunea acestei operații combinate asupra stărilor bazei standard ale celor $n$ Qubiți astfel:

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

Menționăm că, în acest context, scriem șiruri binare de lungime $n$ ca $x_{n-1}\cdots x_0$ și $y_{n-1}\cdots y_0,$ urmând convenția de indexare a Qiskit.

Această formulă ne oferă un instrument util pentru analiza circuitului cuantic de mai sus. După ce primul strat de porți Hadamard este efectuat, starea celor $n+1$ Qubiți (inclusiv cel mai din stânga/de jos Qubit, care este tratat separat față de restul) este

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

Când operația $U_f$ este efectuată, această stare este transformată în

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

prin exact același fenomen de revenire de fază pe care l-am văzut în analiza algoritmului lui Deutsch.

Apoi al doilea strat de porți Hadamard este efectuat, care (prin formula de mai sus) transformă această stare în

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

Această expresie pare oarecum complicată și nu se pot trage prea multe concluzii despre probabilitățile de a obține diferite rezultate ale măsurătorii fără a ști mai multe despre funcția $f.$

Din fericire, tot ce trebuie să știm este probabilitatea ca fiecare dintre rezultatele măsurătorii să fie $0$ — deoarece aceasta este probabilitatea că algoritmul determină că $f$ este constantă. Această probabilitate are o formulă simplă.

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

Mai în detaliu, dacă $f$ este constantă, atunci fie $f(x_{n-1}\cdots x_0) = 0$ pentru orice șir $x_{n-1}\cdots x_0,$ caz în care valoarea sumei este $2^n,$ fie $f(x_{n-1}\cdots x_0) = 1$ pentru orice șir $x_{n-1}\cdots x_0,$ caz în care valoarea sumei este $-2^n.$ Împărțind cu $2^n$ și luând pătratul valorii absolute obținem $1.$

Dacă, pe de altă parte, $f$ este echilibrată, atunci $f$ ia valoarea $0$ pe jumătate dintre șirurile $x_{n-1}\cdots x_0$ și valoarea $1$ pe cealaltă jumătate, astfel că termenii $+1$ și $-1$ din sumă se anulează și rămânem cu valoarea $0.$

Concluzionăm că algoritmul funcționează corect cu condiția că promisiunea este îndeplinită.

Dificultatea clasică

Algoritmul Deutsch-Jozsa funcționează de fiecare dată, oferindu-ne întotdeauna răspunsul corect când promisiunea este îndeplinită, și necesită o singură interogare. Cum se compară aceasta cu algoritmii de interogare clasici pentru problema Deutsch-Jozsa?

În primul rând, orice algoritm clasic determinist care rezolvă corect problema Deutsch-Jozsa trebuie să facă un număr exponențial de interogări: sunt necesare $2^{n-1} + 1$ interogări în cel mai defavorabil caz. Raționamentul este că, dacă un algoritm determinist interoghează $f$ pe $2^{n-1}$ sau mai puține șiruri diferite și obține de fiecare dată aceeași valoare a funcției, atunci ambele răspunsuri sunt încă posibile. Funcția ar putea fi constantă sau ar putea fi echilibrată, dar din ghinioane interogările returnează toate aceeași valoare a funcției.

A doua posibilitate poate părea puțin probabilă — dar pentru algoritmii deterministi nu există aleatoare sau incertitudine, astfel că vor eșua sistematic pe anumite funcții. Avem, prin urmare, un avantaj semnificativ al calculului cuantic față de cel clasic în această privință.

Există totuși o capcană, și anume că algoritmii clasici probabilistici pot rezolva problema Deutsch-Jozsa cu o probabilitate foarte mare folosind doar câteva interogări. În special, dacă pur și simplu alegem câteva șiruri diferite de lungime $n$ în mod aleatoriu și interogăm $f$ pe acele șiruri, este puțin probabil să obținem aceeași valoare a funcției pentru toate atunci când $f$ este echilibrată.

Mai precis, dacă alegem $k$ șiruri de intrare $x^1,\ldots,x^k \in \Sigma^n$ uniform aleatoriu, evaluăm $f(x^1),\ldots,f(x^k),$ și răspundem cu $0$ dacă valorile funcției sunt toate aceleași și cu $1$ dacă nu, atunci vom fi întotdeauna corecți când $f$ este constantă și greșim în cazul că $f$ este echilibrată cu probabilitatea de doar $2^{-k + 1}.$ Dacă luăm $k = 11,$ de exemplu, acest algoritm va răspunde corect cu o probabilitate mai mare de $99,9$%.

Din acest motiv, avem totuși un avantaj destul de modest al calculului cuantic față de cel clasic — dar este un avantaj cuantificabil care reprezintă o îmbunătățire față de algoritmul lui Deutsch.

Deutsch-Jozsa cu 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

Pentru a implementa algoritmul Deutsch-Jozsa în Qiskit, vom începe prin a defini o funcție dj_query care generează un Circuit cuantic ce implementează un gate de interogare, pentru o funcție selectată aleatoriu ce satisface promisiunea problemei Deutsch-Jozsa. Cu o probabilitate de 50%, funcția este constantă, iar cu o probabilitate de 50% funcția este echilibrată. Pentru fiecare dintre cele două posibilități, funcția este selectată uniform dintre funcțiile de acel tip. Argumentul reprezintă numărul de biți de intrare ai funcției.

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

Putem afișa implementarea ca Circuit cuantic a gate-ului de interogare folosind metoda draw, ca de obicei.

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

În continuare, definim o funcție care creează Circuit-ul Deutsch-Jozsa, primind ca argument o implementare ca Circuit cuantic a unui gate de interogare.

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

În final, este definită o funcție care rulează Circuit-ul Deutsch-Jozsa o singură dată.

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"

Putem testa implementarea noastră alegând o funcție aleatoriu, afișând implementarea ca Circuit cuantic a unui gate de interogare pentru această funcție și apoi rulând algoritmul Deutsch-Jozsa pe acea funcție.

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

'balanced'

Problema Bernstein-Vazirani

În continuare, vom discuta o problemă cunoscută sub numele de problema Bernstein-Vazirani. Se mai numește și problema eșantionării Fourier, deși există formulări mai generale ale acestei probleme care poartă același nume.

Mai întâi, să introducem câteva notații. Pentru oricare două șiruri binare $x = x_{n-1} \cdots x_0$ și $y = y_{n-1}\cdots y_0$ de lungime $n,$ definim

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

Vom numi această operație produsul scalar binar. O modalitate alternativă de a o defini este următoarea.

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

Observă că aceasta este o operație simetrică, ceea ce înseamnă că rezultatul nu se schimbă dacă schimbăm $x$ și $y,$ deci suntem liberi să facem asta ori de câte ori este convenabil. Uneori este util să ne gândim la produsul scalar binar $x \cdot y$ ca la paritatea biților lui $x$ de pe pozițiile unde șirul $y$ are un $1,$ sau echivalent, paritatea biților lui $y$ de pe pozițiile unde șirul $x$ are un $1.$

Cu această notație la îndemână, putem acum defini problema Bernstein-Vazirani.

Problema Bernstein-Vazirani

Intrare: o funcție $f:\{0,1\}^n\rightarrow\{0,1\}$
Promisiune: există un șir binar $s = s_{n-1} \cdots s_0$ pentru care $f(x) = s\cdot x$ pentru orice $x\in\Sigma^n$
Ieșire: șirul $s$

Nu avem nevoie de un nou algoritm cuantic pentru această problemă; algoritmul Deutsch-Jozsa o rezolvă. În interesul clarității, să ne referim la Circuit-ul cuantic de mai sus, care nu include pasul clasic de post-procesare al calculului OR, ca la Circuit-ul Deutsch-Jozsa.

Analiza algoritmului

Pentru a analiza modul în care circuitul Deutsch-Jozsa funcționează pentru o funcție care satisface promisiunea problemei Bernstein-Vazirani, vom începe cu o observație rapidă. Folosind produsul scalar binar, putem descrie alternativ acțiunea a $n$ porți Hadamard asupra stărilor bazei standard ale $n$ qubiți astfel:

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

Similar cu ceea ce am văzut când am analizat algoritmul lui Deutsch, aceasta se datorează faptului că valoarea $(-1)^k$ pentru orice întreg $k$ depinde doar de paritatea lui $k$.

Revenind la circuitul Deutsch–Jozsa, după ce primul strat de porți Hadamard este aplicat, starea celor $n+1$ qubiți este

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

Poarta de interogare este apoi aplicată, care (prin fenomenul de retroacțiune a fazei) transformă starea în

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

Folosind formula noastră pentru acțiunea unui strat de porți Hadamard, vedem că al doilea strat de porți Hadamard transformă această stare în

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

Acum putem face câteva simplificări în exponentul lui $-1$ din interiorul sumei. Ni se promite că $f(x) = s\cdot x$ pentru un șir $s = s_{n-1} \cdots s_0,$ deci putem exprima starea ca

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

Deoarece $s\cdot x$ și $x\cdot y$ sunt valori binare, putem înlocui adunarea cu SAU-exclusiv — din nou deoarece singurul lucru care contează pentru un întreg din exponentul lui $-1$ este dacă acesta este par sau impar. Folosind simetria produsului scalar binar, obținem această expresie pentru stare:

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

(Parantezele au fost adăugate pentru claritate, deși nu sunt cu adevărat necesare, deoarece prin convenție produsul scalar binar are prioritate mai mare decât SAU-exclusiv.)

În acest punct, vom folosi următoarea formulă.

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

Putem obține această formulă printr-o formulă similară pentru biți,

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

împreună cu o expansiune a produsului scalar binar și SAU-exclusiv pe biți:

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

Aceasta ne permite să exprimăm starea circuitului imediat înainte de măsurători astfel:

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

Ultimul pas este să folosim încă o formulă, care funcționează pentru orice șir binar $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}$$

Aici folosim o notație simplă pentru șiruri pe care o vom mai utiliza de câteva ori în lecție: $0^n$ este șirul de zerouri de lungime $n.$

Un mod simplu de a argumenta că această formulă funcționează este să considerăm cele două cazuri separat. Dacă $z = 0^n,$ atunci $z\cdot x = 0$ pentru orice șir $x\in\Sigma^n,$ deci valoarea fiecărui termen din sumă este $1,$ și obținem $1$ prin sumarea și împărțirea la $2^n.$ Pe de altă parte, dacă oricare dintre biții lui $z$ este egal cu $1,$ atunci produsul scalar binar $z\cdot x$ este egal cu $0$ pentru exact jumătate din posibilele alegeri pentru $x\in\Sigma^n$ și $1$ pentru cealaltă jumătate — deoarece valoarea produsului scalar binar $z\cdot x$ se inversează (de la $0$ la $1$ sau de la $1$ la $0$) dacă inversăm orice bit al lui $x$ într-o poziție unde $z$ are un $1.$

Dacă aplicăm acum această formulă pentru a simplifica starea circuitului înainte de măsurători, obținem

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

datorită faptului că $s\oplus y = 0^n$ dacă și numai dacă $y = s.$ Astfel, măsurătorile dezvăluie exact șirul $s$ pe care îl căutăm.

Dificultatea clasică

În timp ce circuitul Deutsch-Jozsa rezolvă problema Bernstein-Vazirani cu o singură interogare, orice algoritm de interogare clasic trebuie să facă cel puțin $n$ interogări pentru a rezolva această problemă.

Aceasta poate fi argumentată printr-un argument numit teoretic informațional, care este foarte simplu în acest caz. Fiecare interogare clasică dezvăluie un singur bit de informație despre soluție, iar există $n$ biți de informație care trebuie descoperiți — deci sunt necesare cel puțin $n$ interogări.

Este, de fapt, posibil să rezolvi problema Bernstein-Vazirani clasic interogând funcția pe fiecare dintre cele $n$ șiruri care au un singur $1,$ în fiecare poziție posibilă, și $0$ pentru toți ceilalți biți, ceea ce dezvăluie biții lui $s$ unul câte unul. Prin urmare, avantajul algoritmilor cuantici față de cei clasici pentru această problemă este de $1$ interogare față de $n$ interogări.

Bernstein-Vazirani cu Qiskit

Am implementat deja circuitul Deutsch-Jozsa mai sus, iar acum îl vom folosi pentru a rezolva problema Bernstein-Vazirani. Mai întâi vom defini o funcție care implementează o poartă de interogare pentru problema Bernstein-Vazirani pentru orice șir binar $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"))

Acum putem crea o funcție care rulează circuitul Deutsch-Jozsa pe funcție, folosind funcția compile_circuit definită anterior.

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'

Observație despre nomenclatură

În contextul problemei Bernstein-Vazirani, este frecvent ca algoritmul Deutsch-Jozsa să fie denumit „algoritmul Bernstein-Vazirani." Aceasta este ușor înșelător, deoarece algoritmul este algoritmul Deutsch-Jozsa, așa cum Bernstein și Vazirani au precizat clar în lucrarea lor.

Ceea ce au făcut Bernstein și Vazirani după ce au demonstrat că algoritmul Deutsch-Jozsa rezolvă problema Bernstein-Vazirani (așa cum este enunțată mai sus) a fost să definească o problemă mult mai complicată, cunoscută sub numele de problema recursivă a eșantionării Fourier. Aceasta este o problemă foarte artificială în care soluțiile la diferite instanțe ale problemei deblochează efectiv noi niveluri ale problemei organizate într-o structură arborescentă. Problema Bernstein-Vazirani este în esență doar cazul de bază al acestei probleme mai complicate.

Problema recursivă a eșantionării Fourier a fost primul exemplu cunoscut de problemă de interogare în care algoritmii cuantici au un avantaj super-polinomial față de algoritmii probabilistici, depășind astfel avantajul cuantic față de clasic oferit de algoritmul Deutsch-Jozsa. Intuitiv vorbind, versiunea recursivă a problemei amplifică avantajul de $1$ față de $n$ al algoritmilor cuantici la ceva mult mai mare.

Cel mai dificil aspect al analizei matematice care stabilește acest avantaj este demonstrarea că algoritmii de interogare clasici nu pot rezolva problema fără a face multe interogări. Aceasta este destul de tipic; pentru multe probleme poate fi foarte dificil să excluzi abordări clasice creative care le rezolvă eficient.

Problema lui Simon, și algoritmul pentru aceasta descris în secțiunea următoare, oferă un exemplu mult mai simplu de avantaj super-polinomial (și, de fapt, exponențial) al cuanticului față de clasic, și din acest motiv problema recursivă a eșantionării Fourier este mai rar discutată. Cu toate acestea, este o problemă computațională interesantă în sine.