Κβαντική πολυπλοκότητα Kolmogorov και κβαντικές συσχετίσεις σε ντετερμινιστικές μηχανές κβαντικής Turing

Αναδημοσίευση από τον Πλάτωνα

Ακολουθούν: 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 Lisboa, Πορτογαλία

Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.

Περίληψη

Αυτή η εργασία παρουσιάζει μια μελέτη της πολυπλοκότητας Kolmogorov για γενικές κβαντικές καταστάσεις από την προοπτική των ντετερμινιστικών-ελέγχων κβαντικών μηχανών Turing (dcq-TM). Επεκτείνουμε το μοντέλο dcq-TM για να ενσωματώσει εισόδους και εξόδους μικτής κατάστασης και ορίζουμε καταστάσεις dcq-υπολογίσιμες ως εκείνες που μπορούν να προσεγγιστούν με ένα dcq-TM. Επιπλέον, εισάγουμε (υπό όρους) την πολυπλοκότητα Kolmogorov των κβαντικών καταστάσεων και τη χρησιμοποιούμε για να μελετήσουμε τρεις συγκεκριμένες πτυχές των αλγοριθμικών πληροφοριών που περιέχονται σε μια κβαντική κατάσταση: μια σύγκριση της πληροφορίας σε μια κβαντική κατάσταση με αυτή της κλασικής αναπαράστασής της ως πίνακα πραγματικών αριθμοί, μια εξερεύνηση των ορίων της αντιγραφής κβαντικής κατάστασης στο πλαίσιο της αλγοριθμικής πολυπλοκότητας και μελέτη της πολυπλοκότητας των συσχετίσεων σε κβαντικά συστήματα, με αποτέλεσμα έναν ορισμό με επίγνωση συσχέτισης για αλγοριθμική αμοιβαία πληροφορία που ικανοποιεί τη συμμετρία της ιδιότητας πληροφοριών.

► Δεδομένα 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. Μονόδρομες συναρτήσεις με χρήση αλγοριθμικών και κλασικών θεωριών πληροφοριών. Theory of Computing Systems, 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. Εντροπία και κβαντική πολυπλοκότητα Kolmogorov: Ένα κβαντικό θεώρημα Brudno. Commun. Μαθηματικά. Phys., 265 (1): 437–461, 2006. 10.1007/s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

[4] C. H. Bennett και G. Brassard. Κβαντική κρυπτογραφία: Διανομή δημόσιου κλειδιού και ρίψη νομισμάτων. In 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] E. Bernstein και U. Vazirani. Θεωρία κβαντικής πολυπλοκότητας. 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. Κβαντική πολυπλοκότητα Κολμογκόροφ. Journal of Computer and System Sciences, 63 (2): 201–221, 2001. 10.1006/jcss.2001.1765.
https: / / doi.org/ 10.1006 / jcss.2001.1765

[7] G. Chaitin. Σχετικά με τη διάρκεια των προγραμμάτων για τον υπολογισμό πεπερασμένων δυαδικών ακολουθιών. J. ACM, 13 (4), 1966. 10.1145/321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363

[8] D. Deutsch. Η κβαντική θεωρία, η αρχή Church-Turing και ο παγκόσμιος κβαντικός υπολογιστής. 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] Peter Grünwald και Paul Vitányi. Algorithmic Information Theory, σελίδες 289–325. Ε, Ιανουάριος 2008.
arXiv: 0809.2754

[11] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki και Karol Horodecki. Κβαντική διαπλοκή. Κριτικές της σύγχρονης φυσικής, 81 (2): 865, 2009. 10.1103/RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

[12] Α. Κολμογκόροφ. Τρεις προσεγγίσεις για τον ποσοτικό ορισμό της πληροφορίας. Problems of Information Transmission, 1 (1), 1965. 10.1080/00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030

[13] T. Lee και A. Romashchenko. Η συμμετρία των πληροφοριών που επισκέπτονται ξανά τους πόρους. Theoretical Computer Science, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/j.tcs.2005.07.017. Mathematical Bass of Computer Science 2004.
https: / / doi.org/ 10.1016 / j.tcs.2005.07.017

