BQP luokka

Algoritmien teoriassa monimutkaisuusluokka BQP ( englanniksi  bounded error quantum polynomial time ) on luokka ratkaistavuusongelmia , jotka voidaan ratkaista kvanttitietokoneella polynomiajassa (tehtävän työskentelyaika riippuu polynomiaalisesti tehtävän koosta. syöttötiedot), varmistaen samalla oikean vastauksen saamisen todennäköisyyden vähintään 2/3 jokaiselle syötteelle. Se on BPP-luokan kvanttianalogi .

Toisin sanoen ongelma kuuluu BQP-luokkaan, jos on olemassa kvanttialgoritmi (algoritmi kvanttitietokoneelle), joka ratkaisee tämän ongelman suurella todennäköisyydellä ja jonka taatusti suoritetaan korkeintaan polynomiajassa. Algoritmin mielivaltaisessa ajossa virheellisen vastauksen saamisen todennäköisyys ei saa olla suurempi kuin 1/3.

Tärkeitä edustajia

Kiinnostusta kvanttilaskentaa ja tietokoneita kohtaan aiheuttavat eräät ongelmat, jotka ovat BQP-luokassa, mutta joiden kuuluvuus P-luokkaan on tuntematon:

• Lukujen kertolasku  - Shorin algoritmi [1]
• Diskreetti logaritmi [1]
• Kvanttijärjestelmien simulointi useilla hiukkasilla ( Feynman-ongelma , joskus myös universaali kvanttisimulaattori)

Suhteet muihin luokkiin

Muistiinpanot

1. ↑ 1 2 arXiv: quant-ph/9508027v2 polynomi-aikaalgoritmit alkutekijöihin ja diskreeteille logaritmeille kvanttitietokoneessa , Peter W. Shor . Haettu 4. marraskuuta 2010. Arkistoitu alkuperäisestä 4. joulukuuta 2014. (määrätön)

Kirjallisuus

• "Kvanttilaskennan algoritmit: diskreetit logaritmit ja laskenta" PW Shor, AT&T Bell Labs. doi: 10.1109/SFCS.1994.365700

Linkit

• A. Kh. Shen, M. N. Vyaly, Luentokurssi "Classical and quantum computing". Luento 8: Kvanttilaskennan määritelmä. Esimerkkejä // Intuit.ru, 15.03.2007