Quantum Kolmogorov-kompleksitet og kvantekorrelationer i deterministisk kontrol-kvanteturing-maskiner

Genudgivet af Platon

Abonnenter: 0

Mariano Lemus^1,2, Ricardo Faleiro^1,2, Paulo Mateus^1,2, Nikola Paunković^1,2og André Souto^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, Portugal
³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

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Dette arbejde præsenterer en undersøgelse af Kolmogorovs kompleksitet for generelle kvantetilstande fra perspektivet af deterministisk-kontrol kvante Turing Machines (dcq-TM). Vi udvider dcq-TM-modellen til at inkorporere input og output med blandede tilstande og definerer dcq-beregnelige tilstande som dem, der kan tilnærmes af en dcq-TM. Desuden introducerer vi (betinget) Kolmogorov kompleksitet af kvantetilstande og bruger den til at studere tre særlige aspekter af den algoritmiske information indeholdt i en kvantetilstand: en sammenligning af informationen i en kvantetilstand med den af dens klassiske repræsentation som en række reelle tal, en udforskning af grænserne for kvantetilstandskopiering i sammenhæng med algoritmisk kompleksitet og undersøgelse af kompleksiteten af korrelationer i kvantesystemer, hvilket resulterer i en korrelationsbevidst definition af algoritmisk gensidig information, der tilfredsstiller symmetri af informationsegenskaber.

► BibTeX-data

@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} }

► Referencer

[1] L. Antunes, A. Matos, A. Pinto, A. Souto og A. Teixeira. Envejsfunktioner ved hjælp af algoritmiske og klassiske informationsteorier. Theory of Computing Systems, 52 (1): 162-178, jan 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 og A. Souto. Zgli: En pipeline til klyngedannelse ved kompression med anvendelse på patientstratifikation ved spondyloarthritis. Sensorer, 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 og A. Szkoła. Entropi og kvante Kolmogorov kompleksitet: En kvante Brudnos teorem. Commun. Matematik. Phys., 265 (1): 437-461, 2006. 10.1007/s00220-006-0027-z.
https:///doi.org/10.1007/s00220-006-0027-z

[4] CH Bennett og G. Brassard. Kvantekryptografi: Offentlig nøgledistribution og møntkastning. I Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, side 175, 1984. 10.1016/j.tcs.2014.05.025.
https:///doi.org/10.1016/j.tcs.2014.05.025

[5] E. Bernstein og U. Vazirani. Kvantekompleksitetsteori. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137/S0097539796300921.
https:///doi.org/10.1137/S0097539796300921

[6] A. Berthiaume, W. Dam og S. Laplante. Kvante Kolmogorov kompleksitet. 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. Om længden af programmer til beregning af endelige binære sekvenser. J. ACM, 13 (4), 1966. 10.1145/321356.321363.
https:///doi.org/10.1145/321356.321363

[8] D. Deutsch. Kvanteteori, Church-Turing-princippet og den universelle kvantecomputer. 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. Kvantealgoritmisk entropi. 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 og Paul Vitányi. Algoritmisk informationsteori, side 289-325. E, januar 2008.
arXiv: 0809.2754

[11] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki og Karol Horodecki. Kvantesammenfiltring. Reviews of modern physics, 81 (2): 865, 2009. 10.1103/RevModPhys.81.865.
https:///doi.org/10.1103/RevModPhys.81.865

[12] A. Kolmogorov. Tre tilgange til den kvantitative definition af information. Problemer med informationstransmission, 1 (1), 1965. 10.1080/00207166808803030.
https:///doi.org/10.1080/00207166808803030

[13] T. Lee og A. Romashchenko. Ressourcebegrænset symmetri af genbesøgt information. Teoretisk datalogi, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/j.tcs.2005.07.017. Mathematical Foundations of Computer Science 2004.
https:///doi.org/10.1016/j.tcs.2005.07.017

[14] Ming Li og Paul MB Vitányi. En introduktion til Kolmogorovs kompleksitet og dens anvendelser, 4. udgave. Tekster i datalogi. 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] Noah Linden og Sandu Popescu. Det stoppende problem for kvantecomputere. 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 og A. Souto. Universalitet af kvante Turing-maskiner med deterministisk kontrol. Journal of Logic and Computation, 27 (1): 1-19, 2017. 10.1093/logcom/exv008.
https:///doi.org/10.1093/logcom/exv008

[17] T. Miyadera. Kvante Kolmogorov kompleksitet og informationsforstyrrelse teorem. Entropy, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/e13040778.
https:///doi.org/10.3390/e13040778

[18] T. Miyadera og H. Imai. Kvante Kolmogorov kompleksitet og kvante nøglefordeling. Phys. Rev. A, 79: 012324, jan 2009. 10.1103/PhysRevA.79.012324.
https:///doi.org/10.1103/PhysRevA.79.012324

[19] Takayuki Miyadera og Masanori Ohya. Ved standsning af kvantedrejemaskine. 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 og Vlatko Vedral. Den klassiske kvantegrænse for korrelationer: Uenighed og relaterede mål. Reviews of Modern Physics, 84 (4): 1655, 2012. 10.1103/RevModPhys.84.1655.
https:///doi.org/10.1103/RevModPhys.84.1655