[14] Ming Li και Paul M. B. Vitányi. Εισαγωγή στην πολυπλοκότητα του Kolmogorov και τις εφαρμογές της, 4η Έκδοση. Κείμενα στην Πληροφορική. Springer, 2019. ISBN 978-3-030-11297-4. 10.1007/978-3-030-11298-1.
https://doi.org/10.1007/978-3-030-11298-1

[15] Νόα Λίντεν και Σαντού Ποπέσκου. Το πρόβλημα διακοπής για κβαντικούς υπολογιστές. arXiv προεκτύπωση quant-ph/9806054, 1998. 10.48550/arXiv.quant-ph/9806054.
https://doi.org/10.48550/arXiv.quant-ph/9806054
arXiv: quant-ph / 9806054

[16] Π. Ματέους, Α. Σερνάδας και Α. Σούτο. Καθολικότητα κβαντικών μηχανών Turing με ντετερμινιστικό έλεγχο. Journal of Logic and Computation, 27 (1): 1–19, 2017. 10.1093/logcom/exv008.
https://doi.org/10.1093/logcom/exv008

[17] Τ. Miyadera. Κβαντικό θεώρημα πολυπλοκότητας Kolmogorov και πληροφορίας-διαταραχής. Entropy, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/e13040778.
https: / / doi.org/ 10.3390 / e13040778

[18] T. Miyadera and H. Imai. Κβαντική πολυπλοκότητα Κολμογκόροφ και κατανομή κβαντικού κλειδιού. Phys. Rev. A, 79: 012324, Ιαν 2009. 10.1103/PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[19] Takayuki Miyadera και Masanori Ohya. Σχετικά με τη διαδικασία διακοπής της κβαντικής μηχανής τουρισμού. 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] Kavan Modi, Aharon Brodutch, Hugo Cable, Tomasz Paterek και Vlatko Vedral. Το κλασικό-κβαντικό όριο για συσχετίσεις: Διαφωνία και συναφή μέτρα. Reviews of Modern Physics, 84 (4): 1655, 2012. 10.1103/RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

[21] C. Mora και H. Briegel. Αλγοριθμική πολυπλοκότητα και εμπλοκή κβαντικών καταστάσεων. Physical Review Letters, 95: 200503, 2005. 10.1103/PhysRevLett.95.200503.
https: / / doi.org/ 10.1103 / PhysRevLett.95.200503

[22] C. Mora, H. Briegel, and B. Kraus. Η πολυπλοκότητα της κβαντικής κολμογκόροφ και οι εφαρμογές της. International Journal of Quantum Information, 2007. 10.1142/S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[23] M Muller. Η κβαντική πολυπλοκότητα του Κολμογκόροφ και η κβαντική μηχανή Turing. Ph.D. Thesis, Technical University of Berlin, 2007. 10.48550/arXiv.0712.4377.
https://doi.org/10.48550/arXiv.0712.4377

[24] Μ. Μύλλερ. Ισχυρά καθολικές κβαντικές μηχανές Turing και αμετάβλητη πολυπλοκότητα Kolmogorov. 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] John M Myers. Μπορεί ένας παγκόσμιος κβαντικός υπολογιστής να είναι πλήρως κβαντικός; Physical Review Letters, 78 (9): 1823, 1997. 10.1103/PhysRevLett.78.1823.
https: / / doi.org/ 10.1103 / PhysRevLett.78.1823

[26] Μ. Νίλσεν και Ι. Τσουάνγκ. Κβαντικός Υπολογισμός και Κβαντικές Πληροφορίες. Cambridge University Press, 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] Α. Sarkar, Z. Al-Ars, and K. Bertels. Εκτίμηση αλγοριθμικών πληροφοριών με χρήση κβαντικών υπολογιστών για εφαρμογές γονιδιωματικής. Εφαρμοσμένες Επιστήμες, 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] Ρ. Σολομόνωφ. Μια επίσημη θεωρία επαγωγικών συμπερασμάτων, μέρος i. Information and Control, 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, σελίδες 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, Μάιος 1996. 10.3217/jucs-002-05-0311.
https://doi.org/10.3217/jucs-002-05-0311

