תתי שגרות קוונטיות בסיסיות: מציאת מספר אלמנטים מסומנים וסיכום מספרים

תתי שגרות קוונטיות בסיסיות: מציאת מספר אלמנטים מסומנים וסיכום מספרים

חותמת זמן: 14 במרץ 2024 9:40
תת-שגרות קוונטיות בסיסיות: מציאת מספר אלמנטים מסומנים וסיכום מספרים PlatoBlockchain Data Intelligence. חיפוש אנכי. איי.

יוראן ואן אפלדורן1, סנדר גריבלינג2, ו הרולד ניובור3

1IViR ו-QuSoft, אוניברסיטת אמסטרדם, הולנד
2המחלקה לאקונומטריה וחקר תפעול, אוניברסיטת טילבורג, טילבורג, הולנד
3מכון קורטווג-דה פריס למתמטיקה ו-QuSoft, אוניברסיטת אמסטרדם, הולנד והפקולטה למדעי המחשב, אוניברסיטת רוהר בוכום, גרמניה והמחלקה למדעי המתמטיקה, אוניברסיטת קופנהגן, דנמרק

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

תַקצִיר

אנו מראים כיצד למצוא את כל האלמנטים המסומנים $k$ ברשימה בגודל $N$ באמצעות המספר האופטימלי $O(sqrt{N k})$ של שאילתות קוונטיות ורק תקורה פוליגריתמית במורכבות השער, בהגדרה שבה לאחד יש זיכרון קוונטי קטן. אלגוריתמים קודמים היו בעלי תקורה של גורם $k$ במורכבות השער, או שהיה להם גורם נוסף $log(k)$ במורכבות השאילתה.
לאחר מכן נשקול את הבעיה של מציאת קירוב $delta$ מכפיל של $s = sum_{i=1}^N v_i$ כאשר $v=(v_i) ב-[0,1]^N$, בהינתן גישה לשאילתה קוונטית ל תיאור בינארי של $v$. אנו נותנים אלגוריתם שעושה זאת, בהסתברות של לפחות $1-rho$, תוך שימוש בשאילתות קוונטיות $O(sqrt{N log(1/rho) / delta})$ (תחת הנחות מתונות על $rho$). זה משפר באופן ריבועי את התלות ב-$1/delta$ ו-$log(1/rho)$ בהשוואה ליישום פשוט של הערכת משרעת. כדי להשיג את התלות המשופרת של $log(1/rho)$ אנו משתמשים בתוצאה הראשונה.

► נתוני BibTeX

► הפניות

[1] Srinivasan Arunachalam ורונלד דה וולף. אופטימיזציה של מספר השערים בחיפוש קוונטי. מידע קוונטי. Comput., 17(3-4):251–261, 2017. doi:10.26421/​qic17.3-4.
https: / / doi.org/ 10.26421 / qic17.3-4

[2] José A. Adell ו-P. Jodrá. קולמוגורוב מדויק ומרחקי שונות הכוללים בין כמה התפלגויות בדידות מוכרות. Journal of Inequalities and Applications, 2006(1):1–8, 2006. doi:10.1155/​JIA/​2006/​64307.
https:/​/​doi.org/​10.1155/​JIA/​2006/​64307

[3] יוראן ואן אפלדורן, סנדר גריבלינג, ינאן לי, הרולד ניובור, מייקל וולטר ורונלד דה וולף. אלגוריתמים קוונטיים עבור קנה מידה מטריצה ​​ואיזון מטריצה. ב-Proceedings of 48th International Colloquium on Automata, Languages ​​and Programming (ICALP'21), כרך 198, עמודים 110:1–110:17, 2021. arXiv:2011.12823, doi:10.4230/​LIPIcs.2021.110ICALP.XNUMX.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.110
arXiv: 2011.12823

[4] סקוט אהרונסון ופטריק ראל. ספירה משוערת קוונטית, מפושטת. ב-Symposium on Simplicity in Algorithms, עמודים 24–32, 2020. doi:10.1137/​1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5

[5] מישל בוייר, ז'יל בראסארד, פיטר הייר ואלן טאפ. גבולות הדוקים לחיפוש קוונטי. Fortschritte der Physik, 46(4–5):493–505, 1998. גרסה מוקדמת יותר ב-Physcomp'96. arXiv:quant-ph/​9605034.
arXiv: quant-ph / 9605034

[6] הארי בוהרמן, ריצ'רד קליב, רונלד דה וולף וכריסטוף זלקה. גבולות לאלגוריתמים קוונטיים עם שגיאה קטנה ואפס שגיאה. בסימפוזיון השנתי ה-40 על יסודות מדעי המחשב (FOCS'99), עמודים 358–368. IEEE Computer Society, 1999.

