Algorytm kwantowy – rodzaj algorytmu przeznaczonego do działania na maszynie kwantowej (komputerze kwantowym). Dotychczas powstało kilkanaście algorytmów wykorzystujących możliwości oferowane przez maszyny kwantowe. Należą do nich algorytmy Grovera, Deutscha, SimonaOn the Power of Quantum Computation by Daniel R. Simon (1994), Shora, KitaevaQuantum computations: Algorithms and error correction by A Kitaev (1997) i Bernsteina-VaziraniegoQuantum Complexity Theory by Ethan Bernstein, Umesh Vazirani (1997).
algorytm Deutscha-Jozsy (odróżniania funkcji zrównoważonej od stałej) 1992David Deutsch, Richard Jozsa (1992). "Rapid solutions of problems by quantum computation". Proceedings of the Royal Society of London A 439: 553, algorytm Shora (faktoryzacji, czyli rozkładu liczb na czynniki pierwsze) 1994, algorytm Kitajewa (szybkiej kwantowej transformacji Fouriera) 1995, algorytm Grovera (przeszukiwania bazy danych) 1995, algorytm Simona (znajdowania maski XOR funkcji 2-na-1) 1997.
Algorytmy kwantowe to algorytmy probabilistyczne, czyli oparte na rozkładzie prawdopodobieństwa i ewolucji układu kwantowego w czasie.
Dowolny algorytm kwantowy może być formalnie opisany jako konkretna, kwantowa maszyna Turinga.
Zobacz też informatyka kwantowa komputer kwantowy kryptologia kwantowa
Przypisy
Bibliografia
Krzysztof Giaro, Marcin Kamiński, Wprowadzenie do algorytmów kwantowych, Akademicka Oficyna Wydawnicza EXIT, Warszawa 2003,
Linki zewnętrzne