אינטליגנציה של נתונים גנרטיביים

קוונטית

יתרון קוונטי בחישוב קוונטי מבוסס מדידה שטוחה זמנית

הועלה מחדש על ידי אפלטון
הועלה מחדש על ידי אפלטון

תאריך:

צפיות: 0

מייקל דה אוליביירה1,2,3, לואיס ס ברבוסה1,2,3, וארנסטו פ. גלואו3,4

1אוניברסיטת מינהו, המחלקה למדעי המחשב, בראגה, פורטוגל
2INESC TEC, בראגה, פורטוגל
3המעבדה הבינלאומית לננוטכנולוגיה איבריה (INL) Av. מסטרה חוסה ויגה, 4715-330, בראגה, פורטוגל
4Instituto de Física, Universidade Federal Fluminense Av. גל. Milton Tavares de Souza s/n, Niterói, RJ, 24210-340, ברזיל

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

תַקצִיר

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

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

[תוכן מוטבע]

סיכום פופולרי

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

In this work we analyse the evaluation of Boolean functions, something that quantum computers can do using the correlated outcomes of measurements on entangled Greenberger-Horne-Zeilinger (GHZ) states of many qubits. This variant of measurement-based quantum computation requires no adaptivity, so all qubits can be measured simultaneously. This flat temporal structure of the computational process results, in some cases, in very economical quantum circuits. We identify the characteristics of a Boolean function that determine how many qubits are needed, and the required measurement precision. For a particular family of Boolean functions we show there is a rigorous advantage in width and number of gates with respect to the corresponding family of classical circuits. In the future, our techniques may help devise better ways of using quantum resources also for adaptive circuits displaying more computational expressivity.

► נתוני BibTeX

► הפניות

[1] סקוט אהרונסון, דבון אינגרם וויליאם קרצ'מר. "האקרובטיקה של BQP". בתוך שחר Lovett, עורך, 37th Computational Complexity Conference (CCC 2022). כרך 234 של Leibniz International Proceedings in Informatics (LIPIcs), עמודים 20:1–20:17. Dagstuhl, גרמניה (2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2022.20

[2] ריצ'רד ג'וזה ונואה לינדן. "על תפקידה של הסתבכות בהאצה קוונטית-חישובית". הליכים של החברה המלכותית של לונדון. סדרה א': מדעי המתמטיקה, הפיזיקה וההנדסה 459, 2011–2032 (2003).
https: / / doi.org/ 10.1098 / rspa.2002.1097

[3] מארק הווארד, ג'ואל וולמן, ויקטור וויץ' וג'וזף אמרסון. "הקשר מספק את ה'קסם' לחישוב קוונטי". טבע 510, 351–355 (2014).
https: / / doi.org/ 10.1038 / nature13460

[4] חואן ברמז'ו-וגה, ניקולס דלפוסה, דן אי. בראון, צ'יהאן אוקיי ורוברט ראוסנדורף. "הקשריות כמשאב למודלים של חישוב קוונטי עם קיוביטים". פיזי. הכומר לט. 119, 120505 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.120505

[5] Ernesto F. Galvão. "פונקציות דיסקרטיות של ויגנר והאצת חישוב קוונטי". פיזי. ר' א 71, 042302 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.042302

[6] א' מרי וג'יי אייזרט. "פונקציות ויגנר חיוביות הופכות סימולציה קלאסית של חישוב קוונטי ליעילה". פיזי. הכומר לט. 109, 230503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.230503

[7] לאב ק' גרובר. "היתרונות של סופרפוזיציה". מדע 280, 228–228 (1998).
https: / / doi.org/ 10.1126 / science.280.5361.228

[8] רוברט ראוסנדורף והנס ג'יי בריגל. "מחשב קוונטי חד כיווני". פיזי. הכומר לט. 86, 5188–5191 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[9] מארטן ואן דן נסט, אקימסה מיאקה, וולפגנג דיר והנס ג'יי בריגל. "משאבים אוניברסליים לחישוב קוונטי מבוסס מדידה". פיזי. הכומר לט. 97, 150504 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.150504

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

[11] וינסנט דנוס ואלחם כשפי. "דטרמיניזם במודל החד-כיווני". פיזי. ר' א 74, 052310 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052310

[12] דניאל אי בראון, אלהם כשפי, מהדי מחלה וסימון פרדריקס. "זרימה כללית ודטרמיניזם בחישוב קוונטי מבוסס מדידה". New Journal of Physics 9, 250 (2007).
https:/​/​doi.org/​10.1088/​1367-2630/​9/​8/​250

[13] מייקל ג'יי ברמנר, אשלי מונטנרו ודן ג'יי שפרד. "מורכבות ממוצעת של מקרה מול סימולציה משוערת של חישובים קוונטיים לנסיעה". פיזי. הכומר לט. 117, 080501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501

