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

ולאחרונה ניגשו אלי עמיתיי ושאלו: "אתה מבין איך מחשב קוונטי עובד? אתה יכול לספר לנו?" ואז הבנתי שאני לא היחיד שיש לו בעיה להרכיב תמונה קוהרנטית בראש שלי.

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

תוכן העניינים

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

כתב ויתור

(לתוכן)

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

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

מבוא

(לתוכן)

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

איך הכל התחיל

(לתוכן)

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

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

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

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

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

• [1994]. פ' שור. עוצב על ידי אלגוריתם פירוק מספרים קוונטי
• [1998]. נוצר מחשב קוונטי 2 קיוביטים ראשון
• [2001]. IBM הציגה ביצוע האלגוריתם של שור להרחבת מספר 15
• [2007-2016]. D- גל יוצר ומפתח מחשב עם 128-2000 קיוביטים
• [2012]. מיושם באוניברסיטת קליפורניה האלגוריתם של שור למספר 21
• [2016]. גוגל דימה מולקולת מימן במחשב 9 קיוביטים
• [2017]. IBM מדמה בריליום הידריד BeH2 (שלושה אטומים)
• [2019]. IBM Q System One. מחשב 20 קיוביטים בענן
• [2019]. גוגל שקמה. מחשב 53 qubit. עליונות קוונטית?

כפי שניתן לראות, חלפו 17 שנים (מ-1981 עד 1998) מרגע הרעיון ועד להטמעתו הראשונה במחשב עם 2 קיוביטים, ו-21 שנים (מ-1998 עד 2019) עד שמספר הקיוביטים עלה ל-53. לקח 11 שנים (מ-2001 עד 2012) כדי לשפר את התוצאה של האלגוריתם של שור (נסתכל על זה ביתר פירוט בהמשך) מהמספר 15 ל-21. כמו כן, רק לפני שלוש שנים הגענו לנקודה של ליישם את מה שפיינמן דיבר עליו, וללמוד לדגמן את המערכות הפיזיות הפשוטות ביותר.

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

שחקנים מובילים

(לתוכן)

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

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

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

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

כיווני פיתוח

(לתוכן)

כרגע (יכול להיות שאני טועה, תקן אותי) המאמצים העיקריים (והתוצאות המשמעותיות יותר או פחות) של כל השחקנים המובילים מתרכזים בשני תחומים:

• מחשבים קוונטיים מיוחדים, שמטרתן לפתור בעיה ספציפית אחת, למשל, בעיית אופטימיזציה. דוגמה למוצר היא מחשבי D-Wave קוונטים.
• מחשבים קוונטיים אוניברסליים - אשר מסוגלים ליישם אלגוריתמים קוונטיים שרירותיים (שור, גרובר וכו'). הטמעות מ-IBM, גוגל.

וקטורים אחרים של התפתחות שהפיזיקה הקוונטית נותנת לנו, כגון:

• חיישנים קוונטיים
• רשת קוונטית כבסיס ל הצפנה קוונטית
• ועוד הרבה

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

בנוסף אתה יכול לקרוא מפת דרכים לפיתוח טכנולוגיות קוונטיות, ובכן, גוגל "פיתוח טכנולוגיות קוונטיות", לדוגמה, כאן, כאן и כאן.

יסודות. אובייקט קוונטי ומערכות קוונטיות

(לתוכן)

הדבר הכי חשוב להבין מהסעיף הזה הוא זה

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

מהו עצם קוונטי?

אובייקט קוונטי - אובייקט של עולם המיקרו (עולם קוונטי) המציג תכונות קוונטיות:

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

בואו נסתכל על כל נכס ביתר פירוט:

יש מצב מוגדר עם שתי רמות גבול (מצב סיום)

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

נמצא בסופרפוזיציה של מצבו עד לרגע המדידה

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

מסתבך עם עצמים אחרים כדי ליצור מערכות קוונטיות

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

עומד במשפט ללא שיבוט (לא ניתן להעתיק מצב של אובייקט)

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

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

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

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

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

אז התכונה השלישית קובעת שאובייקטים קוונטיים יכולים להסתבך כדי ליצור מערכות קוונטיות. מהי מערכת קוונטית?

מערכת קוונטית - מערכת של עצמים קוונטיים מסתבכים עם התכונות הבאות:

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

(ומסתכל קצת קדימה)

מסקנה לתוכניות קוונטיות:

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

השוואה בין מחשב קוונטי למחשב קונבנציונלי

(לתוכן)

כעת נשווה מחשב קונבנציונלי למחשב קוונטי.

	מחשב רגיל	מחשב קוונטי
לוגיקה	0 / 1	`a|0> + b|1>, a^2+b^2=1`
פיסיקה	טרנזיסטור מוליכים למחצה	אובייקט קוונטי
ספק מידע	רמות מתח	קיטוב, ספין,...
פעולות	NOT, AND, OR, XOR מעל ביטים	שסתומים: CNOT, Hadamard,…
מערכת יחסים	שבב מוליכים למחצה	בלבול אחד עם השני
אלגוריתמים	סטנדרטי (ראה שוט)	מבצעים (שור, גרובר)
עיקרון	דיגיטלי, דטרמיניסטי	אנלוגי, הסתברותי

רמת היגיון

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

זה מה שהם הגיעו אליו qubit. במצבי הגבול שלו הוא מממש מצבים הדומים ל-0 ו-1 |0> ו-|1>, ובסופרפוזיציה מייצגת התפלגות הסתברות על פני מצבי הגבול שלה |0> и |1>:

 a|0> + b|1>, такое, что a^2+b^2=1

a ו-b מייצגים אמפליטודות של הסתברות, והריבועים של המודולים שלהם הם ההסתברויות בפועל להשיג בדיוק ערכים כאלה של מצבי הגבול |0> и |1>, אם אתה ממוטט את הקיוביט עם מדידה עכשיו.

רובד פיזי

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

אחסון בינוני

עבור מחשב רגיל זה חַשְׁמַל - רמות מתח, נוכחות או היעדר זרם וכו', עבור קוונטי - אותו דבר מצב של עצם קוונטי (כיוון קיטוב, ספין וכו'), שעשוי להיות במצב של סופרפוזיציה.

