על קידוד בלוק קוונטי יעיל של אופרטורים פסאודו-דיפרנציאליים

על קידוד בלוק קוונטי יעיל של אופרטורים פסאודו-דיפרנציאליים

צומת המקור: 2694594

האויה לי1, הונגקאנג ני2, ו לקסינג יינג1,2

1המחלקה למתמטיקה, אוניברסיטת סטנפורד, סטנפורד, קליפורניה 94305
2המכון להנדסה חישובית ומתמטית, אוניברסיטת סטנפורד, סטנפורד, קליפורניה 94305

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

תַקצִיר

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

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

► נתוני BibTeX

► הפניות

[1] ד' אן ול' לין. פותר מערכת ליניארית קוונטית המבוסס על מחשוב קוונטי אדיאבטי אופטימלי בזמן ואלגוריתם אופטימיזציה משוערת קוונטית. ACM Transactions on Quantum Computing, 3: 1–28, 2022. 10.1145/​3498331.
https: / / doi.org/ 10.1145 / 3498331

[2] DW Berry, AM Childs, R. Cleve, R. Kothari ו-RD Somma. הדמיית דינמיקה המילטונית עם סדרת טיילור קטומה. מכתבי סקירה פיזית, 114: 090502, 2015. 10.1103/​PhysRevLett.114.090502.
https: / / doi.org/ 10.1103 / PhysRevLett.114.090502

[3] ג' ביילקין ול' מונזון. על קירוב פונקציות בסכומים מעריכי. Applied and Computational Harmonic Analysis, 19: 17–48, 2005. 10.1016/​j.acha.2005.01.003.
https:/​/​doi.org/​10.1016/​j.acha.2005.01.003

[4] ד' קאמפס ור' ואן ביאומן. אגדה: מעגלים קוונטיים משוערים מהירים עבור קידודי בלוק. בשנת 2022 כנס IEEE הבינלאומי למחשוב קוונטי והנדסה (QCE), עמודים 104–113. IEEE, 2022. 10.1109/​QCE53715.2022.00029.
https: / / doi.org/ 10.1109 / QCE53715.2022.00029

[5] D. Camps, L. Lin, R. Van Beeumen, ו-C. Yang. מעגלים קוונטיים מפורשים עבור קידודי בלוק של מטריצה ​​דלילה מסוימת. arXiv preprint arXiv:2203.10236, 2022. 10.48550/​arXiv.2203.10236.
https://​/​doi.org/​10.48550/​arXiv.2203.10236
arXiv: 2203.10236

[6] Y. Cao, A. Papageorgiou, I. Petras, J. Traub, and S. Kais. אלגוריתם קוונטי ותכנון מעגלים הפותרים את משוואת הרעיל. New Journal of Physics, 15 (1): 013021, 2013. 10.1088/​1367-2630/​15/​1/​013021.
https:/​/​doi.org/​10.1088/​1367-2630/​15/​1/​013021

[7] G. Castelazo, QT Nguyen, G. De Palma, D. Englund, S. Lloyd ו-BT Kiani. אלגוריתמים קוונטיים עבור קונבולוציית קבוצות, מתאם צולב ותמורות שוות ערך. Physical Review A, 106: 032402, 2022. 10.1103/​PhysRevA.106.032402.
https: / / doi.org/ 10.1103 / PhysRevA.106.032402

[8] R. Chao, D. Ding, A. Gilyen, C. Huang, and M. Szegedy. מציאת זוויות לעיבוד אותות קוונטי עם דיוק מכונה. arXiv preprint arXiv:2003.02831, 2020. 10.48550/​arXiv.2003.02831.
https://​/​doi.org/​10.48550/​arXiv.2003.02831
arXiv: 2003.02831

[9] AM Childs, R. Kothari, ו-RD Somma. אלגוריתם קוונטי למערכות של משוואות ליניאריות עם תלות משופרת באופן אקספוננציאלי בדייקנות. SIAM Journal on Computing, 46: 1920–1950, 2017. 10.1137/​16M1087072.
https: / / doi.org/ 10.1137 / 16M1087072

[10] AM Childs, J.-P. ליו, וא. אוסטרנדר. אלגוריתמים קוונטיים בעלי דיוק גבוה עבור משוואות דיפרנציאליות חלקיות. Quantum, 5: 574, 2021. 10.22331/​q-2021-11-10-574.
https:/​/​doi.org/​10.22331/​q-2021-11-10-574

[11] ד נחושת. טרנספורמציה פורייה משוערת שימושית בפקטור קוונטי. arXiv preprint quant-ph/​0201067, 2002. 10.48550/​arXiv.quant-ph/​0201067.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​0201067
arXiv: quant-ph / 0201067

