پیچیدگی کوانتومی کولموگروف و همبستگی‌های کوانتومی در ماشین‌های تورینگ کوانتومی با کنترل قطعی

بازنشر افلاطون

دنبال: 0

ماریانو لموس^1,2، ریکاردو فالیرو^1,2, پائولو ماتئوس^1,2, نیکولا پاونکوویچ^1,2و آندره سوتو^2,3,4

¹Departamento de Matemática، Instituto Superior Técnico، Universidade de Lisboa، Av.Rovisco Pais، 1049-001 Lisboa، پرتغال
²Instituto de Telecomunicações, Av.Rovisco Pais, 1049-001 Lisboa, پرتغال
³Lasige، Faculdade de Ciências da Universidade de Lisboa، Campo Grande، 1749-016 Lisboa، پرتغال
⁴Departamento de Informática، Faculdade de Ciências da Universidade de Lisboa، Campo Grande، 1749-016 لیسبون، پرتغال

این مقاله را جالب می دانید یا می خواهید بحث کنید؟ SciRate را ذکر کنید یا در SciRate نظر بدهید.

چکیده

این کار مطالعه ای از پیچیدگی کلموگروف برای حالت های کوانتومی عمومی از دیدگاه ماشین های تورینگ کوانتومی با کنترل قطعی (dcq-TM) ارائه می دهد. ما مدل dcq-TM را گسترش می‌دهیم تا ورودی‌ها و خروجی‌های حالت مختلط را ترکیب کند و حالت‌های قابل محاسبه dcq را به‌عنوان حالت‌هایی تعریف می‌کنیم که می‌توانند با یک dcq-TM تقریب شوند. علاوه بر این، پیچیدگی حالت‌های کوانتومی کلموگروف (شرطی) را معرفی می‌کنیم و از آن برای مطالعه سه جنبه خاص از اطلاعات الگوریتمی موجود در یک حالت کوانتومی استفاده می‌کنیم: مقایسه اطلاعات در یک حالت کوانتومی با نمایش کلاسیک آن به عنوان آرایه‌ای از واقعیات. اعداد، کاوش در محدودیت‌های کپی حالت کوانتومی در زمینه پیچیدگی الگوریتمی، و مطالعه پیچیدگی همبستگی‌ها در سیستم‌های کوانتومی، که منجر به تعریفی آگاه از همبستگی برای اطلاعات متقابل الگوریتمی می‌شود که تقارن ویژگی اطلاعات را برآورده می‌کند.

► داده های BibTeX

