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^[1], Shora, Kitaeva^[2] i Bernsteina-Vaziraniego^[3].

algorytm Deutscha-Jozsy (odróżniania funkcji zrównoważonej od stałej) 1992^[4],
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^[5].

Zobacz też

Przypisy

↑ On the Power of Quantum Computation by Daniel R. Simon (1994)
↑ Quantum computations: Algorithms and error correction by A Kitaev (1997)
↑ Quantum Complexity Theory by Ethan Bernstein, Umesh Vazirani (1997)
↑ David Deutsch, Richard Jozsa (1992). "Rapid solutions of problems by quantum computation". Proceedings of the Royal Society of London A 439: 553
↑ AbelA. Molina AbelA., JohnJ. Watrous JohnJ., Revisiting the simulation of quantum Turing machines by quantum circuits, „Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences”, 475 (2226), 2019, s. 20180767, DOI: 10.1098/rspa.2018.0767, ISSN 1364-5021 [dostęp 2020-05-27] .

Bibliografia

MikaM. Hirvensalo MikaM., Algorytmy kwantowe, PawełP. Zabierowski (tłum.), Warszawa: WSiP, 2004, ISBN 83-02-09155-3, OCLC 749548876 .
Krzysztof Giaro, Marcin Kamiński, Wprowadzenie do algorytmów kwantowych, Akademicka Oficyna Wydawnicza EXIT, Warszawa 2003, ISBN 83-87674-57-5

[1] On the Power of Quantum Computation by Daniel R. Simon (1994)

[2] Quantum computations: Algorithms and error correction by A Kitaev (1997)

[3] Quantum Complexity Theory by Ethan Bernstein, Umesh Vazirani (1997)

[4] David Deutsch, Richard Jozsa (1992). "Rapid solutions of problems by quantum computation". Proceedings of the Royal Society of London A 439: 553

[5] AbelA. Molina AbelA., JohnJ. Watrous JohnJ., Revisiting the simulation of quantum Turing machines by quantum circuits, „Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences”, 475 (2226), 2019, s. 20180767, DOI: 10.1098/rspa.2018.0767, ISSN 1364-5021 [dostęp 2020-05-27] .

[1]

[2]

[3]

[4]

[5]