[7] ז'יל בראסארד, פיטר הייר, מישל מוסקה ואלן טאפ. הגברה ואומדן משרעת קוונטית. ב-Quantum Computation and Quantum Information: A Millennium Volume, כרך 305 של מתמטיקה עכשווית, עמודים 53–74. American Mathematical Society, 2002. doi:10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P

[8] ריצ'רד ברנט ופול צימרמן. Modern Computer Arithmetic, כרך 18. הוצאת אוניברסיטת קיימברידג', 2010.

[9] רן קנטי, גיא אבן ועודד גולדרייך. גבולות תחתונים לאלגוריתמי דגימה להערכת הממוצע. מכתבי עיבוד מידע, 53(1):17–25, ינואר 1995. doi:10.1016/​0020-0190(94)00171-T.
https:/​/​doi.org/​10.1016/​0020-0190(94)00171-T

[10] קרלו סיליברטו, מארק הרבסטר, אלסנדרו דויד איאלונגו, מסימיליאנו פונטיל, אנדראה רוצ'טו, סימון סבריני ולאונרד ווסניג. למידת מכונה קוונטית: פרספקטיבה קלאסית. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, jan 2018. doi:10.1098/​rspa.2017.0551.
https: / / doi.org/ 10.1098 / rspa.2017.0551

[11] תומאס ה. קורמן, צ'ארלס אי. לייזרסון, רונלד ל. ריבסט וקליפורד סטיין. מבוא לאלגוריתמים. MIT Press, מהדורה רביעית, 4.

[12] פ' דיאקוניס וד' פרידמן. רצפים סופיים להחלפה. The Annals of Probability, 8(4):745–764, 1980. כתובת URL: https://www.jstor.org/​stable/​2242823.
https: / / www.jstor.org/ stable / 2242823

[13] כריסטוף דיר ופיטר הייר. אלגוריתם קוונטי למציאת המינימום, 1996. doi:10.48550/​arXiv.quant-ph/​9607014.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9607014
arXiv: quant-ph / 9607014

[14] כריסטוף דיר, מארק הייליגמן, פיטר הייר ומהדי מהלה. מורכבות שאילתה קוונטית של כמה בעיות גרפים. SIAM Journal on Computing, 35(6):1310–1328, ינואר 2006. doi:10.1137/​050644719.
https: / / doi.org/ 10.1137 / 050644719

[15] פול דאגום, ריצ'רד קארפ, מייקל לובי ושלדון רוס. אלגוריתם אופטימלי להערכת מונטה קרלו. SIAM Journal on Computing, 29(5):1484–1496, ינואר 2000. doi:10.1137/​S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

[16] ויטוריו ג'ובנטי, סת' לויד ולורנצו מקונה. זיכרון גישה אקראית קוונטי. Physical Review Letters, 100(16), אפריל 2008. doi:10.1103/​physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

