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

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

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

ואדים קלוצ'ניקוב1,2, קריסטין לאוטר3, רומי מינקו4,5, אדם פצניק1, וכריסטוף פטיט6,7

1Microsoft Quantum, רדמונד, וושינגטון, ארה"ב
2Microsoft Quantum, טורונטו, ON, קליפורניה
3Facebook AI Research, סיאטל, WA, ארה"ב
4אוניברסיטת אוקספורד, אוקספורד, בריטניה
5מכון היילברון למחקר מתמטי, אוניברסיטת בריסטול, בריסטול, בריטניה
6אוניברסיטת ברמינגהם, ברמינגהם, בריטניה
7אוניברסיטת ליבר דה בריסל, בריסל, בלגיה

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

תַקצִיר

אנו נותנים הליך חדשני לקירוב יחידות יחיד קיוביט כלליות משער אוניברסלי סופי על ידי הפחתת הבעיה לבעיית קירוב גודל חדשנית, תוך השגת שיפור מיידי באורך הרצף בפקטור של 7/9. הרחבת העבודות [28] ו [15], אנו מראים שלקיחת תערובות הסתברותיות של ערוצים כדי לפתור נפילה [13] ובעיות קירוב לגודל חוסכות גורם של שניים בעלויות הקירוב. בפרט, על פני ערכת שערים של Clifford+$sqrt{mathrm{T}}$ אנו משיגים ספירת שערים ממוצעת ללא קליפורד של $0.23log_2(1/varepsilon)+2.13$ ו-T-count $0.56log_2(1/varepsilon)+5.3 $ עם קירובים מעורבים של סתירה לדיוק נורמות היהלומים $varepsilon$.
מאמר זה מספק סקירה הוליסטית של קירוב שערים, בנוסף לתובנות החדשות הללו. אנו נותנים הליך מקצה לקצה לקירוב שערים עבור קבוצות שערים כלליות הקשורות לאלגברות קווטרניוניות מסוימות, ומספקים דוגמאות פדגוגיות באמצעות קבוצות שערים סובלני תקלות נפוצות (V, Clifford+T ו- Clifford+$sqrt{mathrm{T}}$) . אנו מספקים גם תוצאות מספריות מפורטות עבור ערכות שערים של Clifford+T ו-Clifford+$sqrt{mathrm{T}}$. במאמץ לשמור על המאמר עצמאי, אנו כוללים סקירה כללית של האלגוריתמים הרלוונטיים לספירת נקודות שלמות ולפתרון משוואות נורמות יחסיות. אנו מספקים מספר יישומים נוספים של בעיות קירוב הגודל, כמו גם אלגוריתמים משופרים לסינתזה מדויקת, בנספחים.

► נתוני BibTeX

► הפניות

[1] פרנק ארוטה, קונאל אריה, ריאן באבוש, דייב בייקון, ג'וזף סי ברדין, רמי ברנדס, רופאק ביזוואז, סרג'יו בוישו, פרננדו GSL ברנדאו, דייוויד א. ביואל, בריאן בורקט, יו צ'ן, זי'ון צ'ן, בן צ'יארו, רוברטו קולינס, וויליאם קורטני, אנדרו דונסוורת', אדוארד פרחי, ברוקס פוקסן, אוסטין פאולר, קרייג גידני, מריסה ג'וסטינה, רוב גראף, קית' גרין, סטיב האבגר, מתיו פ. הריגן, מייקל ג'יי הרטמן, אלן הו, מרקוס הופמן, טרנט הואנג, טראוויס S. Humble, סרגיי V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naman, Matthew Neeley, Charles Neil, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, כריס קווינטנה, אלינור ג'י ריפל, פדרם רושאן, ניקולס סי רובין, דניאל סאנק, קווין ג'יי סאצינגר, ואדים סמליאנסקי, קווין ג'יי סונג, מתיו ד טרווית'יק, עמית וינסנצ'ר, בנג'מין וילונגה, תיאודור ווייט, ז' ג'יימי יאו , Ping Yeh, Adam Zalcman, Hartmut Neven, וג'ון M. Martinis, "עליונות קוונטית באמצעות מעבד מוליך-על הניתן לתכנות" Nature 574, 505-510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[2] Wojciech Banaszczyk "אי-שוויון עבור גופים קמורים וסריג הדדי קוטבי ב $R^n$" Discrete & Computational Geometry 13, 217–231 (1995).
https: / / doi.org/ 10.1007 / BF02574039