[12] PC Costa, S. Jordan, ו-A. Ostrander. אלגוריתם קוונטי להדמיית משוואת הגלים. Physical Review A, 99: 012323, 2019. 10.1103/​PhysRevA.99.012323.
https: / / doi.org/ 10.1103 / PhysRevA.99.012323

[13] PC Costa, D. An, YR Sanders, Y. Su, R. Babbush, and DW Berry. פותר מערכות ליניאריות קוונטיות בקנה מידה אופטימלי באמצעות משפט אדיאבטי דיסקרטי. PRX Quantum, 3: 040303, 2022. 10.1103/​PRXQuantum.3.040303.
https: / / doi.org/ 10.1103 / PRXQuantum.3.040303

[14] AJ דה סילבה ופארק DK. מעגלים קוונטיים בעומק ליניארי עבור שערים מבוקרים מולטיקווביט. Physical Review A, 106: 042602, 2022. 10.1103/​PhysRevA.106.042602.
https: / / doi.org/ 10.1103 / PhysRevA.106.042602

[15] ל' דמנט ול' יינג. חישוב סמלים דיסקרטי. סקירת SIAM, 53: 71–104, 2011. 10.1137/​080731311.
https: / / doi.org/ 10.1137 / 080731311

[16] Y. Dong, X. Meng, KB Whaley, ול. Lin. הערכת פקטור פאזה יעילה בעיבוד אותות קוונטי. Physical Review A, 103: 042419, 2021. 10.1103/​PhysRevA.103.042419.
https: / / doi.org/ 10.1103 / PhysRevA.103.042419

[17] Y. Dong, L. Lin, H. Ni, and J. Wang. עיבוד אותות קוונטי אינסופי. arXiv preprint arXiv:2209.10162, 2022. 10.48550/​arXiv.2209.10162.
https://​/​doi.org/​10.48550/​arXiv.2209.10162
arXiv: 2209.10162

[18] A. Gilyén, Y. Su, GH Low, and N. Wiebe. טרנספורמציה של ערך יחיד קוונטי ומעבר לכך: שיפורים מעריכי עבור אריתמטיקה של מטריצה ​​קוונטית. הליכים של סימפוזיון ACM SIGACT השנתי ה-51 על תורת המחשוב, 2019. 10.1145/​3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366

[19] ל. גרובר וטי רודולף. יצירת סופרפוזיציות המתאימות להתפלגויות הסתברות הניתנות לשילוב יעיל. arXiv preprint quant-ph/​0208112, 2002. 10.48550/​arXiv.quant-ph/​0208112.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​0208112
arXiv: quant-ph / 0208112

[20] ג'יי הא. פירוק מוצר של פונקציות תקופתיות בעיבוד אותות קוונטיים. קוונטית, 3: 190, 2019. 10.22331 / q-2019-10-07-190.
https:/​/​doi.org/​10.22331/​q-2019-10-07-190

[21] AW Harrow, A. חסידים, and S. Lloyd. אלגוריתם קוונטי למערכות ליניאריות של משוואות. מכתבי סקירה פיזית, 103: 150502, 2009. 10.1103/​PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

[22] AY Kitaev. חישובים קוונטיים: אלגוריתמים ותיקון שגיאות. Russian Mathematical Surveys, 52: 1191, 1997. 10.1070/​RM1997v052n06ABEH002155.
https:/​/​doi.org/​10.1070/​RM1997v052n06ABEH002155

[23] AY Kitaev, A. Shen, MN Vyalyi, ו-MN Vyalyi. חישוב קלאסי וקוונטי. American Mathematical Soc., 2002. 10.1090/​gsm/​047.
https: / / doi.org/ 10.1090 / gsm / 047

[24] ל 'לין וי' טונג. סינון קוונטי אופטימלי מבוסס פולינום בעזרת יישום לפתרון מערכות לינאריות קוונטיות. קוונטית, 4: 361, 2020. 10.22331 / q-2020-11-11-361.
https:/​/​doi.org/​10.22331/​q-2020-11-11-361

[25] GH Low ו-IL Chuang. הדמיית המילטון אופטימלית על ידי עיבוד אותות קוונטי. מכתבי סקירה פיזית, 118: 010501, 2017. 10.1103/​PhysRevLett.118.010501.
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[26] א.מהסינגה וג'יי וואנג. מעגלים קוונטיים יעילים למטריצות טופליץ והאנקל. Journal of Physics A: Mathematical and Theoretical, 49: 275301, 2016. 10.1088/​1751-8113/​49/​27/​275301.
https:/​/​doi.org/​10.1088/​1751-8113/​49/​27/​275301