[14] מאטי ג'יי הובאן, ג'ואל ג'יי וולמן, חוסיין אנואר, נאירי אושר, רוברט ראוסנדורף ודן א' בראון. "חישוב קלאסי מבוסס מדידה". פיזי. הכומר לט. 112, 140505 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.112.140505

[15] מייקל ג'יי ברמנר, אשלי מונטנרו ודן ג'יי שפרד. "השגת עליונות קוונטית עם חישובי נסיעה קוונטיים דלילים ורועשים". קוונטים 1, 8 (2017).
https:/​/​doi.org/​10.22331/​q-2017-04-25-8

[16] לאונרדו נובו, חואני ברמז'ו-וגה וראול גרסיה-פטרון. "יתרון קוונטי ממדידות אנרגיה של מערכות קוונטיות בגוף רבים". Quantum 5, 465 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-02-465

[17] Masahito Hayashi ויוקי טאקוצ'י. "אימות חישובים קוונטיים לנסיעה באמצעות הערכת נאמנות של מצבי גרף משוקלל". New Journal of Physics 21, 93060 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab3d88

[18] חואן ברמז'ו-וגה, דומיניק הנגליטר, מרטין שוורץ, רוברט ראוסנדורף וג'נס אייזרט. "ארכיטקטורות לסימולציה קוונטית המציגות מהירות קוונטית". פיזי. Rev. X 8, 021010 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.021010

[19] ג'ייקוב מילר, סטיבן סנדרס ואקימאסה מיאקה. "עליונות קוונטית בחישוב מבוסס מדידה בזמן קבוע: ארכיטקטורה מאוחדת לדגימה ואימות". פיזי. ר' א 96, 062320 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062320

[20] מאטי J Hoban, Earl T Campbell, Klearchos Loukopoulos ו-Dan E Browne. "חישוב קוונטי מבוסס מדידה לא אדפטיבי ואי-שוויון בל רב-צדדי". New Journal of Physics 13, 23014 (2011).
https:/​/​doi.org/​10.1088/​1367-2630/​13/​2/​023014

[21] ריוחי מורי. "ייצוג פורייה תקופתי של פונקציות בוליאניות". מידע קוונטי. מחשוב. 19, 392–412 (2019). כתובת אתר: https://​/​dl.acm.org/​doi/​abs/​10.5555/​3370251.3370253.
https: / / dl.acm.org/ doi / abs / 10.5555 / 3370251.3370253

[22] מרקוס פרמבס, סם רוברטס, ארל טי קמפבל וסטיבן ד ברטלט. "היררכיות של משאבים לחישוב קוונטי מבוסס מדידה". New Journal of Physics 25, 013002 (2023).
https://doi.org/​10.1088/​1367-2630/​acaee2

[23] Jelena Mackeprang, Daniel Bhatti, Matty J Hoban, וסטפני בארז. "כוחם של קוויטריטים עבור מחשוב קוונטי מבוסס מדידה לא אדפטיבי". New Journal of Physics 25, 073007 (2023).
https://doi.org/​10.1088/​1367-2630/​acdf77

[24] דניאל קולינס, ניקולס גיסין, סנדו פופסקו, דיוויד רוברטס ולריו סקאראני. "אי-שוויון מסוג פעמון לזיהוי אי-הפרדה אמיתית של $mathit{n}$-Body". פיזי. הכומר לט. 88, 170405 (2002).
https: / / doi.org/ 10.1103 / PhysRevLett.88.170405

[25] ניקולס ברונר, דניאל קוולקנטי, סטפנו פירוניו, ולריו סקאראני וסטפני ווהנר. "לא מקומיות של פעמון". כומר מוד. פיזי. 86, 419–478 (2014).
https: / / doi.org/ 10.1103 / RevModPhys.86.419

[26] דמיטריס קרבצ'נקו. "משחקים קוונטיים, מדינות קוונטיות, המאפיינים והיישומים שלהם". עבודת דוקטורט. אוניברסיטת Latvijas. (2013).

[27] וויליאם סלופסטרה. "הגבול התחתון של ההסתבכות הדרושה כדי לשחק משחקים לא מקומיים של XOR". Journal of Mathematical Physics 52, 102202 (2011).
https: / / doi.org/ 10.1063 / 1.3652924

[28] Andris Ambainis, Jānis Iraids, Dmitry Kravchenko, ו-Madars Virza. "יתרון של אסטרטגיות קוונטיות במשחקי xor סימטריים אקראיים". ב-Antonín Kučera, Thomas A. Henzinger, Jaroslav Nešetřil, Tomáš Vojnar, and David Antoš, עורכים, מתמטיקה והנדסה שיטות במדעי המחשב. עמודים 57–68. ברלין, היידלברג (2013). שפרינגר ברלין היידלברג.
https:/​/​doi.org/​10.1007/​978-3-642-36046-6_7

