Kvanttilaskennan monimutkaisuusteoria tai kvanttikompleksisuusteoria on osa teoreettisen tietojenkäsittelytieteen laskennallista kompleksisuusteoriaa. Se tutkii kompleksisuusluokkia, jotka on määritelty kvanttitietokoneiden ja kvantti-informaation avulla, jotka ovat kvanttimekaniikkaan perustuvia laskentamalleja. Se käsittelee ongelmien vaikeutta suhteessa näihin kompleksisuusluokkiin sekä kvanttikompleksisuusluokkien ja klassisten eli (ei-kvantti) kompleksisuusluokkien välistä suhdetta.[1][2][3][4]
- ↑ Watrous, John: ”Quantum Computational Complexity”, Encyclopedia of Complexity and Systems Science. (Meyers, R. (kirjan toimittaja)) New York, (NY): Springer, 2013. doi:10.1007/978-3-642-27737-5_428-3 ISBN 978-3-642-27737-5 Artikkelin verkkoversio (viitattu 4.12.2023). (englanniksi)
- ↑ Watrous, John: Quantum Computational Complexity. arXiv: Quantum Physics (quant-ph), 2008. arXiv:0804.3401v1 doi:10.48550/arXiv.0804.3401 Artikkelin verkkoversio. (PDF) Viitattu 4.12.2023. (englanniksi)
- ↑ Aaronson, Scott: The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes. arXiv: Quantum Physics (quant-ph), 2016. doi:10.48550/arXiv.1607.05256 Artikkelin verkkoversio. (PDF) Viitattu 4.12.2023. (englanniksi)
- ↑ Kaznatcheev, Artem: Quantum query complexity Theoretical Computer Science. 21.7.2011. Stack Exchange, (yhteisöblogi). Arkistoitu 8.9.204. Viitattu 4.12.2023. (englanniksi)