Modelul de calcul bazat pe interogări

Când modelăm calculele în termeni matematici, ne gândim de obicei la tipul de proces reprezentat în figura de mai jos, în care informațiile sunt furnizate ca intrare, are loc un calcul și se produce o ieșire.

Deși este adevărat că calculatoarele pe care le folosim astăzi primesc și produc în mod continuu intrări și ieșiri, interacționând practic atât cu noi, cât și cu alte calculatoare într-un mod care nu este reflectat în figură, intenția nu este de a reprezenta funcționarea continuă a calculatoarelor. Mai degrabă, este de a crea o abstractizare simplă a calculului, concentrându-ne pe sarcini de calcul izolate. De exemplu, intrarea ar putea codifica un număr, un vector, o matrice, un graf, o descriere a unei molecule sau ceva mai complex, în timp ce ieșirea codifică o soluție la sarcina de calcul pe care o avem în minte.

Punctul-cheie este că intrarea este furnizată calculului, de obicei sub forma unui șir binar, fără ca vreo parte din ea să fie ascunsă.

Descrierea modelului

În modelul de calcul bazat pe interogări, întreaga intrare nu este furnizată calculului ca într-un model mai standard sugerat mai sus. Mai degrabă, intrarea este pusă la dispoziție sub forma unei funcții, pe care calculul o accesează prin interogări. Alternativ, putem considera calculele din modelul bazat pe interogări ca având acces aleatoriu la biți (sau segmente de biți) ai intrării.

Ne referim adesea la intrare ca fiind furnizată de un oracol sau o cutie neagră în contextul modelului bazat pe interogări. Ambii termeni sugerează că o descriere completă a intrării este ascunsă de la calcul, singura modalitate de a o accesa fiind să pui întrebări. Este ca și cum am consulta Oracolul din Delphi despre intrare: aceasta nu ne va spune tot ce știe, ci răspunde doar la întrebări specifice. Termenul cutie neagră are sens mai ales când ne gândim la intrare ca fiind reprezentată de o funcție; nu putem privi în interiorul funcției și înțelege cum funcționează, putem doar să o evaluăm pe argumente pe care le selectăm.

Vom lucra exclusiv cu șiruri binare în această lecție, spre deosebire de șiruri care conțin simboluri diferite, deci să scriem $\Sigma = \{0,1\}$ de acum înainte pentru a face referire la alfabetul binar pentru confort. Vom analiza diferite probleme de calcul, cu câteva exemple simple descrise în scurt timp, dar pentru toate acestea intrarea va fi reprezentată de o funcție de forma

$$f:\Sigma^n \rightarrow \Sigma^m$$

pentru doi întregi pozitivi $n$ și $m.$ Firește, am putea alege un alt nume în locul lui $f,$ dar vom păstra $f$ pe tot parcursul lecției.

A spune că un calcul face o interogare înseamnă că este selectat un șir $x \in \Sigma^n$, iar apoi șirul $f(x)\in\Sigma^m$ este pus la dispoziția calculului de către oracol. Modul precis în care funcționează acest lucru pentru algoritmii cuantici va fi discutat în scurt timp — trebuie să ne asigurăm că este posibil să facem asta cu o operație cuantică unitară care permite ca interogările să fie realizate în superpoziție — dar deocamdată putem gândi la asta în mod intuitiv, la un nivel înalt.

În final, modul în care vom măsura eficiența algoritmilor bazați pe interogări este simplu: vom număra numărul de interogări pe care le necesită. Aceasta este legată de timpul necesar pentru a efectua un calcul, dar nu este exact același lucru, deoarece ignorăm timpul pentru operațiile altele decât interogările și tratăm, de asemenea, interogările ca și cum fiecare ar avea un cost unitar. Putem lua în considerare operațiile pe lângă interogări dacă dorim (și uneori se face asta), dar limitarea atenției noastre doar la numărul de interogări ajută la menținerea lucrurilor simple.

Exemple de probleme bazate pe interogări

Iată câteva exemple simple de probleme bazate pe interogări.

• OR. Funcția de intrare are forma $f:\Sigma^n \rightarrow \Sigma$ (deci $m=1$ pentru această problemă). Sarcina este de a produce ieșirea $1$ dacă există un șir $x\in\Sigma^n$ pentru care $f(x) = 1,$ și de a produce ieșirea $0$ dacă nu există un astfel de șir. Dacă ne gândim la funcția $f$ ca reprezentând o secvență de $2^n$ biți la care avem acces aleatoriu, problema este de a calcula SAU (OR) al acestor biți.

• Paritatea. Funcția de intrare are din nou forma $f:\Sigma^n \rightarrow \Sigma.$ Sarcina este de a determina dacă numărul de șiruri $x\in\Sigma^n$ pentru care $f(x) = 1$ este par sau impar. Mai precis, ieșirea cerută este $0$ dacă mulțimea $\{x\in\Sigma^n : f(x) = 1\}$ are un număr par de elemente și $1$ dacă are un număr impar de elemente. Dacă ne gândim la funcția $f$ ca reprezentând o secvență de $2^n$ biți la care avem acces aleatoriu, problema este de a calcula paritatea (sau SAU-exclusiv) a acestor biți.

• Minimul. Funcția de intrare are forma $f:\Sigma^n \rightarrow \Sigma^m$ pentru orice alegeri de întregi pozitivi $n$ și $m.$ Ieșirea cerută este șirul $y \in \{f(x) : x\in\Sigma^n\}$ care apare primul în ordonarea lexicografică (adică, de dicționar) a lui $\Sigma^m.$ Dacă ne gândim la funcția $f$ ca reprezentând o secvență de $2^n$ întregi codificați ca șiruri de lungime $m$ în notație binară la care avem acces aleatoriu, problema este de a calcula minimul acestor întregi.

