Wprowadzenie do algorytmów kwantowych

Pomysł budowy komputera, który działałby zgodnie z prawami fizyki kwantowej i w sposób istotny wykorzystywał te prawa, ma niemalże dwadzieścia lat. Przez ten czas prowadzone były zarówno badania teoretyczne, jak i prace nad konstrukcją komputera kwantowego. Jakkolwiek postęp w dziedzinie technologii jest znaczny, to nie dysponujemy jeszcze maszynami liczącymi, których działanie trzeba wyjaśniać na poziomie fizyki kwantowej. Podejmowane dotychczas próby konstrukcji należy nazwać eksperymentami.

W dziedzinie badań teoretycznych osiągnięto szereg ważnych rezultatów. Opracowano model obliczeń kwantowych, podano pierwsze algorytmy i stworzono teorię ich złożoności obliczeniowej. Z tych pierwszych studiów wynika, że komputer kwantowy może rozwiązywać pewne zadania szybciej niż maszyny klasyczne. Brak jednak dokładnych wyników, a siłą napędową dalszych badań jest nadzieja, że problemy, których nie można efektywnie rozwiązać w modelu klasycznym, będą miały takie rozwiązanie w modelu kwantowym.

Celem tej pracy jest prezentacja kwantowego modelu obliczeń. Szczególny nacisk położono na zagadnienia matematyczne i informatyczne. Zadbano o wyjaśnienie podstaw teoretycznych, podanie pełnych dowodów poprawności algorytmów kwantowych oraz szacowanie złożoności obliczeniowej.