[3] אדריאנו ברנקו, צ'ארלס ה. בנט, ריצ'רד קליב, דיוויד פ. דיווינצ'נזו, נורמן מרגולוס, פיטר שור, טיכו סליאטור, ג'ון א. סמולין והאראלד ויינפורטר, "שערים יסוד לחישוב קוונטי" סקירה פיזיקלית A 52, 3457–3467 ( 1995).
https: / / doi.org/ 10.1103 / PhysRevA.52.3457

[4] אנדראס בלאס, אלכס בוכרוב ויורי גורביץ', "מעגלי פאולי+V אופטימליים ללא אנציל לסיבובים ציריים" Journal of Mathematical Physics 56, 122201 (2015).
https: / / doi.org/ 10.1063 / 1.4936990
arXiv: 1412.1033

[5] מייקל בוורלנד, ארל קמפבל, מארק הווארד, ואדים קלוצ'ניקוב, "גבולות תחתונים של המשאבים שאינם קליפורד לחישובים קוונטיים" Quantum Science and Technology 5, 035009 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab8963
arXiv: 1904.01124

[6] Michael E. Beverland, Prakash Murali, Matthias Troyer, Krysta M. Svore, Torsten Hoefler, Vadym Kliuchnikov, Guang Hao Low, Mathias Soeken, Aarthi Sundaram, ואלכסנדר Vaschillo, "Assessing requirements to scale to advantage quantum praktisk" (2022).
https://​/​doi.org/​10.48550/​arXiv.2211.07629
arXiv: 2211.07629

[7] Jean Bourgainand Alex Gamburd "משפט הפערים הספקטרלי ב-SU$(d)$" Journal of the European Mathematical Society 14, 1455–1511 (2012).
https: / / doi.org/ 10.4171 / JEMS / 337

[8] אלכס בוצ'רוב, יורי גורביץ' וקריסטה מ' סבור, "פירוק יעיל של שערים של קוויביט בודדים לתוך מעגלים בסיסיים V" סקירה פיזית A 88, 1-13 (2013).
https: / / doi.org/ 10.1103 / PhysRevA.88.012313
arXiv: 1303.1411

[9] סרגיי בראוויאן ואלכסיי קיטאיב "חישוב קוונטי אוניברסלי עם שערי קליפורד אידיאליים ואציליות רועשות" פיזי. ר' א 71, 022316 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.022316

[10] סרגיי בראוויאן ורוברט קוניג "סיווג שערים מוגנים טופולוגית לקודי מייצב מקומיים" פיזי. הכומר לט. 110, 170503 (2013).
https: / / doi.org/ 10.1103 / PhysRevLett.110.170503

[11] Michael E. Beverland, Aleksander Kubica, ו-Krysta M. Svore, "עלות האוניברסליות: מחקר השוואתי של תקורה של זיקוק המדינה והחלפת קודים עם קודי צבע" PRX Quantum 2, 020341 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.020341

[12] אלכס בוצ'רוב, מרטין רוטלר וקריסטה מ' סבור, "סינתזה יעילה של מעגלים קוונטיים חוזרים-עד-הצלחה אוניברסליים" מכתבי סקירה פיזית 114, 080502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.080502
arXiv: 1404.5320

