BQP

בתורת הסיבוכיות, המחלקה BQP ‏ (Bounded error, Quantum, Polynomial time) היא מחלקת סיבוכיות המכילה את כלל הבעיות הניתנות להכרעה על ידי מכונת טיורינג קוונטית, בעלת זמן ריצה פולינומי אשר צודקת בהסתברות "טובה", כלומר ההסתברות שהמכונה תחזיר תשובה נכונה (עבור הרצה נתונה) היא גבוהה מ-2/3, ובאופן דומה, הסתברות הכישלון חסומה (מלעיל) ב–1/3.

כבכל המחלקות בהם הסתברות הכישלון חסומה, ניתן להפעיל את האלגוריתם הקוונטי שוב ושוב, על מנת להקטין את הסתברות השגיאה באופן מעריכי. כמו כן, כלל המחלקות ${\displaystyle \left.BQP_{p}\right.}$ בהן הסתברות הכישלון חסומה על ידי ${\displaystyle p\in [0,0.5)}$ שקולות זו לזו.