결정론적 제어 양자 튜링 머신의 양자 콜모고로프 복잡성 및 양자 상관관계

플라톤에 의해 재발행

팔로워 : 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 리스본, 포르투갈
³Lasige, Faculdade de Ciências da Universidade de Lisboa, Campo Grande, 1749-016 리스본, 포르투갈
⁴Departamento de Informática, Faculdade de Ciências da Universidade de Lisboa, Campo Grande, 1749-016 리스본, 포르투갈

이 논문이 흥미 롭거나 토론하고 싶습니까? SciRate에 댓글을 달거나 댓글 남기기.

추상

이 연구는 결정론적 제어 양자 튜링 머신(dcq-TM)의 관점에서 일반적인 양자 상태에 대한 Kolmogorov 복잡성에 대한 연구를 제시합니다. 우리는 혼합 상태 입력과 출력을 통합하기 위해 dcq-TM 모델을 확장하고, dcq-TM에 의해 근사화될 수 있는 상태로 dcq 계산 가능 상태를 정의합니다. 또한, 우리는 양자 상태의 (조건부) 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. 알고리즘 및 고전 정보 이론을 사용하는 단방향 함수. 컴퓨팅 시스템 이론, 52(1): 162–178, 2013년 1433월. ISSN 0490-10.1007. 00224/s012-9418-XNUMX-z.
https : / /doi.org/ 10.1007 / s00224-012-9418-z

[2] D. Azevedo, AM Rodrigues, H. Canhão, AM Carvalho 및 A. Souto. Zgli: 척추관절염 환자 계층화에 적용하여 압축을 통한 클러스터링을 위한 파이프라인. 센서, 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의 정리. 커뮤니케이터 수학. Phys., 265 (1): 437–461, 2006. 10.1007/s00220-006-0027-z.
https : / /doi.org/ 10.1007 / s00220-006-0027-z

[4] CH 베넷과 G. 브라사드. 양자 암호화: 공개 키 배포 및 동전 던지기. 컴퓨터, 시스템 및 신호 처리에 관한 IEEE 국제 컨퍼런스 진행, 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 컴퓨팅 저널, 26(5): 1411–1473, 1997. 10.1137/S0097539796300921.
https : / /doi.org/ 10.1137 / S0097539796300921

[6] A. Berthiaume, W. Dam, S. Laplante. 양자 콜모고로프(Quantum Kolmogorov) 복잡성. 컴퓨터 및 시스템 과학 저널, 63(2): 201–221, 2001. 10.1006/jcss.2001.1765.
https : / /doi.org/ 10.1006 / jcss.2001.1765

[7] G. 차이틴. 유한한 이진수열을 계산하는 프로그램의 길이에 관한 것입니다. J. ACM, 13(4), 1966. 10.1145/321356.321363.
https : / /doi.org/ 10.1145 / 321356.321363

[8] D. 독일어. 양자 이론, 교회-튜링 원리 및 보편적인 양자 컴퓨터. 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: 수학 및 일반, 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). 알고리즘 정보 이론, 289~325페이지. E, 2008년 XNUMX월.
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] A. 콜모고로프. 정보의 정량적 정의에 대한 세 가지 접근 방식. 정보 전송 문제, 1 (1), 1965. 10.1080/00207166808803030.
https : / /doi.org/ 10.1080 / 00207166808803030

[13] T. Lee와 A. Romashchenko. 정보의 자원 제한 대칭이 재검토되었습니다. 이론적인 컴퓨터 과학, 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] 밍 리(Ming Li)와 폴 MB 비타니(Paul MB Vitányi). Kolmogorov 복잡성 및 응용 프로그램 소개, 4판. 컴퓨터 과학의 텍스트. 스프링거, 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 사전 인쇄 퀀트-ph/9806054, 1998. 10.48550/arXiv.퀀트-ph/9806054.
https:///doi.org/10.48550/arXiv.quant-ph/9806054
arXiv : 퀀트 -PH / 9806054

[16] P. 마테우스, A. 세르나다스, A. 소토. 결정론적 제어를 갖춘 양자 튜링 기계의 보편성. 논리 및 계산 저널, 27(1): 1–19, 2017. 10.1093/logcom/exv008.
https://doi.org/10.1093/logcom/exv008

[17] T. 미야데라. 양자 콜모고로프(Quantum Kolmogorov) 복잡성과 정보 교란 정리. 엔트로피, 13(4): 778-789, 2011. ISSN 1099-4300. 10.3390/e13040778.
https : / /doi.org/10.3390/e13040778