[13] אלכס בוצ'רוב, מרטין רוטלר וקריסטה מ' סבור, "סינתזה יעילה של מעגלים קוונטיים הסתברותיים עם נפילה" Physical Review A 91, 052317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.052317
arXiv: 1409.3552

[14] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer, "מחשוב קוונטי משופר קטליזה חישובית" Phys. Rev. Research 3, 033055 (2021).
https: / / doi.org/ 10.1103 / PhysRevResearch.3.033055

[15] ארל קמפבל "רצפי שערים קצרים יותר עבור מחשוב קוונטי על ידי ערבוב יחידות" Physical Review A 95 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.042306
arXiv: 1612.02689

[16] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, "תיאוריית השגיאה של טרטר עם קנה מידה של קומוטטור" פיזי. Rev. X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020

[17] Denis X. Charles, Kristin E. Lauter, ואייל Z. Goren, "Cryptographic Hash Functions from Expander Graphs" Journal of Cryptology 22, 93–113 (2009).
https: / doi.org/â € ‹10.1007 / s00145-007-9002-x

[18] אנרי כהן "נושאים מתקדמים בתורת המספרים החישוביים" שפרינגר ניו יורק (2000).
https:/​/​doi.org/​10.1007/​978-1-4419-8489-0

[19] אנרי כהן "קורס בתורת המספרים האלגברית החישובית" שפרינגר ברלין היידלברג (1993).
https:/​/​doi.org/​10.1007/​978-3-662-02945-9

[20] ערכת נתונים של מעגלים קוונטיים קצרים (2023).
https://​/​azure-quantum-notebooks.azurefd.net/​publicdata/​shorter-quantum-circuits-dataset.tar

[21] בריאן איסטיננד עמנואל קניל "הגבלות על ערכות שערים קוונטיים מקודדים רוחביים" פיזי. הכומר לט. 102, 110502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.110502

[22] סיימון פורסט, דיוויד גוסט, ואדים קליוצ'ניקוב ודיוויד מקינון, "סינתזה מדויקת של יחידות קיוביט יחידות על פני ערכות שערים של קליפורד-ציקלוטומיות" Journal of Mathematical Physics 56, 082201 (2015).
https: / / doi.org/ 10.1063 / 1.4927100

[23] Daniel Gottesmanand Isaac L. Chuang "הדגמת הכדאיות של חישוב קוונטי אוניברסלי באמצעות טלפורטציה ופעולות קיוביט בודדות" Nature 402, 390–393 (1999).
https: / / doi.org/ 10.1038 / 46503

[24] קרייג גידני ואוסטין ג'. פאולר "מפעלי מדינת קסם יעילים עם טרנספורמציה מזורזת של $|CCZ⟩$ ל-$2|T⟩$" Quantum 3, 135 (2019).
https:/​/​doi.org/​10.22331/​q-2019-04-30-135

[25] Joachim von zur Gathenand Jürgen Gerhard "Modern Computer Algebra" הוצאת אוניברסיטת קיימברידג' (2013).
https: / / doi.org/ 10.1017 / CBO9781139856065

[26] קרייג גידני "חציית העלות של הוספה קוונטית" Quantum 2, 74 (2018).
https:/​/​doi.org/​10.22331/​q-2018-06-18-74

[27] דיוויד גוסט, ואדים קליוצ'ניקוב, מישל מוסקה ווינסנט רוסו, מידע קוונטי "אלגוריתם ל-T-Count". מחשוב. 14, 1261–1276 (2014).
https://​/​doi.org/​10.48550/​arXiv.1308.4134

[28] Matthew B. Hastings "הפיכת שגיאות סינתזת שער לשגיאות לא קוהרנטיות" מידע וחישוב קוונטי 17, 488–494 (2017).
https://​/​doi.org/​10.48550/​arXiv.1612.01011
arXiv: 1612.01011

