Complexité quantique de Kolmogorov et corrélations quantiques dans les machines de Turing quantiques à contrôle déterministe

Complexité quantique de Kolmogorov et corrélations quantiques dans les machines de Turing quantiques à contrôle déterministe

Horodatage: 18 janvier 2024 6:07 AM
Nœud source: 3070552

Mariano Lemus1,2, Ricardo Faleiro1,2, Paulo Mateus1,2, Nikola Paunkovic1,2et une André Souto2,3,4

1Departamento de Matemática, Instituto Superior Técnico, Universidade de Lisboa, Av.Rovisco Pais, 1049-001 Lisboa, Portugal
2Instituto de Telecomunicações, Av.Rovisco Pais, 1049-001 Lisbonne, Portugal
3Lasige, Faculdade de Ciências da Universidade de Lisboa, Campo Grande, 1749-016 Lisbonne, Portugal
4Departamento de Informática,Faculdade de Ciências da Universidade de Lisboa, Campo Grande, 1749-016 Lisbonne, Portugal

Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.

Abstract

Ce travail présente une étude de la complexité de Kolmogorov pour les états quantiques généraux du point de vue des machines de Turing quantiques à contrôle déterministe (dcq-TM). Nous étendons le modèle dcq-TM pour incorporer des entrées et sorties d'états mixtes, et définissons les états calculables par dcq comme ceux qui peuvent être approchés par un dcq-TM. De plus, nous introduisons la complexité (conditionnelle) de Kolmogorov des états quantiques et l'utilisons pour étudier trois aspects particuliers de l'information algorithmique contenue dans un état quantique : une comparaison de l'information dans un état quantique avec celle de sa représentation classique comme un tableau d'informations réelles. nombres, une exploration des limites de la copie d'état quantique dans le contexte de la complexité algorithmique et une étude de la complexité des corrélations dans les systèmes quantiques, aboutissant à une définition sensible aux corrélations pour les informations mutuelles algorithmiques qui satisfont la symétrie des propriétés de l'information.

► Données BibTeX

► Références

L. Antunes, A. Matos, A. Pinto, A. Souto et A. Teixeira. Fonctions à sens unique utilisant les théories algorithmiques et classiques de l'information. Théorie des systèmes informatiques, 52 (1) : 162-178, janvier 2013. ISSN 1433-0490. 10.1007/​s00224-012-9418-z.
https: / / doi.org/ 10.1007 / s00224-012-9418-z

D. Azevedo, A. M. Rodrigues, H. Canhão, A. M. Carvalho et A. Souto. Zgli : Un pipeline de regroupement par compression avec application à la stratification des patients atteints de spondylarthrite. Capteurs, 23 (3), 2023. ISSN 1424-8220. 10.3390/​s23031219.
https: / / doi.org/ 10.3390 / s23031219

F. Benatti, T. Krüger, M. Müller, R. Siegmund-Schultze et A. Szkoła. Entropie et complexité quantique de Kolmogorov : un théorème quantique de Brudno. Commun. Mathématiques. Phys., 265 (1) : 437-461, 2006. 10.1007/​s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

C. H. Bennett et G. Brassard. Cryptographie quantique : distribution de clés publiques et tirage au sort. Dans Actes de la Conférence internationale de l'IEEE sur les ordinateurs, les systèmes et le traitement du signal, page 175, 1984. 10.1016/​j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

E. Bernstein et U. Vazirani. Théorie de la complexité quantique. SIAM Journal on Computing, 26 (5) : 1411-1473, 1997. 10.1137/​S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

A. Berthiaume, W. Dam et S. Laplante. Complexité quantique de Kolmogorov. Journal of Computer and System Sciences, 63 (2) : 201-221, 2001. 10.1006/​jcss.2001.1765.
https: / / doi.org/ 10.1006 / jcss.2001.1765

