Panimula

Ang Grover's algorithm ay isang quantum algorithm para sa tinatawag na mga problemang unstructured search na nag-aalok ng quadratic na pagpapabuti kumpara sa mga klasikal na algorithm. Ang ibig sabihin nito ay ang Grover's algorithm ay nangangailangan ng bilang ng mga operasyon na katumbas ng square root ng bilang ng mga operasyong kailangan para malutas ang unstructured search sa klasikal na paraan — na katumbas ng pagsasabing ang mga klasikal na algorithm para sa unstructured search ay dapat magkaroon ng halaga na hindi bababa sa antas ng square ng halaga ng Grover's algorithm.

Ang Grover's algorithm, kasama ang mga extension nito at ang pinagbabatayang pamamaraan, ay malawak na magagamit, na nagbibigay ng quadratic na kalamangan para sa maraming kawili-wiling computational na gawain na maaaring hindi mukhang mga unstructured search problem sa simula.

Bagaman ang malawak na kakayahang magamit ng pamamaraan ng paghahanap ng Grover ay kapansin-pansin, dapat na kilalanin dito sa simula ng aralin na ang quadratic na kalamangan na inaalok nito ay mukhang hindi malamang na makapagbibigay ng praktikal na kalamangan ng quantum sa klasikal na computing sa malapit na hinaharap. Ang klasikal na computing hardware ay mas advanced kaysa sa quantum computing hardware — at ang quadratic na kalamangan ng quantum sa klasikal na inaalok ng Grover's algorithm ay tiyak na mawawala dahil sa nakamamanghang bilis ng mga modernong klasikal na computer para sa anumang unstructured search problem na maaaring makatwirang patakbuhin sa malapit na hinaharap.

Habang sumusulong ang teknolohiya ng quantum computing, gayunpaman, ang Grover's algorithm ay maaaring magkaroon ng potensyal. Sa katunayan, ang ilan sa pinakamahalaga at pinakamakapangyarihang klasikal na algorithm na natuklasan, kabilang ang fast Fourier transform at mabilis na pag-sort (halimbawa, quicksort at merge sort), ay nag-aalok ng bahagyang mas mababa sa quadratic na kalamangan kumpara sa mga simpleng paraan sa mga problemang niresolba nila. Ang pangunahing pagkakaiba dito, siyempre, ay ang isang ganap na bagong teknolohiya (ibig sabihin, quantum computing) ang kailangan para patakbuhin ang Grover's algorithm. Bagaman ang teknolohiyang ito ay bago pa rin kumpara sa klasikal na computing, hindi tayo dapat magmadaling maliitin ang potensyal ng mga pag-unlad sa teknolohiya na maaaring payagan ang isang quadratic na kalamangan ng quantum sa klasikal na computing na makapagbigay ng mga kongkretong praktikal na benepisyo balang araw.

Video ng aralin

Sa sumusunod na video, inagapayan ni John Watrous ang nilalaman ng araling ito tungkol sa Grover's algorithm. 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.