BQP klasse

I teorien om algoritmer er kompleksitetsklassen BQP (fra engelsk  bounded error quantum polynomial time ) en klasse af løselighedsproblemer, der kan løses af en kvantecomputer i polynomiel tid (tiden til at arbejde på en opgave afhænger polynomielt af størrelsen på inputdataene), samtidig med at sandsynligheden for at opnå det rigtige svar sikres med mindst 2/3 for enhver input. Det er en kvanteanalog af BPP-klassen .

Med andre ord hører et problem til BQP-klassen, hvis der eksisterer en kvantealgoritme (algoritme til en kvantecomputer), der løser dette problem med høj sandsynlighed og med garanti ikke kører på mere end polynomisk tid. For en vilkårlig kørsel af algoritmen bør sandsynligheden for at få et forkert svar ikke være mere end 1/3.

Vigtige repræsentanter

Interessen for kvanteberegning og computere er forårsaget af nogle problemer, der er i BQP-klassen, men hvis tilhørsforhold til P-klassen er ukendt:

• Talfaktorisering  - Shor 's algoritme [1]
• Diskret logaritme [1]
• Simulering af kvantesystemer med flere partikler ( Feynman problem , nogle gange også en universel kvantesimulator)

Forhold til andre klasser

Noter

1. ↑ 1 2 arXiv: quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logaritms on a Quantum Computer , Peter W. Shor . Hentet 4. november 2010. Arkiveret fra originalen 4. december 2014. (ubestemt)

Litteratur

• "Algorithmer til kvanteberegning: diskrete logaritmer og factoring" PW Shor, AT&T Bell Labs. doi:10.1109/SFCS.1994.365700

Links

• A. Kh. Shen, M. N. Vyaly, Forelæsningsforløb "Klassisk og kvanteberegning". Forelæsning 8: Definition af kvanteberegning. Eksempler // Intuit.ru, 03/15/2007