Luăm în considerare și probleme bazate pe interogări în care avem o promisiune asupra intrării. Ceea ce înseamnă asta este că ni se oferă un fel de garanție asupra intrării și nu suntem responsabili pentru ce se întâmplă când această garanție nu este îndeplinită. Un alt mod de a descrie acest tip de problemă este de a spune că unele funcții de intrare (cele pentru care promisiunea nu este satisfăcută) sunt considerate intrări de tip „nu contează". Nu se impun cerințe de niciun fel algoritmilor atunci când li se dau intrări de tip „nu contează".

Iată un exemplu de problemă cu o promisiune:

• Căutarea unică. Funcția de intrare are forma $f:\Sigma^n \rightarrow \Sigma,$ și ni se promite că există exact un șir $z\in\Sigma^n$ pentru care $f(z) = 1,$ cu $f(x) = 0$ pentru toate șirurile $x\neq z.$ Sarcina este de a găsi acest șir unic $z.$

Toate cele patru exemple descrise mai sus sunt naturale, în sensul că sunt ușor de descris și ne putem imagina o varietate de situații sau contexte în care ar putea apărea.

Prin contrast, unele probleme bazate pe interogări nu sunt deloc „naturale" în acest mod. De fapt, în studiul modelului bazat pe interogări, uneori concepem probleme foarte complexe și extrem de artificiale, unde este dificil să ne imaginăm că cineva ar vrea vreodată să le rezolve în practică. Asta nu înseamnă că problemele nu sunt interesante, totuși! Lucrurile care par artificiale sau nenaturale la prima vedere pot oferi indicii neașteptate sau inspira idei noi. Algoritmul cuantic al lui Shor pentru factorizare, care a fost inspirat de algoritmul lui Simon, este un exemplu excelent. Este, de asemenea, o parte importantă a studiului modelului bazat pe interogări să căutăm extreme, care pot lumina atât avantajele potențiale, cât și limitările calculului cuantic.

Porțile de interogare

Când descriem calcule cu circuite, interogările sunt realizate prin porți speciale numite porți de interogare.

Cel mai simplu mod de a defini porțile de interogare pentru circuitele booleene clasice este să le permitem pur și simplu să calculeze funcția de intrare $f$ în mod direct, așa cum sugerează figura de mai jos.

Când un circuit boolean este creat pentru o problemă bazată pe interogări, funcția de intrare $f$ este accesată prin aceste porți, iar numărul de interogări pe care le face circuitul este pur și simplu numărul de porți de interogare care apar în circuit. Firele de intrare ale circuitului boolean însuși sunt inițializate la valori fixe, care ar trebui considerate ca parte a algoritmului (spre deosebire de a fi intrări ale problemei).

De exemplu, iată un circuit boolean cu porți de interogare clasice care rezolvă problema parității descrisă mai sus pentru o funcție de forma $f:\Sigma\rightarrow\Sigma$:

Acest algoritm face două interogări deoarece există două porți de interogare. Modul în care funcționează este că funcția $f$ este interogată pe cele două intrări posibile, $0$ și $1,$ iar rezultatele sunt introduse într-un circuit boolean care calculează XOR. (Acest circuit particular a apărut ca exemplu de circuit boolean în lecția Circuite cuantice din cursul Bazele informației cuantice.)

Pentru circuitele cuantice, această definiție a porților de interogare nu funcționează, deoarece aceste porți vor fi ne-unitare pentru unele alegeri ale funcției $f.$ Deci, ce facem în schimb este să definim porți de interogare unitare care operează conform sugestiei din această figură pe stări din baza standard:

Aici, presupunem că $x\in\Sigma^n$ și $y\in\Sigma^m$ sunt șiruri arbitrare. Notația $y\oplus f(x)$ se referă la SAU-exclusiv pe biți al două șiruri, care au lungimea $m$ în acest caz. De exemplu, $001 \oplus 101 = 100.$

Vorbind intuitiv, ceea ce face poarta $U_f$ (pentru orice funcție $f$ aleasă) este să repete șirul de intrare superior $x$ și să aplice XOR al valorii funcției $f(x)$ pe șirul de intrare inferior $y,$ ceea ce este o operație unitară pentru orice alegere a funcției $f.$ De fapt, este o operație deterministă și este propria sa inversă. Aceasta implică faptul că, ca matrice, $U_f$ este întotdeauna o matrice de permutare, adică o matrice cu un singur $1$ pe fiecare linie și fiecare coloană, cu toate celelalte intrări fiind $0.$ Aplicarea unei matrice de permutare unui vector pur și simplu amestecă intrările vectorului (de unde termenul matrice de permutare) și, prin urmare, nu schimbă norma euclidiană a acelui vector — ceea ce relevă că matricele de permutare sunt întotdeauna unitare.

Trebuie subliniat că, atunci când analizăm algoritmii bazați pe interogări numărând pur și simplu numărul de interogări pe care le face un algoritm bazat pe interogări, ignorăm complet dificultatea construirii fizice a porților de interogare — atât pentru versiunile clasice, cât și pentru cele cuantice descrise mai sus. Vorbind intuitiv, construcția porților de interogare face parte din pregătirea intrării, nu din găsirea unei soluții.

Asta poate părea nerezonabil, dar trebuie să ținem cont că nu încercăm să descriem calculul practic sau să contabilizăm pe deplin resursele necesare. Mai degrabă, definim un model teoretic care ajută la iluminarea avantajelor potențiale ale calculului cuantic. Vom mai vorbi despre acest punct în lecția care urmează acesteia, când ne vom îndrepta atenția spre un model de calcul mai standard, în care intrările sunt furnizate explicit circuitelor ca șiruri binare.