Panimula

Ang mga quantum algorithm ay nag-aalok ng mapapantunayang kalamangan kumpara sa mga klasikal na algorithm sa query model ng computation. Pero paano naman ang mas karaniwang modelo ng computation, kung saan ang mga input ng problema ay ibinibigay nang malinaw imbes na sa anyo ng isang oracle o black box? Ito ay isang mas mahirap na tanong na sagutin, at para matugunan ito kailangan muna nating magtayo ng matibay na pundasyon para sa ating imbestigasyon. Iyon ang pangunahing layunin ng araling ito.

Magsisimula tayo sa pagtalakay ng computational cost, para sa parehong klasikal at quantum na mga computation, at kung paano ito masusukat. Ito ay isang pangkalahatang konsepto na maaaring ilapat sa malawak na hanay ng mga computational na problema — pero para mapanatiling simple ang mga bagay, pangunahin nating susuriin ito sa pamamagitan ng computational number theory, na tumutugon sa mga computational na gawain na malamang na pamilyar sa karamihan ng mga mambabasa, kabilang ang pangunahing aritmetika, pagkuha ng greatest common divisors, at integer factorization. Bagama't ang computational number theory ay isang makitid na larangan ng aplikasyon, ang mga problemang ito ay angkop para ilarawan ang mga pangunahing isyu (at nangyari ring lubhang may kaugnayan ang mga ito sa araling kasunod nito).

Ang ating pokus ay sa mga algorithm, kumpara sa patuloy na umuusbong na hardware na pinagpapatakbo ng mga ito. Kaugnay nito, mas interesado tayo sa kung paano nagsiskalang ang gastos ng pagpapatakbo ng isang algorithm habang lumalaki ang laki ng mga partikular na instance ng problema na pinatatakbo nito, kaysa kung ilang segundo, minuto, o oras ang kailangan ng isang partikular na computation. Ito ang ating pinagtutuunan ng pansin upang kilalanin ang katotohanan na ang mga algorithm ay may pundamental na kahalagahan, at natural na gagamitin ang mga ito laban sa mas malalaking instance ng problema gamit ang mas mabilis at mas maaasahang hardware habang umuunlad ang teknolohiya.

Sa wakas, lalapit tayo sa isang kritikal na mahalagang gawain, na ang pagpapatakbo ng mga klasikal na computation sa mga quantum na computer. Ang dahilan kung bakit mahalaga ang gawaing ito ay hindi dahil umaasa tayong palitan ang mga klasikal na computer ng mga quantum na computer — na tila labis na hindi malamang mangyari sa lalong madaling panahon, kung meron man — kundi dahil nagbubukas ito ng maraming kawili-wiling posibilidad para sa mga quantum algorithm. Partikular na, ang mga klasikal na computation na tumatakbo sa mga quantum na computer ay nagiging available bilang mga subroutine, na epektibong ginagamit ang dekada ng pananaliksik at pag-unlad sa mga klasikal na algorithm sa paghahanap ng mga quantum computational na kalamangan.

Video ng aralin

Sa sumusunod na video, ginagabayan ka ni John Watrous sa nilalaman ng araling ito tungkol sa mga pundasyon ng quantum algorithmic. Bilang kahalili, maaari mong buksan ang YouTube video para sa araling ito sa hiwalay na window. I-download ang mga slide para sa araling ito.