BQP

הקשר המשוער בין מחלקות סיבוכיות שונות

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

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

בעיות ידועות

המחלקה BQP מכילה את בעיית הפירוק של מספר שלם לגורמים ראשוניים, וכן את בעיית הלוגריתם הדיסקרטי.

קשרים עם מחלקות סיבוכיות אחרות

המקבילה הקלאסית למחלקה זו היא המחלקה BPP, בה מכונת הטיורינג היא אקראית, אך לא קוונטית. מכיוון שמכונה קלאסית היא מקרה פרטי של מכונה קוונטית (בה לא מנוצל ה"כוח הקוונטי"), המחלקה BQP מכילה את המחלקה BPP, כלומר $BPP\subseteq BQP$. מכיוון שהמחלקה P מוכלת בBPP, מתקבל כי

$P\subseteq BPP\subseteq BQP$.

בעיות פתוחות במדעי המחשב: מהו הקשר בין BQP למחלקה NP? (בעיות פתוחות נוספות במדעי המחשב)

המחלקה PSPACE מכילה את המחלקה BQP. אם נבטא את המכונה הקוונטית כרצף של שערים קוונטים, ניתן יהיה להמיר כל שער במטריצה יוניטרית. התוצאה הסופית של רצף השערים נתון כמכפלה של המטריצות המתאימות. על ידי ביצוע פעולת הכפלת המטריצות (בצורה יעילה מבחינת הזיכרון) ניתן לבצע את החישוב בזיכרון פולינומי שגודלו כגודל המטריצות. לפיכך מתקבל כי

$P\subseteq BPP\subseteq BQP\subseteq PSPACE$.

מכיוון שהקשר בין P ובין PSPACE הוא שאלה פתוחה, כך גם היחס המדויק בין המחלקות לעיל.

הקשר בין BQP לבין NP אינו ידוע גם כן.