פעולות

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

דוגמאות לשערים קוונטיים:

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

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

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

מערכת יחסים

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

קיוביט אחד גם חסר תועלת עבורנו (טוב, ולו רק במונחים אקדמיים),

כדי לבצע חישובים אנו זקוקים למערכת של קיוביטים (אובייקטים קוונטיים)

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

אלגוריתמים

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

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

עיקרון

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

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

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

יישומים פיזיים של קיוביטים

(לתוכן)

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

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

יש תגובה מקסימה к статье, שבו המגוון הנוכחי של יישומים פיזיים של הקיוביט נחשב ביתר פירוט, נפרט את המוכרים והנפוצים ביותר:

• קיוביטים מוליכים-על
• טעינה קיוביטים
• מלכודות יונים
• נקודות קוונטיות
• ועוד הרבה רעיונות אקזוטיים (אניונים וכו')

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

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

יסודות. איך עובד מחשב קוונטי

(לתוכן)

החומרים למדור זה (משימה ותמונות) לקוחים מהמאמר "רק על הדברים הקשים. איך עובד מחשב קוונטי?.

אז תארו לעצמכם שיש לנו את המשימה הבאה:

יש קבוצה של שלושה אנשים: (A)ndrey, (B)olodya ו-(C)erezha. יש שתי מוניות (0 ו-1).

ידוע גם ש:

• (A)ndrey, (B)olodya הם חברים
• (א)נדריי, (ג)רזה הם אויבים
• (B)olodya ו-(C)erezha הם אויבים

משימה: למקם אנשים במוניות כך מקסימום (חברים) и דקות (אויבים)

דֵרוּג: L = (מספר חברים) - (מספר אויבים) לכל אפשרות לינה

חשוב: בהנחה שאין היוריסטיות, אין פתרון אופטימלי. במקרה זה, ניתן לפתור את הבעיה רק ​​על ידי חיפוש מלא של אפשרויות.

פתרון במחשב רגיל

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

יש לנו 2 אפשרויות לינה אפשריות (מונית 0 ומונית 1) ו-3 אנשים. מרחב פתרון 2 ^ 3 = 8. ניתן אפילו לעבור על 8 אפשרויות באמצעות מחשבון, זו לא בעיה. עכשיו בואו נסבך את הבעיה - יש לנו 20 אנשים ושני אוטובוסים, מרחב הפתרון 2^20 = 1. גם שום דבר לא מסובך. בואו נגדיל את מספר האנשים פי 2.5 - קחו 50 איש ושתי רכבות, מרחב הפתרון הוא עכשיו 2^50 = 1.12 x 10^15. מחשב (על) רגיל כבר מתחיל להיתקל בבעיות רציניות. בואו נגדיל את מספר האנשים פי 2, 100 אנשים כבר יתנו לנו 1.2x10^30 אפשרויות אפשריות.

זהו, לא ניתן לחשב את המשימה הזו בפרק זמן סביר.

חיבור מחשב על

המחשב החזק ביותר כיום הוא מספר 1 של Top500זה פסגה, פרודוקטיביות 122 Pflops. בואו נניח שאנחנו צריכים 100 פעולות כדי לחשב אפשרות אחת, ואז כדי לפתור את הבעיה עבור 100 אנשים נצטרך:

(1.2 x 10^30 100) / 122×10^15 / (606024365) = 3 x 10^37 שנים.

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

האם יש חלופות? כפי שאולי ניחשתם, כן, יש.

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

רק קצת קומבינטוריקה, תורת הסתברות ונסיין מוזר

בוא ניקח שקית ונכניס אותה לתוכה 1000 כדורים לבנים ו-1000 שחורים. נערוך ניסוי - נוציא את הכדור, רשום את הצבע, מחזירים את הכדור לשקית ומערבבים את הכדורים בשקית.

הניסוי בוצע 10 פעמים, שלף 10 כדורים שחורים. אולי? דַי. האם המדגם הזה נותן לנו מושג הגיוני לגבי התפלגות האמיתית בתיק? ברור שלא. מה צריך לעשות - נכון, עמ'חזור על הניסוי מיליון פעמים וחשב את התדרים של כדורים שחורים ולבנים. אנחנו מקבלים, למשל 49.95% שחור ו-50.05% לבן. במקרה זה, מבנה ההתפלגות ממנה אנו דוגמים (מוציאים כדור אחד) כבר פחות או יותר ברור.

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

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

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

חיבור בין תיאוריה לפרקטיקה

עכשיו במקום כדורים שחורים ולבנים, בואו ניקח כדורי ביליארד ונשים אותם בשקית 1000 כדורים עם מספר 2, 1000 עם מספר 7 ו-10 כדורים עם מספרים אחרים. בואו נדמיין נסיין שמאומן בפעולות הפשוטות ביותר (להוציא כדור, לרשום את המספר, להחזיר את הכדור לשקית, לערבב את הכדורים בשקית) והוא עושה זאת תוך 150 מיקרו שניות. ובכן, נסיינית כזו על מהירות (לא פרסומת לסמים!!!). ואז תוך 150 שניות הוא יוכל לבצע את הניסוי שלנו מיליון פעמים ולספק לנו את התוצאות הממוצעות.

הם הושיבו את הנסיין, נתנו לו שקית, הסתובבו, המתינו 150 שניות וקיבלו:

מספר 2 - 49.5%, מספר 7 - 49.5%, שאר המספרים בסך הכל - 1%.

כן זה נכון, התיק שלנו הוא מחשב קוונטי עם אלגוריתם שפותר את הבעיה שלנו, והכדורים הם פתרונות אפשריים. מכיוון שיש שני פתרונות נכונים, אז מחשב קוונטי ייתן לנו כל אחד מהפתרונות האפשריים הללו בהסתברות שווה, ו-0.5% (10/2000) שגיאות, שעליו נדבר בהמשך.

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

מדרגיות של מחשב קוונטי

עכשיו תארו לעצמכם שעבור משימה הכוללת 100 אנשים (מרחב פתרון 2^100 אנחנו זוכרים את זה), יש גם רק שתי החלטות נכונות. לאחר מכן, אם ניקח 100 קיוביטים ונכתוב אלגוריתם שמחשב את הפונקציה האובייקטיבית שלנו (L, ראה למעלה) על פני הקיוביטים הללו, אז נקבל שקית שבה יהיו 1000 כדורים עם המספר של התשובה הנכונה הראשונה, 1000 עם המספר של התשובה השנייה הנכונה ו-10 כדורים עם מספרים אחרים. ובתוך אותן 150 שניות הנסיין שלנו ייתן לנו אומדן של התפלגות ההסתברות של תשובות נכונות.

זמן הביצוע של אלגוריתם קוונטי (עם כמה הנחות) יכול להיחשב קבוע O(1) ביחס לממד של מרחב הפתרון (2^N).

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

קוביט ועולמות מקבילים

איך זה קורה? מה מאפשר למחשב קוונטי לבצע חישובים כל כך מהר? הכל קשור לאופי הקוונטי של הקיוביט.

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

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

קח (ב) צעיר ובואו נדמיין גם את מצבו כקיוביט. מתעוררים שני עולמות מקבילים נוספים. אבל לעת עתה זוגות העולמות הללו (א) и (ב) לא לקיים אינטראקציה כלל. מה צריך לעשות כדי ליצור קָשׁוּר מערכת? זה נכון, אנחנו צריכים את הקיוביטים האלה לקשור (בלבל). אנחנו לוקחים את זה ומבלבלים את זה (א) עם (ב) - אנו מקבלים מערכת קוונטית של שני קיוביטים (א, ב), מממש בתוך עצמו ארבע תלויים הדדיים עולמות מקבילים. לְהוֹסִיף (ס)ארגי ונקבל מערכת של שלושה קיוביטים (א ב ג), יישום שמונה תלויים הדדיים עולמות מקבילים.

המהות של המחשוב הקוונטי (הטמעה של שרשרת של שערים קוונטיים על מערכת של קיוביטים מחוברים) היא העובדה שהחישוב מתרחש בכל העולמות המקבילים בו זמנית.

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

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

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

אלגוריתמים קוונטיים

(לתוכן)

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

האלגוריתמים הידועים ביותר כיום הם:

• האלגוריתם של שורה
• האלגוריתם של גרובר
• אלגוריתם דויטש-ג'וזי

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

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

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

האלגוריתם של שור.

(לתוכן)

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

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

עד כה ממצאים יותר מצניעות. תוצאות הפקטוריזציה הטובות ביותר עם האלגוריתם של שור - מספרים 15 и 21, שזה הרבה פחות מ-2048 סיביות. לגבי שאר התוצאות מהטבלה, שונה אלגוריתם חישובים, אבל אפילו התוצאה הטובה ביותר לפי אלגוריתם זה (291311) רחוקה מאוד מיישום אמיתי.

אתה יכול לקרוא עוד על האלגוריתם של שור, למשל, כאן. לגבי יישום מעשי - כאן.

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

האלגוריתם של גרובר

(לתוכן)

האלגוריתם של גרובר - אלגוריתם קוונטי פתרון בעיית הספירה, כלומר מציאת פתרון למשוואה F(X) = 1, כאשר F הוא פונקציה בוליאנית מ n משתנים. הוצע על ידי מתמטיקאי אמריקאי דייג גרובר в השנה 1996.

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

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

האלגוריתם של גרובר. תאר לעצמך שיש לך N חלקים של קופסאות סגורות ממוספרות. כולם ריקים מלבד אחד שמכיל כדור. המשימה שלך: גלה את מספר התיבה שבה נמצא הכדור (מספר לא ידוע זה מסומן לעתים קרובות באות w).

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

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

מסתבר שאם נתרגם את הבעיה הזו עם קופסאות, כדור ואורקל לשפה קוונטית, נקבל תוצאה יוצאת דופן: כדי למצוא את המספר של קופסה עם כדור בין N תיבות, אנחנו צריכים להפריע לאורקל רק בערך SQRT (נ) פעמים!

כלומר, המורכבות של משימת החיפוש באמצעות האלגוריתם של גרובר מצטמצמת בשורש של פעמים.

אלגוריתם דויטש-ג'וזי

(לתוכן)

אלגוריתם דויטש-ג'וזה (המכונה גם אלגוריתם דויטש-ג'וזה) - [אלגוריתם קוונטי](https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B9%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC), предложенный דוד דויטש и ריצ'רד ג'וזה в השנה 1992, והפך לאחת הדוגמאות הראשונות של אלגוריתמים שתוכננו לביצוע על מחשבים קוונטיים. _