[29] ארם וו הארו, בנג'מין רכט, ויצחק ל 'צ'ואנג, "קירובים יעילים בדידים של שערים קוונטיים" כתב העת לפיזיקה מתמטית 43, 4445-4451 (2002).
https: / / doi.org/ 10.1063 / 1.1495899

[30] קנת אירלנד ומייקל רוזן "מבוא קלאסי לתורת המספרים המודרנית" שפרינגר ניו יורק (1990).
https:/​/​doi.org/​10.1007/​978-1-4757-2103-4

[31] רבן איטן, רוג'ר קולבק, איבן קוקולג'אן, ג'ונתן הום ומתיאס כריסטאנדל, "מעגלים קוונטיים לאיזומטריות" פיזי. ר' א 93, 032318 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.032318

[32] רבן איטן, אוליבר רירדון-סמית', עמנואל מלבטי, לוקה מונדדה, גבריאל פאובר, איתן רדמונד, רבג'וט סינג קולי ורוג'ר קולבק, "מבוא ל-UniversalQCompiler" (2021).
https://​/​doi.org/​10.48550/​arXiv.1904.01072
arXiv: 1904.01072

[33] נתנאל ג'ונסטון, דיוויד וו. קריבס, ו-ורן אי. פולסן, "מחשוב נורמות מיוצבות לפעולות קוונטיות באמצעות התיאוריה של מפות מוגבלות לחלוטין" מידע קוונטי. מחשוב. 9, 16–35 (2009).
https://​/​doi.org/​10.48550/​arXiv.0711.3636

[34] אלכסנדר יעקובלביץ' חינצ'ין "ניסוח כמותי של תורת הקירוב של קרונקר" Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya 12, 113–122 (1948).

[35] V Kliuchnikov, A Bocharov, M Roetteler, and J Yard, "A Framework for Approximating Unitary Qubit" (2015).
https://​/​doi.org/​10.48550/​arXiv.1510.03888
arXiv: 1510.03888

[36] פיליפ קיי, ריימונד לאפלם ומישל מוסקה, "מבוא למחשוב קוונטי" הוצאת אוניברסיטת אוקספורד (2006).
https: / / doi.org/ 10.1093 / oso / 9780198570004.001.0001

[37] V Kliuchnikov, D Maslov, and M Mosca, "קירוב אסימפטוטי אופטימלי של יחידות קוויביט בודדות על ידי מעגלים קליפורד ו-T באמצעות מספר קבוע של קוויביטים נלווים" מכתבי סקירה פיזית 110, 190502 (2013).
https: / / doi.org/ 10.1103 / PhysRevLett.110.190502
arXiv: 1212.0822

[38] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca, "סינתזה מדויקת מהירה ויעילה של יחידות קוביט בודדות שנוצרו על ידי קליפורד ו-T Gates" מידע קוונטי. מחשוב. 13, 607–630 (2013).
https://​/​doi.org/​10.48550/​arXiv.1206.5236

[39] V Kliuchnikovand J Yard "מסגרת לסינתזה מדויקת" (2015).
https://​/​doi.org/​10.48550/​arXiv.1504.04350
arXiv: 1504.04350

[40] Guang Hao Lowand Isaac L. Chuang "סימולציית המילטון אופטימלית על ידי עיבוד אותות קוונטי" פיזי. הכומר לט. 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[41] Franz Lemmermeyer "האלגוריתם האוקלידי בשדות מספרים אלגבריים" Expositiones Mathematicae 13, 385–416 (1995).

[42] HW Lenstra "תכנות שלמים עם מספר קבוע של משתנים" Mathematics of Operations Research 8, 538–548 (1983).
https: / / doi.org/ 10.1287 / moor.8.4.538

[43] דניאל ליטינסקי "משחק של קודי שטח: מחשוב קוונטי בקנה מידה גדול עם ניתוח סריג" Quantum 3, 128 (2019).
https:/​/​doi.org/​10.22331/​q-2019-03-05-128