@article{Lemus2024quantumkolmogorov, doi = {10.22331/q-2024-01-18-1230}, url = {https://doi.org/10.22331/q-2024-01-18-1230}, title = {Quantum {K}olmogorov complexity and quantum correlations in deterministic-control quantum {T}uring machines}, author = {Lemus, Mariano and Faleiro, Ricardo and Mateus, Paulo and Paunkovi{‘{c}}, Nikola and Souto, Andr{‘{e}}}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1230}, month = jan, year = {2024} }

◄ مراجع

[1] L. Antunes، A. Matos، A. Pinto، A. Souto و A. Teixeira. توابع یک طرفه با استفاده از نظریه های اطلاعات الگوریتمی و کلاسیک. نظریه سیستم های محاسباتی، 52 (1): 162-178، ژانویه 2013. ISSN 1433-0490. 10.1007/s00224-012-9418-z.
https://doi.org/10.1007/s00224-012-9418-z

[2] D. Azevedo، A. M. Rodrigues، H. Canhão، A. M. Carvalho و A. Souto. Zgli: خط لوله ای برای خوشه بندی با فشرده سازی با کاربرد در طبقه بندی بیمار در اسپوندیلوآرتریت. Sensors, 23 (3), 2023. ISSN 1424-8220. 10.3390/s23031219.
https://doi.org/10.3390/s23031219

[3] F. Benatti، T. Krüger، M. Müller، R. Siegmund-Schultze، و A. Szkoła. آنتروپی و پیچیدگی کوانتومی کولموگروف: قضیه کوانتومی برودنو. اشتراک. ریاضی. Phys., 265 (1): 437-461, 2006. 10.1007/s00220-006-0027-z.
https://doi.org/10.1007/s00220-006-0027-z

[4] سی اچ. بنت و جی. براسارد. رمزنگاری کوانتومی: توزیع کلید عمومی و پرتاب سکه. در مجموعه مقالات کنفرانس بین المللی IEEE در مورد رایانه ها، سیستم ها و پردازش سیگنال، صفحه 175، 1984. 10.1016/j.tcs.2014.05.025.
https://doi.org/10.1016/j.tcs.2014.05.025

[5] ای برنشتاین و یو وزیرانی. نظریه پیچیدگی کوانتومی SIAM Journal on Computing, 26 (5): 1411-1473, 1997. 10.1137/S0097539796300921.
https://doi.org/10.1137/S0097539796300921

[6] A. Berthiaume، W. Dam و S. Laplante. پیچیدگی کوانتومی کولموگروف مجله علوم کامپیوتر و سیستم، 63 (2): 201–221، 2001. 10.1006/jcss.2001.1765.
https://doi.org/10.1006/jcss.2001.1765

[7] جی. چایتین. در مورد طول برنامه ها برای محاسبه دنباله های باینری محدود. J. ACM, 13 (4), 1966. 10.1145/321356.321363.
https://doi.org/10.1145/321356.321363

[8] D. Deutsch. نظریه کوانتومی، اصل چرچ-تورینگ و کامپیوتر کوانتومی جهانی. انجمن سلطنتی لندن Proceedings Series A, 400 (1818): 97–117, 1985. 10.1098/rspa.1985.0070.
https://doi.org/10.1098/rspa.1985.0070

[9] P. Gács. آنتروپی الگوریتمی کوانتومی مجله فیزیک الف: ریاضی و عمومی، 34 (35): 6859، 2001. 10.1088/0305-4470/34/35/312.
https://doi.org/10.1088/0305-4470/34/35/312

[10] پیتر گرونوالد و پل ویتانی. نظریه اطلاعات الگوریتمی، صفحات 289-325. E، ژانویه 2008.
arXiv: 0809.2754

[11] ریشارد هورودسکی، پاول هورودسکی، میشال هورودکی، و کارول هورودکی. درهمتنیدگی کوانتومی. بررسی‌های فیزیک مدرن، 81 (2): 865، 2009. 10.1103/RevModPhys.81.865.
https://doi.org/10.1103/RevModPhys.81.865

[12] A. Kolmogorov. سه رویکرد برای تعریف کمی اطلاعات. مسائل انتقال اطلاعات، 1 (1)، 1965. 10.1080/00207166808803030.
https://doi.org/10.1080/00207166808803030

[13] تی لی و آ. رومشچنکو. تقارن محدود به منبع اطلاعات مورد بازبینی مجدد قرار گرفت. علوم کامپیوتر نظری، 345 (2): 386–405، 2005. ISSN 0304-3975. 10.1016/j.tcs.2005.07.017. مبانی ریاضی علوم کامپیوتر 2004.
https://doi.org/10.1016/j.tcs.2005.07.017

[14] مینگ لی و پل ام بی ویتانی. مقدمه ای بر پیچیدگی کولموگروف و کاربردهای آن، ویرایش چهارم. متون در علوم کامپیوتر. Springer, 4. ISBN 2019-978-3-030-11297. 4/10.1007-978-3-030-11298.
https://doi.org/10.1007/978-3-030-11298-1

[15] نوح لیندن و ساندو پوپسکو. مشکل توقف کامپیوترهای کوانتومی arXiv preprint quant-ph/9806054, 1998. 10.48550/arXiv.quant-ph/9806054.
https://doi.org/10.48550/arXiv.quant-ph/9806054
arXiv:quant-ph/9806054

[16] P. Mateus، A. Sernadas، و A. Souto. جهانی بودن ماشین های تورینگ کوانتومی با کنترل قطعی مجله منطق و محاسبات، 27 (1): 1-19، 2017. 10.1093/logcom/exv008.
https://doi.org/10.1093/logcom/exv008

[17] تی میادرا. قضیه پیچیدگی کوانتومی کولموگروف و اختلال اطلاعات. آنتروپی، 13 (4): 778-789، 2011. ISSN 1099-4300. 10.3390/e13040778.
https://doi.org/10.3390/e13040778

[18] T. Miyadera و H. Imai. پیچیدگی کوانتومی کولموگروف و توزیع کلید کوانتومی فیزیک Rev. A, 79: 012324, Jan 2009. 10.1103/PhysRevA.79.012324.
https://doi.org/10.1103/PhysRevA.79.012324

[19] تاکایوکی میادرا و ماسانوری اوهیا. در مورد توقف فرآیند ماشین تورینگ کوانتومی Open Systems & Information Dynamics، 12 (3): 261–264، 2005. 10.1007/s11080-005-0923-2.
https://doi.org/10.1007/s11080-005-0923-2

[20] کاوان مودی، آهارون بروداچ، هوگو کیبل، توماش پاترک و ولاتکو ودرال. مرز کوانتومی کلاسیک برای همبستگی ها: اختلاف و معیارهای مرتبط Reviews of Modern Physics, 84 (4): 1655, 2012. 10.1103/RevModPhys.84.1655.
https://doi.org/10.1103/RevModPhys.84.1655

[21] سی. مورا و اچ. بریگل. پیچیدگی الگوریتمی و درهم تنیدگی حالات کوانتومی Physical Review Letters, 95: 200503, 2005. 10.1103/PhysRevLett.95.200503.
https://doi.org/10.1103/PhysRevLett.95.200503

[22] سی. مورا، اچ. بریگل و بی. کراوس. پیچیدگی کوانتومی کولموگروف و کاربردهای آن مجله بین المللی اطلاعات کوانتومی، 2007. 10.1142/S0219749907003171.
https://doi.org/10.1142/S0219749907003171

[23] ام مولر. پیچیدگی کوانتومی کولموگروف و ماشین تورینگ کوانتومی Ph.D. پایان نامه، دانشگاه فنی برلین، 2007. 10.48550/arXiv.0712.4377.
https://doi.org/10.48550/arXiv.0712.4377

[24] ام. مولر. ماشین‌های تورینگ کوانتومی جهانی قوی و تغییرناپذیری پیچیدگی کولموگروف. IEEE Transactions on Information Theory, 54 (2): 763-780, 2008. ISSN 0018-9448. 10.1109/TIT.2007.913263.
https://doi.org/10.1109/TIT.2007.913263

[25] جان ام مایرز. آیا یک کامپیوتر کوانتومی جهانی می تواند کاملا کوانتومی باشد؟ Physical Review Letters, 78 (9): 1823, 1997. 10.1103/PhysRevLett.78.1823.
https://doi.org/10.1103/PhysRevLett.78.1823

[26] ام. نیلسن و آی. چوانگ. محاسبات کوانتومی و اطلاعات کوانتومی انتشارات دانشگاه کمبریج، 2010. 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[27] یک رستگین یک کران پایین در خطای نسبی شبیه‌سازی حالت مختلط و عملیات مرتبط. Journal of Optics B: Quantum and Semiclassical Optics, 5 (6): S647, 2003. 10.1088/1464-4266/5/6/017.
https://doi.org/10.1088/1464-4266/5/6/017

[28] الف سرکار، ز الارس و کی برتلز. تخمین اطلاعات الگوریتمی با استفاده از محاسبات کوانتومی برای کاربردهای ژنومیک علوم کاربردی، 11 (6)، 2021. ISSN 2076-3417. 10.3390/app11062696.
https://doi.org/10.3390/app11062696

[29] کلود الوود شانون یک نظریه ریاضی ارتباطات. The Bell System Technical Journal, 27 (3): 379–423, 7 1948. 10.1002/j.1538-7305.1948.tb01338.x.
https://doi.org/10.1002/j.1538-7305.1948.tb01338.x

[30] آر. سولومونوف. نظریه رسمی استنتاج استقرایی، بخش اول. اطلاعات و کنترل، 7 (1)، 1964. 10.1016/S0019-9958(64)90223-2.
https://doi.org/10.1016/S0019-9958(64)90223-2

[31] A. Souto، L. Antunes، P. Mateus و A. Teixeira. شاهد پنهان شدن بدون استخراج کننده یا شبیه ساز. در F. Manea, R. Miller, and D. Nowotka, ویراستاران, Sailing Routes in the World of Computation, pages 397–409, Cham, 2018. Springer International Publishing. 10.1007/978-3-319-94418-0_40.
https://doi.org/10.1007/978-3-319-94418-0_40

[32] K. Svozil. نظریه اطلاعات الگوریتمی کوانتومی Journal of Universal Computer Science, 2 (5): 311–346, May 1996. 10.3217/jucs-002-05-0311.
https://doi.org/10.3217/jucs-002-05-0311

[33] آندریا تکسیرا، آرماندو ماتوس، آندره سوتو و لوئیس آنتونس. اندازه گیری آنتروپی در مقابل پیچیدگی کولموگروف. آنتروپی، 13 (3): 595–611، 2011. ISSN 1099-4300. 10.3390/e13030595.
https://doi.org/10.3390/e13030595

[34] P. Vitányi. پیچیدگی کوانتومی کولموگروف بر اساس توصیفات کلاسیک. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/18.945258.
https://doi.org/10.1109/18.945258

[35] پل ویتانی. سه رویکرد برای تعریف کمی اطلاعات در یک حالت کوانتومی خالص. در مجموعه مقالات پانزدهمین کنفرانس سالانه IEEE در مورد پیچیدگی محاسباتی، صفحات 15-263. IEEE، 270. 2000/CCC.10.1109.
https://doi.org/10.1109/CCC.2000.856757

[36] A K Zvonkin و L A Levin. پیچیدگی اجسام محدود و توسعه مفاهیم اطلاعات و تصادفی بودن با استفاده از نظریه الگوریتم ها. بررسی‌های ریاضی روسیه، 25 (6): 83، دسامبر 1970. 10.1070/RM1970v025n06ABEH001269.
https://doi.org/10.1070/RM1970v025n06ABEH001269

ذکر شده توسط

[1] آن برودبنت، مارتی کارونن، و سباستین لرد، "نصیحت کوانتومی غیرقابل شبیه سازی"، arXiv: 2309.05155, (2023).

نقل قول های بالا از SAO/NASA Ads (آخرین به روز رسانی با موفقیت 2024-01-18 23:13:56). فهرست ممکن است ناقص باشد زیرا همه ناشران داده های استنادی مناسب و کاملی را ارائه نمی دهند.

On سرویس استناد شده توسط Crossref هیچ داده ای در مورد استناد به آثار یافت نشد (آخرین تلاش 2024-01-18 23:13:55).

این مقاله در Quantum تحت عنوان منتشر شده است Creative Commons Attribution 4.0 International (CC BY 4.0) مجوز. حق چاپ نزد دارندگان حق چاپ اصلی مانند نویسندگان یا مؤسسات آنها باقی می ماند.

محتوای مبتنی بر SEO و توزیع روابط عمومی. امروز تقویت شوید.
PlatoData.Network Vertical Generative Ai. به خودت قدرت بده دسترسی به اینجا.
PlatoAiStream. هوش وب 3 دانش تقویت شده دسترسی به اینجا.
PlatoESG. کربن ، CleanTech، انرژی، محیط، خورشیدی، مدیریت پسماند دسترسی به اینجا.
PlatoHealth. هوش بیوتکنولوژی و آزمایشات بالینی. دسترسی به اینجا.
منبع: https://quantum-journal.org/papers/q-2024-01-18-1230/

تمبر زمان: ژانویه 18، 2024

تمبر زمان: آوریل 13، 2023

بازنشر افلاطون

چکیده

► داده های BibTeX

◄ مراجع

ذکر شده توسط

به سمت یک چارچوب کلی از معیارهای تصادفی شده که نویز غیر مارکوویی را در بر می گیرد

شاهد بعد محیطی از طریق همبستگی های زمانی

همبستگی های محدود شده توسط اندازه گیری های مرکب

دینامیک تعادل جهانی مدل Sachdev-Ye-Kitaev

عمده سازی پیوسته در فضای فاز کوانتومی

در مورد ضرایب انقباض، سفارشات جزئی و تقریب ظرفیت برای کانال های کوانتومی

بهینه سازی کوانتومی برابری: کامپایلر

شبکه های کوانتومی بهینه شده

فریم های متقابل بی طرفانه

حل مشکلات آشکارساز تک فوتون

تقویت رمزنگاری مستقل از دستگاه با غیرمحلی سه جانبه

درباره‌ ما

جستجوی عمودی و هوش مصنوعی

سکو

همیشه در ارتباط ماندن

حساب