Ang query model ng computation

Kapag nag-momodel tayo ng mga computation sa mathematical na paraan, karaniwang iniisip natin ang uri ng proseso na ipinapakita sa sumusunod na figure, kung saan ang impormasyon ay ibinibigay bilang input, nagaganap ang isang computation, at nalilikha ang output.

Bagama't totoo na ang mga computer na ginagamit natin ngayon ay patuloy na tumatanggap ng input at gumagawa ng output — na mahalagang nakikipag-ugnayan sa atin at sa ibang mga computer sa paraang hindi narerepresenta ng figure — ang layunin ay hindi ilarawan ang patuloy na operasyon ng mga computer. Sa halip, ito ay lumikha ng isang simpleng abstraction ng computation, na nakatuon sa mga naka-isolate na computational task. Halimbawa, ang input ay maaaring mag-encode ng isang numero, vector, matrix, graph, paglalarawan ng isang molekula, o isang bagay na mas kumplikado, habang ang output ay nag-e-encode ng solusyon sa computational task na iniisip natin.

Ang pangunahing punto ay ang input ay ibinibigay sa computation, karaniwang sa anyo ng isang binary string, nang walang anumang bahagi nito na nakatago.

Paglalarawan ng modelo

Sa query model ng computation, ang buong input ay hindi ibinibigay sa computation tulad ng sa mas karaniwang modelo na iminungkahi sa itaas. Sa halip, ang input ay ginagawang available sa anyo ng isang function, na ina-access ng computation sa pamamagitan ng paggawa ng mga query. Bilang alternatibo, maaari nating tingnan ang mga computation sa query model bilang may random access sa mga bit (o mga segment ng bit) ng input.

Madalas nating tinutukoy ang input bilang ibinibigay ng isang oracle o black box sa konteksto ng query model. Ang parehong termino ay nagmumungkahi na ang kumpletong paglalarawan ng input ay nakatago mula sa computation, at ang tanging paraan upang ma-access ito ay ang magtanong. Para bang kumukonsulta tayo sa Oracle sa Delphi tungkol sa input: hindi niya sasabihin sa atin ang lahat ng alam niya, sumasagot lang siya sa mga tiyak na tanong. Ang terminong black box ay may katuturan lalo na kapag iniisip natin ang input bilang kinakatawan ng isang function; hindi natin maaaring tingnan ang loob ng function at maunawaan kung paano ito gumagana, maaari lang nating e-evaluate ito sa mga argumento na aming pinipili.

Gagamit tayo ng eksklusibong mga binary string sa araling ito, sa halip na mga string na naglalaman ng iba't ibang simbolo, kaya isulatin natin ang $\Sigma = \{0,1\}$ mula rito upang tumukoy sa binary alphabet para sa kaginhawaan. Mag-iisip tayo ng iba't ibang computational problem, na may ilang simpleng halimbawa na inilalarawan sa lalong madaling panahon, ngunit para sa lahat ng ito ang input ay kinakatawan ng isang function na may sumusunod na anyo

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

para sa dalawang positibong integer na $n$ at $m.$ Natural, maaari tayong pumili ng ibang pangalan sa halip na $f,$ ngunit mananatili tayo sa $f$ sa buong aralin.

Ang sabihing ang isang computation ay gumagawa ng query ay nangangahulugang may napiling string na $x \in \Sigma^n,$ at pagkatapos ay ginagawang available ang string na $f(x)\in\Sigma^m$ sa computation ng oracle. Ang tiyak na paraan na ito ay gumagana para sa mga quantum algorithm ay tatalakayin sa lalong madaling panahon — kailangan nating tiyakin na posible itong gawin gamit ang isang unitary quantum operation na nagpapahintulot na gumawa ng mga query sa superposition — ngunit sa ngayon maaari nating isipin ito sa mataas na antas nang intuitive.

Sa wakas, ang paraan na susukat tayo ng kahusayan ng mga query algorithm ay simple: bibilangin natin ang bilang ng mga query na kinakailangan nila. Ito ay may kaugnayan sa oras na kinakailangan upang magsagawa ng isang computation, ngunit hindi ito eksaktong katulad dahil binabalewala natin ang oras para sa mga operasyon maliban sa mga query, at tinatrato rin natin ang mga query na parang bawat isa ay may unit cost. Maaari nating isaalang-alang ang mga operasyon bukod sa mga query kung gusto natin (at minsan ginagawa ito), ngunit ang pagtutok lamang sa bilang ng mga query ay nakakatulong na panatilihing simple ang mga bagay.

