1המחלקה לפיזיקה, ETH ציריך, שוויץ
2המכון ללימודים עיוניים, ETH ציריך, שוויץ
מצא את העיתון הזה מעניין או רוצה לדון? סקייט או השאירו תגובה ב- SciRate.
תַקצִיר
הוכחה לקוונטיות היא סוג של פרוטוקול אתגר-תגובה שבו מאמת קלאסי יכול לאשר ביעילות את $textit{quantum advantage}$ של מוכיח לא מהימן. כלומר, מוכיח קוונטי יכול לענות בצורה נכונה על האתגרים של המאמת ולהתקבל, בעוד שכל מוכיח קלאסי בזמן פולינום יידחה בסבירות גבוהה, בהתבסס על הנחות חישוביות מתקבלות על הדעת. כדי לענות על האתגרים של המאמת, הוכחות קיימות לקוונטיות דורשות בדרך כלל מהמוכיח הקוונטי לבצע שילוב של מעגלים ומדידות קוונטיים בגודל פולינום.
במאמר זה, אנו נותנים שתי הוכחות למבני קוונטיות שבהן המוכיח צריך לבצע רק $textit{מעגלים קוונטיים בעומק קבוע}$ (ומדידות) יחד עם חישוב קלאסי של עומק לוג. הבנייה הראשונה שלנו היא מהדר גנרי המאפשר לנו לתרגם את כל ההוכחות הקיימות לקוונטיות לגרסאות עומק קוונטי קבוע. הבנייה השנייה שלנו מבוססת על בעיית $textit{learning with rounding}$, ומניבה מעגלים עם עומק קצר יותר ודורשים פחות קיוביטים מהבנייה הגנרית. בנוסף, למבנה השני יש גם חוסן מסוים נגד רעש.
► נתוני BibTeX
► הפניות
[1] סקוט אהרונסון ואלכס ארכיפוב. המורכבות החישובית של אופטיקה ליניארית. בהליכי סימפוזיון ACM השנתי הארבעים ושלושה על תורת המחשוב, עמודים 333–342, 2011.
https: / / doi.org/ 10.1145 / 1993636.1993682
[2] פרנק ארוט, קונאל אריה, ריאן בבוש, דייב בייקון, ג'וזף סי ברדין, רמי ברנדס, רופאק ביזוואז, סרג'יו בוישו, פרננדו GSL ברנדאו, דיוויד א. בואל ועוד. עליונות קוונטית באמצעות מעבד מוליך-על הניתן לתכנות. טבע, 574(7779):505–510, 2019.
https://doi.org/10.1038/s41586-019-1666-5
[3] MD SAJID ANIS, Abby-Mitchell, Héctor Abraham, AduOffei, et al. Qiskit: מסגרת קוד פתוח עבור מחשוב קוונטי, 2021.
[4] סנג'ייב ארורה ובועז ברק. מורכבות חישובית: גישה מודרנית. הוצאת אוניברסיטת קיימברידג ', 2009.
[5] סקוט אהרונסון וליג'י צ'ן. יסודות תיאורטיים של מורכבות של ניסויי עליונות קוונטית. ב-Proceedings of the 32nd Computational Complexity Conference, CCC '17, עמודים 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
[6] סקוט אהרונסון וסם גאן. על הקשיות הקלאסית של זיוף מידוד חוצה אנטרופיה ליניארית. תורת המחשוב, 16(11):1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[7] ב' אפלבאום, י' ישי, וע' קושילוביץ. קריפטוגרפיה ב-${NC}^0$. בסימפוזיון השנתי ה-45 של IEEE על יסודות מדעי המחשב, עמודים 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak, ו-Daniel Wichs. למידה עם עיגול, ביקור מחדש. ב-Advances in Cryptology – CRYPTO 2013, עמודים 57–74, ברלין, היידלברג, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] דיוויד א ברינגטון. תוכניות הסתעפות בגודל פולינום מוגבל מזהות בדיוק את השפות האלה ב-${NC}^1$. כתב עת למדעי המחשב והמערכת, 38(1):150–164, 1989.
https://doi.org/10.1016/0022-0000(89)90037-8
[10] צביקה ברקרסקי, פול כריסטיאנו, אורמילה מהדב, אומש וזיראני ותומאס וידיק. בדיקה קריפטוגרפית של קוונטיות ואקראיות הניתנת לאישור ממכשיר קוונטי יחיד. בשנת 2018 IEEE סימפוזיון שנתי 59 על יסודות מדעי המחשב (FOCS), עמודים 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] קולין ד' ברוזביץ', ג'ון צ'יבריני, רוברט מקונל וג'רמי מ' סייג'. מחשוב קוונטי לכודים: התקדמות ואתגרים. ביקורות פיזיקה יישומית, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] אדם בולנד, ביל פפרמן, צ'ינמאי נירקה ואומש וזיראני. על המורכבות והאימות של דגימת מעגל אקראית קוונטית. טבע פיזיקה, 15(2):159–163, פברואר 2019.
https://doi.org/10.1038/s41567-018-0318-2
[13] סרג'יו בוישו, סרגיי וי איסקוב, ואדים N Smelyanskiy, ריאן בבוש, נאן דינג, ג'אנג ג'יאנג, מייקל ג'יי ברמנר, ג'ון מ. מרטיניס והרטמוט נבן. מאפיין עליונות קוונטית במכשירים לטווח הקרוב. טבע פיזיקה, 14(6):595–600, 2018.
https: / doi.org/â € ‹10.1038 / s41567-018-0124-x
[14] צביקה ברקרסקי, ונקטה קופולה, אומש וזיראני ותומאס וידיק. הוכחות פשוטות יותר של קוונטיות. בכנס ה-15 על התיאוריה של חישוב קוונטי, תקשורת וקריפטוגרפיה (TQC 2020), כרך 158 של Leibniz International Proceedings in Informatics (LIPIcs), עמודים 8:1–8:14, Dagstuhl, גרמניה, 2020. Schloss Dagstuhl–Leibniz- Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, כריס פייקרט ואלון רוזן. פונקציות פסאודורנדום וסריג. בהתקדמות בקריפטולוגיה – EUROCRYPT 2012, עמודים 719–737. שפרינגר ברלין היידלברג, 2012.
https://doi.org/10.1007/978-3-642-29011-4_42
[16] ג'ון פ. קלוזר, מייקל א הורן, אבנר שמעוני וריצ'רד א הולט. ניסוי מוצע לבדיקת תיאוריות מקומיות של משתנים נסתרים. מכתבי סקירה פיזית, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[17] מתיו קודרון, ג'לקס סטארק ותומס וידיק. יישוב מסחר לזמן: אקראיות הניתנת לאישור ממעגלים בעומק נמוך. תקשורת בפיזיקה מתמטית, 382(1):49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] ריצ'רד קליב וג'ון ווטרוס. מעגלים מקבילים מהירים להתמרת פורייה הקוונטית. בסימפוזיון השנתי ה-41 של הליכים על יסודות מדעי המחשב, עמודים 526–536. IEEE, 2000.
https: / / doi.org/ 10.1109 / SFCS.2000.892140
[19] פייר דוסארט. Autour de la fonction qui compte le nombre de nombres premiers. עבודת דוקטורט, Université de Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] אוסטין ג'י פאולר, מתאו מריאנטוני, ג'ון מ' מרטניס ואנדרו נ' קללנד. קודי שטח: לקראת חישוב קוונטי מעשי בקנה מידה גדול. סקירה פיזית A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] פרנסואה לה גאל. התכתבות פרטית, 2022.
[22] קרייג גידני ומרטין אקרה. כיצד להפעיל מספרי RSA שלמים של 2048 סיביות תוך 8 שעות באמצעות 20 מיליון קיוביטים רועשים. Quantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] אלכסנדרו גאורגיו ומתי ג'יי הובאן. קשה להעריך את האנטרופיה של יציאות מעגלים רדודים. arXiv preprint arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] שואיצ'י הירהרה ופרנסואה לה גאל. מבחן קוונטיות עם מעגלים קוונטיים בעומק קטן. בסימפוזיון הבינלאומי ה-46 על יסודות מתמטיים של מדעי המחשב (MFCS 2021), כרך 202 של Leibniz International Proceedings in Informatics (LIPIcs), עמודים 59:1–59:15, Dagstuhl, גרמניה, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] ארם וו הארו ואשלי מונטנרו. עליונות חישובית קוונטית. טבע, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] פיטר הייר ורוברט ספאלק. Quantum Fan-out הוא רב עוצמה. תורת המחשוב, 1(5):81–103, 2005.
https: / / doi.org/ 10.4086 / toc.2005.v001a005
[27] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, and Jianxin Chen. סימולציה קלאסית של מעגלי עליונות קוונטית. arXiv preprint arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] גרגורי ד' כהנמוקו-מאייר. זיוף נתונים קוונטיים: הבסה קלאסית של מבחן קוונטי מבוסס IQP. arXiv preprint arXiv:1912.05547, 2019.
https:///doi.org/10.48550/arXiv.1912.05547
arXiv: 1912.05547
[29] Gregory D. Kahanamoku-Mayer, Soonwon Choi, Umesh V. V. Vazirani, ו-Norman Y. Yao. יתרון קוונטי הניתן לאימות קלאסית ממבחן פעמון חישובי. טבע פיזיקה, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] ואדים ליובשבסקי, כריס פייקרט ועודד רגב. על סריג אידיאלי ולמידה עם שגיאות מעל טבעות. בכנס בינלאומי שנתי על התיאוריה והיישומים של טכניקות קריפטוגרפיות, עמודים 1–23. ספרינגר, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] אורמילה מהדב. אימות קלאסי של חישובים קוונטיים. בשנת 2018 IEEE 59th Annual Symposium on Foundations of Science Computer (FOCS), עמודים 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[32] מייקל א נילסן ואייזק צ'ואנג. חישוב קוונטי ומידע קוונטי, 2002.
[33] AS Popova ו-AN Rubtsov. פיצוח סף היתרון הקוונטי עבור דגימת בוזון גאוס. ב-Quantum 2.0 Conference and Exhibition, עמוד QW2A.15. Optica Publishing Group, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] ג'ון פרסקיל. מחשוב קוונטי בעידן NISQ ואילך. Quantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] מייקל או רבין. אלגוריתם הסתברותי לבדיקת ראשוניות. כתב עת לתורת המספרים, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] עודד רגב. על סריג, למידה עם שגיאות, קודים ליניאריים אקראיים והצפנה. Journal of the ACM (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[37] דן שפרד ומייקל ג'יי ברמנר. חישוב קוונטי לא מובנה באופן זמני. הליכים של החברה המלכותית א': מדעי המתמטיקה, הפיזיקה וההנדסה, 465(2105):1413–1439, 2009.
https: / / doi.org/ 10.1098 / rspa.2008.0443
[38] פיטר וו שור. אלגוריתמים לחישוב קוונטי: לוגריתמים נפרדים ופירוק. בסימפוזיון השנתי ה-35 של הליכים על יסודות מדעי המחשב, עמודים 124–134. IEEE, 1994.
https: / / doi.org/ 10.1109 / SFCS.1994.365700
[39] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han , Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao , Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, ו-Jian-Wei Pan. יתרון חישובי קוונטי חזק באמצעות מעבד קוונטי מוליך-על. פיזי. ר' לט., 127:180501, 2021.
https: / / doi.org/ 10.1103 / PhysRevLett.127.180501
[40] K Wright, KM Beck, Sea Debnath, JM Amini, Y Nam, N Grzesiak, JS Chen, NC Pisenti, M Chmielewski, C Collins, et al. השוואת מחשב קוונטי של 11 קיוביטים. תקשורת טבע, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. עיבוד מידע קוונטי עם מעגלים מוליכים-על: סקירה. דוחות על התקדמות בפיזיקה, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] אדם בן ווטס, רובין כותרי, לוק שייפר ואבישי טל. הפרדה אקספוננציאלית בין מעגלים קוונטיים רדודים ומעגלים קלאסיים רדודים ללא גבולות. בהליכים של סימפוזיון ACM SIGACT השנתי ה-51 על תורת המחשוב, עמודים 515–526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
[43] אנדרו צ'י-צ'יה יאו. כיצד ליצור ולהחליף סודות. בסימפוזיון השנתי ה-27 על יסודות מדעי המחשב (sfcs 1986), עמודים 162–167. IEEE, 1986.
https: / / doi.org/ 10.1109 / SFCS.1986.25
[44] Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He -ליאנג הואנג, יונג-הנג הואו, ליפינג לי, נה לי, שאווי לי, יואן לי, פוטיאן ליאנג, צ'ון לין, ג'ין לין, האוראן צ'יאן, דן קיאו, האו רונג, הונג סו, ליהוא סאן, ליאנגיואן וואנג, שייו וואנג. , Dachao Wu, Yulin Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei ג'או, ליאנג ג'ואו, צ'או-יאנג לו, צ'נג-ז'י פנג, שיאובו ג'ו וג'יאן-וויי פאן. יתרון חישובי קוונטי באמצעות דגימת מעגל אקראית של 60 קיוביטים 24 מחזורים. עלון המדע, 67(3):240–245, 2022.
https: / / doi.org/ 10.1016 / j.scib.2021.10.017
[45] Daiwei Zhu, Gregory D. Kahanamoku-Mayer, Laura Lewis, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidik, Umesh Vazirani, Norman Y. Yao, Marko Cetina, וכריסטופר מונרו. פרוטוקולים אינטראקטיביים עבור יתרון קוונטי הניתן לאימות קלאסית. arXiv preprint arXiv:2112.05156, 2021.
https:///doi.org/10.48550/arXiv.2112.05156
arXiv: 2112.05156
[46] האן-סן ז'ונג, הואי וואנג, יו-האו דנג, מינג-צ'נג צ'ן, לי-צ'או פנג, יי-האן לואו, ג'יאן צ'ין, דיאן וו, שינג דינג, יי הו, פנג הו, שיאו-יאן יאנג, ווי- Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. יתרון חישובי קוונטי באמצעות פוטונים. מדע, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
מצוטט על ידי
[1] נתנן טנטיוואסדאקארן, אשווין וישוואנת ורובן ורסן, "היררכיה של סדר טופולוגי מיחידות עומק סופיות, מדידה והזנה קדימה", arXiv: 2209.06202.
[2] סרגיי בראווי, אייזק קים, אלכסנדר קליש ורוברט קניג, "מעגלים אדפטטיביים בעומק קבוע למניפולציה של כל אדם לא-אבל". arXiv: 2205.01933.
[3] Daiwei Zhu, Gregory D. Kahanamoku-Mayer, Laura Lewis, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidik, Umesh. Vazirani, Norman Y. Yao, Marko Cetina, וכריסטופר מונרו, "פרוטוקולים אינטראקטיביים ליתרון קוונטי שניתן לאימות קלאסי", arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo, ודמיטרי ואסילייב, "-PRFs מפתח-הומומורפי-ספציפיים לכוכבים מרגרסיה לינארית ותורת הקבוצות הקיצוניות", arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, ו-Norman Y. Yao, "יתרון קוונטי שניתן לאימות קלאסי ממבחן פעמון חישובי", טבע פיזיקה 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, ואבישי טל, "On Certified Randomness from Quantum Advantage Experiments", arXiv: 2111.14846.
[7] Nai-Hui Chia ושי-האן הונג, "אימות קלאסי של עומק קוונטי", arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa, ו-Seiichiro Tani, "בדיקה עצמית חישובית למצבי קסם סבוכים", סקירה פיזית A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde, ו-Eneet Kaur, "הערכת עקבות מרובה משתנים בעומק קוונטי קבוע", arXiv: 2206.15405.
הציטוטים לעיל הם מ- מודעות SAO / NASA (עודכן לאחרונה בהצלחה 2022-09-21 12:16:02). הרשימה עשויה להיות שלמה מכיוון שלא כל בעלי האתרים מספקים נתוני ציטוט ראויים ומלאים.
On השירות המוזכר של קרוסרף לא נמצאו נתונים על ציטוט עבודות (ניסיון אחרון 2022-09-21 12:16:00)
מאמר זה מתפרסם בקוונטים תחת התקציב ייחוס Creative Commons 4.0 הבינלאומי (CC BY 4.0) רישיון. זכויות יוצרים נשארות עם בעלי זכויות היוצרים המקוריים כמו המחברים או מוסדותיהם.
