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
- ↑ Abel Molina, John Watrous, 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
- Mika Hirvensalo, Algorytmy kwantowe, Paweł 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.