[44] AK Lenstra, HW Lenstra, ול. Lovász, "פקטור פולינומים עם מקדמים רציונליים" Mathematische Annalen 261, 515–534 (1982).
https: / / doi.org/ 10.1007 / BF01457454

[45] A. Lubotzky, R. Phillips, and P. Sarnak, "Ramanujan graphs" Combinatorica 8, 261–277 (1988).
https: / / doi.org/ 10.1007 / BF02126799

[46] איזוואר מגסאן, ג'יי מ 'גמבטה, וג'וזף אמרסון, "אפיון שערים קוונטיים באמצעות ביצוע מבחני ביצועים אקראיים" Phys. הכומר A 85, 042311 (2012).
https: / / doi.org/ 10.1103 / PhysRevA.85.042311

[47] עמנואל מלווטי, רבן איטן ורוג'ר קולבק, "מעגלים קוונטיים לאיזומטריות דלילות" Quantum 5, 412 (2021).
https:/​/​doi.org/​10.22331/​q-2021-03-15-412

[48] Michael A. Nielsenand Isaac L. Chuang "חישוב קוונטי ומידע קוונטי" הוצאת אוניברסיטת קיימברידג' (2012).
https: / / doi.org/ 10.1017 / CBO9780511976667

[49] מחברת Shorter Quantum Circuits (2023).
https:/​/​github.com/​microsoft/​Quantum/​blob/​a57178163b64a060d37603355c8a78571075f679/​samples/​azure-quantum/​shorter-quantum-circuits/​shorter-quantum-circuits-dataset.ipynb

[50] גבריאל נבה, אריק מ. ריינס, וניל ג'יי.איי סלואן, "קבוצות קליפורד אמיתיות ומורכבות" שפרינגר ברלין היידלברג (2006).
https:/​/​doi.org/​10.1007/​3-540-30731-1_6

[51] Yunseong Nam, Yuan Su, and Dmitri Maslov, "טרנספורמציה קוונטית פורייה משוערת עם שערים של O(n log(n)) T" npj Quantum Information 6, 26 (2020).
https:/​/​doi.org/​10.1038/​s41534-020-0257-5

[52] כריסטוף פטיט, קריסטין לאוטר וז'אן ז'אק קוויסקוטר, "ניתוח קריפטי מלא של פונקציות LPS ו-Morgenstern Hash" (2008).
https:/​/​doi.org/​10.1007/​978-3-540-85855-3_18

[53] אדוארדו קרוואלו פינטו וכריסטוף פטיט "אלגוריתמים טובים יותר למציאת נתיבים ב-LPS Ramanujan graphs" Journal of Mathematical Cryptology 12, 191–202 (2018).
https: / / doi.org/ 10.1515 / jmc-2017-0051

[54] Adam Paetznickand Krysta M. Svore "חזרה-עד-הצלחה: פירוק לא-דטרמיניסטי של יחידות קוויביט יחידות" מידע וחישוב קוונטי 14, 1277-1301 (2014).
https://​/​doi.org/​10.48550/​arXiv.1311.1074
arXiv: 1311.1074

[55] Ori Parzanchevski and Peter Sarnak "Super-Golden-Gates for PU(2)" Advances in Mathematics 327, 869–901 (2018) כרך מיוחד לכבוד דוד קז'דן.
https://doi.org/​10.1016/​j.aim.2017.06.022

[56] ניל ג'יי רוס "קירוב קליפורד אופטימלי ללא אנסילה+V של סיבובי Z" מידע קוונטי. מחשוב. 15, 932–950 (2015).
https://​/​doi.org/​10.48550/​arXiv.1409.4355

[57] ניל ג'יי רוסנד פיטר סלינגר "קירוב קליפורד+T אופטימלי ללא אנסיליה של סיבובי z" Quantum Information & Computation 15, 932–950 (2015).
https://​/​doi.org/​10.48550/​arXiv.1403.2975
arXiv: 1403.2975