[17] סנדר גריבלינג והרולד ניובור. גבול קוונטי תחתון ועליון משופר עבור קנה מידה מטריצה. ב-Proceedings of 39th International Symposium on Theoretical Aspects of Science (STACS'22), כרך 219, עמודים 35:1–35:23, 2022. arXiv:2109.15282, doi:10.4230/​LIPIcs.STACS.2022.35.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2022.35
arXiv: 2109.15282

[18] מארט דה גראף ורונלד דה וולף. על גרסאות קוונטיות של עקרון יאו. בסימפוזיון ה-19 על היבטים תיאורטיים של מדעי המחשב (STACS'02), כרך 2285 של הערות הרצאה במדעי המחשב, עמודים 347–358, ברלין, היידלברג, 2002. Springer. doi:10.1007/​3-540-45841-7_28.
https:/​/​doi.org/​10.1007/​3-540-45841-7_28

[19] לאב ק' גרובר. אלגוריתם מכאני קוונטי מהיר לחיפוש מסד נתונים. ב-Proceedings of 38th Annual ACM Symposium on Theory of Computing (STOC'96), עמודים 212–219, 1996. arXiv:quant-ph/​9605043, doi:10.1145/​237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: quant-ph / 9605043

[20] לאב ק' גרובר. טלחישוב קוונטי, 1997. מזכר טכני של Bell Labs ITD97-31630F. doi:10.48550/​arXiv.quant-ph/​9704012.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9704012
arXiv: quant-ph / 9704012

[21] לאב ק' גרובר. מסגרת לאלגוריתמים מכאניים קוונטיים מהירים. ב-Proceedings of the Thirtyth Annual ACM Symposium on the Theory of Computing (STOC'98), עמודים 53–62, 1998. arXiv:quant-ph/​9711043, doi:10.1145/​276698.276712.
https: / / doi.org/ 10.1145 / 276698.276712
arXiv: quant-ph / 9711043

[22] יאסין חמודי. אומדן ממוצע תת-גאוסי קוונטי. ב-29th Annual European Symposium on Algorithms (ESA 2021), כרך 204 של Leibniz International Proceedings in Informatics (LIPIcs), עמודים 50:1–50:17, 2021. doi:10.4230/​LIPIcs.ESA.2021.50.
https://doi.org/​10.4230/​LIPIcs.ESA.2021.50

[23] סוונטה יאנסון. גבולות זנב לסכומים של משתנים גיאומטריים ואקספוננציאליים. סטטיסטיקה ומכתבי הסתברות, 135:1–6, 2018. doi:10.1016/​j.spl.2017.11.017.
https:/​/​doi.org/​10.1016/​j.spl.2017.11.017

[24] דונלד ארווין קנוט. אמנות תכנות המחשב, כרך ג'. Addison-Wesley, מהדורה 2, 1998. כתובת אתר: https://www.worldcat.org/​oclc/​312994415.
https://www.worldcat.org/​oclc/​312994415

[25] רובין קוטארי וריאן אודונל. הערכה ממוצעת כאשר יש לך את קוד המקור; או, שיטות קוונטיות מונטה קרלו. ב-Proceedings of the Annual ACM-SIAM Symposium on Algorithms Discrete (SODA'2023), עמודים 23–1186, 1215. doi:2023/​10.1137.ch1.9781611977554.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[26] מייקל א. נילסן ואייזק ל. צ'ואנג. חישוב קוונטי ומידע קוונטי. הוצאת אוניברסיטת קיימברידג', 2002.

[27] אשווין נאיאק ופליקס וו. מורכבות השאילתה הקוונטית של קירוב החציון והסטטיסטיקה הקשורה. ב-Proceedings of the 31st Annual ACM SIGACT Symposium on Theory of Computing (STOC'99), עמודים 384–393, 1999. arXiv:quant-ph/​9804066, doi:10.1145/​301250.301349.
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: quant-ph / 9804066

[28] ב. רוס. קירוב בינומי להתפלגות הבינומית של פואסון: הרחבת קראוטצ'וק. Theory of Probability & Its Applications, 45(2):258–272, 2001. doi:10.1137/​S0040585X9797821X.
https://doi.org/​10.1137/​S0040585X9797821X

[29] רוברט מ. יאנג. 75.9 קבוע אוילר. The Mathematical Gazette, 75(472):187–190, 1991. doi:10.2307/​3620251.
https: / / doi.org/ 10.2307 / 3620251

מצוטט על ידי

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

בול זמן:

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