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

הנקודה השקרית בהנחת היסוד היא כי קומפוזיציה של שערים חד-קיוביים ושני קווביטים יוצגו על ידי הרכב כלשהו של מטריצות 2 × 2 ו -4 × 4. למעשה, אם שער של קוביט יחיד (עבור שתי קוביות זה דומה) פועל על הקובית $ i $ מתוך $ n $, יש להטיל את המטריצה ​​ל $$ (Id_2) ^ {\ זמני (i-1)} \ זמן A \ זמן (Id_2) ^ {\ זמן (n-i)}, $$ כאשר $ A $ הוא המטריצה ​​המקורית של $ 2 × 2 $, על מנת לתאר את פעולתו במצב $ n $ -qubit. זו מטריצה ​​של מידות $ 2 ^ n × 2 ^ n $ ללא קשר לסוג השער.

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

  לכל אינדקס u, 0 ≤ u < 2 ^ n:
  הגדר u_i = ערך סיביות של סיבית i-th של u
  הגדר v = u XOR 2 ^ i
  אם u_i = 0:
    חדש (psi [u], psi [v]) = a * psi [u] + b * psi [v]
  אַחֵר:
    חדש (psi [u], psi [v]) = d * psi [u] + c * psi [v]
 

כן, בליבת האלגוריתם הפסאודו הזה יש רק כפל דו ממדי. אבל זה נעשה $ 2 ^ n $ פעמים.

עוד לפני שמגיעים ל לבצע את הסימולציה הקלאסית בפועל, אפשר לאזול את הזיכרון הזמין אפילו ב אחסון המדינה בכל רגע מסוים. קח $ n = 100 $ qubits, זה $ 2 ^ {100} $ משרעות מורכבות של דיוק כפול (128 ביט כל אחת). אני מקבל הערכה העולה על קיבולת אחסון הנתונים של כל המחשבים בכדור הארץ בכ- 14 סדרי גודל, כך שלא נראה את זה בקרוב. בינתיים, מחשב קוונטי עם 100 סיביות היה מתחיל להיות מעניין ליישומים, בתיאוריה זה לא נדיר לראות הרבה יותר מזה החזוי.

אם לומר זאת באופן שונה, החלל הילברט (H) עבור המעגל הקוונטי שלך גדל באופן אקספוננציאלי ($ \ text {dim H} = 2 ^ n $) כאשר n הוא מספר הקוביטים.יש סוג של מעגלים קוונטיים שניתן ליישם בזמן פולינומי, אך הם דורשים שהשערים במעגל הקוונטי יוגבלו לקבוצת פאולי ו / או לנורמליזציה של קבוצת פאולי (משפט גוטסמן קניל).זה גם מגביל איזה סוג של מודלים של שגיאות משתמשים במעגל הקוונטי.הסיבה הבסיסית היא שיש איזומורפיזם שאפשר להגדיר בין קבוצת פאולי למרחב הווקטורי מעל השדה הסופי עם אלמנטים.ריבוי האלמנטים של קבוצת פאולי הופך לתוצר סימפלקטי של יסודות החלל הווקטורי.

כי המטריצות גדולות ממה שאתה חושב.

שקול כמה מעגלים פשוטים ב- 8 קוביטים; אולי טרנספורמציה של פורייה. הוא משתמש ב ~ 40 שערים, וכל שער מכפיל את וקטור מצב המערכת של 8 הקוביטים במטריקס כלשהו. כדי לדמות מערכת זו באופן קלאסי. אתה עשוי לצפות שנצטרך להשקיע משהו כמו $ 40 \ cdot 8 = 320 $ יחידות שרירותיות לעבודה חישובית (AUCW).

אך לווקטור מצב המערכת יש משרעת לכל מצב קלאסי אפשרי של המערכת. ניתן להקצות לשמונה סיביות $ 2 ^ 8 = 256 $ ערכים אפשריים, ולכן וקטור המדינה שלנו חייב להכיל 256 ערכים לא שמונה או שש עשרה. בהתאם, מטריצה ​​שהופכת מערכת זו חייבת להיות בגודל 256 $ \ 256 $, אם כי רק 256 $ זה באמת הערכה גסה טובה בהרבה של "גודל העבודה" מכיוון שמטריצת שער בודד תהיה דלילה. הניחוש שלנו 40 $ \ cdot 8 = 320 $ AUCW היה רחוק! ניחוש טוב בהרבה הוא $ 40 \ cdot 2 ^ 8 = 40 \ cdot 256 = 10240 $. אז $ 10 $ קילו AUCW.

בעיה זו מחמירה את הדרך דרך ככל שמספר הקוביטים גדל. עם 50 קוביט, לווקטור המדינה יש $ 2 ^ {50} $ כניסות, המטריצות הן $ 2 ^ {50} \ פעמים 2 ^ {50} $, טרנספורמציית פורייה משתמשת ~ 1250 שערים, ועלינו להוציא מיליון מיליון million AUCWs לבצע את הסימולציה הקלאסית. ואילו המחשב הקוונטי עושה רק 1250 AUQW.