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.

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

P\subseteq BPP \subseteq BQP \subseteq PSPACE.

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

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