לדלג לתוכן

BQP

מתוך ויקיפדיה, האנציקלופדיה החופשית
הקשר המשוער בין מחלקות סיבוכיות שונות

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

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

בעיות ידועות

[עריכת קוד מקור | עריכה]

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

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

[עריכת קוד מקור | עריכה]

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

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

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

.

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

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