algorytm kwantowy

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, Simona, Shora, Kitaeva i Bernsteina-Vaziraniego. * algorytm Deutscha-Jozsy (odróżniania funkcji zrównoważonej od stałej) 1992, * algorytm Shora (faktoryzacji, czyli rozkładu liczb na czynniki pierwsze) 1994, * (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.