הבעיה של Deutsch-Jozsi היא לקבוע אם פונקציה של מספר משתנים בינאריים F(x1, x2, ... xn) היא קבועה (לוקחת את הערך 0 או 1 עבור כל ארגומנטים) או מאוזנת (עבור חצי מהתחום שהיא לוקחת הערך 0, עבור החצי השני 1). במקרה זה, זה נחשב ידוע מראש שהפונקציה היא קבועה או מאוזנת. (C)

עוד אפשר לקרוא כאן. הסבר פשוט יותר:

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

בעיות של מחשבים קוונטיים

(לתוכן)

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

• רגישות לסביבה ואינטראקציה עם הסביבה
• צבירת טעויות במהלך חישובים
• קשיים באתחול ראשוני של מצבי קיוביט
• קשיים ביצירת מערכות מולטי קיוביט

אני ממליץ בחום לקרוא את המאמר "מאפיינים של מחשבים קוונטיים", במיוחד ההערות אליו.

בואו נארגן את כל הבעיות העיקריות לשלוש קבוצות גדולות ונסתכל מקרוב על כל אחת מהן:

דקוהרנטיות

(לתוכן)

תיאור מ-N+1.

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

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

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

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

יש נפלא сайтאיפה אתה יכול להסתכל טבלאות השוואה של פרמטרים של כל המערכות הקוונטיות שנוצרו. מאמר זה כולל רק שני מעבדים מובילים כדוגמאות - מבית IBM IBM Q System One מ גוגל שקמה. כפי שאנו יכולים לראות, זמן הדקוהרנטיות (T2) אינו עולה על 200 מיקרון.

