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.