המורכבות הקוונטית קולמוגורוב ומתאמים קוונטיים במכונות טיורינג קוונטיות בקרה דטרמיניסטית

הועלה מחדש על ידי אפלטון

עוקב: 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, Portugal
²Instituto de Telecomunicações, Av.Rovisco Pais, 1049-001 Lisboa, פורטוגל
³Lasige, Faculdade de Ciências da Universidade de Lisboa, Campo Grande, 1749-016 Lisboa, Portugal
⁴Departamento de Informática,Faculdade de Ciências da Universidade de Lisboa, Campo Grande, 1749-016 Lisboa, Portugal

מצא את העיתון הזה מעניין או רוצה לדון? סקייט או השאירו תגובה ב- 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, and 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, AM Rodrigues, H. Canhão, AM Carvalho, ו-A. Souto. זגלי: צינור לאיסוף על ידי דחיסה עם יישום על ריבוד חולים בספונדילוארתריטיס. חיישנים, 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, and A. Szkoła. אנטרופיה ומורכבות קוונטית קולמוגורוב: משפט קוונטים של ברודנו. Commun. מתמטיקה. Phys., 265 (1): 437–461, 2006. 10.1007/s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

[4] CH Bennett and G. Brassard. הצפנה קוונטית: הפצת מפתח ציבורי והטלת מטבעות. ב-Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, עמוד 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] א' ברתיאום, וו' דאם וס' לפלנטה. המורכבות הקוונטית של קולמוגורוב. כתב עת למדעי המחשב והמערכת, 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] ד דויטש. תורת הקוונטים, עקרון הכנסייה-טיורינג והמחשב הקוונטי האוניברסלי. Royal Society of London 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. אנטרופיה אלגוריתמית קוונטית. Journal of Physics A: Mathematical and General, 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] א קולמוגורוב. שלוש גישות להגדרה כמותית של מידע. בעיות של העברת מידע, 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] מינג לי ופול MB Vitányi. מבוא למורכבות קולמוגורוב ויישומיה, מהדורה רביעית. טקסטים במדעי המחשב. שפרינגר, 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. אוניברסליות של מכונות טיורינג קוונטיות עם בקרה דטרמיניסטית. Journal of Logic and Computation, 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] ט' מיאדרה וה' אימאי. המורכבות הקוונטית קולמוגורוב והפצת מפתח קוונטי. פיזי. Rev. A, 79: 012324, ינואר 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] קאבן מודי, אהרון ברודוץ', הוגו כבל, תומאש פטרק וולטקו ודראל. הגבול הקלאסי-קוונטי עבור מתאמים: מחלוקת ומדדים קשורים. ביקורות על פיזיקה מודרנית, 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] סי' מורה, ח' בריגל וב' קראוס. המורכבות הקוונטית קולמוגורוב והיישומים שלה. International Journal of Quantum Information, 2007. 10.1142/S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[23] מ. מולר. המורכבות הקוונטית קולמוגורוב ומכונת הטיורינג הקוונטית. דוקטורט. תזה, האוניברסיטה הטכנית של ברלין, 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/S10.1016-0019(9958)64-90223.
https://doi.org/10.1016/S0019-9958(64)90223-2

[31] A. Souto, L. Antunes, P. Mateus, and A. Teixeira. עד מסתתר ללא חולצים או סימולטורים. בתוך F. Manea, R. Miller, and D. Nowotka, עורכים, Sailing Routes in the World of Computing, עמודים 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] ק סבוזיל. תורת המידע האלגוריתמי הקוונטי. Journal of Universal Computer Science, 2 (5): 311–346, מאי 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] פ. ויטאני. המורכבות הקוונטית של קולמוגורוב מבוססת על תיאורים קלאסיים. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/18.945258.
https: / / doi.org/ 10.1109 / 18.945258

[35] פול ויטני. שלוש גישות להגדרה כמותית של מידע במצב קוונטי טהור אינדיבידואלי. בכנס IEEE השנתי ה-15 של Proceedings בנושא מורכבות חישובית, עמודים 263–270. IEEE, 2000. 10.1109/CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

[36] א"ק זבונקין ול"א לוין. מורכבותם של עצמים סופיים ופיתוח מושגי מידע ואקראיות באמצעות תורת האלגוריתמים. Russian Mathematical Surveys, 25 (6): 83, דצמבר 1970. 10.1070/RM1970v025n06ABEH001269.
https://doi.org/10.1070/RM1970v025n06ABEH001269

מצוטט על ידי

[1] אן ברודבנט, מרטי קרבונן וסבסטיאן לורד, "עצות קוונטיות בלתי ניתנות לשיבוט", arXiv: 2309.05155, (2023).

הציטוטים לעיל הם מ- מודעות SAO / NASA (עודכן לאחרונה בהצלחה 2024-01-18 23:13:56). הרשימה עשויה להיות שלמה מכיוון שלא כל בעלי האתרים מספקים נתוני ציטוט ראויים ומלאים.

On השירות המוזכר של קרוסרף לא נמצאו נתונים על ציטוט עבודות (ניסיון אחרון 2024-01-18 23:13:55)

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

הפצת תוכן ויחסי ציבור מופעל על ידי SEO. קבל הגברה היום.
PlatoData.Network Vertical Generative Ai. העצים את עצמך. גישה כאן.
PlatoAiStream. Web3 Intelligence. הידע מוגבר. גישה כאן.
PlatoESG. פחמן, קלינטק, אנרגיה, סביבה, שמש, ניהול פסולת. גישה כאן.
PlatoHealth. מודיעין ביוטכנולוגיה וניסויים קליניים. גישה כאן.
מקור: https://quantum-journal.org/papers/q-2024-01-18-1230/

בול זמן: ינואר 18, 2024

בול זמן: ספטמבר 11, 2023

הועלה מחדש על ידי אפלטון

תַקצִיר

► נתוני BibTeX

► הפניות

מצוטט על ידי

אבחון רמות עקרה עם כלים מ-Quantum Optimal Control

חידוד של Positivstellensatz של רזניק עם יישומים לתורת המידע הקוונטי

טלפורטציה מטהרת

ניתן להעריך ערוצי פאולי ממדידות תסמונת בתיקון שגיאות קוונטי

מיצוי איתן של נתונים תרמיים מדגימת מצבים ודינמיקה בזמן אמת במחשבים קוונטיים

חישוב קוונטי סובלני לתקלות של נתונים מולקולריים

1000 מאמרים קוונטיים!

שילוב קוואנטום מונטה קרלו: היתרון המלא בעומק מעגל מינימלי

על אלגוריתמים בעומק נמוך להערכת פאזה קוונטית

הערכות אנרגיית מצב קרקע עמידים ברעש ממעגלים קוונטיים עמוקים

אודות

חיפוש אנכי ו- Ai

פלטפורמה

שמור על קשר

חֶשְׁבּוֹן