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.