[29] אנדריס אמביניס וג'ניס איראידס. "יתרון מוכח לאסטרטגיות קוונטיות במשחקי XOR סימטריים אקראיים". ב- Simone Severini ופרננדו ברנדאו, עורכים, הכנס ה-8 בנושא התיאוריה של חישוב קוונטי, תקשורת וקריפטוגרפיה (TQC 2013). כרך 22 של Leibniz International Proceedings in Informatics (LIPIcs), עמודים 146–156. Dagstuhl, גרמניה (2013). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2013.146

[30] סמואל מרקוביץ' ובני רזניק. "השלכות של מורכבות תקשורת במערכות רב-צדדיות". פיזי. ר' א 77, 032120 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.032120

[31] מרסין פאלובסקי, תומאש פטרק, דגומיר קסליקובסקי, ולריו סקאראני, אנדראס וינטר ומארק ז'וקובסקי. "סיבתיות מידע כעיקרון פיזיקלי". טבע 461, 1101–1104 (2009).
https: / / doi.org/ 10.1038 / nature08400

[32] סנדו פופסקו ודניאל רוהרליך. "אי-לוקאליות קוונטית כאקסיומה". יסודות הפיזיקה 24, 379–385 (1994).
https: / / doi.org/ 10.1007 / BF02058098

[33] ג'ונתן בארט, נואה לינדן, סרג' מסאר, סטפנו פירוניו, סנדו פופסקו ודיוויד רוברטס. "מתאמים לא מקומיים כמשאב תיאורטי מידע". פיזי. ר' א 71, 022101 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.022101

[34] א.א. רזבורוב. "מורכבות תקשורת קוונטית של פרדיקטים סימטריים". איזבסטיה: מתמטיקה 67, 145 (2003).
https:/​/​doi.org/​10.1070/​IM2003v067n01ABEH000422

[35] Zhiqiang Zhang ו-Yaoyun Shi. "מורכבות תקשורת של פונקציות XOR סימטריות". מידע וחישוב קוונטי 9, 255–263 (2009). כתובת אתר: https://​/​dl.acm.org/​doi/​abs/​10.5555/​2011781.2011786.
https: / / dl.acm.org/ doi / abs / 10.5555 / 2011781.2011786

[36] פייר בוטרון. "תיבות לא מקומיות ומורכבות תקשורת". תזה לתואר שני. אוניברסיטת פול סבטייה טולוז השלישית. (2022). כתובת אתר: https://​/​pierre-botteron.github.io/​Articles/​2022-06-MSc-Thesis.pdf.
https://​/​pierre-botteron.github.io/​Articles/​2022-06-MSc-Thesis.pdf

[37] קוואנגיל ביי ובן וונמין. "קריטריונים כלליים של אי-לוקאליות תחת סימטריית המתאם". פיזי. ר' א 98, 022116 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.022116

[38] מרקוס פרמבס, סם רוברטס וסטיבן ד' בארטלט. "קונטקסטואליות כמשאב לחישוב קוונטי מבוסס מדידה מעבר לקיוביטים". New Journal of Physics 20, 103011 (2018).
https: / / doi.org/ 10.1088 / 1367-2630 / aae3ad

[39] סרגיי בראווי, דיוויד גוסט ורוברט קוניג. "יתרון קוונטי עם מעגלים רדודים". מדע 362, 308–311 (2018).
https: / / doi.org/ 10.1126 / science.aar3106

[40] דניאל גריר ולוק שייפר. "מעגלי קליפורד אינטראקטיביים: יתרון קוונטי נגד NC¹ ומעבר לכך". בהליכים של סימפוזיון ACM SIGACT השנתי ה-52 על תורת המחשוב. עמודים 875–888. STOC 2020 ניו יורק, ניו יורק, ארה"ב (2020). האגודה למכונות מחשוב.
https: / / doi.org/ 10.1145 / 3357713.3384332

[41] ליבור קאהה, חאבייר קויט-רוי ורוברט קניג. "טלפורטציה של שער יחיד מספק יתרון קוונטי" (2022). arXiv:2209.14158.
arXiv: 2209.14158

