1مركز نظم الكم الهندسية ، كلية الفيزياء ، جامعة سيدني ، سيدني ، نيو ساوث ويلز 2006 ، أستراليا
2معهد الفيزياء النظرية ، جامعة كولونيا ، ألمانيا
تجد هذه الورقة مثيرة للاهتمام أو ترغب في مناقشة؟ Scite أو ترك تعليق على SciRate.
ملخص
يوفر التحقيق في المحاكاة الكلاسيكية للدوائر الكمومية طريقًا واعدًا نحو فهم القوة الحسابية للأنظمة الكمومية. يعتمد ما إذا كان يمكن محاكاة فئة من الدوائر الكمومية بكفاءة باستخدام كمبيوتر كلاسيكي احتمالي ، أو من الصعب إثباتها ، يعتمد بشكل حاسم على المفهوم الدقيق لـ "المحاكاة الكلاسيكية" وعلى وجه الخصوص على الدقة المطلوبة. نقول أن فكرة المحاكاة الكلاسيكية ، التي نسميها محاكاة EPSILON (أو $ epsilon $ -المحاكاة باختصار) ، تجسد جوهر امتلاك "القوة الحسابية المكافئة" كنظام كمومي يحاكيه: من المستحيل إحصائيًا التمييز بين وكيل مع إمكانية الوصول إلى محاكي $ epsilon $ من أحد يمتلك نظام الكم المحاكي. نحن نربط محاكاة $ epsilon $ بمختلف المفاهيم البديلة للمحاكاة التي تركز في الغالب على جهاز محاكاة نسميه $ textit {poly-box} $. ينتج مربع متعدد تقديرات مضافة دقيقة $ 1 / poly $ لاحتمالات وهوامش Born. اكتسبت فكرة المحاكاة هذه أهمية من خلال عدد من نتائج المحاكاة الأخيرة. بقبول بعض الافتراضات النظرية الحسابية المعقولة ، نوضح أن محاكاة $ epsilon $ أقوى بشكل صارم من مربع متعدد من خلال إظهار أن دوائر IQP ودوائر Clifford التي تم حقنها في حالة سحرية غير مشروطة يصعب على $ epsilon $ -المحاكاة ومع ذلك فهي تقبل بولي -صندوق. على النقيض من ذلك ، نوضح أيضًا أن هذين المفهومين متكافئان بموجب افتراض إضافي حول ندرة توزيع المخرجات ($ textit {poly-sparsity} $).
► بيانات BibTeX
ferences المراجع
[1] RP Feynman، "Simulation Physics with Computers،" Int. J. نظرية. فيز. ، 21 ، 467-488 (1982).
الشبكي: / / doi.org/ 10.1007 / BF02650179
[2] S. Aaronson و D. Gottesman ، "محاكاة محسنة لدارات التثبيت ،" Phys. القس أ ، 70 ، 052328 (2004).
الشبكي: / / doi.org/ 10.1103 / PhysRevA.70.052328
[3] LG Valiant ، "دوائر الكم التي يمكن محاكاتها بشكل كلاسيكي في وقت كثير الحدود" ، مجلة SIAM للحوسبة ، 31 ، 1229-1254 (2002).
الشبكي: / / doi.org/ 10.1137 / S0097539700377025
[4] BM Terhal و DP DiVincenzo ، "المحاكاة الكلاسيكية للدوائر الكمومية غير المتفاعلة ،" Phys. القس A 65 ، 032325 (2002).
الشبكي: / / doi.org/ 10.1103 / PhysRevA.65.032325
[5] SD بارتليت ، BC Sanders ، SL Braunstein ، و K. Nemoto ، "المحاكاة الكلاسيكية الفعالة لعمليات المعلومات الكمومية المتغيرة المستمرة ،" Phys. القس ليت. 88 ، 097904 (2002).
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.88.097904
[6] L. Gurvits ، "حول تعقيد التمييز المختلط والمشاكل ذات الصلة" في: Jedrzejowicz J. ، Szepietowski A. (eds) أسس الرياضيات لعلوم الكمبيوتر 2005. MFCS 2005. ملاحظات المحاضرة في علوم الكمبيوتر ، المجلد 3618. Springer ، برلين ، هايدلبرغ (2005).
الشبكي: / / doi.org/ 10.1007 / 11549345_39
[7] S. Aaronson و A. Arkhipov ، "التعقيد الحسابي للبصريات الخطية" ، في وقائع الندوة السنوية الثالثة والأربعين ACM حول نظرية الحوسبة ، 333-342 ، ACM (2011).
الشبكي: / / doi.org/ 10.1145 / 1993636.1993682
[8] MJ Bremner و R. Jozsa و DJ Shepherd ، "المحاكاة الكلاسيكية لاستبدال الحسابات الكمية تنطوي على انهيار التسلسل الهرمي متعدد الحدود" بروك. R. Soc. أ 467 ، (2010).
الشبكي: / / doi.org/ 10.1098 / rspa.2010.0301
[9] MJ Bremner، A. Montanaro، and DJ Shepherd، "متوسط تعقيد الحالة مقابل المحاكاة التقريبية لاستبدال الحسابات الكمومية" ، فيز. القس ليت. 117 ، 080501 (2016).
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.117.080501
[10] X. Gao ، S.-T. وانغ ، ولام. دوان ، "التفوق الكمومي لمحاكاة نموذج تدور Ising الثابت المتغير" ، Phys. القس ليت. 118 ، 040502 (2017).
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.118.040502
[11] J. Bermejo-Vega، D. Hangleiter، M. Schwarz، R. Raussendorf، and J. Eisert، "هياكل لمحاكاة الكم تظهر تسريعًا كميًا" ، Phys. مراجعة X 8 ، 021010 (2018).
الشبكي: / / doi.org/ 10.1103 / PhysRevX.8.021010
[12] B. Fefferman و C. Umans ، "قوة أخذ العينات الكمومية ،" arXiv preprint arXiv: 1507.05592 ، (2015).
أرخايف: 1507.05592
[13] T. Morimae و K. Fujii و JF Fitzsimons ، "صلابة المحاكاة الكلاسيكية لنموذج qubit واحد نظيف" Phys. القس ليت. 112 ، 130502 (2014).
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.112.130502
[14] T. Morimae و K. Fujii و H. Nishimura، "Power of one nonclean qubit،" Phys. القس A 95 ، 042336 (2017).
الشبكي: / / doi.org/ 10.1103 / PhysRevA.95.042336
[15] S. Boixo و SV Isakov و VN Smelyanskiy و R. Babbush و N.Ding و Z. Jiang و MJ Bremner و JM Martinis و H. Neven ، "توصيف التفوق الكمي في الأجهزة القريبة المدى" Nature Phys. 14 ، 595-600 (2018).
الشبكي: / / doi.org/ 10.1038 / s41567-018-0124-X
[16] A. Bouland ، JF Fitzsimons ، و DE Koh ، "تصنيف التعقيد لدوائر كليفورد المترافقة" ، في مؤتمر التعقيد الحسابي الثالث والثلاثين (CCC 33) (RA Servedio ، ed.) ، المجلد. 2018 من إجراءات Leibniz الدولية في المعلوماتية (LIPIcs) ، (Dagstuhl ، ألمانيا) ، ص 102: 21-1: 21 ، Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik ، 25.
الشبكي: / / doi.org/ 10.4230 / LIPIcs.CCC.2018.21
[17] دي جي برود ، "محاكاة كلاسيكية فعالة لدوائر الثقاب ذات المدخلات والقياسات المعممة" ، فيز. القس A 93 ، 062332 (2016).
الشبكي: / / doi.org/ 10.1103 / PhysRevA.93.062332
[18] R. Jozsa و A. Miyake ، "أعواد الثقاب والمحاكاة الكلاسيكية للدوائر الكمومية" بروك. R. Soc. أ 464 ، 3089-3106 (2008).
الشبكي: / / doi.org/ 10.1098 / rspa.2008.0189
[19] V. Veitch ، C. Ferrie ، D. Gross ، و J. Emerson ، "شبه سلبية احتمالية كمورد لحساب الكم" ، New J. Phys. 14 ، 113011 (2012).
https://doi.org/10.1088/1367-2630/14/11/113011
[20] V. Veitch و N. Wiebe و C. Ferrie و J. Emerson ، "مخطط محاكاة فعال لفئة من تجارب البصريات الكمومية مع تمثيل Wigner غير السلبي" New J. Phys. 15 ، 013037 (2013).
https://doi.org/10.1088/1367-2630/15/1/013037
[21] A. Mari و J. Eisert ، "إن وظائف Wigner الإيجابية تجعل المحاكاة الكلاسيكية للحساب الكمومي فعالة" ، فيز. القس ليت. 109 ، 230503 (2012).
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.109.230503
[22] S. Bravyi و D. Gosset ، "محاكاة كلاسيكية محسنة للدوائر الكمومية التي تهيمن عليها بوابات كليفورد" ، فيز. القس ليت. 116 ، 250501 (2016).
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.116.250501
[23] RS Bennink و EM Ferragut و TS Humble و JA Laska و JJ Nutaro و MG Pleszkoch و RC Pooser ، "محاكاة غير متحيزة لدوائر الكم بالقرب من Clifford ،" Phys. القس أ 95 ، 062337 (2017).
الشبكي: / / doi.org/ 10.1103 / PhysRevA.95.062337
[24] MJ Bremner و A. Montanaro و DJ Shepherd ، "تحقيق التفوق الكمي باستخدام الحوسبة الكمومية المتفرقة والصاخبة
ns ، "Quantum 1 ، 8 (2017).
https://doi.org/10.22331/q-2017-04-25-8
[25] M. Oszmaniec و DJ Brod ، "المحاكاة الكلاسيكية للبصريات الضوئية الخطية مع الجسيمات المفقودة" ، New J. Phys. 20 ، 092002 (2018).
الشبكي: / / doi.org/ 10.1088 / 1367-2630 / aadfa8
[26] M. Howard و E. Campbell ، "تطبيق نظرية الموارد للحالات السحرية على الحوسبة الكمومية التي تتحمل الأخطاء" ، فيز. القس ليت. 118 ، 090501 (2017).
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.118.090501
[27] H. Pashayan ، JJ Wallman ، و SD Bartlett ، "تقدير احتمالات نتائج الدوائر الكمومية باستخدام القدرات شبه الكربونية ،" Phys. القس ليت. 115 ، 070501 (2015).
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.115.070501
[28] فان دين نيست ، "المحاكاة الكلاسيكية الفعالة لتحولات فورييه الكمية ودوائر التسوية فوق مجموعات أبيليان" ، arXiv preprint arXiv: 1201.4867 ، 2012.
أرخايف: 1201.4867
[29] J. Bermejo-Vega و M. Van Den Nest ، "المحاكاة الكلاسيكية لدارات التسوية بمجموعة Abelian مع قياسات وسيطة ،" Quantum Info. احسب. 14 ، 181-216 (2014).
[30] M. Schwarz و M. Van Den Nest ، "محاكاة الدوائر الكمية مع توزيعات خرج متفرقة" ، arXiv preprint arXiv: 1310.6749 ، 2013.
أرخايف: 1310.6749
[31] S. Bravyi و G. Smith و JA Smolin ، "تداول الموارد الحسابية الكلاسيكية والكمية" ، فيز. مراجعة X ، 6 ، 021043 (2016).
الشبكي: / / doi.org/ 10.1103 / PhysRevX.6.021043
[32] K. Temme ، S. Bravyi ، و JM Gambetta ، "التخفيف من الأخطاء في الدوائر الكمية قصيرة العمق ،" Phys. القس ليت. 119 ، 180509 (2017).
الشبكي: / / doi.org/ 10.1103 / PhysRevLett.119.180509
[33] فان دين نيست ، "المحاكاة الكلاسيكية للحساب الكمي ، نظرية جوتسمان-نيل ، وما بعدها بقليل" ، معلومات الكم. احسب. 10 ، 258-271 (2010).
[34] R. Jozsa و N. Linden ، "حول دور التشابك في تسريع الحوسبة الكمومية" بروك. R. Soc. أ 459 ، 2011-2032 (2003).
الشبكي: / / doi.org/ 10.1098 / rspa.2002.1097
[35] BM Terhal و DP DiVincenzo ، "الحساب الكمي التكيفي ، والدوائر الكمومية ذات العمق الثابت وألعاب آرثر ميرلين ،" Quantum Info. احسب. 4 ، 134-145 (2004).
[36] T. Morimae ، "صلابة أخذ العينات بشكل نموذجي من نموذج qubit واحد نظيف مع خطأ مسافة تباين إجمالي ثابت" ، فيز. القس أ 96 ، 040302 (2017).
الشبكي: / / doi.org/ 10.1103 / PhysRevA.96.040302
[37] أرونسون ، "تكافؤ العينات والبحث" ، نظرية أنظمة الحوسبة ، 55 ، 281-298 (2014).
https://doi.org/10.1007/s00224-013-9527-3
[38] فان دين نيست ، "محاكاة أجهزة الكمبيوتر الكمومية بالطرق الاحتمالية" ، Quantum Info. احسب. 11 ، 784-812 (2011).
[39] شيبرد ، "matroids الثنائية وتوزيع الاحتمالات الكمومية" ، arXiv preprint arXiv: 1005.1744 ، (2010).
أرخايف: 1005.1744
[40] S. Bravyi و A. Kitaev ، "الحوسبة الكمومية الشاملة مع بوابات كليفورد المثالية والأنسيلات الصاخبة" ، فيز. القس أ 71 ، 022316 (2005).
الشبكي: / / doi.org/ 10.1103 / PhysRevA.71.022316
[41] R. Jozsa و M. Van Den Nest ، "تعقيد المحاكاة الكلاسيكية لدوائر Clifford الممتدة" ، Quantum Info. احسب. 14 ، 633-648 (2014).
[42] LA Goldberg و H. Guo ، "تعقيد تقريب وظائف تقسيم Ising و Tutte ذات القيمة المعقدة". مركب. 26 ، 765-833 (2017).
https://doi.org/10.1007/s00037-017-0162-2
[43] كوبيربرغ ، "ما مدى صعوبة تقريب كثيرات حدود جونز؟" ، نظرية الحوسبة ، 11 ، 183-219 (2015).
الشبكي: / / doi.org/ 10.4086 / toc.2015.v011a006
[44] ك. فوجي و ت. موريما ، "تبديل الدوائر الكمومية وتعقيد وظائف التقسيم Ising" ، New J. Phys. 19 ، 033003 (2017).
الشبكي: / / doi.org/ 10.1088 / 1367-2630 / aa5fdb
[45] Stahlke ، "التداخل الكمي كمورد لتسريع الكم ،" Phys. القس أ 90 ، 022302 (2014).
الشبكي: / / doi.org/ 10.1103 / PhysRevA.90.022302
[46] Shepherd and MJ Bremner، "حساب كمومي غير منظم مؤقتًا" بروك. R. Soc. أ 465 ، 1413-1439 (2009).
الشبكي: / / doi.org/ 10.1098 / rspa.2008.0443
[47] DJ Shepherd ، "تعقيد الكم: قيود على الخوارزميات والمعماريات ،" arXiv preprint arXiv: 1005.1425 (2010).
أرخايف: 1005.1425
[48] د. فيرتيجان ، "أبعاد الدراجات والنقاط الخاصة لكثيرة حدود توت" ، ج. كومبين. نظرية سير. ب 74 ، 378-396 (1998).
الشبكي: / / doi.org/ 10.1006 / jctb.1998.1860
[49] R. Renner and S. Wolf، "Smooth Rényi entropy and Applications" في الندوة الدولية حول نظرية المعلومات ، 2004. ISIT 2004. Proceedings.، pp. 233 (2004).
الشبكي: / / doi.org/ 10.1109 / ISIT.2004.1365269
[50] ستوكميير ، "تعقيد الحساب التقريبي" ، في وقائع الندوة السنوية الخامسة عشرة لـ ACM حول نظرية الحوسبة ، ص 118-126 ، ACM ، (1983).
الشبكي: / / doi.org/ 10.1145 / 800061.808740
[51] تودا ، "PP صعب مثل التسلسل الهرمي للوقت متعدد الحدود" ، SIAM Journal on Computing 20، 865-877 (1991).
الشبكي: / / doi.org/ 10.1137 / 0220053
[52] S. Aaronson و T. Hance ، "تعميم وإلغاء توزيع خوارزمية تقريب Gurvits للعنصر الدائم" ، Quantum Info. احسب. 14 ، 541-559 (2014).
دليلنا يستخدم من قبل
[1] جيمس ر. سيدون وإيرل كامبل ، "قياس كمية السحر للعمليات متعددة الوحدات" ، وقائع الجمعية الملكية س
f London Series A 475 2227، 20190251 (2019).
[2] باتريك رال ، ودانيال ليانغ ، وجيريمي كوك ، وويليام كريتشمر ، "محاكاة الدوائر الكمومية الكمية عبر انتشار باولي" ، Physical Review A 99 6، 062337 (2019).
[3] Wojciech Roga و Masahiro Takeoka ، "المحاكاة الكلاسيكية لأخذ عينات البوزون مع إنتاج متناثر" ، أرخايف: 1904.05494.
[4] تيانيي بينج ، آرام هارو ، ماريس أوزولز ، وشياودي وو ، "محاكاة دوائر كمية كبيرة على كمبيوتر كمومي صغير" ، أرخايف: 1904.00102.
[5] أنجيلا كارانجاي ، جويل والمان ، وستيفن د. بارتليت ، "السياقية تحد من كفاءة المحاكاة الكلاسيكية للعمليات الكمية" ، أرخايف: 1802.07744.
[6] Michał Oszmaniec و Daniel J. Brod ، "المحاكاة الكلاسيكية للبصريات الضوئية الخطية مع الجسيمات المفقودة" ، مجلة جديدة للفيزياء 20 9 ، 092002 (2018).
[7] Mithuna Yoganathan و Richard Jozsa و Sergii Strelchuk ، "الميزة الكمية لدوائر Clifford الأحادية مع مدخلات الحالة السحرية" ، وقائع الجمعية الملكية في لندن ، السلسلة A 475 2225 ، 20180427 (2019).
[8] Piers Lillystone و Joseph Emerson، "A Contextual $ psi $ -Epistemic Model of $ n $ -Qubit Stabilizer Formical"، أرخايف: 1904.04268.
[9] Daochen Wang ، "محاكاة الدوائر الكمومية بالدوائر الكلاسيكية" ، أرخايف: 1904.05282.
[10] باتريك رال ، "محاكاة الدوائر الكمومية عن طريق خلط الأوراق بوليس" ، أرخايف: 1804.05404.
[11] ليوناردو نوفو وجواني بيرميجو فيجا وراؤول غارسيا باترون ، "ميزة الكم من قياسات الطاقة للأنظمة الكمومية للعديد من الأجسام" ، أرخايف: 1912.06608.
[12] فيليب ب. ماسيجيفسكي ، زولتان زيمبوراس وميخا أوزمانيك ، "تخفيف ضوضاء القراءة في الأجهزة الكمومية القريبة المدى عن طريق المعالجة اللاحقة الكلاسيكية بناءً على التصوير المقطعي للكاشف" ، أرخايف: 1907.08518.
الاستشهادات المذكورة أعلاه من إعلانات ساو / ناسا (تم آخر تحديث بنجاح 2020-01-22 17:25:20). قد تكون القائمة غير كاملة نظرًا لأن جميع الناشرين لا يقدمون بيانات اقتباس مناسبة وكاملة.
On خدمة Crossref's cited-by service لم يتم العثور على بيانات حول الاستشهاد بالأعمال (المحاولة الأخيرة 2020-01-22 17:25:18).
نشرت هذه الورقة في الكم تحت نسبة المشاع الإبداعي 4.0 الدولية (CC BY 4.0) رخصة. يظل حقوق الطبع والنشر مع مالكي حقوق الطبع والنشر الأصليين مثل المؤلفين أو مؤسساتهم.
المصدر: https://quantum-journal.org/papers/q-2020-01-13-223/