[21] C. Mora og H. Briegel. Algoritmisk kompleksitet og sammenfiltring af kvantetilstande. Physical Review Letters, 95: 200503, 2005. 10.1103/PhysRevLett.95.200503.
https:///doi.org/10.1103/PhysRevLett.95.200503

[22] C. Mora, H. Briegel og B. Kraus. Quantum Kolmogorov kompleksitet og dens applikationer. International Journal of Quantum Information, 2007. 10.1142/S0219749907003171.
https:///doi.org/10.1142/S0219749907003171

[23] M Muller. Quantum Kolmogorov kompleksitet og kvante Turing maskinen. Ph.D. Speciale, Tekniske Universitet i Berlin, 2007. 10.48550/arXiv.0712.4377.
https:///doi.org/10.48550/arXiv.0712.4377

[24] M. Müller. Stærkt universelle kvante Turing-maskiner og invarians af Kolmogorov-kompleksitet. 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. Kan en universel kvantecomputer være fuld kvante? Physical Review Letters, 78 (9): 1823, 1997. 10.1103/PhysRevLett.78.1823.
https:///doi.org/10.1103/PhysRevLett.78.1823

[26] M. Nielsen og I. Chuang. Kvanteberegning og kvanteinformation. Cambridge University Press, 2010. 10.1017/CBO9780511976667.
https:///doi.org/10.1017/CBO9780511976667

[27] En Rastegin. En nedre grænse for den relative fejl ved blandet tilstandskloning og relaterede operationer. 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] A. Sarkar, Z. Al-Ars og K. Bertels. Estimering af algoritmisk information ved hjælp af kvanteberegning til genomiske applikationer. Applied Sciences, 11 (6), 2021. ISSN 2076-3417. 10.3390/app11062696.
https:///doi.org/10.3390/app11062696

[29] Claude Elwood Shannon. En matematisk teori om kommunikation. 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] R. Solomonoff. En formel teori om induktiv inferens, del 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 og A. Teixeira. Vidne gemmer sig uden ekstraktorer eller simulatorer. I F. Manea, R. Miller og D. Nowotka, redaktører, Sailing Routes in the World of Computation, side 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. Kvantealgoritmisk informationsteori. Journal of Universal Computer Science, 2 (5): 311-346, maj 1996. 10.3217/jucs-002-05-0311.
https:///doi.org/10.3217/jucs-002-05-0311

[33] Andreia Teixeira, Armando Matos, André Souto og Luís Antunes. Entropimål vs. Kolmogorov-kompleksitet. Entropy, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/e13030595.
https:///doi.org/10.3390/e13030595

[34] P. Vitányi. Quantum Kolmogorov kompleksitet baseret på klassiske beskrivelser. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/18.945258.
https:///doi.org/10.1109/18.945258

[35] Paul Vitanyi. Tre tilgange til den kvantitative definition af information i en individuel ren kvantetilstand. I Proceedings 15th Annual IEEE Conference on Computational Complexity, side 263-270. IEEE, 2000. 10.1109/CCC.2000.856757.
https:///doi.org/10.1109/CCC.2000.856757

[36] AK Zvonkin og LA Levin. Kompleksiteten af endelige objekter og udviklingen af begreberne information og tilfældighed ved hjælp af teorien om algoritmer. Russian Mathematical Surveys, 25 (6): 83, dec. 1970. 10.1070/RM1970v025n06ABEH001269.
https://doi.org/10.1070/RM1970v025n06ABEH001269

Citeret af

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

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2024-01-18 23:13:56). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2024-01-18 23:13:55).

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.

SEO Powered Content & PR Distribution. Bliv forstærket i dag.
PlatoData.Network Vertical Generative Ai. Styrk dig selv. Adgang her.
PlatoAiStream. Web3 intelligens. Viden forstærket. Adgang her.
PlatoESG. Kulstof, CleanTech, Energi, Miljø, Solenergi, Affaldshåndtering. Adgang her.
PlatoHealth. Bioteknologiske og kliniske forsøgs intelligens. Adgang her.
Kilde: https://quantum-journal.org/papers/q-2024-01-18-1230/

Tidsstempel: Januar 18, 2024

Tidsstempel: April 13, 2023

Genudgivet af Platon

Abstrakt

► BibTeX-data

► Referencer

Citeret af

På vej mod en generel ramme for randomiseret benchmarking, der inkorporerer ikke-Markovsk støj

Vidne til miljødimension gennem tidsmæssige sammenhænge

Korrelationer begrænset af sammensatte målinger

Universel ligevægtsdynamik i Sachdev-Ye-Kitaev-modellen

Kontinuerlig majorisering i kvantefaserum

Om kontraktionskoefficienter, delordrer og tilnærmelse af kapaciteter for kvantekanaler

Paritetskvanteoptimering: Compiler

Optimerede kvantenetværk

Gensidigt upartiske rammer

Løs problemer med enkelt fotondetektor

Forøgelse af enhedsuafhængig kryptografi med tredelt ikke-lokalitet

Om os

Vertikal søgning & Ai

perron

Stay Connected

Konto