[18] T. 미야데라와 H. 이마이. Quantum Kolmogorov 복잡성 및 양자 키 분포. 물리. A, 79: 012324, 2009년 10.1103월. 79.012324/PhysRevA.XNUMX.
https : / /doi.org/10.1103/ PhysRevA.79.012324

[19] 미야데라 타카유키와 오야 마사노리. 양자 튜링 기계의 정지 과정에 대해. 개방형 시스템 및 정보 역학, 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. 상관 관계에 대한 고전적 양자 경계: 불일치 및 관련 측정. 현대 물리학 리뷰, 84(4): 1655, 2012. 10.1103/RevModPhys.84.1655.
https : / /doi.org/10.1103/ RevModPhys.84.1655

[21] C. 모라와 H. 브리겔. 양자 상태의 알고리즘 복잡성과 얽힘. 물리적 검토 편지, 95: 200503, 2005. 10.1103/PhysRevLett.95.200503.
https : / /doi.org/10.1103/ PhysRevLett.95.200503

[22] C. 모라, H. 브리겔, B. 크라우스. Quantum Kolmogorov 복잡성과 그 응용. 국제양자정보저널, 2007. 10.1142/S0219749907003171.
https : / /doi.org/ 10.1142 / S0219749907003171

[23] 엠 뮬러. 양자 콜모고로프(Quantum Kolmogorov) 복잡성과 양자 튜링 기계. 박사. 베를린 기술대학교 논문, 2007. 10.48550/arXiv.0712.4377.
https:///doi.org/10.48550/arXiv.0712.4377

[24] M. 뮐러. 강력한 보편적인 양자 튜링 기계와 Kolmogorov 복잡성의 불변성. 정보 이론에 관한 IEEE 거래, 54 (2): 763-780, 2008. ISSN 0018-9448. 10.1109/TIT.2007.913263.
https : / //doi.org/10.1109/TIT.2007.913263

[25] 존 M 마이어스. 범용 양자 컴퓨터가 완전 양자 컴퓨터가 될 수 있나요? Physical Review Letters, 78 (9): 1823, 1997. 10.1103/PhysRevLett.78.1823.
https : / /doi.org/10.1103/ PhysRevLett.78.1823

[26] M. Nielsen과 I. Chuang. 양자 계산 및 양자 정보. 캠브리지 대학 출판부, 2010. 10.1017/CBO9780511976667.
https : / /doi.org/ 10.1017 / CBO9780511976667

[27] 라스테긴. 혼합 상태 복제 및 관련 작업의 상대 오류에 대한 하한입니다. 광학 저널 B: 양자 및 반고전 광학, 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 및 K. Bertels. 유전체학 응용을 위한 양자 컴퓨팅을 사용하여 알고리즘 정보를 추정합니다. 응용 과학, 11 (6), 2021. ISSN 2076-3417. 10.3390/app11062696.
https://doi.org/10.3390/app11062696

[29] 클로드 엘우드 섀넌. 의사소통의 수학적 이론. 벨 시스템 기술 저널, 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. 솔로몬노프. 귀납적 추론의 형식적 이론, 파트 i. 정보 및 통제, 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 및 D. Nowotka 편집자, 계산 세계의 항해 경로, 페이지 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월. 002/jucs-05-0311-XNUMX.
https://doi.org/10.3217/jucs-002-05-0311

[33] 안드레아 테세이라, 아르만도 마토스, 안드레 소토, 루이스 안투네스. 엔트로피 측정 대 Kolmogorov 복잡성. 엔트로피, 13(3): 595–611, 2011. ISSN 1099-4300. 10.3390/e13030595.
https : / /doi.org/10.3390/e13030595

[34] P. Vitányi. 고전적 설명을 기반으로 한 Quantum Kolmogorov 복잡성. 정보 이론에 관한 IEEE 거래, 47(6): 2464–2479, 2001. 10.1109/18.945258.
https : / /doi.org/ 10.1109 / 18.945258

[35] 폴 비타니. 개별 순수 양자 상태에서 정보의 정량적 정의에 대한 세 가지 접근 방식입니다. 계산 복잡성에 관한 제15회 연례 IEEE 컨퍼런스 진행, 263~270페이지. IEEE, 2000/CCC.10.1109.
https : / /doi.org/10.1109/CCC.2000.856757

[36] AK Zvonkin과 LA Levin. 유한 객체의 복잡성과 알고리즘 이론을 통한 정보 및 무작위성의 개념 개발. 러시아 수학 조사, 25(6): 83, 1970년 10.1070월. 1970/RM025v06n001269ABEHXNUMX.
https://doi.org/10.1070/RM1970v025n06ABEH001269