Kokie įrodymai rodo, kad BQP gali būti galingesnis už klasikinį daugianario laiką, ir kokie yra problemų, kurios, kaip manoma, yra BQP, bet ne BPP, pavyzdžiai?

Vienas iš pagrindinių kvantinio sudėtingumo teorijos klausimų yra tai, ar kvantiniai kompiuteriai gali efektyviau išspręsti tam tikras problemas nei klasikiniai kompiuteriai. Problemų, kurias gali efektyviai išspręsti kvantinis kompiuteris, klasė yra žinoma kaip BQP (ribotos klaidos kvantinis polinominis laikas), kuri yra analogiška problemų klasei, kurią galima efektyviai išspręsti.

Tagged pagal: , , , , , , ,

Kas yra sudėtingumo klasė BQP ir kaip ji susijusi su klasikinėmis sudėtingumo klasėmis P ir BPP?

Sudėtingumo klasė BQP, kuri reiškia „ribotos klaidos kvantinį polinominį laiką“, yra pagrindinė kvantinio sudėtingumo teorijos sąvoka. Tai yra sprendimų problemų, kurias gali išspręsti kvantinis kompiuteris daugianario laiku su ribota klaidos tikimybe, rinkinys. Norint suprasti BQP, pirmiausia svarbu suvokti klasikinį sudėtingumą

Tagged pagal: , , , , ,