פורטל:מחשבים/הידעת?/31

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

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