[33] Andreia Teixeira, Armando Matos, André Souto και Luís Antunes. Μέτρα εντροπίας έναντι πολυπλοκότητας Kolmogorov. Entropy, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/e13030595.
https: / / doi.org/ 10.3390 / e13030595

[34] P. Vitányi. Κβαντική πολυπλοκότητα Kolmogorov βασισμένη σε κλασικές περιγραφές. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/18.945258.
https: / / doi.org/ 10.1109 / 18.945258

[35] Paul Vitanyi. Τρεις προσεγγίσεις για τον ποσοτικό ορισμό της πληροφορίας σε μια μεμονωμένη καθαρή κβαντική κατάσταση. In Proceedings 15th Annual IEEE Conference on Computational Complexity, σελίδες 263–270. IEEE, 2000. 10.1109/CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

[36] A K Zvonkin και L A Levin. Η πολυπλοκότητα των πεπερασμένων αντικειμένων και η ανάπτυξη των εννοιών της πληροφορίας και της τυχαιότητας μέσω της θεωρίας των αλγορίθμων. Russian Mathematical Surveys, 25 (6): 83, dec 1970. 10.1070/RM1970v025n06ABEH001269.
https://doi.org/10.1070/RM1970v025n06ABEH001269

Αναφέρεται από

[1] Anne Broadbent, Martti Karvonen και Sébastien Lord, «Uncloneable Quantum Advice», 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 Διεθνής (CC BY 4.0) άδεια. Τα πνευματικά δικαιώματα παραμένουν στους κατόχους των πρωτότυπων δικαιωμάτων πνευματικής ιδιοκτησίας όπως οι δημιουργοί ή τα ιδρύματά τους

SEO Powered Content & PR Distribution. Ενισχύστε σήμερα.
PlatoData.Network Vertical Generative Ai. Ενδυναμώστε τον εαυτό σας. Πρόσβαση εδώ.
PlatoAiStream. Web3 Intelligence. Ενισχύθηκε η γνώση. Πρόσβαση εδώ.
PlatoESG. Ανθρακας, Cleantech, Ενέργεια, Περιβάλλον, Ηλιακός, Διαχείριση των αποβλήτων. Πρόσβαση εδώ.
PlatoHealth. Ευφυΐα βιοτεχνολογίας και κλινικών δοκιμών. Πρόσβαση εδώ.
πηγή: https://quantum-journal.org/papers/q-2024-01-18-1230/

Σφραγίδα ώρας: Ιανουάριος 18, 2024

Σφραγίδα ώρας: 13 Απριλίου 2023

Αναδημοσίευση από τον Πλάτωνα

Περίληψη

► Δεδομένα BibTeX

► Αναφορές

Αναφέρεται από

Προς ένα γενικό πλαίσιο τυχαιοποιημένης συγκριτικής αξιολόγησης που ενσωματώνει μη-μαρκοβιανό θόρυβο

Μαρτυρική διάσταση περιβάλλοντος μέσω χρονικών συσχετισμών

Συσχετισμοί που περιορίζονται από σύνθετες μετρήσεις

Καθολική δυναμική εξισορρόπησης του μοντέλου Sachdev-Ye-Kitaev

Συνεχής μείζονα στο χώρο κβαντικής φάσης

Σχετικά με τους συντελεστές συστολής, τις μερικές τάξεις και την προσέγγιση των χωρητικοτήτων για κβαντικά κανάλια

Parity Quantum Optimization: Μεταγλωττιστής

Βελτιστοποιημένα Κβαντικά Δίκτυα

Αμοιβαία αμερόληπτα πλαίσια

Επίλυση προβλημάτων ανιχνευτή ενός φωτονίου

Ενίσχυση κρυπτογραφίας ανεξάρτητης συσκευής με τριμερή μη τοπικότητα

Σχετικά με μας

Κάθετη αναζήτηση & Ai

Πλατφόρμα

Μείνετε συνδεδεμένοι

Λογαριασμός