משפט גוטסמן-ניל

משפט גוטסמן-ניל הוא משפט יסודי במחשוב קוונטי הקובע כי מעגל קוונטי הממומש על ידי שערי קליפורד יכול להיות מסומלץ בזמן פולינומי על מחשב קלאסי, וכך אין יתרון חישוב למעגל קוונטי שכזה. המשפט פורסם לראשונה במאמר מאת דניאל גוטסמן (אנ'), פיזיקאי וחוקר מחשוב קוונטי, בסוף שנות ה־90 של המאה ה־20 ונושא גם את שמו של עמנואל ניל (Emanuel Knill) שתרם ליישום המשפט.

חבורת קליפורד

חבורת קליפורד (אנ') היא קבוצת אופרטורים קוונטיים המפורסמת בעיקר בתחום תיקון השגיאות הקוונטי. החבורה כוללת את קבוצת המכפלות של חבורת פאולי כך שהקבוצה ממופה אל תוך עצמה. כלומר, אם עבור שער ${\displaystyle L}$ מסוים קיימים שערי פאולי ${\displaystyle P_{1},P_{2}}$ כך ש ${\displaystyle LP_{1}L^{\dagger }=P_{2}}$ אזי ${\displaystyle L}$ שייך לחבורת קליפורד.

שערי פאולי על קיוביט בודד מוגדרים כך:

${\displaystyle \sigma _{0}=I={\begin{bmatrix}1&0\\0&1\end{bmatrix}},\quad \sigma _{1}=X={\begin{bmatrix}0&1\\1&0\end{bmatrix}},\quad \sigma _{2}=Y={\begin{bmatrix}0&-i\\i&0\end{bmatrix}},{\text{ and }}\sigma _{3}=Z={\begin{bmatrix}1&0\\0&-1\end{bmatrix}}}$

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

${\displaystyle \mathbf {C} _{n}=\{V\in U_{2^{n}}\mid V\mathbf {P} _{n}V^{\dagger }=\mathbf {P} _{n}\}.}$. גודל חבורת קליפורד המוגדרת על קיוביט n-ממדי הוא ${\displaystyle 2^{n^{2}+2n+3}\prod _{j=1}^{n}(4^{j}-1)}$.

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

שערי קליפורד

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

1. שער אדמר, המקיים ${\displaystyle HXH^{\dagger }=Z}$ ו ${\displaystyle HZH^{\dagger }=X}$. ולכן שייך לקבוצת קליפורד. חשיבותו של שער זה היא שהוא מספק את ${\displaystyle {\frac {1}{\sqrt {2}}}}$ לשערים האוניטריים.
2. שער הפאזה ${\displaystyle S={\begin{bmatrix}1&0\\0&e^{i{\frac {\pi }{2}}}\end{bmatrix}}={\begin{bmatrix}1&0\\0&i\end{bmatrix}}={\sqrt {Z}}}$ המקיים ${\displaystyle SXS^{\dagger }=Y}$ ו- ${\displaystyle SZS^{\dagger }=Z}$, ולכן גם הוא שייך לקבוצה. החשיבות של השער היא בכך שהוא מספק את האיבר המדומה.
3. שער CNOT (אנ'), המקיים כי עבור שער P

   

   שער CNOT בייצוג של שער קוונטי

${\displaystyle P}$	CNOT ${\displaystyle P}$ CNOT${\displaystyle ^{\dagger }}$
${\displaystyle X\otimes I}$	${\displaystyle X\otimes X}$
${\displaystyle I\otimes X}$	${\displaystyle I\otimes X}$
${\displaystyle Z\otimes I}$	${\displaystyle Z\otimes I}$
${\displaystyle I\otimes Z}$	${\displaystyle Z\otimes Z}$

ולכן אף הוא שייך לקבוצה. חשיבותו של השער שהוא מאפשר לשזור בין הקיוביטים וכן כי בלעדיו השערים יפעלו על קיוביט בודד בלבד.

באופן שקול, כלל שערי פאולי הם שערי קליפורד שהרי ${\displaystyle \sigma _{i}\sigma _{j}\sigma _{i}^{\dagger }=\sigma _{i}\sigma _{j}\sigma _{i}=i\epsilon _{ijk}\sigma _{k}\sigma _{i}=-\epsilon _{ijk}\epsilon _{kij}\sigma _{j}}$ כך שהמכפלה שייכת לחבורת פאולי, ולכן השערים שייכים לחבורת קליפורד.

דוגמאות נוספות לשערי קליפורד הן שערי SWAP, iSWAP וטופולי.

המשפט

המשפט אומר כי כל מחשב קוונטי המערב:

1. הכנה של הקיוביטים בבסיס החישובי^[1]
2. שערי קליפורד
3. מדידות בבסיס החישובי
4. אפשרות לביצוע פעולות קלאסיות על תוצאות המדידות

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

קווים מנחים להוכחת המשפט

הוכחת המשפט משתמשת בפורמליזם המייצבים, המוצג בהרחבה במאמרו של גוטסמן, אשר מאפשר לתאר את המצבים בצורה שקלה לפענוח קלאסי. עבור מחשב קוונטי המקיים את תנאי המשפט מתקיים כי כל שער קליפורד מתורגם כעדכון של היוצרים של אותה קבוצת מייצבים, עדכון זה לוקח ${\displaystyle O(n^{2})}$. לאחר הפעלת השערים המצבים קורסים למצבים מייצבים, המדידה אף היא יכולה להתבצע על ידי מחשב קלאסי.

קיימת הוכחה אלטרנטיבית למשפט^[2] שאינה משתמשת בפורמליזם המייצבים. ההוכחה משתמשת בכך שניתן "לצמצם" את שערי קליפורד למעגל HT (מעגל המשתמש בשער אדמר ושער טופולי (שניתן לסמלוץ קלאסי), לאחר מכן ההוכחה מתארת את המצב של המערכת המתוארת במשפט כמרחב אפיני מממד סופי – שגם לכך יש מימוש קלאסי. לבסוף ההוכחה משתמשת באינדוקציה ממעגל פשוט יחיסת למעגל מורכבת יותר על ידי הוספה של שערי קליפורד בזה אחר זה.

משתנים רציפים

פונקציית ויגנר חיובית של מצב גאוסי – מצב ואקום

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

מצבים אלו, הנקראים מצבים גאוסיים הם סט מצבים המוגדרים כך שפונקציית ויגנר (אנ') (פונקציית קוואזי הסתברות) המוגדרת כך:

${\displaystyle W(q,p)\triangleq {\frac {1}{\pi \hbar }}\int _{-\infty }^{\infty }\psi ^{*}(q+x)\psi (q-x)e^{2ipx/\hbar }\ dx}$^[3] היא פונקציה גאוסית, פונקציה זו יכולה לשמש לחישוב צפיפות ההסתברות כפונקציה של המיקום ${\displaystyle q}$ והתנע ${\displaystyle p}$.

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

פונקציית ויגנר של מצב פוק ${\displaystyle n=5}$, בכחול החלקים השליליים – המשאבים החישוביים הקוונטים

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

קישורים חיצוניים

• Gross, D. “Hudson’s Theorem for Finite-Dimensional Quantum Systems.” Journal of Mathematical Physics, vol. 47, no. 12, 1 Dec. 2006
• Van den Nest, Maarten. “Classical Simulation of Quantum Computation, the Gottesman-Knill Theorem, and Slightly Beyond.” ArXiv.org, 6 Nov. 2008, arxiv.org/abs/0811.0898. Accessed 14 Oct. 2009.
• Nielsen, Michael A, and Isaac L Chuang. Quantum Computation and Quantum Information. Cambridge Cambridge University Press, 2019, p. 464.
• Gottesman, Daniel. “The Heisenberg Representation of Quantum Computers.” ArXiv (Cornell University), 1 Jan. 1998

הערות שוליים

1. Computational Basis – an overview | ScienceDirect Topics, www.sciencedirect.com
2. Maarten Van den Nest, Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond, 2009
3. בחלק מהמקורות משתמשים בכך ש ${\displaystyle \hbar =1}$ על מנת לפשט את הביטוי
4. Stephen D. Bartlett, Barry C. Sanders, Samuel L. Braunstein, Kae Nemoto, Efficient Classical Simulation of Continuous Variable Quantum Information Processes, Physical Review Letters 88, 2002-02-14 doi: 10.1103/PhysRevLett.88.097904