Wprowadzenie

Algorytmy kwantowe oferują udowodnione przewagi nad algorytmami klasycznymi w modelu zapytań obliczeniowych. Ale co z bardziej standardowym modelem obliczeniowym, w którym dane wejściowe problemu są podawane wprost, a nie w postaci wyroczni lub czarnej skrzynki? Okazuje się, że jest to znacznie trudniejsze pytanie, i aby je rozwiązać, musimy najpierw zbudować solidne podstawy dla naszych badań. Temu właśnie służy ta lekcja.

Zaczniemy od omówienia kosztu obliczeniowego, zarówno dla obliczeń klasycznych, jak i kwantowych, oraz sposobu jego mierzenia. Jest to ogólna koncepcja, którą można zastosować do szerokiej gamy problemów obliczeniowych — ale dla uproszczenia będziemy ją analizować głównie przez pryzmat obliczeniowej teorii liczb, która zajmuje się zadaniami obliczeniowymi prawdopodobnie znajomymi większości czytelników, w tym podstawową arytmetyką, obliczaniem największych wspólnych dzielników i faktoryzacją liczb całkowitych. Choć obliczeniowa teoria liczb jest wąską dziedziną zastosowań, problemy te dobrze ilustrują podstawowe kwestie (a przy okazji są bardzo istotne dla lekcji następującej po tej).

Skupiamy się na algorytmach, a nie na stale ulepszającym się sprzęcie, na którym są uruchamiane. W związku z tym bardziej interesuje nas to, jak koszt uruchomienia algorytmu skaluje się w miarę wzrostu rozmiarów konkretnych instancji problemu, niż ile sekund, minut czy godzin wymaga dane obliczenie. Skupiamy się na tym aspekcie kosztu obliczeniowego, uznając fundamentalne znaczenie algorytmów, które w naturalny sposób będą stosowane wobec coraz większych instancji problemów na szybszym i bardziej niezawodnym sprzęcie w miarę postępu technologicznego.

Na koniec zajmiemy się krytycznie ważnym zadaniem, jakim jest uruchamianie klasycznych obliczeń na komputerach kwantowych. Powód, dla którego to zadanie jest ważne, nie polega na tym, że liczymy na zastąpienie komputerów klasycznych kwantowymi — co wydaje się niezwykle mało prawdopodobne w najbliższym czasie, jeśli w ogóle — lecz dlatego, że otwiera wiele interesujących możliwości dla algorytmów kwantowych. Konkretnie, klasyczne obliczenia uruchamiane na komputerach kwantowych stają się dostępne jako podprogramy, efektywnie wykorzystując dziesięciolecia badań i rozwoju klasycznych algorytmów w dążeniu do kwantowych przewag obliczeniowych.

Wideo do lekcji

W poniższym filmie John Watrous przeprowadzi Cię przez treść tej lekcji dotyczącej kwantowych podstaw algorytmicznych. Możesz też otworzyć film na YouTube w osobnym oknie. Pobierz slajdy do tej lekcji.