ניתן ללמוד PAC כראוי אם ורק אם $textsf{RP}=textsf{NP}$

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

עוקב: 0

המחלקה למדעי המחשב, אוניברסיטת טקסס באוסטין

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

תַקצִיר

בהינתן מערך נתונים של מצבי קלט, מדידות והסתברויות, האם ניתן לחזות ביעילות את הסתברויות המדידה הקשורות למעגל קוונטי? עבודה אחרונה של קארו ודטה [19] חקר את הבעיה של לימוד מעגלים קוונטיים של PAC במובן תיאורטי של מידע, והותיר שאלות פתוחות של יעילות חישובית. בפרט, מחלקה מועמדת אחת של מעגלים שעבורם יתכן למידה יעילה הייתה זו של מעגלי קליפורד, מכיוון שמערכת המצבים המקבילה שנוצרת על ידי מעגלים כאלה, המכונים מצבי מייצב, ידועים כניתנים ללמידה יעילה של PAC [44]. כאן אנו מספקים תוצאה שלילית, המראה שלמידה נכונה של מעגלי CNOT עם שגיאה 1/ poly($n$) קשה ללומדים קלאסיים אלא אם כן $textsf{RP = NP}$, ששוללת את האפשרות של לומדים חזקים בהנחות תאורטיות סטנדרטיות של מורכבות. בתור האנלוגי הקלאסי ותת-הקבוצה של מעגלי קליפורד, זה מוביל באופן טבעי לתוצאת קשיות גם עבור מעגלי קליפורד. בנוסף, אנו מראים שאם $textsf{RP = NP}$ אז היו קיימים אלגוריתמי למידה תקינים יעילים עבור מעגלי CNOT וקליפורד. לפי טיעונים דומים, אנו מוצאים גם שלומד קוונטי יעיל עבור מעגלים כאלה קיים אם ורק אם $textsf{NP ⊆ RQP}$. אנו משאירים את בעיית הקשיחות ללמידה לא נכונה או שגיאת $mathcal{O(1)}$ פתוחה לעבודה עתידית.

► נתוני BibTeX