G. Chaitin. Sur la longueur des programmes de calcul de séquences binaires finies. J. ACM, 13 (4), 1966. 10.1145/​321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363

D. Deutsch. Théorie quantique, principe de Church-Turing et ordinateur quantique universel. Actes de la Royal Society of London, série A, 400 (1818) : 97-117, 1985. 10.1098/​rspa.1985.0070.
https: / / doi.org/ 10.1098 / rspa.1985.0070

P. Gács. Entropie algorithmique quantique. 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

Peter Grünwald et Paul Vitányi. Théorie de l'information algorithmique, pages 289-325. E, janvier 2008.
arXiv: 0809.2754

Ryszard Horodecki, Paweł Horodecki, Michał Horodecki et Karol Horodecki. Intrication quantique. Revues de physique moderne, 81 (2) : 865, 2009. 10.1103/​RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

A. Kolmogorov. Trois approches de la définition quantitative de l'information. Problèmes de transmission de l'information, 1 (1), 1965. 10.1080/​00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030

T. Lee et A. Romashchenko. La symétrie de l'information limitée aux ressources est revisitée. Informatique théorique, 345 (2) : 386-405, 2005. ISSN 0304-3975. 10.1016/​j.tcs.2005.07.017. Fondements mathématiques de l'informatique 2004.
https: / / doi.org/ 10.1016 / j.tcs.2005.07.017

Ming Li et Paul MB Vitányi. Une introduction à la complexité de Kolmogorov et à ses applications, 4e édition. Textes en informatique. Springer, 2019. ISBN978-3-030-11297-4. 10.1007/​978-3-030-11298-1.
https:/​/​doi.org/​10.1007/​978-3-030-11298-1

Noah Linden et Sandu Popescu. Le problème de l’arrêt des ordinateurs quantiques. préimpression arXiv quant-ph/​9806054, 1998. 10.48550/​arXiv.quant-ph/​9806054.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9806054
arXiv: quant-ph / 9806054

P. Mateus, A. Sernadas et A. Souto. Universalité des machines de Turing quantiques à contrôle déterministe. Journal of Logic and Computation, 27 (1) : 1-19, 2017. 10.1093/​logcom/​exv008.
https://​/​doi.org/​10.1093/​logcom/​exv008

T. Miyadera. Complexité quantique de Kolmogorov et théorème de perturbation de l'information. Entropie, 13 (4) : 778-789, 2011. ISSN 1099-4300. 10.3390/​e13040778.
https: / / doi.org/ 10.3390 / e13040778

T. Miyadera et H. Imai. Complexité quantique de Kolmogorov et distribution des clés quantiques. Phys. A, 79 : 012324, janvier 2009. 10.1103/​PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

Takayuki Miyadera et Masanori Ohya. Sur l’arrêt du processus de machine de turing quantique. Systèmes ouverts et dynamique de l'information, 12 (3) : 261-264, 2005. 10.1007/​s11080-005-0923-2.
https:/​/​doi.org/​10.1007/​s11080-005-0923-2

Kavan Modi, Aharon Brodutch, Hugo Cable, Tomasz Paterek et Vlatko Vedral. La limite quantique classique pour les corrélations : Discorde et mesures associées. Reviews of Modern Physics, 84 (4): 1655, 2012. 10.1103/​RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

C. Mora et H. Briegel. Complexité algorithmique et intrication des états quantiques. Lettres d'examen physique, 95 : 200503, 2005. 10.1103/​PhysRevLett.95.200503.
https: / / doi.org/ 10.1103 / PhysRevLett.95.200503

C. Mora, H. Briegel et B. Kraus. Complexité quantique de Kolmogorov et ses applications. Journal international d'information quantique, 2007. 10.1142/​S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

M Muller. Complexité quantique de Kolmogorov et machine quantique de Turing. doctorat Thèse, Université technique de Berlin, 2007. 10.48550/​arXiv.0712.4377.
https://​/​doi.org/​10.48550/​arXiv.0712.4377

