قسم علوم الكمبيوتر ، جامعة تكساس في أوستن ، أوستن ، تكساس 78712 ، الولايات المتحدة الأمريكية
تجد هذه الورقة مثيرة للاهتمام أو ترغب في مناقشة؟ Scite أو ترك تعليق على SciRate.
ملخص
إن الاقتراح الرائد للتحقق من تجارب التفوق الكمي على المدى القريب على الدوائر الكمومية العشوائية الصاخبة هو قياس الانتروبيا الخطي. بالنسبة لدائرة كمومية $ C $ على $ n $ كيوبت وعينة $ z في {0,1،0} ^ n $ ، يتضمن المعيار حساب $ | langle z | C | 2 ^ n rangle | ^ 0 $ ، أي الاحتمال قياس $ z $ من توزيع المخرجات $ C $ على مدخلات جميع الأصفار. في ظل تخمين قوي حول الصلابة الكلاسيكية لتقدير احتمالات خرج الدوائر الكمومية ، لا يمكن لأي خوارزمية كلاسيكية متعددة الحدود مع إعطاء $ C $ إخراج سلسلة $ z $ بحيث يكون $ | langle z | C | 2 ^ nrangle | ^ 1 $ هو أكبر بكثير من $ frac {2} {2019 ^ n} $ (Aaronson and Gunn، 0). من ناحية أخرى ، بالنسبة لدائرة كمومية عشوائية $ C $ ، فإن أخذ عينات $ z $ من توزيع مخرجات $ C $ يحقق $ | langle z | C | 2 ^ nrangle | ^ 2 almost frac {2} {2019 ^ n} في المتوسط (Arute et al. ، XNUMX).
بالتشابه مع متباينة Tsirelson من الارتباطات الكمية غير المحلية ، نسأل: هل يمكن لخوارزمية كمومية متعددة الحدود أن تحقق أداءً أفضل بكثير من $ frac {2} {2 ^ n} $؟ ندرس هذا السؤال في نموذج الاستعلام (أو الصندوق الأسود) ، حيث يتم منح خوارزمية الكم وصول أوراكل إلى $ C $. نوضح أنه بالنسبة إلى أي $ varepsilon ge frac {1} {mathrm {poly} (n)} $ ، يتم إخراج نموذج $ z $ بحيث يكون $ | langle z | C | 0 ^ nrangle | ^ 2 ge frac {2 + تتطلب varepsilon} {2 ^ n} $ في المتوسط $ Omegaleft على الأقل (frac {2 ^ {n / 4}} {mathrm {poly} (n)} right) $ من طلبات البحث إلى $ C $ ، ولكن ليس أكثر من $ Oleft (2 ^ {n / 3} right) $ queries إلى $ C $ ، إذا كان $ C $ إما Haar-random $ n $-qubit الوحدوي ، أو إعداد حالة متعارف عليه أوراكل لـ Haar-random $ n $ -qubit حالة. نوضح أيضًا أنه عند عينات $ C $ من توزيع فورييه لدالة منطقية عشوائية ، فإن الخوارزمية البسيطة التي تأخذ عينات من $ C $ هي خوارزمية استعلام واحد مثالية لتعظيم $ | langle z | C | 1 ^ nrangle | ^ 0 $ في المتوسط.
ملخص شعبي
نجادل بأن هذا الحد الأعلى لقوة الخوارزميات الكلاسيكية لـ Linear XEB مشابه لتباين بيل في الارتباطات غير المحلية: كلاهما يلتقط حدودًا متأصلة على قوة المعلومات الكلاسيكية والحساب الذي قد ينتهك في الإعداد الكمي. بدافع من هذا الارتباط ، نسأل: ما هو نظير السيادة الكمومية لمتباينة Tsirelson؟ أي ما هي أعلى درجة XEB خطية يمكن تحقيقها بواسطة خوارزمية كمومية فعالة؟ نعطي دليلاً على أن الخوارزمية الكمومية الساذجة لاجتياز المعيار هي الأمثل أساسًا في هذا الصدد.
► بيانات BibTeX
ferences المراجع
[1] سكوت آرونسون. أخذ العينات الدائرية العشوائية: الأفكار والمشاكل المفتوحة. الموجة الكمومية في الحوسبة ، 2020. URL https: / / simons.berkeley.edu/ talks / tbd-124.
https: / / simons.berkeley.edu/ talks / tbd-124
[2] سكوت آرونسون وليجي تشين. أسس نظرية التعقيد لتجارب التفوق الكمومي. في رايان أودونيل ، محرر ، مؤتمر التعقيد الحسابي الثاني والثلاثون (CCC 32) ، المجلد 2017 من Leibniz International Proceedings in Informatics (LIPIcs) ، الصفحات 79: 22-1: 22 ، Dagstuhl ، ألمانيا ، 67. Schloss Dagstuhl – Leibniz-Zentrum فور إنفورماتيك. ردمك 2017-978-3-95977-040. 8 / LIPIcs.CCC.10.4230 عنوان URL http: / / drops.dagstuhl.de/ opus / volltexte / 2017.22/2017.
الشبكي: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.22
HTTP: / / drops.dagstuhl.de/ التأليف / volltexte / 2017/7527
[3] سكوت آرونسون وسام جن. حول الصلابة الكلاسيكية لانتحال معايير الانتروبيا الخطية. نظرية الحوسبة ، 16 (11): 1-8 ، 2020. 10.4086 / toc.2020.v016a011. عنوان URL http: / / www.theoryofcomputing.org/ articles / v016a011.
الشبكي: / / doi.org/ 10.4086 / toc.2020.v016a011
http: / / www.theoryofcomputing.org/ articles / v016a011
[4] سكوت آرونسون وروبن كوثاري وويليام كريتشمر وجوستين ثالر. حدود كمية أقل للعد التقريبي عبر Laurent Polynomials. في Shubhangi Saraf ، محرر ، المؤتمر الخامس والثلاثين للتعقيد الحسابي (CCC 35) ، المجلد 2020 من Leibniz International Proceedings in Informatics (LIPIcs) ، الصفحات 169: 7-1: 7 ، Dagstuhl ، ألمانيا ، 47. Schloss Dagstuhl – Leibniz-Zentrum für Informatik . ردمك 2020-978-3-95977-156. 6 / LIPIcs.CCC.10.4230. عنوان URL https: / / drops.dagstuhl.de/ opus / volltexte / 2020.7/2020.
الشبكي: / / doi.org/ 10.4230 / LIPIcs.CCC.2020.7
https: / / drops.dagstuhl.de/ opus / volltexte / 2020/12559
[5] دوريت أهارونوف وأليكسي كيتاييف ونعوم نيسان. الدوائر الكمومية ذات الحالات المختلطة. في وقائع الندوة السنوية الثلاثين حول نظرية الحوسبة ، STOC '98 ، الصفحة 20-30 ، نيويورك ، نيويورك ، الولايات المتحدة الأمريكية ، 1998. Association for Computing Machinery. ردمك 0897919629 / 10.1145. عنوان URL https: / / doi.org/ 276698.276708 / 10.1145.
الشبكي: / / doi.org/ 10.1145 / 276698.276708
[6] أندريس أمبينيس. فهم الخوارزميات الكمومية من خلال تعقيد الاستعلام. في وقائع المؤتمر الدولي لعلماء الرياضيات 2018 ، المجلد 3 ، الصفحات 3249-3270 ، 2018. 10.1142 / 9789813272880_0181.
الشبكي: / / doi.org/ 10.1142 / 9789813272880_0181
[7] أندريس أمبينيس ، لوك ماجنين ، مارتن رويتلر ، وجيريمي رولاند. الخصوم بمساعدة التماثل لتوليد الحالة الكمومية. في وقائع المؤتمر السنوي السادس والعشرين لـ IEEE 2011 حول التعقيد الحسابي ، CCC '26 ، الصفحة 11–167 ، الولايات المتحدة الأمريكية ، 177. IEEE Computer Society. ردمك 2011. 9780769544113 / CCC.10.1109. URL https: / / doi.org/ 2011.24 / CCC.10.1109.
الشبكي: / / doi.org/ 10.1109 / CCC.2011.24
[8] أندريس أمبينيس وأنسيس روزمانيس ودومينيك أونروه. الهجمات الكمومية على أنظمة الإثبات الكلاسيكية: صلابة اللف الكمي. في وقائع الندوة السنوية الخامسة والخمسين IEEE لعام 2014 حول أسس علوم الكمبيوتر ، FOCS '55 ، صفحة 14-474 ، الولايات المتحدة الأمريكية ، 483. IEEE Computer Society. ردمك 2014. 9781479965175 / FOCS.10.1109. URL https: / / doi.org/2014.57 / FOCS.10.1109.
الشبكي: / / doi.org/ 10.1109 / FOCS.2014.57
[9] سرينيفاسان أروناشالام ، ألكسندر بيلوفس ، أندرو إم تشايلدز ، روبن كوثاري ، أنسيس روزمانيس ، ورونالد دي وولف. جامع القسيمة الكم. في ستيفن تي فلاميا ، محرر ، المؤتمر الخامس عشر لنظرية الحساب الكمي والتواصل والتشفير (TQC 15) ، المجلد 2020 من إجراءات لايبنيز الدولية للمعلوماتية (LIPIcs) ، الصفحات 158: 10-1: 10 ، داغستول ، ألمانيا ، 17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ردمك 2020-978-3-95977-146. 7 / LIPIcs.TQC.10.4230. عنوان URL https: / / drops.dagstuhl.de/ opus / volltexte / 2020.10/2020.
الشبكي: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.10
https: / / drops.dagstuhl.de/ opus / volltexte / 2020/12069
[10] فرانك أروت ، كونال أريا ، رايان بابوش ، وآخرون. التفوق الكمي باستخدام معالج فائق التوصيل قابل للبرمجة. الطبيعة ، 574 (7779): 505-510 ، 2019. 10.1038 / s41586-019-1666-5. عنوان URL https: / / doi.org/ 10.1038 / s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5
[11] روبرت بيلز وهاري بورمان وريتشارد كليف وميشيل موسكا ورونالد دي وولف. حدود الكم الأدنى بواسطة كثيرات الحدود. J. ACM، 48 (4): 778-797، July 2001. ISSN 0004-5411. 10.1145 / 502090.502097. URL https: / / doi.org/10.1145 / 502090.502097.
الشبكي: / / doi.org/ 10.1145 / 502090.502097
[12] جون بيل. حول مفارقة أينشتاين - بودولسكي - روزين. الفيزياء ، 1: 195 - 200 نوفمبر 1964. 10.1103 / PhysicsPhysiqueFizika.1.195. عنوان URL https: / / link.aps.org/ doi / 10.1103 / PhysicsPhysiqueFizika.1.195.
الشبكي: / / doi.org/ 10.1103 / PhysicsPhysiqueFizika.1.195
[13] ألكسندر بيلوفس. الاختلافات في الخصم الكمومي ، 2015.
أرخايف: 1504.06943
[14] ألكسندر بيلوفس وأنسيس روزمانيس. حد أدنى كمي محكم للعد التقريبي مع الحالات الكمومية ، 2020.
أرخايف: 2002.06879
[15] فرناندو جي إس إل برانداو وآرام دبليو هارو وميشاو هوروديكي. الدوائر الكمومية العشوائية المحلية هي تصميمات متعددة الحدود تقريبية. الاتصالات في الفيزياء الرياضية ، 346 (2): 397-434 ، 2016. 10.1007 / s00220-016-2706-8. URL https: / / doi.org/ 10.1007 / s00220-016-2706-8.
https://doi.org/10.1007/s00220-016-2706-8
[16] جيل براسارد وبيتر هوير وآلان تاب. تحليل التشفير الكمي لوظائف التجزئة الخالية من المخالب. أخبار SIGACT ، 28 (2): 14-19 ، يونيو 1997. ISSN 0163-5700. 10.1145 / 261342.261346. عنوان URL https: / / doi.org/10.1145 / 261342.261346.
الشبكي: / / doi.org/ 10.1145 / 261342.261346
[17] جيل براسارد وبيتر هوير وميشيل موسكا وآلان تاب. تضخيم وتقدير السعة الكمومية. في الحساب الكمي والمعلومات الكمومية ، المجلد 305 من الرياضيات المعاصرة ، الصفحات 53-74. الجمعية الرياضية الأمريكية ، 2002. ISBN 9780821821404. 10.1090 / conm / 305.
الشبكي: / / doi.org/ 10.1090 / conm / 305
[18] مارك بون وجوستين ثالر. حدود سفلية مزدوجة للدرجة التقريبية وعدم المساواة ماركوف-بيرنشتاين. المشاة. الكمبيوتر ، 243 (C): 2-25 ، أغسطس 2015. ISSN 0890-5401. 10.1016 / j.ic.2014.12.003. عنوان URL https: / / doi.org/ 10.1016 / j.ic.2014.12.003.
https: / / doi.org/ 10.1016 / j.ic.2014.12.003
[19] بوريس سيريلسون (تسيريلسون). التعميمات الكمومية لعدم مساواة بيل. رسائل في الفيزياء الرياضية ، 4 (2): 93-100 ، 1980. 10.1007 / BF00417500. URL https: / / doi.org/ 10.1007 / BF00417500.
الشبكي: / / doi.org/ 10.1007 / BF00417500
[20] جون إف كلوزر ومايكل أ. هورن وأبنر شموني وريتشارد هولت. تجربة مقترحة لاختبار نظريات المتغيرات المخفية المحلية. فيز. القس ليت ، 23: 880-884 ، أكتوبر 1969. 10.1103 / PhysRevLett.23.880. عنوان URL https: / / link.aps.org/ doi / 10.1103 / PhysRevLett.23.880.
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.23.880
[21] ريتشارد كليف وبيتر هوير وبنجامين تونر وجون واتروس. عواقب وحدود الاستراتيجيات غير المحلية. في وقائع المؤتمر السنوي التاسع عشر IEEE حول التعقيد الحسابي ، CCC '19 ، الصفحة 04-236 ، الولايات المتحدة الأمريكية ، 249. IEEE Computer Society. ردمك 2004. 0769521207 / CCC.10.1109.
الشبكي: / / doi.org/ 10.1109 / CCC.2004.1313847
[22] ارام هارو وسعيد مهربان. تصميمات t أحادية تقريبية بواسطة دارات كمومية قصيرة عشوائية باستخدام أقرب الجيران والبوابات بعيدة المدى ، 2018.
أرخايف: 1809.06957
[23] نورمان ل.جونسون وصمويل كوتز. نماذج الجرة وتطبيقاتها: نهج لنظرية الاحتمالية المنفصلة الحديثة. وايلي ، 1977. ISBN 9780471446309.
[24] شيلبي كيميل ، سيدريك ين يو لين ، جوانج هاو لو ، ماريس أوزولس ، وثيودور جي يودر. محاكاة هاميلتونية مع التعقيد الأمثل للعينة. معلومات الكم npj ، 3 (1): 13 ، 2017. 10.1038 / s41534-017-0013-7. عنوان URL https: / / doi.org/ 10.1038 / s41534-017-0013-7.
https://doi.org/10.1038/s41534-017-0013-7
[25] وليام كريتشمر. التفوق الكمومي Tsirelson عدم المساواة. في James R. Lee ، محرر ، 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) ، المجلد 185 من Leibniz International Proceedings in Informatics (LIPIcs) ، pages 13: 1–13: 13 ، Dagstuhl ، Germany ، 2021. Schloss Dagstuhl– Leibniz-Zentrum für Informatik. ردمك 978-3-95977-177-1. 10.4230 / LIPIcs.ITCS.2021.13. عنوان URL https: / / drops.dagstuhl.de/ opus / volltexte / 2021/13552.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2021.13
https: / / drops.dagstuhl.de/ opus / volltexte / 2021/13552
[26] تروي لي ، وراجات ميتال ، وبن دبليو ريتشارت ، وروبرت أبالك ، وماريو سيجيدي. تعقيد الاستعلام الكمي لتحويل الحالة. في وقائع الندوة السنوية 2011nd IEEE 52 حول أسس علوم الكمبيوتر ، FOCS '11 ، صفحة 344-353 ، الولايات المتحدة الأمريكية ، 2011. IEEE Computer Society. ردمك 9780769545714. 10.1109 / FOCS.2011.75. عنوان URL https: / / doi.org/ 10.1109 / FOCS.2011.75.
الشبكي: / / doi.org/ 10.1109 / FOCS.2011.75
[27] ناثان ليندزي وأنسيس روزمانيس. حد سفلي محكم لمحو المؤشر غير المتماسك. في Thomas Vidick ، محرر ، 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) ، المجلد 151 من Leibniz International Proceedings in Informatics (LIPIcs) ، صفحات 59: 1-59: 37 ، Dagstuhl ، Germany ، 2020. Schloss Dagstuhl – Leibniz- Zentrum fuer Informatik. ردمك 978-3-95977-134-4. 10.4230 / LIPIcs.ITCS.2020.59. عنوان URL https: / / drops.dagstuhl.de/ opus / volltexte / 2020/11744.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2020.59
https: / / drops.dagstuhl.de/ opus / volltexte / 2020/11744
[28] فريدريك ماغنيز ، أشوين ناياك ، جيريمي رولاند ، وميكلوس سانثا. البحث عن طريق المشي الكمي. في وقائع ندوة ACM السنوية التاسعة والثلاثين حول نظرية الحوسبة ، STOC '07 ، صفحة 575-584 ، نيويورك ، نيويورك ، الولايات المتحدة الأمريكية ، 2007. Association for Computing Machinery. ردمك 9781595936318. 10.1145 / 1250790.1250874. عنوان URL https: / / doi.org/ 10.1145 / 1250790.1250874.
الشبكي: / / doi.org/ 10.1145 / 1250790.1250874
[29] رايان أودونيل. تحليل وظائف منطقية. مطبعة جامعة كامبريدج ، الولايات المتحدة الأمريكية ، 2014. ISBN 1107038324. 10.1017 / CBO9781139814782.
الشبكي: / / doi.org/ 10.1017 / CBO9781139814782
[30] مارتن راب وأنجيليكا ستيجر. "الكرات في صناديق" - تحليل بسيط ومحكم. في وقائع ورشة العمل الدولية الثانية حول تقنيات العشوائية والتقريب في علوم الكمبيوتر ، عشوائي 98 ، الصفحات 159-170 ، برلين ، هايدلبرغ ، 1998. Springer-Verlag. ردمك 354065142X. 10.1007 / 3-540-49543-6_13.
https://doi.org/10.1007/3-540-49543-6_13
[31] بن دبليو ريتشارت. تأملات في خوارزميات الاستعلام الكمي. في وقائع الندوة السنوية الثانية والعشرين لـ ACM-SIAM حول الخوارزميات المنفصلة ، SODA '11 ، الصفحة 560-569 ، الولايات المتحدة الأمريكية ، 2011. جمعية الرياضيات الصناعية والتطبيقية. 10.1137 / 1.9781611973082.44.
الشبكي: / / doi.org/ 10.1137 / 1.9781611973082.44
[32] ألفريد ريني. في نظرية إحصائيات النظام. Acta Mathematica Academiae Scientiarum Hungarica، 4 (3): 191-231، 1953. 10.1007 / BF02127580. عنوان URL https: / / doi.org/ 10.1007 / BF02127580.
الشبكي: / / doi.org/ 10.1007 / BF02127580
دليلنا يستخدم من قبل
[1] Daniel Stilck França و Raul Garcia-Patron ، "لعبة ذات ميزة كمية: ربط التحقق والمحاكاة" ، أرخايف: 2011.12173.
[2] نيكولاس لاراكوينت ، "فصل أوراكل الكم من الدول المعقدة ولكن سهلة التحديد" ، أرخايف: 2104.07247.
[3] سكوت آرونسون ، "المشكلات المفتوحة المتعلقة بتعقيد الاستعلام الكمي" ، أرخايف: 2109.06917.
الاستشهادات المذكورة أعلاه من إعلانات ساو / ناسا (تم آخر تحديث بنجاح 2021-10-07 11:15:15). قد تكون القائمة غير كاملة نظرًا لأن جميع الناشرين لا يقدمون بيانات اقتباس مناسبة وكاملة.
لا يمكن أن تجلب استشهد تبادل البيانات أثناء آخر محاولة 2021-10-07 11:15:13: لا يمكن جلب البيانات المستشهد بها من 10.22331 / q-2021-10-07-560 من Crossref. هذا أمر طبيعي إذا تم تسجيل DOI مؤخرًا.
نشرت هذه الورقة في الكم تحت نسبة المشاع الإبداعي 4.0 الدولية (CC BY 4.0) رخصة. يظل حقوق الطبع والنشر مع مالكي حقوق الطبع والنشر الأصليين مثل المؤلفين أو مؤسساتهم.
أفلاطون. Web3 مُعاد تصوره. تضخيم ذكاء البيانات.
انقر هنا للوصول.
المصدر: https://quantum-journal.org/papers/q-2021-10-07-560/