לא מצאתי נתונים מדויקים על השקמה, אבל ברוב המקרים מאמר על עליונות קוונטית שני מספרים ניתנים - מיליון חישובים ב-1 שניות, במקום אחר - עבור 130 שניות ללא אובדן אותות בקרה וכו'.. בכל מקרה, זה נותן לנו זמן דה-קוהרנטיות הוא בערך 150 מיקרון. זכור שלנו נסיין עם תיק? ובכן, הנה הוא.

שם מחשב	N Qubits	מקסימום מזווג	T2 (µs)
IBM Q System One	20	6	70
גוגל שקמה	53	4	~ 150-200

במה דה-קוהרנטיות מאיימת עלינו?

הבעיה העיקרית היא שאחרי 150 μs, מערכת המחשוב שלנו של N קיוביטים מסובכים תתחיל להפיק רעש לבן הסתברותי במקום התפלגות הסתברותית של פתרונות נכונים.

כלומר, אנחנו צריכים:

• אתחול מערכת הקיוביט
• בצע חישוב (שרשרת פעולות שער)
• קרא את התוצאה

ותעשה את כל זה תוך 150 מיקרו שניות. לא היה לי זמן - התוצאה הפכה לדלעת.

אבל זה לא הכל…

שגיאות

(לתוכן)

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

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

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

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

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

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

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