Mga halimbawa ng query problem

Narito ang ilang simpleng halimbawa ng mga query problem.

• OR. Ang input function ay may anyo na $f:\Sigma^n \rightarrow \Sigma$ (kaya $m=1$ para sa problemang ito). Ang gawain ay mag-output ng $1$ kung mayroong string na $x\in\Sigma^n$ kung saan $f(x) = 1,$ at mag-output ng $0$ kung walang ganitong string. Kung iniisip natin ang function na $f$ bilang kumakatawan sa isang sequence ng $2^n$ na bit na may random access tayo, ang problema ay ang i-compute ang OR ng mga bit na ito.

• Parity. Ang input function ay muli may anyo na $f:\Sigma^n \rightarrow \Sigma.$ Ang gawain ay tukuyin kung ang bilang ng mga string na $x\in\Sigma^n$ kung saan $f(x) = 1$ ay even o odd. Upang maging tiyak, ang kinakailangang output ay $0$ kung ang set na $\{x\in\Sigma^n : f(x) = 1\}$ ay may even na bilang ng mga elemento at $1$ kung ito ay may odd na bilang ng mga elemento. Kung iniisip natin ang function na $f$ bilang kumakatawan sa isang sequence ng $2^n$ na bit na may random access tayo, ang problema ay ang i-compute ang parity (o exclusive-OR) ng mga bit na ito.

• Minimum. Ang input function ay may anyo na $f:\Sigma^n \rightarrow \Sigma^m$ para sa anumang pagpipilian ng mga positibong integer na $n$ at $m.$ Ang kinakailangang output ay ang string na $y \in \{f(x) : x\in\Sigma^n\}$ na unang lumabas sa lexicographic (iyon ay, dictionary) na pagkakasunud-sunod ng $\Sigma^m.$ Kung iniisip natin ang function na $f$ bilang kumakatawan sa isang sequence ng $2^n$ na integer na naka-encode bilang mga string ng haba na $m$ sa binary notation na may random access tayo, ang problema ay ang i-compute ang minimum ng mga integer na ito.

Isinasaalang-alang din natin ang mga query problem kung saan mayroon tayong promise sa input. Ang ibig sabihin nito ay binibigyan tayo ng ilang uri ng garantiya sa input, at hindi tayo responsable para sa mangyayari kapag ang garantiyang ito ay hindi natutupad. Isa pang paraan upang ilarawan ang ganitong uri ng problema ay sabihin na ang ilang input function (ang mga kung saan hindi nasatisfied ang promise) ay itinuturing na "don't care" na mga input. Walang anumang mga kinakailangan ang inilalagay sa mga algorithm kapag binibigyan sila ng "don't care" na mga input.

Narito ang isang halimbawa ng isang problema na may promise:

• Unique search. Ang input function ay may anyo na $f:\Sigma^n \rightarrow \Sigma,$ at ipinangako na mayroon lamang isang string na $z\in\Sigma^n$ kung saan $f(z) = 1,$ na may $f(x) = 0$ para sa lahat ng string na $x\neq z.$ Ang gawain ay hanapin ang natatanging string na $z.$

Ang lahat ng apat na halimbawang nabanggit ay natural, sa kahulugang madali itong ilarawan at maaari nating isipin ang iba't ibang sitwasyon o konteksto kung saan maaari itong lumabas.

Sa kabaligtaran, ang ilang mga query problem ay hindi "natural" tulad nito. Sa katunayan, sa pag-aaral ng query model, minsan ay lumilikha tayo ng napakakomplikado at lubhang gawa-gawa na mga problema kung saan mahirap isipin na may sinuman ay talagang gustong lutasin ang mga ito sa practice. Hindi ito nangangahulugang ang mga problema ay hindi kawili-wili, bagaman! Ang mga bagay na maaaring mukhang gawa-gawa o hindi natural sa simula ay maaaring magbigay ng mga hindi inaasahang pahiwatig o magbigay inspirasyon ng mga bagong ideya. Ang quantum algorithm ni Shor para sa factoring, na inspirado ng algorithm ni Simon, ay isang magandang halimbawa. Ito rin ay isang mahalagang bahagi ng pag-aaral ng query model na maghanap ng mga sukdulan, na maaaring magbigay-liwanag sa parehong mga potensyal na kalamangan at limitasyon ng quantum computing.

Mga query gate