@article{Liang2023cliffordcircuitscan, doi = {10.22331/q-2023-06-07-1036}, url = {https://doi.org/10.22331/q-2023-06-07-1036}, {title = {קליפורד ניתן להרוויח מעגלים {P}באופן {PAC} {L}אם ורק אם {$textsf{RP}=textsf{NP}$}}, מחבר = {Liang, Daniel}, יומן = {{Quantum}} , issn = {2521-327X}, מוציא לאור = {{Verein zur F{"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, נפח = {7}, עמודים = {1036}, חודש = יוני, שנה = {2023} }

► הפניות

[1] סקוט אהרונסון. יכולת הלמידה של מצבים קוונטיים. הליכים של החברה המלכותית A: Mathematical, Physical and Engineering Sciences, 463 (2088): 3089–3114, 2007. 10.1098/rspa.2007.0113.
https: / / doi.org/ 10.1098 / rspa.2007.0113

[2] סקוט אהרונסון. טומוגרפיית צללים של מצבים קוונטיים. ב-Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 325–338, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355599. 10.1145/3188745.3188802.
https: / / doi.org/ 10.1145 / 3188745.3188802

[3] סקוט אהרונסון ודניאל גוטסמן. סימולציה משופרת של מעגלי מייצב. Physical Review A, 70 (5): 052328, 2004. 10.1103/physreva.70.052328.
https: / / doi.org/ 10.1103 / physreva.70.052328

[4] JB Altepeter, D. Branning, E. Jeffrey, TC Wei, PG Kwiat, RT Thew, JL O'Brien, MA Nielsen, and AG White. טומוגרפיה של תהליך קוונטי בסיוע אנסילה. פיזי. Rev. Lett., 90: 193601, May 2003. 10.1103/PhysRevLett.90.193601.
https: / / doi.org/ 10.1103 / PhysRevLett.90.193601

[5] מרטין אנתוני ופיטר ל' בארטלט. למידת פונקציות מאינטרפולציה. קומבינטוריקה, הסתברות ומחשוב, 9 (3): 213–225, 2000. 10.1017/S0963548300004247.
https: / / doi.org/ 10.1017 / S0963548300004247

[6] Srinivasan Arunachalam ורונלד דה וולף. טור אורח: סקר של תורת הלמידה הקוונטית. חדשות ACM SIGACT, 48 (2): 41–67, 2017. 10.1145/3106700.3106710.
https: / / doi.org/ 10.1145 / 3106700.3106710

[7] Srinivasan Arunachalam ורונלד דה וולף. מורכבות דגימה קוונטית אופטימלית של אלגוריתמי למידה. בתוך Ryan O'Donnell, עורך, 32nd Computational Complexity Conference (CCC 2017), כרך 79 של Leibniz International Proceedings in Informatics (LIPIcs), עמודים 25:1–25:31, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-040-8. 10.4230/LIPIcs.CCC.2017.25.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.25

[8] Srinivasan Arunachalam, Alex B Grilo, והנרי יואן. למידת שאילתות סטטיסטיות קוונטיות. arXiv preprint arXiv:2002.08240, 2020. https://doi.org/10.48550/arXiv.2002.08240.
https:///doi.org/10.48550/arXiv.2002.08240
arXiv: 2002.08240

[9] Srinivasan Arunachalam, Alex Bredariol Grilo, ו- Aarthi Sundaram. קשיות קוונטית של לימוד מעגלים קלאסיים רדודים. SIAM Journal on Computing, 50 (3): 972–1013, 2021. 10.1137/20M1344202.
https: / / doi.org/ 10.1137 / 20M1344202

[10] צ'ארלס ה' בנט וג'יל בראסארד. הצפנה קוונטית: הפצת מפתח ציבורי והטלת מטבעות. מדעי המחשב העיוני, 560: 7–11, דצמבר 2014. ISSN 0304-3975. 10.1016/j.tcs.2014.05.025.
https: / doi.org/â € ‹10.1016 / j.tcs 2014.05.025

[11] צ'ארלס ה' בנט וסטיבן ג'יי ויזנר. תקשורת באמצעות מפעילי חלקיק אחד ושני על מצבי איינשטיין-פודולסקי-רוזן. פיזי. Rev. Lett., 69: 2881–2884, Nov 1992. 10.1103/PhysRevLett.69.2881.
https: / / doi.org/ 10.1103 / PhysRevLett.69.2881

[12] צ'ארלס ה' בנט, ז'יל בראסארד, קלוד קרפו, ריצ'רד ג'וזה, אשר פרס וויליאם ק. ווטרס. טלפורטציה של מצב קוונטי לא ידוע דרך ערוצי קלאסיים כפולים ואיינשטיין-פודולסקי-רוזן. פיזי. Rev. Lett., 70: 1895–1899, Mar 1993. 10.1103/PhysRevLett.70.1895.
https: / / doi.org/ 10.1103 / PhysRevLett.70.1895

[13] איתן ברנשטיין ואומש וזירני. תיאוריית המורכבות הקוונטית. כתב העת SIAM on Computing, 26 (5): 1411–1473, 1997. 10.1137 / S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

[14] אברהם בלום. קשיות חישוב של למידה. http:///www.cs.cmu.edu/ avrim/ML07/lect1007.pdf, 2015. כתובת URL http:///www.cs.cmu.edu/ avrim/ML07/lect1007.pdf. הערות הרצאה עבור CS 10-806 יסודות למידת מכונה ומדעי הנתונים.
http:///www.cs.cmu.edu/~avrim/ML07/lect1007.pdf

[15] אברים ל. בלום ורונלד ל. ריבסט. אימון רשת עצבית בת 3 צמתים הוא np-complete. רשתות עצביות, 5 (1): 117–127, 1992. ISSN 0893-6080. https://doi.org/10.1016/S0893-6080(05)80010-3.
https://doi.org/10.1016/S0893-6080(05)80010-3

[16] Anselm Blumer, A. Ehrenfeucht, David Haussler, and Manfred K. Warmuth. יכולת למידה ומימד ה-Vapnik-Chervonenkis. J. ACM, 36 (4): 929–965, אוקטובר 1989. ISSN 0004-5411. 10.1145/76359.76371.
https: / / doi.org/ 10.1145 / 76359.76371

[17] ג'ונתן F Buss, Gudmund S Frandsen, וג'פרי O Shalit. המורכבות החישובית של כמה בעיות של אלגברה לינארית. כתב עת למדעי המחשב והמערכת, 58 (3): 572–596, 1999. ISSN 0022-0000. https://doi.org/10.1006/jcss.1998.1608.
https: / / doi.org/ 10.1006 / jcss.1998.1608

[18] מתיאס סי קארו. סיווג בינארי עם מופעים קלאסיים ותוויות קוונטיות. Quantum Machine Intelligence, 3 (1), מאי 2021. 10.1007/s42484-021-00043-z.
https: / / doi.org/ 10.1007 / s42484-021-00043-z

[19] מתיא סי' קארו ואישון דאתא. פסאודו מימד של מעגלים קוונטיים. Quantum Machine Intelligence, 2 (2), נובמבר 2020. ISSN 2524-4914. 10.1007/s42484-020-00027-5.
https://doi.org/10.1007/s42484-020-00027-5

[20] Hao-Chung Cheng, Min-Hsiu Hsieh ו-Ping-Cheng Yeh. יכולת הלמידה של מדידות קוונטיות לא ידועות. מידע קוונטי. Comput., 16 (7–8): 615–656, מאי 2016. ISSN 1533-7146. 10.26421/QIC16.7-8-4.
https: / / doi.org/ 10.26421 / QIC16.7-8-4

[21] אייזק ל. צ'ואנג ו-MA Nielsen. מרשם לקביעה ניסיונית של הדינמיקה של קופסה שחורה קוונטית. Journal of Modern Optics, 44 (11-12): 2455–2467, 1997. 10.1080/09500349708231894.
https: / / doi.org/ 10.1080 / 09500349708231894

[22] קאי-מין צ'ונג והאן-הסואן לין. אלגוריתמים יעילים לדוגמה ללמידת ערוצים קוונטיים במודל PAC ובעיית אפליה במצב משוער. ב-Min-Hsiu Hsieh, עורך, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), כרך 197 של Leibniz International Proceedings in Informatics (LIPIcs), עמודים 3:1–3:22, Dagstuhl, Germany, 2021. Leibniz Informatik International. ISBN 978-3-95977-198-6. 10.4230/LIPIcs.TQC.2021.3.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2021.3

[23] עמית דניאלי ושי שלו-שוורץ. מגבלות תיאורטיות של מורכבות בלימוד dnf's. בתוך ויטלי פלדמן, אלכסנדר רחלין ואוהד שמיר, עורכים, הכנס השנתי ה-29 לתיאוריית הלמידה, כרך 49 של Proceedings of Machine Learning Research, עמודים 815–830, אוניברסיטת קולומביה, ניו יורק, ניו יורק, ארה"ב, 23–26 ביוני 2016. PMLR. כתובת האתר https:///proceedings.mlr.press/v49/daniely16.html.
https:///proceedings.mlr.press/v49/daniely16.html

[24] סטיבן טי פלמיה, דיוויד גרוס, יי-קאי ליו וג'נס אייזרט. טומוגרפיה קוונטית באמצעות חישה דחוסה: גבולות שגיאה, מורכבות מדגם ואומדנים יעילים. New Journal of Physics, 14 (9): 095022, ספטמבר 2012. 10.1088/1367-2630/14/9/095022.
https://doi.org/10.1088/1367-2630/14/9/095022

[25] פול וו. גולדברג ומארק אר ג'רום. מגביל את ממד ה-Vapnik-Chervonenkis של מחלקות מושגים בפרמטרים של מספרים ממשיים. למידת מכונה, 18: 131–148, 1995. 10.1007/BF00993408.
https: / / doi.org/ 10.1007 / BF00993408

[26] דניאל גוטסמן. קודי מייצב ותיקון שגיאות קוונטי, 1997.

[27] דניאל גוטסמן. ייצוג הייזנברג של מחשבים קוונטיים, 1998.

[28] Venkatesan Guruswami ו Prasad Raghavendra. קשיות של לימוד חצאי חללים עם רעש. SIAM Journal on Computing, 39 (2): 742–765, 2009. 10.1137/070685798.
https: / / doi.org/ 10.1137 / 070685798

[29] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. טומוגרפיה אופטימלית לדוגמא של מצבים קוונטיים. IEEE Transactions on Information Theory, עמודים 1–1, 2017. ISSN 1557-9654. 10.1109/tit.2017.2719044.
https: / / doi.org/ 10.1109 / tit.2017.2719044

[30] ניקה הגטלאב. הרצאה 9: קשיות הלמידה. https://www.cs.cornell.edu/courses/cs6781/2020sp/lectures/09-hardness1.pdf, 2020. כתובת URL https:///www.cs.cornell.edu/ courses/cs6781/2020sp/lectures/09-hardness1.pdf. הערות הרצאה עבור CS6781 - יסודות תיאורטיים של למידת מכונה.
https:///www.cs.cornell.edu/courses/cs6781/2020sp/lectures/09-hardness1.pdf

[31] הסין-יואן הואנג, ריצ'רד קואנג וג'ון פרסקיל. חיזוי תכונות רבות של מערכת קוונטית ממעט מאוד מדידות. פיזיקת הטבע, אוקטובר 2020. 10.1038/s41567-020-0932-7.
https://doi.org/10.1038/s41567-020-0932-7

[32] יונתן כץ. הערות על תיאוריית המורכבות הרצאה 3. https://www.cs.umd.edu/jkatz/complexity/f11/lecture3.pdf, 2011. URL https:///www.cs.umd.edu/ jkatz/complexity/f11/lecture3. הערות הרצאה עבור CS 652 - תורת המורכבות.
https:///www.cs.umd.edu/~jkatz/complexity/f11/lecture3.pdf

[33] מיכאל חריטונוב. קשיות קריפטוגרפית של למידה ספציפית להפצה. ב-Proceedings of the 93th Annual ACM Symposium on Theory of Computing, STOC '372, עמוד 381–1993, ניו יורק, ניו יורק, ארה"ב, 0897915917. Association for Computing Machinery. ISBN 10.1145. 167088.167197/XNUMX.
https: / / doi.org/ 10.1145 / 167088.167197

[34] J. Kleinberg and E. Tardos. עיצוב אלגוריתם. Pearson Education, 2022. ISBN 9780132131087. URL https:///books.google.com/books?id=GORecgAACAAJ.
https:///books.google.com/books?id=GORecgAACAAJ

[35] אדם קליבנס. מודל הלמידה של PAC. https://www.cs.utexas.edu/klivans/f06lec2.pdf, 2005. כתובת URL https:///www.cs.utexas.edu/klivans/f06lec2.pdf. הערות הרצאה עבור CS 395T למידה חישובית.
https:///www.cs.utexas.edu/~klivans/f06lec2.pdf

[36] רוברט קניג וג'ון א' סמולין. כיצד לבחור ביעילות אלמנט שרירותי של קבוצת קליפורד. Journal of Mathematical Physics, 55 (12): 122202, דצמבר 2014. ISSN 1089-7658. 10.1063/1.4903507.
https: / / doi.org/ 10.1063 / 1.4903507

[37] ריצ'רד קואנג ודיוויד גרוס. מצבי מייצב של Qubit הם 3-עיצובים השלכתיים מורכבים, 2015.

[38] צ'ינג-יי לאי והאו-צ'ונג צ'נג. לימוד מעגלים קוונטיים של כמה שערי t. IEEE Transactions on Information Theory, עמודים 1–1, 2022. 10.1109/TIT.2022.3151760.
https: / doi.org/â € ‹10.1109 / TIT.2022.3151760

[39] ריצ'רד א' לואו. למידה ובדיקה של אלגוריתמים עבור קבוצת קליפורד. פיזי. Rev. A, 80: 052314, נובמבר 2009. 10.1103/PhysRevA.80.052314.
https: / / doi.org/ 10.1103 / PhysRevA.80.052314

[40] אשלי מונטנרו. לימוד מצבי מייצב על ידי דגימת בל, 2017.

[41] ריאן אודונל וג'ון רייט. טומוגרפיה קוונטית יעילה. בהליכים של סימפוזיון ACM השנתי הארבעים ושמונה על תורת המחשוב, STOC '16, עמוד 899–912, ניו יורק, ניו יורק, ארה"ב, 2016. Association for Computing Machinery. ISBN 9781450341325. 10.1145/2897518.2897544.
https: / / doi.org/ 10.1145 / 2897518.2897544

[42] ריאן אודונל וג'ון רייט. טומוגרפיה קוונטית יעילה ii. ב-Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 962–974, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450345286. 10.1145/3055399.3055454.
https: / / doi.org/ 10.1145 / 3055399.3055454

[43] Yihui Quek, Srinivasan Arunachalam, וג'ון A Smolin. למידה פרטית מרמזת על יציבות קוונטית. בתוך M. Ranzato, A. Beygelzimer, Y. Dauphin, PS Liang, and J. Wortman Vaughan, עורכים, Advances in Neural Information Processing Systems, כרך 34, עמודים 20503–20515. Curran Associates, Inc., 2021. כתובת URL https:///proceedings.neurips.cc/paper/2021/file/abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf.
https://proceedings.neurips.cc/paper/2021/file/abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf

[44] אנדריאה רוצ'טו. מצבי מייצב ניתנים ללמידה יעילה של PAC. מידע וחישוב קוונטי, 18 (7-8): 541–552, 2018. 10.26421/qic18.7-8-1.
https: / / doi.org/ 10.26421 / qic18.7-8-1

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

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

[47] לסלי ג'י ואליאנט. תיאוריה של הנלמד. תקשורת של ה-ACM, 27 (11): 1134–1142, 1984. 10.1145/1968.1972.
https: / / doi.org/ 10.1145 / 1968.1972

[48] יואוט ואן דן ברג. שיטה פשוטה לדגימה אקראית של מפעילי קליפורד. בשנת 2021 כנס IEEE הבינלאומי למחשוב והנדסה קוונטי (QCE), עמודים 54–59, 2021. 10.1109/QCE52317.2021.00021.
https: / / doi.org/ 10.1109 / QCE52317.2021.00021

[49] Mithuna Yoganathan. תנאי שבו סימולציה קלאסית מרמזת על יכולת למידה יעילה של המדינה, 2019.

[50] Huangjun Zhu. קבוצות מולטיקווביט קליפורד הן 3 עיצובים אחידים. פיזי. Rev. A, 96: 062336, Dec 2017. 10.1103/PhysRevA.96.062336.
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

מצוטט על ידי

[1] לורנצו ליאונה, סלווטורה FE אוליביירו, סת לויד ואליוסקיה חממה, "לימוד מפענחים יעילים למערבלים קוונטיים כמו-כאוטיים", arXiv: 2212.11338, (2022).

[2] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder, "אלגוריתמים אופטימליים ללימוד מצבי פאזה קוונטיים", arXiv: 2208.07851, (2022).

[3] Anurag Anshu ו-Srinivasan Arunachalam, "סקר על המורכבות של למידת מצבים קוונטיים", arXiv: 2305.20069, (2023).

הציטוטים לעיל הם מ- מודעות SAO / NASA (עודכן לאחרונה בהצלחה 2023-06-07 22:21:42). הרשימה עשויה להיות שלמה מכיוון שלא כל בעלי האתרים מספקים נתוני ציטוט ראויים ומלאים.

On השירות שצוטט על ידי Crossref לא נמצאו נתונים על ציטוט עבודות (ניסיון אחרון 2023-06-07 22:21:40)

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

הפצת תוכן ויחסי ציבור מופעל על ידי SEO. קבל הגברה היום.
EVM Finance. ממשק מאוחד למימון מבוזר. גישה כאן.
Quantum Media Group. IR/PR מוגבר. גישה כאן.
PlatoAiStream. Web3 Data Intelligence. הידע מוגבר. גישה כאן.
מקור: https://quantum-journal.org/papers/q-2023-06-07-1036/

בול זמן: יוני 7, 2023

בול זמן: יאן 11, 2024

ניתן ללמוד את מעגלי קליפורד כראוי PAC אם ורק אם $textsf{RP}=textsf{NP}$

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

תַקצִיר

► נתוני BibTeX

► הפניות

מצוטט על ידי

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

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

תרדמת הגשה עונתית

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

שיטת אימות הפרד-וכבש עבור חישוב קוונטי רועש בקנה מידה בינוני

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

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

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

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

פרדוקס הרדי מוטה לחילוץ אקראיות בלתי תלוי במכשיר

מעבדים קוונטיים Fermion-Qudit להדמיית תיאוריות מד סריג עם חומר

אודות

חיפוש אנכי ו- Ai

פלטפורמה

שמור על קשר

חֶשְׁבּוֹן