על אותו דבר מקוון ישנן טבלאות השוואתיות של מעבדים לפי רמות שגיאה. לשם השוואה, ניקח את אותם מעבדים כמו בדוגמה הקודמת – IBM IBM Q System One и גוגל שקמה:

מחשבים	1-Qubit Gate Fidelity	2-Qubit Gate Fidelity	קריאת נאמנות
IBM Q System One	99.96%	98.31%	-
גוגל שקמה	99.84%	99.38%	96.2%

כאן נֶאֱמָנוּת הוא מדד לדמיון של שני מצבים קוונטיים. ניתן לבטא באופן גס את גודל השגיאה כ-1-Fidelity. כפי שאנו יכולים לראות, שגיאות בשערי 2 קיוביטים ושגיאות קריאה הן המכשול העיקרי לביצוע אלגוריתמים מורכבים וארוכים במחשבים קוונטיים קיימים.

עוד אפשר לקרוא מפת דרכים משנת 2016 שנים מ NQIT כדי לפתור את בעיית תיקון השגיאות.

ארכיטקטורת מעבד

(לתוכן)

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

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

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

קישוריות מקסימלית ומספר קיוביטים מקסימלי עבור אותם שבבים עליונים:

שם מחשב	N Qubits	מקסימום מזווג	T2 (µs)
IBM Q System One	20	6	70
גוגל שקמה	53	4	~ 150-200

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

אז:

• כרגע אין ארכיטקטורות מחוברות לחלוטין עם יותר מ-6 קיוביטים
• כדי להסתבך qubit 0 s במעבד אמיתי, למשל, qubit 15 עשוי לדרוש כמה עשרות פעולות נוספות
• יותר פעולות -> יותר שגיאות -> השפעה חזקה יותר של דה-קוהרנטיות

תוצאות של

(לתוכן)

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

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

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

אנו מודדים זמן קוהרנטיות של קוויביט העולה על 0.5 שניות, ועם מיגון מגנטי אנו מצפים שזה ישתפר להיות ארוך מ-1000 שניות

אתה יכול גם לקרוא על טכנולוגיה זו כאן או למשל כאן.

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

ולבסוף, ארכיטקטורות מודרניות אינן מאפשרות ליישם תוכניות הסתבכות טובות יותר מ-1 ל-4 או 1 ל-6 בעלות מינימלית.

דרכים לפתור בעיות

(לתוכן)

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

• שימוש בתאי קריו עם טמפרטורות נמוכות (10 mK (-273,14 מעלות צלזיוס))
• שימוש ביחידות מעבד המוגנות בצורה מקסימלית מהשפעות חיצוניות
• שימוש במערכות תיקון שגיאות קוונטיות (Logic Qubit)
• שימוש במייעל בעת תכנות מעגלים עבור מעבד ספציפי

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

D- גל

(לתוכן)

מחשב D-Wave 2000Q 2000 קיוביט. מָקוֹר: מערכות D-Wave

על רקע ההכרזה של גוגל על ​​השגת עליונות קוונטית באמצעות מעבד של 53 קיוביטים, מחשבים и הכרזות מחברת D-Wave, שמספר הקיוביטים בה הוא באלפים, קצת מבלבל. ובכן, באמת, אם 53 קיוביטים היו מסוגלים להשיג עליונות קוונטית, אז מה מסוגל מחשב עם 2048 קיוביטים? אבל לא הכל כל כך טוב...

בקיצור (נלקח מהוויקי):

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

לפרטים נוספים תוכלו לקרוא, למשל, כאן, כאן (זהירות, אסור לפתוח מרוסיה), או סקוט אהרונסון в статье מ _ שלו פוסט בבלוג. אגב, אני ממליץ בחום לקרוא את הבלוג שלו באופן כללי, יש שם הרבה חומר טוב

באופן כללי, כבר מתחילת ההכרזות היו לקהילה המדעית שאלות לגבי מחשבי D-Wave. לדוגמה, בשנת 2014, IBM הטיל ספק בעובדה ש-D-Wave משתמש באפקטים קוונטיים. זה הגיע לנקודה שבשנת 2015, גוגל, יחד עם נאס"א, קנתה את אחד מהמחשבים הקוונטיים הללו ולאחר מחקר מְאוּשָׁר, כי כן, המחשב עובד ומחשב את הבעיה מהר יותר מאשר רגיל. אתה יכול לקרוא עוד על ההצהרה של גוגל כאן ו, למשל, כאן.

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

קצת על אמולציית מחשב קוונטית

(לתוכן)

ניתן לחקות מחשוב קוונטי במחשב רגיל. אכן, תראה:

• המצב של הקיוביט יכול להיות דמיינו מספר מורכב, תופס מ-2x32 עד 2x64 סיביות (8-16 בתים) בהתאם לארכיטקטורת המעבד
• ניתן לייצג את המצב של N קיוביטים מחוברים כ-2^N מספרים מרוכבים, כלומר. 2^(3+N) עבור ארכיטקטורת 32 סיביות ו-2^(4+N) עבור 64 סיביות.
• פעולה קוונטית על N קיוביטים יכולה להיות מיוצגת על ידי מטריצה ​​2^N x 2^N

לאחר מכן:

• כדי לאחסן את המצבים המדמים של 10 קיוביטים, יש צורך ב-8 KB
• כדי לאחסן את המצבים של 20 קיוביטים אתה צריך 8 MB
• כדי לאחסן את המצבים של 30 קיוביטים, יש צורך ב-8 GB
• דרושים 40 טרה-בייט כדי לאחסן את המצבים של 8 קיוביטים
• כדי לאחסן את המצבים של 50 קיוביטים, יש צורך ב-8 פטה-בייט וכו'.

(C)

לשם השוואה, פסגה (טופ-1 מ-Top-500) נושא רק 2.8 פטה-בייט של זיכרון.