[58] פיטר סרנק "מכתב לאהרונסון ופולינגטון על משפט סולביי-קיטאיב ושערי הזהב, 2015".
http://publications.ias.edu/​sarnak/​paper/​2637

[59] Naser T Sardari "Complexity of Strong Approximation on the Sphere" הודעות בינלאומיות למחקר מתמטיקה 2021, 13839–13866 (2021).
https:/​/​doi.org/​10.1093/​imrn/​rnz233

[60] פיטר סלינגר "קירוב יעיל של Clifford+T של אופרטורים של קיוביט בודדים" Quantum Information & Computation 15, 159–180 (2015).
https://​/​doi.org/​10.48550/​arXiv.1212.6253
arXiv: 1212.6253

[61] תקשורת פרטית של Zachary Stier (2020).

[62] Jean-Pierre Tillichand Gilles Zémor "התנגשויות עבור פונקציית הגיבוב של גרף מרחיב LPS" כנס בינלאומי שנתי על התיאוריה והיישומים של טכניקות קריפטוגרפיות 254–269 (2008).
https:/​/​doi.org/​10.1007/​978-3-540-78967-3_15

[63] ג'ון וייט "Quaternion Algebras" שפרינגר הבינלאומי הוצאה לאור (2021).
https:/​/​doi.org/​10.1007/​978-3-030-56694-4

[64] לורנס סי וושינגטון "מבוא לשדות ציקלוטומיים" ספרינגר ניו יורק (1997).
https:/​/​doi.org/​10.1007/​978-1-4612-1934-7

[65] ג'ון ווטרוס "Theory of Quantum Information" הוצאת אוניברסיטת קיימברידג' (2018).
https: / / doi.org/ 10.1017 / 9781316848142

[66] Paul Websterand Stephen D. Bartlett "שערים קוונטיים עמידים לתקלות עם פגמים בקודי מייצבים טופולוגיים" Phys. Rev. A 102, 022403 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.022403

מצוטט על ידי

[1] דניאל ליטינסקי ונעמי ניקרסון, "נפח פעיל: ארכיטקטורה למחשבים קוונטיים יעילים סובלני תקלות עם חיבורים לא מקומיים מוגבלים", arXiv: 2211.15465, (2022).

[2] פסקל באסלר, מתיאס ציפר, כריסטופר צדז'יץ', מרקוס היינריך, פטריק ה. הובר, מייקל יוהנינג ומרטין קליש, "סינתזה של וקומפילציה עם שערים מרובים קיוביטים אופטימליים בזמן", קוונטום 7, 984 (2023).

[3] Seiseki Akibue, Go Kato, and Seiichiro Tani, "סינתזה יחידה הסתברותית עם דיוק אופטימלי", arXiv: 2301.06307, (2023).

[4] תומס לובינסקי, קסנדרה גרנדה, עמוס אנדרסון, אלן גלר, מרטין רוטלר, אנדריי פטרנקו ובטינה היים, "קידום חישוב קוונטי-קלאסי היברידי עם ביצוע בזמן אמת", גבולות בפיסיקה 10, 940293 (2022).

[5] Seiseki Akibue, Go Kato, and Seiichiro Tani, "סינתזת מצב הסתברותית המבוססת על קירוב קמור אופטימלי", arXiv: 2303.10860, (2023).

הציטוטים לעיל הם מ- מודעות SAO / NASA (עודכן לאחרונה בהצלחה 2023-12-19 01:59:59). הרשימה עשויה להיות שלמה מכיוון שלא כל בעלי האתרים מספקים נתוני ציטוט ראויים ומלאים.

On השירות המוזכר של קרוסרף לא נמצאו נתונים על ציטוט עבודות (ניסיון אחרון 2023-12-19 01:59:58)

בול זמן:

עוד מ יומן קוונטים