[42] פרנסואה לה גאל. "יתרון קוונטי ממוצע עם מעגלים רדודים". בתוך אמיר שפילקה, עורך, כנס מורכבות חישובית ה-34 (CCC 2019). כרך 137 של Leibniz International Proceedings in Informatics (LIPIcs), עמודים 21:1—-21:20. Dagstuhl, גרמניה (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2019.21

[43] מתיו קודרון, ג'לקס סטארק ותומס וידיק. "יישוב מסחר לזמן: אקראיות הניתנת לאישור ממעגלים בעומק נמוך". תקשורת בפיזיקה מתמטית 382, ​​49–86 (2021).
https: / / doi.org/ 10.1007 / s00220-021-03963-w

[44] סרגיי בראווי, דיוויד גוסט, רוברט קוניג ומרקו טומיכל. "יתרון קוונטי עם מעגלים רדודים רועשים". טבע פיזיקה 16, 1040–1045 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

[45] Atsuya Hasegawa ופרנסואה לה גאל. "יתרון קוונטי עם מעגלים רדודים תחת שחיתות שרירותית". ב-Hee-Kap Ahn ו-Kunihiko Sadakane, עורכים, סימפוזיון בינלאומי 32 על אלגוריתמים וחישובים (ISAAC 2021). כרך 212 של Leibniz International Proceedings in Informatics (LIPIcs), עמודים 74:1–74:16. Dagstuhl, גרמניה (2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://​/​doi.org/​10.4230/​LIPIcs.ISAAC.2021.74

[46] אדם בן ווטס, רובין כותרי, לוק שייפר ואבישי טל. "הפרדה אקספוננציאלית בין מעגלים קוונטיים רדודים ומעגלים קלאסיים רדודים עם מאוורר-אין". בהליכים של סימפוזיון ACM SIGACT השנתי ה-51 על תורת המחשוב. עמודים 515–526. STOC 2019 ניו יורק, ניו יורק, ארה"ב (2019). האגודה למכונות מחשוב.
https: / / doi.org/ 10.1145 / 3313276.3316404

[47] נטלי פרהם. "על הכוח והמגבלות של מעגלים קוונטיים רדודים". תזה לתואר שני. אוניברסיטת ווטרלו. (2022). כתובת אתר: https://​/​uwspace.uwaterloo.ca/​handle/​10012/​18702.
https://uwspace.uwaterloo.ca/ ידית/10012/18702

[48] דמיטרי מסלוב, ג'ין-סונג קים, סרגיי בראווי, תיאודור ג'יי יודר ושרה שלדון. "יתרון קוונטי לחישובים עם שטח מוגבל". טבע פיזיקה 17, 894–897 (2021).
https:/​/​doi.org/​10.1038/​s41567-021-01271-7

[49] פאריד אבלייב, אאידה גיינוטדינובה, מרק קרפינסקי, כריסטופר מור וכריסטופר פולט. "על כוח החישוב של תוכנית הסתעפות הסתברותית וקוונטית". מידע וחישוב 203, 145–162 (2005).
https: / / doi.org/ 10.1016 / j.ic.2005.04.003

[50] ד שפרד ומ.ג'יי ברמנר. "חישוב קוונטי לא מובנה באופן זמני". Proceedings of the Royal Society of London Series A 465, 1413–1439 (2009).
https: / / doi.org/ 10.1098 / rspa.2008.0443

[51] דניאל מ. גרינברגר, מייקל א הורן ואנטון זיילינגר. "מעבר למשפט בל". ב-Menas Kafatos, עורך, משפט בל, תורת הקוונטים ותפיסות היקום. עמודים 69–72. דורדרכט (1989). ספרינגר הולנד.
https:/​/​doi.org/​10.1007/​978-94-017-0849-4_10

[52] דיוגו קרוז, רומיין פורנייה, פביאן גרמיון, אליקס ז'נרוט, קניצ'י קומאגטה, טארה טוסיץ', ג'רלה ת'יזברומל, צ'ון לאם צ'אן, ניקולס מקריס, מארק-אנדרה דופרטויס וקלמנט ג'ברזאק-גלי. "אלגוריתמים קוונטיים יעילים למדינות GHZ ו-W, ויישום במחשב הקוונטי של IBM". Advanced Quantum Technologies 2, 1900015 (2019).
https: / / doi.org/ 10.1002 / qute.201900015

[53] ר"פ ורנר ומ"מ וולף. "אי-שוויון של מתאם פעמון רב-חלקי עבור שני נקודות צפייה דיכוטומיות בכל אתר". פיזי. ר' א 64, 032112 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.032112

[54] ריאן אודונל. "ניתוח של פונקציות בוליאניות". הוצאת אוניברסיטת קיימברידג'. (2014). כתובת אתר: http://​/​www.cs.cmu.edu/​ ./​odonnell/​papers/​Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf.
http://​/​www.cs.cmu.edu/​~./​odonnell/​papers/​Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf

[55] אנסטסיה צ'יסטופולסקיה ולדימיר V. Podolskii. "מורכבות עץ החלטות זוגיות גדולה יותר מפירוט" (2018). arXiv:1810.08668.
arXiv: 1810.08668

[56] קנטאו ו-M Videau. "פונקציות בוליאניות סימטריות". IEEE Transactions on Information Theory 51, 2791–2811 (2005).
https: / doi.org/â € ‹10.1109 / TIT.2005.851743

[57] לארי ג'יי סטוקמאייר. "על המורכבות השילובית של פונקציות בוליאניות סימטריות מסוימות". תורת המערכות המתמטית 10, 323–336 (1976).
https: / / doi.org/ 10.1007 / BF01683282

[58] RF ארנולד ו-MA הריסון. "מאפיינים אלגבריים של פונקציות בוליאניות סימטריות וסימטריות חלקיות". IEEE Transactions on Electronic Computers EC-12, 244–251 (1963).
https://doi.org/​10.1109/​PGEC.1963.263535

[59] בריקן ובארט פרנל. "על החסינות האלגברית של פונקציות בוליאניות סימטריות". ב-Subhamoy Maitra, CE Veni Madhavan, and Ramarathnam Venkatesan, עורכים, Progress in Cryptology – INDOCRYPT 2005. כרך 3797 של הערות הרצאה במדעי המחשב, עמודים 35–48. ברלין, היידלברג (2005). שפרינגר ברלין היידלברג.
https: / doi.org/â € ‹10.1007 / 11596219_4

[60] הארי בוהרמן ורונלד דה וולף. "מדדי מורכבות ומורכבות עץ ההחלטות: סקר". מדעי המחשב עיוני 288, 21–43 (2002).
https:/​/​doi.org/​10.1016/​S0304-3975(01)00144-X

[61] מתיו איימי, דמיטרי מסלוב, מישל מוסקה ומרטין רוטלר. "אלגוריתם פגישה באמצע לסינתזה מהירה של מעגלים קוונטיים אופטימליים לעומק". IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems 32, 818–830 (2013).
https: / / doi.org / 10.1109 / TCAD.2013.2244643

[62] VV Shende, SS בולוק ו-IL Markov. "סינתזה של מעגלים קוונטיים-לוגיים". IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems 25, 1000–1010 (2006).
https: / / doi.org / 10.1109 / TCAD.2005.855930

[63] Juha J Vartiainen, Mikko Mötönen, Martti M Salomaa. "פירוק יעיל של שערים קוונטיים". פיזי. הכומר לט. 92, 177902 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.92.177902

[64] ביי זנג, שי צ'ן ואייזק ל צ'ואנג. "פעולות למחצה קליפורד, מבנה של היררכיית $mathcal{C}_{k}$ ומורכבות שערים לחישוב קוונטי סובלני לתקלות". פיזי. ר' א 77, 042313 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.042313

[65] גארי ג'יי מוני, צ'ארלס די היל ולויד CL הולנברג. "סינתזה אופטימלית של שער קיוביט בודד בהיררכיית קליפורד". Quantum 5, 396 (2021).
https:/​/​doi.org/​10.22331/​q-2021-02-15-396

[66] נאדיש דה סילבה. "טלפורטציה יעילה של שער קוונטי בממדים גבוהים יותר". הליכים של החברה המלכותית A 477, 20200865 (2021).
https: / / doi.org/ 10.1098 / rspa.2020.0865

[67] דניאל גוטסמן ואייזק ל צ'ואנג. "הדגמת הכדאיות של חישוב קוונטי אוניברסלי באמצעות טלפורטציה ופעולות קיוביט בודדות". טבע 402, 390–393 (1999).
https: / / doi.org/ 10.1038 / 46503

[68] דניאל גוטסמן. "הייצוג של הייזנברג של מחשבים קוונטיים" (1998). arXiv:quant-ph/​9807006.
arXiv: quant-ph / 9807006

[69] ואדים קליוצ'ניקוב, דמיטרי מסלוב ומישל מוסקה. "סינתזה מדויקת מהירה ויעילה של יחידות קיוביט בודדות שנוצרו על ידי קליפורד ושערי t". מידע קוונטי. מחשוב. 13, 607–630 (2013). כתובת אתר: https://​/​dl.acm.org/​doi/​abs/​10.5555/​2535649.2535653.
https: / / dl.acm.org/ doi / abs / 10.5555 / 2535649.2535653

[70] ניקולס ברונר, ג'יימס שארם ותאמאס ורטסי. "בדיקת המבנה של הסתבכות רב-חלקית עם אי-שוויון פעמון". פיזי. הכומר לט. 108, 110501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.108.110501

[71] ג'וליה קמפה, הירוטדה קובאיאשי, קייג'י מאצומוטו, בן טונר ותומאס וידיק. "קשה להעריך משחקים מסובכים". SIAM Journal on Computing 40, 848–877 (2011).
https: / / doi.org/ 10.1137 / 090751293

[72] Yihui Quek, Eneet Kaur, ומארק M. Wilde. "הערכת עקבות מרובה משתנים בעומק קוונטי קבוע". Quantum 8, 1220 (2024).
https:/​/​doi.org/​10.22331/​q-2024-01-10-1220

[73] פיטר סלינגר. "קירוב קליפורד+T יעיל של מפעילי קוויביט בודדים". מידע קוונטי. מחשוב. 15, 159–180 (2015).

[74] ואדים קליוצ'ניקוב, דמיטרי מסלוב ומישל מוסקה. "קירוב מעשי של יחידות קוויביט בודדות על ידי מעגלים קוואנטיים של קליפורד ו-T". IEEE Transactions on Computers 65, 161–172 (2016).
https: / / doi.org/ 10.1109 / TC.2015.2409842

[75] ניל ג'יי רוס. "קירוב CLIFFORD+V אופטימלי ללא אנסילה של סיבובי Z". מידע קוונטי. מחשוב. 15, 932–950 (2015). כתובת אתר: https://​/​dl.acm.org/​doi/​abs/​10.5555/​2871350.2871354.
https: / / dl.acm.org/ doi / abs / 10.5555 / 2871350.2871354

[76] איתן ברנשטיין ואומש וזיראני. "תורת המורכבות הקוונטית". בהליכים של סימפוזיון ACM השנתי העשרים וחמישה על תורת המחשוב. עמודים 11–20. STOC '93 ניו יורק, ניו יורק, ארה"ב (1993). האגודה למכונות מחשוב.
https: / / doi.org/ 10.1145 / 167088.167097

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

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

[79] אינגו וגנר. "המורכבות של פונקציות בוליאניות". John Wiley $&$ Sons, Inc. USA (1987).

[80] הריברט וולמר. "מבוא למורכבות מעגלים: גישה אחידה". Springer Publishing Company, Incorporated. (2010). מהדורה 1. כתובת אתר: https://​/​link.springer.com/​book/​10.1007/​978-3-662-03927-4.
https:/​/​link.springer.com/​book/​10.1007/​978-3-662-03927-4

[81] ר סמולנסקי. "שיטות אלגבריות בתורת הגבולות התחתונים למורכבות מעגל בוליאני". בהליכים של סימפוזיון ACM השנתי התשעה עשר על תורת המחשוב. עמודים 77–82. STOC '87 ניו יורק, ניו יורק, ארה"ב (1987). האגודה למכונות מחשוב.
https: / / doi.org/ 10.1145 / 28395.28404

[82] ג'ייקומאר רדהקרישנן. "גבולות טובים יותר לנוסחאות סף". בשנת [1991] סימפוזיון השנתי ה-32 של הליכים של יסודות מדעי המחשב. עמודים 314–323. IEEE Computer Society (1991).
https: / / doi.org/ 10.1109 / SFCS.1991.185384

[83] מייקל ג'יי פישר, אלברט אר מאייר ומייקל ס פטרסון. "$Omega(Nlog n)$ גבולות תחתונים על אורך נוסחאות בוליאניות". SIAM J. Comput. 11, 416–427 (1982).
https: / / doi.org/ 10.1137 / 0211033

[84] סנג'יב ארורה ובועז ברק. "מורכבות חישובית: גישה מודרנית". הוצאת אוניברסיטת קיימברידג'. ארה"ב (2009). מהדורה 1. כתובת אתר: https://​/​dl.acm.org/​doi/​abs/​10.5555/​1540612.
https: / / dl.acm.org/ doi / abs / 10.5555 / 1540612

[85] סקוט אהרונסון. "כמה מבנה נדרש להאצות קוונטיות ענקיות?" (2022). arXiv:2209.06930.
arXiv: 2209.06930

[86] דיוויד א ברינגטון. "תוכניות הסתעפות בגודל פולינום מוגבל מכירות בדיוק את השפות הללו ב-NC1". כתב עת למדעי המחשב והמערכת 38, 150–164 (1989).
https:/​/​doi.org/​10.1016/​0022-0000(89)90037-8

[87] סקוט אהרונסון ואלכס ארכיפוב. "המורכבות החישובית של אופטיקה לינארית". בהליכים של סימפוזיון ACM השנתי הארבעים ושלושה על תורת המחשוב. עמודים 333–342. STOC '11 ניו יורק, ניו יורק, ארה"ב (2011). האגודה למכונות מחשוב.
https: / / doi.org/ 10.1145 / 1993636.1993682

[88] פיטר וו שור. "אלגוריתמים של זמן פולינומי לפיקטוריזציה ראשונית וללוגריתמים בדידים במחשב קוונטי". SIAM Review 41, 303–332 (1999).
https: / / doi.org/ 10.1137 / S0036144598347011

[89] דניאל אר סיימון. "על כוחו של חישוב קוונטי". SIAM Journal on Computing 26, 1474–1483 (1997).
https: / / doi.org/ 10.1137 / S0097539796298637

[90] ז'יל בראסארד, הארי בוהרמן, נואה לינדן, אנדרה אלן מתות, אלן טאפ ואונגר פאלק. "מגבלה על אי-מקומיות בכל עולם שבו מורכבות התקשורת אינה טריוויאלית". פיזי. הכומר לט. 96, 250401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.96.250401

[91] וים ואן דאם. "השלכות בלתי סבירות של אי-לוקאליות סופר חזקה". מחשוב טבעי 12, 9–12 (2013).
https:/​/​doi.org/​10.1007/​s11047-012-9353-6

[92] מתיו איימי ומישל מוסקה. "אופטימיזציה של T-Count וקודי ריד-מולר". IEEE Transactions on Information Theory 65, 4771–4784 (2019).
https: / doi.org/â € ‹10.1109 / TIT.2019.2906374

[93] פיטר בורגסר, מייקל קלוזן ומוחמד א שוקרולהי. "תיאוריית המורכבות האלגברית". כרך 315. Springer Science & Business Media. (2013). כתובת אתר: https://​/​dl.acm.org/​doi/​abs/​10.5555/​1965416.
https: / / dl.acm.org/ doi / abs / 10.5555 / 1965416

[94] גואנג האו נמוך ואייזק ל. צ'ואנג. "סימולציה המילטונית אופטימלית על ידי עיבוד אותות קוונטי". פיזי. הכומר לט. 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[95] ג'ונגוואן האה. "פירוק מוצר של פונקציות מחזוריות בעיבוד אותות קוונטי". Quantum 3, 190 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-190

[96] סקוט אהרונסון, שלו בן דוד, רובין כותרי, שראבס ראו ואבישי טל. "השלכות תואר לעומת תואר משוער והשלכות קוונטיות של משפט הרגישות של הואנג". בהליכים של סימפוזיון ACM SIGACT השנתי ה-53 על תורת המחשוב. עמודים 1330–1342. STOC 2021 ניו יורק, ניו יורק, ארה"ב (2021). האגודה למכונות מחשוב.
https: / / doi.org/ 10.1145 / 3406325.3451047

[97] האו הואנג. "תתי גרפים מושרים של היפרקוביות והוכחה להשערת הרגישות". Annals of Mathematics 190, 949–955 (2019).
https: / / doi.org/ 10.4007 / annals.2019.190.3.6

[98] אנדריס אמביניס, קספרס באלודיס, אלכסנדרס בלובס, טרוי לי, מיקלוש סנטה וג'וריס סמוטרובס. "הפרדות במורכבות שאילתה בהתבסס על פונקציות מצביע". J. ACM 64 (2017).
https: / / doi.org/ 10.1145 / 3106234

[99] פיטר הייר ורוברט ספאלק. "מעגלים קוונטיים עם מניפה בלתי מוגבלת". בתוך הלמוט אלט ומישל חביב, עורכים, STACS 2003. עמודים 234–246. ברלין, היידלברג (2003). שפרינגר ברלין היידלברג.
https:/​/​doi.org/​10.1007/​3-540-36494-3_22

[100] Austin K Daniel, Yingyue Zhu, C Huerta Alderete, Vikas Buchemmavari, Alaina M Green, Nhung H Nguyen, Tyler G Thurtell, Andrew Zhao, Norbert M Linke, ו-Akimasa Miyake. "יתרון חישובי קוונטי מעיד על ידי משחקים לא מקומיים עם מצב האשכול המחזורי". פיזי. ר' מחקר 4, 033068 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033068

[101] פול הרינגר ורוברט ראוסנדורף. "סיווג של חוט קוונטי מבוסס מדידה במייצב PEPS". Quantum 7, 1041 (2023).
https:/​/​doi.org/​10.22331/​q-2023-06-12-1041

[102] אבישק אנאנד. "על כוחם של מעגלים קוונטיים וקלסיים משולבים בעומק נמוך". תזה לתואר שני. אוניברסיטת ווטרלו. (2022). כתובת אתר: https://​/​uwspace.uwaterloo.ca/​handle/​10012/​18805.
https://uwspace.uwaterloo.ca/ ידית/10012/18805

[103] ג'ון פרסקיל. "מחשוב קוונטי בעידן NISQ ומעבר לו". Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[104] Bülent Demirel, Weikai Weng, Christopher Thalacker, Matty Hoban, and Stefanie Barz. "מתאמים לחישוב וחישוב למתאמים". npj Quantum Information 7, 1–8 (2021).
https:/​/​doi.org/​10.1038/​s41534-020-00354-2

[105] Manoranjan Swain, Amit Rai, Bikash K Behera, ו-Prasanta K Panigrahi. "הדגמה נסיונית של הפרות אי השוויון של מרמין ושל סבטליצ'ני למדינות W ו-GHZ". Quantum Information Processing 18, 218 (2019).
https:/​/​doi.org/​10.1007/​s11128-019-2331-5

[106] בו יאנג, רודי ריימונד, הירושי אימאי, היונגסוק צ'אנג והידפומי היראישי. "בדיקת אי-שוויון פעמונים ניתנים להרחבה עבור מצבי גרף קוונטי במכשירי ibm קוונטים". IEEE Journal on Emerging and Selected Topics in Circuits and Systems 12, 638–647 (2022).
https:/​/​doi.org/​10.1109/​JETCAS.2022.3201730

[107] F. Baccari, R. Augusiak, I. Šupić, J. Tura, and A. Acín. "אי שוויון פעמון ניתנים להרחבה עבור מצבי גרף קיוביט ובדיקה עצמית חזקה". פיזי. הכומר לט. 124, 020402 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.124.020402

[108] Ken X Wei, Isaac Lauer, Srikanth Srinivasan, Neereja Sundaresan, Douglas T McClure, David Toyli, David C McKay, Jay M Gambetta, and Sarah Sheldon. "אימות מצבי גרינברגר-הורן-זיילינגר סבוכים רב-חלקיים באמצעות קוהרנטיות קוונטית מרובות". פיזי. Rev. A 101, 032343 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.032343

[109] Wei-Jia Huang, Wei-Chen Chien, Chien-Hung Cho, Che-Chun Huang, Tsung-Wei Huang, and Ching-Ray Chang. "אי השוויון של Mermin של קיוביטים מרובים עם מדידות אורתוגונליות במערכת IBM Q 53-qubit". הנדסה קוונטית 2, e45 (2020).
https://doi.org/​10.1002/​que2.45

[110] מירון שפר, דניאל אזס ועמנואל ג' דלה טורה. "משחקים קוונטיים לא מקומיים עם שישה קוביטים רועשים בענן". Advanced Quantum Technologies 5, 2100081 (2022).
https: / / doi.org/ 10.1002 / qute.202100081

[111] Vedran Dunjko, Theodoros Kapourniotis, and Elham Kashefi. "מחשוב קלאסי מאובטח משופר קוונטי". מידע קוונטי. מחשוב. 16, 61–86 (2016).

[112] סטפני בארז, Vedran Dunjko, Florian Schlederer, Merritt Moore, Elham Kashefi, Ian A. Walmsley. "מחשוב מואצל משופר באמצעות קוהרנטיות". פיזי. ר' א 93, 032339 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.032339

[113] מרקו קלמנטי, אנה פפה, אנדראס אקשטיין, איאן א. וולמסלי, אלהם קשפי וסטפני בארז. "חישוב רב-צדדי קלאסי באמצעות משאבים קוונטיים". סקירה פיזית A 96, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062317

[114] נאסיר אחמד וקאמיסטי ראמאוהן ראו. "טרנספורמציה של וולש-האמרד". טרנספורמציות אורתוגונליות לעיבוד אותות דיגיטלי. עמודים 99–152. ספרינגר (1975).

[115] מייקל א נילסן ואייזק ל צ'ואנג. "חישוב קוונטי ומידע קוונטי: מהדורת יום השנה ה-10". הוצאת אוניברסיטת קיימברידג'. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

[116] פיליפ פיינסילבר ויז'י קוצ'יק. "פולינומים קראוטצ'וק ומטריצות קראוטצ'וק". עמודים 115–141. ההתקדמות האחרונה בהסתברות יישומית. ספרינגר ארה"ב. בוסטון, MA (2005).
https:/​/​doi.org/​10.1007/​0-387-23394-6_5

[117] פיליפ פיינסילבר ורנה שוט. "קראוטצ'וק טרנספורמציות והתהפכויות". עלון למדעים מתמטיים עמודים 1–19 (2018).
https:/​/​doi.org/​10.1007/​s13373-018-0132-2

[118] M. Stobińska, A. Buraczewski, M. Moore, WR Clements, JJ Renema, SW Nam, T. Gerrits, A. Lita, WS Kolthammer, A. Eckstein, and IA Walmsley. "הפרעות קוונטיות מאפשרות עיבוד מידע קוונטי בזמן קבוע". Science Advances 5, eaau9674 (2019).
https: / / doi.org/ 10.1126 / sciadv.aau9674

[119] רבינדרן קנן ואחים בכם. "אלגוריתמים פולינומיים לחישוב הצורות הרגילות של סמית' והרמיט של מטריצה ​​שלמה". SIAM Journal on Computing 8, 499–507 (1979).
https: / / doi.org/ 10.1137 / 0208040

[120] ג'וש אלמן ווירג'יניה ואסילבסקה וויליאמס. "שיטת לייזר מעודנת וכפל מטריצה ​​מהיר יותר". בהליכים של סימפוזיון ACM-SIAM השנתי שלושים ושניים על אלגוריתמים בדידים. עמוד 522–539. SODA '21USA (2021). החברה למתמטיקה תעשייתית ויישומית.
https: / / doi.org/ 10.1137 / 1.9781611976465.32

מצוטט על ידי

מאמר זה מתפרסם בקוונטים תחת התקציב ייחוס Creative Commons 4.0 הבינלאומי (CC BY 4.0) רישיון. זכויות יוצרים נשארות עם בעלי זכויות היוצרים המקוריים כמו המחברים או מוסדותיהם.

ספוט_ימג

המודיעין האחרון

ספוט_ימג

זכויות יוצרים @ 2024 Plato Technologies Inc.