שיא סימולציה נוכחי - 49 קיוביטים נמסרו בשנה שעברה למחשב העל הסיני הגדול ביותר (Sunway Taihu Light)

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

אני גם ממליץ לקרוא את ההערה הזו. משם:

בפעולה - לאמולציה מדויקת של מעגל של 49 קיוביטים המורכב מכ-39 "מחזורים" (שכבות עצמאיות של שערים) זה לקח 2^63 מכפלות מורכבות - 4 Pflops של מחשב-על למשך 4 שעות

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

עליונות מחשוב קוונטי.

(לתוכן)

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

עליונות קוונטית – יכולת מחשוב קוונטי מכשירים לפתרון בעיות שמחשבים קלאסיים כמעט ולא יכולים לפתור.

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

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

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

הצהרת עליונות קוונטית של גוגל

(לתוכן)

מעבד שקמה 54 קיוביטים

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

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

באינטרנט ממש שם הופיע רב חומרים בנושא זה, שמידתם השתנתה מ נלהב до סקֶפְּטִי.

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

וכמובן, סקוט אהרונסון בו פוסט בבלוג לא יכולתי להתעלם מהאמירה הזו. שֶׁלוֹ анализ יחד עם כל הקישורים ו שאלות נפוצות בנושא עליונות קוונטית עליונה של סקוט! כרגיל, שווה להשקיע בהם את הזמן. על הרכזת יש תרגום זה שאלות נפוצות, והקפד לקרוא את ההערות, יש קישורים למסמכים ראשוניים שהודלפו באינטרנט לפני ההכרזה הרשמית.

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

אני כמובן יכול להגיד לך, אבל אני מרגיש די טיפש. החישוב הוא כדלקמן: הנסיין יוצר מעגל קוונטי אקראי C (כלומר, רצף אקראי של שערים של 1 קיוביט ו-2 קיוביטים בין השכנים הקרובים ביותר, בעומק של, למשל, 20, הפועל על רשת דו-ממדית של n = 2-50 קיוביטים). לאחר מכן הנסיין שולח C למחשב הקוונטי, ומבקש ממנו להחיל את C למצב התחלתי של 60, למדוד את התוצאה בבסיס {0}, לשלוח בחזרה רצף נצפה (מחרוזת) של n-bit, ולחזור על כמה אלף או מיליוני פעמים. לבסוף, תוך שימוש בידע שלו ב-C, הנסיין מבצע בדיקה סטטיסטית כדי לראות אם התוצאה תואמת את הפלט הצפוי מהמחשב הקוונטי.

בקצרה מאוד:

• מעגל אקראי באורך 20 של 53 קיוביטים נוצר באמצעות שערים
• המעגל מתחיל במצב ההתחלתי [0...0] לביצוע
• הפלט של המעגל הוא מחרוזת סיביות אקראית (דוגמה)
• התפלגות התוצאה אינה אקראית (הפרעה)
• התפלגות הדגימות שהתקבלו מושווה לזו הצפויה
• מסכמת עליונות קוונטית

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

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

תקציר

(לתוכן)

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

פיתוח המחשוב הקוונטי יאפשר לנו (יום אחד) לפתור בעיות:

• מודלים של מערכות פיזיקליות מורכבות ברמה הקוונטית
• בלתי פתיר במחשב רגיל בגלל מורכבות חישובית

הבעיות העיקריות ביצירה והפעלה של מחשבים קוונטיים:

• דקוהרנטיות
• שגיאות (דה-קוהרנטיות ושער)
• ארכיטקטורת מעבד (מעגלי קיוביט מחוברים במלואם)

מצב העניינים הנוכחי:

• למעשה - ממש ההתחלה R & D.
• אין עדיין ניצול מסחרי אמיתי (ולא ברור מתי יהיה)

מה יכול לעזור:

• סוג של גילוי פיזי שמוזיל את עלות החיווט והפעלת המעבדים
• גילוי משהו שיגדיל את זמן הדקוהרנטיות בסדר גודל ו/או יפחית שגיאות

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

בינתיים אנחנו צוברים ניסיון בתכנות קוונטי, איסוף ויצירת אלגוריתמים קוונטיים, בדיקת רעיונות וכו' וכו'. אנחנו מחכים לפריצת דרך.

מסקנה

(לתוכן)

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

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