Kapag naglalarawan tayo ng mga computation gamit ang mga circuit, ginagawa ang mga query sa pamamagitan ng mga espesyal na gate na tinatawag na query gate.

Ang pinakasimpleng paraan upang tukuyin ang mga query gate para sa mga classical Boolean circuit ay ang payagan silang direktang i-compute ang input function na $f,$ tulad ng iminumungkahi ng sumusunod na figure.

Kapag ang isang Boolean circuit ay nilikha para sa isang query problem, ang input function na $f$ ay ina-access sa pamamagitan ng mga gate na ito, at ang bilang ng mga query na ginagawa ng circuit ay simpleng bilang ng mga query gate na lumalabas sa circuit. Ang mga input wire ng Boolean circuit mismo ay ini-initialize sa mga fixed na halaga, na dapat ituring bilang bahagi ng algorithm (kumpara sa pagiging mga input sa problema).

Halimbawa, narito ang isang Boolean circuit na may mga classical query gate na naglulutas ng parity problem na inilarawan sa itaas para sa isang function ng anyo na $f:\Sigma\rightarrow\Sigma$:

Ang algorithm na ito ay gumagawa ng dalawang query dahil may dalawang query gate. Ang paraan ng pagtatrabaho nito ay ang function na $f$ ay ique-query sa dalawang posibleng input, $0$ at $1,$ at ang mga resulta ay ipinasok sa isang Boolean circuit na nag-co-compute ng XOR. (Ang partikular na circuit na ito ay lumabas bilang isang halimbawa ng Boolean circuit sa aralin na Quantum circuits ng kursong Basics of quantum information.)

Para sa mga quantum circuit, ang kahulugang ito ng mga query gate ay hindi gumagana, dahil ang mga gate na ito ay magiging non-unitary para sa ilang pagpipilian ng function na $f.$ Kaya, ang gagawin natin sa halip ay tukuyin ang mga unitary query gate na gumaganap tulad ng iminumungkahi ng figure na ito sa mga standard basis state:

Dito, ang ating pagpapalagay ay ang $x\in\Sigma^n$ at $y\in\Sigma^m$ ay mga arbitrary na string. Ang notasyong $y\oplus f(x)$ ay tumutukoy sa bitwise exclusive-OR ng dalawang string, na may haba na $m$ sa kasong ito. Halimbawa, $001 \oplus 101 = 100.$

Sa intuitive na pagsasalita, ang ginagawa ng gate na $U_f$ (para sa anumang piniling function na $f$) ay ang i-echo ang itaas na input string na $x$ at i-XOR ang function value na $f(x)$ sa ibabang input string na $y,$ na isang unitary operation para sa bawat pagpipilian ng function na $f.$ Sa katunayan, ito ay isang deterministic na operasyon, at ito ang sarili nitong inverse. Nangangahulugan ito na, bilang isang matrix, ang $U_f$ ay palaging isang permutation matrix, ibig sabihin isang matrix na may iisang $1$ sa bawat row at bawat column, na ang lahat ng iba pang entry ay $0.$ Ang pag-apply ng permutation matrix sa isang vector ay simpleng nag-s-shuffle ng mga entry ng vector (kaya ang terminong permutation matrix), at samakatuwid ay hindi binabago ang Euclidean norm ng vector na iyon — nagpapakita na ang mga permutation matrix ay palaging unitary.

Dapat i-highlight na, kapag sinusuri natin ang mga query algorithm sa pamamagitan lamang ng pagbibilang ng bilang ng mga query na ginagawa ng isang query algorithm, ganap nating binabalewala ang kahirapan ng pisikal na pagtatayo ng mga query gate — para sa parehong classical at quantum na mga bersyon na nabanggit kanina. Sa intuitive na pagsasalita, ang konstruksyon ng mga query gate ay bahagi ng paghahanda ng input, hindi bahagi ng paghahanap ng solusyon.

Maaaring mukhang hindi makatuwiran iyon, ngunit kailangan nating tandaan na hindi tayo nagtatangkang ilarawan ang praktikal na computing o ganap na i-account ang mga kinakailangang resources. Sa halip, nagtatukoy tayo ng isang theoretical model na tumutulong na magbigay-liwanag sa mga potensyal na kalamangan ng quantum computing. Magkakaroon tayo ng mas maraming sasabihin tungkol sa puntong ito sa aralin kasunod nito kapag ibinalik natin ang ating atensyon sa isang mas karaniwang modelo ng computation kung saan ang mga input ay ibinibigay nang tahasan sa mga circuit bilang mga binary string.