M. Muller. Machines de Turing quantiques fortement universelles et invariance de la complexité de Kolmogorov. Transactions IEEE sur la théorie de l'information, 54 (2) : 763-780, 2008. ISSN 0018-9448. 10.1109/​TIT.2007.913263.
https: / / doi.org/ 10.1109 / TIT.2007.913263

John M. Myers. Un ordinateur quantique universel peut-il être entièrement quantique ? Lettres d'examen physique, 78 (9) : 1823, 1997. 10.1103/​PhysRevLett.78.1823.
https: / / doi.org/ 10.1103 / PhysRevLett.78.1823

M. Nielsen et I. Chuang. Calcul quantique et information quantique. Cambridge University Press, 2010. 10.1017/​CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

Un Rastegin. Limite inférieure de l'erreur relative du clonage à états mixtes et des opérations associées. Journal of Optics B : Optique quantique et semi-classique, 5 (6) : S647, 2003. 10.1088/​1464-4266/​5/​6/​017.
https:/​/​doi.org/​10.1088/​1464-4266/​5/​6/​017

A. Sarkar, Z. Al-Ars et K. Bertels. Estimation des informations algorithmiques à l'aide de l'informatique quantique pour les applications génomiques. Sciences appliquées, 11 (6), 2021. ISSN 2076-3417. 10.3390/​app11062696.
https://​/​doi.org/​10.3390/​app11062696

Claude Elwood Shannon. Une théorie mathématique de la communication. Le journal technique du système Bell, 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

R. Solomonoff. Une théorie formelle de l'inférence inductive, partie i. Information et contrôle, 7 (1), 1964. 10.1016/​S0019-9958(64)90223-2.
https:/​/​doi.org/​10.1016/​S0019-9958(64)90223-2

A. Souto, L. Antunes, P. Mateus et A. Teixeira. Témoin caché sans extracteurs ni simulateurs. Dans F. Manea, R. Miller et D. Nowotka, éditeurs, 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

K. Svozil. Théorie de l'information algorithmique quantique. Journal of Universal Computer Science, 2 (5) : 311-346, mai 1996. 10.3217/​jucs-002-05-0311.
https://​/​doi.org/​10.3217/​jucs-002-05-0311

Andreia Teixeira, Armando Matos, André Souto et Luís Antunes. Mesures d'entropie par rapport à la complexité de Kolmogorov. Entropie, 13 (3) : 595-611, 2011. ISSN 1099-4300. 10.3390/​e13030595.
https: / / doi.org/ 10.3390 / e13030595

P. Vitányi. Complexité quantique de Kolmogorov basée sur des descriptions classiques. Transactions IEEE sur la théorie de l'information, 47 (6) : 2464-2479, 2001. 10.1109/​18.945258.
https: / / doi.org/ 10.1109 / 18.945258

Paul Vitanyi. Trois approches de la définition quantitative de l'information dans un état quantique pur individuel. Dans Actes de la 15e conférence annuelle de l'IEEE sur la complexité informatique, pages 263 à 270. IEEE, 2000. 10.1109/​CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

AK Zvonkin et LA Levin. La complexité des objets finis et le développement des notions d'information et d'aléatoire à travers la théorie des algorithmes. Russian Mathematical Surveys, 25 (6) : 83, décembre 1970. 10.1070/​RM1970v025n06ABEH001269.
https:/​/​doi.org/​10.1070/​RM1970v025n06ABEH001269

Cité par

[1] Anne Broadbent, Martti Karvonen et Sébastien Lord, « Uncloneable Quantum Advice », arXiv: 2309.05155, (2023).

Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2024-01-18 23:13:56). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.

On Le service cité par Crossref aucune donnée sur la citation des œuvres n'a été trouvée (dernière tentative 2024-01-18 23:13:55).

Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.

Horodatage:

Plus de Journal quantique