תודה על תשומת הלב שלך, אני מקווה שמאמר זה יהיה שימושי למישהו.

(C) קרוגר

תודות

(לתוכן)

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

@a5b להערות עשירות במידע על "מאפיינים של מחשבים קוונטיים", ולא רק לה, מה שבמידה רבה עזר לי להבין את הפאזל הזה.

לכל כותבי המאמרים והפרסומים שהחומרים שלהם שימשו לכתיבת מאמר זה.

רשימת משאבים

(לתוכן)

מאמרי אקטואליה מאת [The National Academies Press]

http://cs.brown.edu/courses/csci1800/sources/2018_NAE_QuantumComputing_ProgressAndProspects.pdf
https://www.nap.edu/catalog/25196/quantum-computing-progress-and-prospects

מאמרים מהבר (בסדר אקראי)

https://habr.com/ru/post/458450/
https://habr.com/ru/post/401315/
https://habr.com/ru/post/458134/
https://habr.com/ru/post/246483/
https://habr.com/ru/post/95428/
https://habr.com/ru/post/387761/
https://habr.com/ru/post/468911/
https://habr.com/ru/post/435560/
https://habr.com/ru/post/316810/
https://habr.com/ru/company/microsoft/blog/351624/
https://habr.com/ru/company/microsoft/blog/351628/
https://habr.com/ru/company/ua-hosting/blog/377533/
https://habr.com/ru/company/acronis/blog/455559/
https://habr.com/ru/company/yandex/blog/332106/
https://habr.com/ru/company/mailru/blog/350208/
https://habr.com/ru/company/mailru/blog/476444/
https://habr.com/ru/company/misis/blog/470445/
https://habr.com/ru/company/it-grad/blog/452424/
https://habr.com/ru/company/piter/blog/450480/

מאמרים לא ממוינים (אך לא פחות מעניינים) מהאינטרנט

http://homepages.spa.umn.edu/~duplij/publications/Duplij-Shapoval_TOPOLOGICAL-QUANTUM-COMPUTERS.pdf
https://quantum.country/qcvc
http://extremal-mechanics.org/wp-content/uploads/2015/07/RIFFEL.pdf
https://thecode.media/quantum/
https://naked-science.ru/article/nakedscience/quantum-computers
https://ru.ihodl.com/technologies/2018-10-29/prosto-o-slozhnom-kak-rabotaet-kvantovyj-kompyuter/
https://pikabu.ru/story/chto_takoe_kvantovyiy_kompyuter_5204054
https://nplus1.ru/search?q=%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D0%B0%D1%8F+%D0%B0%D0%B7%D0%B1%D1%83%D0%BA%D0%B0
https://www.scottaaronson.com/blog/?p=4372
https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80
https://quantumcomputingreport.com/scorecards/qubit-quality/
https://quantumcomputing.stackexchange.com/questions/2499/is-quantum-computing-just-pie-in-the-sky
https://quantumcomputing.stackexchange.com/questions/1289/how-does-a-quantum-computer-do-basic-math-at-the-hardware-level
https://www.extremetech.com/extreme/284306-how-quantum-computing-works
https://techno.nv.ua/it-industry/chto-takoe-kvantovyy-kompyuter-i-kvantovoe-prevoshodstvo-google-protiv-ibm-50049940.html
https://www.nature.com/articles/s41586-019-1666-5?utm_source=commission_junction&utm_medium=affiliate
https://petrimazepa.com/nemnogo_o_kvantovykh_kompyuterakh
https://www.forbes.ru/tehnologii/371669-ibm-protiv-d-wave-nastupila-li-era-kvantovyh-kompyuterov

קורסים והרצאות

https://www.coursera.org/learn/kvantovyye-vychisleniya
https://www.youtube.com/watch?v=uPw9nkJAwDY&amp=&index=4&amp=&t=0s
https://courses.edx.org/courses/BerkeleyX/CS191x/2013_Spring/course/#
https://www.youtube.com/watch?v=xLfFWXUNJ_I&list=PLnbH8YQPwKbnofSQkZE05PKzPXzbDCVXv
https://cs269q.stanford.edu/syllabus.html
https://quantum-computing.ibm.com/support/guides/user-guide?section=5dcb2b45330e880045abccb0
https://gitlab.com/qkitchen/basics-of-quantum-computing

מקור: www.habr.com