[27] S. McArdle, A. Gilyén, and M. Berta. הכנת מצב קוונטי ללא חשבון קוהרנטי. arXiv preprint arXiv:2210.14892, 2022. 10.48550/​arXiv.2210.14892.
https://​/​doi.org/​10.48550/​arXiv.2210.14892
arXiv: 2210.14892

[28] A. Montanaro ו-S. Pallister. אלגוריתמים קוונטיים ושיטת האלמנטים הסופיים. Physical Review A, 93: 032324, 2016. 10.1103/​PhysRevA.93.032324.
https: / / doi.org/ 10.1103 / PhysRevA.93.032324

[29] י' נאם, י' סו, וד' מסלוב. טרנספורמציה קוונטית פורייה משוערת עם o (n log (n)) שערים t. NPJ Quantum Information, 6: 26, 2020. 10.1038/​s41534-020-0257-5.
https:/​/​doi.org/​10.1038/​s41534-020-0257-5

[30] QT Nguyen, BT Kiani, ו-S. Lloyd. אלגוריתם קוונטי עבור גרעינים צפופים ומלאים באמצעות מטריצות היררכיות. Quantum, 6: 876, 2022. 10.22331/​q-2022-12-13-876.
https:/​/​doi.org/​10.22331/​q-2022-12-13-876

[31] MA נילסן ואני צ'ואנג. חישוב קוונטי ומידע קוונטי. האגודה האמריקאית למורים לפיזיקה, 2002. 10.1119/​1.1463744.
https: / / doi.org/ 10.1119 / 1.1463744

[32] EG Rieffel ו-WH Polak. מחשוב קוונטי: הקדמה עדינה. MIT Press, 2011. 10.1063/​PT.3.1442.
https://doi.org/ 10.1063/PT.3.1442

[33] S. Sachdeva, NK Vishnoi, et al. אלגוריתמים מהירים יותר באמצעות תורת הקירוב. יסודות ומגמות במדעי המחשב התיאורטיים, 9: 125–210, 2014. 10.1561/​0400000065.
https: / / doi.org/ 10.1561 / 0400000065

[34] EM סטיין ו-TS מרפי. ניתוח הרמוני: שיטות ממש-משתנים, אורתוגונליות ואינטגרלים נדנודים, כרך 3. הוצאת Princeton University, 1993. ISBN 9780691032160. URL https://​/​press.princeton.edu/​books/​hardcover/​9780691032160 -אנליזה-pms-43-נפח-43.
https://​/​press.princeton.edu/​books/​hardcover/​9780691032160/​harmonic-analysis-pms-43-volume-43

[35] Y. Tong, D. An, N. Wiebe, and L. Lin. היפוך מהיר, פותרי מערכת ליניארית קוונטית מותנים מראש, חישוב מהיר של פונקציות ירוקות והערכה מהירה של פונקציות מטריצה. Physical Review A, 104, 2021. 10.1103/​PhysRevA.104.032422.
https: / / doi.org/ 10.1103 / PhysRevA.104.032422

[36] R. Vale, TMD Azevedo, I. Araújo, IF Araujo, ו-AJ da Silva. פירוק של שערים יחידים יחידים עם שליטה מרובה שליטה. arXiv preprint arXiv:2302.06377, 2023. 10.48550/​arXiv.2302.06377.
https://​/​doi.org/​10.48550/​arXiv.2302.06377
arXiv: 2302.06377

[37] MW וונג. מבוא לאופרטורים פסאודו-דיפרנציאליים. World Scientific, 1999. 10.1142/​4047.
https: / / doi.org/ 10.1142 / 4047

[38] ל. יינג. פירוק יציב עבור גורמי פאזה של עיבוד אותות קוונטי. Quantum, 6: 842, 2022. 10.22331/​q-2022-10-20-842.
https:/​/​doi.org/​10.22331/​q-2022-10-20-842

מצוטט על ידי

[1] דיוויד ג'נינגס, מתאו Lostaglio, Sam Pallister, Andrew T Sornborger ו- Yiğit Subaşı, "אלגוריתם פותר ליניארי קוונטי יעיל עם עלויות שוטפות מפורטות", arXiv: 2305.11352, (2023).

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

לא ניתן היה להביא נתונים מצוטטים על ידי קרוסרף במהלך ניסיון אחרון 2023-06-02 12:49:57: לא ניתן היה להביא נתונים שהובאו עבור 10.22331 / q-2023-06-02-1031 מקרוסרף. זה נורמלי אם ה- DOI נרשם לאחרונה.

בול זמן:

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