Độ phức tạp lượng tử Kolmogorov và mối tương quan lượng tử trong máy Turing lượng tử điều khiển xác định

Độ phức tạp lượng tử Kolmogorov và mối tương quan lượng tử trong máy Turing lượng tử điều khiển xác định

Dấu thời gian: ngày 18 tháng 2024 năm 6 07:XNUMX sáng
Nút nguồn: 3070552

Mariano Lemus1,2, Ricardo Faleiro1,2, Paulo Mateus1,2, Nikola Paunković1,2và André Souto2,3,4

1Departamento de Matemática, Instituto Superior Técnico, Đại học Lisboa, Av.Rovisco Pais, 1049-001 Lisboa, Bồ Đào Nha
2Instituto de Telecomunicações, Av.Rovisco Pais, 1049-001 Lisboa, Bồ Đào Nha
3Lasige, Faculdade de Ciências da Đại học Lisboa, Campo Grande, 1749-016 Lisboa, Bồ Đào Nha
4Departamento de Informática,Faculdade de Ciências da Universidade de Lisboa, Campo Grande, 1749-016 Lisboa, Bồ Đào Nha

Tìm bài báo này thú vị hay muốn thảo luận? Scite hoặc để lại nhận xét về SciRate.

Tóm tắt

Công trình này trình bày một nghiên cứu về độ phức tạp Kolmogorov đối với các trạng thái lượng tử nói chung từ góc độ của Máy Turing lượng tử điều khiển xác định (dcq-TM). Chúng tôi mở rộng mô hình dcq-TM để kết hợp các trạng thái đầu vào và đầu ra hỗn hợp, đồng thời xác định các trạng thái có thể tính toán dcq là các trạng thái có thể được xấp xỉ bởi dcq-TM. Hơn nữa, chúng tôi giới thiệu độ phức tạp Kolmogorov (có điều kiện) của các trạng thái lượng tử và sử dụng nó để nghiên cứu ba khía cạnh cụ thể của thông tin thuật toán chứa trong trạng thái lượng tử: so sánh thông tin ở trạng thái lượng tử với thông tin biểu diễn cổ điển của nó như một mảng thực. các số, khám phá các giới hạn của việc sao chép trạng thái lượng tử trong bối cảnh phức tạp của thuật toán và nghiên cứu về độ phức tạp của các mối tương quan trong các hệ lượng tử, dẫn đến định nghĩa nhận biết tương quan cho thông tin lẫn nhau về thuật toán thỏa mãn tính đối xứng của đặc tính thông tin.

► Dữ liệu BibTeX

► Tài liệu tham khảo

[1] L. Antunes, A. Matos, A. Pinto, A. Souto và A. Teixeira. Hàm một chiều sử dụng lý thuyết thông tin cổ điển và thuật toán. Lý thuyết về hệ thống máy tính, 52 (1): 162–178, tháng 2013 năm 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 và A. Souto. Zgli: Một quy trình phân cụm bằng cách nén với ứng dụng phân tầng bệnh nhân trong bệnh viêm cột sống dính khớp. Cảm biến, 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 và A. Szkoła. Entropy và độ phức tạp lượng tử Kolmogorov: Định lý Brudno lượng tử. Cộng đồng. Toán học. Phys., 265 (1): 437–461, 2006. 10.1007/​s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

[4] CH Bennett và G. Brassard. Mật mã lượng tử: Phân phối khóa công khai và tung đồng xu. Trong Kỷ yếu của Hội nghị Quốc tế IEEE về Máy tính, Hệ thống và Xử lý Tín hiệu, trang 175, 1984. 10.1016/​j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

[5] E. Bernstein và U. Vazirani. Lý thuyết phức tạp lượng tử. Tạp chí Máy tính SIAM, 26 (5): 1411–1473, 1997. 10.1137/​S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

[6] A. Berthiaume, W. Dam và S. Laplante. Độ phức tạp lượng tử Kolmogorov. Tạp chí Khoa học Máy tính và Hệ thống, 63 (2): 201–221, 2001. 10.1006/​jcss.2001.1765.
https: / / doi.org/ 10.1006 / jcss.2001.1765

[7] G. Chaitin. Về độ dài của chương trình tính toán chuỗi nhị phân hữu hạn. J. ACM, 13(4), 1966. 10.1145/​321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363

[8] D. tiếng Đức. Lý thuyết lượng tử, nguyên lý Church-Turing và máy tính lượng tử phổ quát. Hiệp hội Kỷ yếu Hoàng gia Luân Đôn Series A, 400 (1818): 97–117, 1985. 10.1098/​rspa.1985.0070.
https: / / doi.org/ 10.1098 / rspa.1985.0070

[9] P. Gác. Entropy thuật toán lượng tử. Tạp chí Vật lý A: Toán học và Đại cương, 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 và Paul Vitányi. Lý thuyết thông tin thuật toán, trang 289–325. E, tháng 2008 năm XNUMX.
arXiv: 0809.2754

[11] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki và Karol Horodecki. Rối lượng tử. Nhận xét về vật lý hiện đại, 81 (2): 865, 2009. 10.1103 / RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

[12] A. Kolmogorov. Ba cách tiếp cận để định nghĩa định lượng thông tin. Các vấn đề về truyền tải thông tin, 1(1), 1965. 10.1080/​00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030

[13] T. Lee và A. Romashchenko. Xem lại tính đối xứng giới hạn tài nguyên của thông tin. Khoa học máy tính lý thuyết, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/​j.tcs.2005.07.017. Cơ sở toán học của khoa học máy tính 2004.
https: / / doi.org/ 10.1016 / j.tcs.2005.07.017

[14] Ming Li và Paul MB Vitányi. Giới thiệu về Độ phức tạp Kolmogorov và các ứng dụng của nó, Phiên bản thứ 4. Các văn bản trong Khoa học máy tính. 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 và Sandu Popescu. Vấn đề dừng lại đối với máy tính lượng tử. arXiv bản in trước 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 và A. Souto. Tính phổ biến của máy Turing lượng tử với điều khiển xác định. Tạp chí Logic và Tính toán, 27 (1): 1–19, 2017. 10.1093/​logcom/​exv008.
https://​/​doi.org/​10.1093/​logcom/​exv008

[17] T. Miyadera. Định lý độ phức tạp lượng tử Kolmogorov và nhiễu loạn thông tin. Entropy, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/​e13040778.
https: / / doi.org/ 10.3390 / e13040778

[18] T. Miyadera và H. Imai. Độ phức tạp lượng tử Kolmogorov và phân phối khóa lượng tử. Vật lý. Rev. A, 79: 012324, tháng 2009 năm 10.1103. 79.012324/​PhysRevA.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[19] Takayuki Miyadera và Masanori Ohya. Về quá trình dừng của máy turing lượng tử. Hệ thống mở & Động lực thông tin, 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 và Vlatko Vedral. Ranh giới cổ điển-lượng tử cho các mối tương quan: Sự bất hòa và các biện pháp liên quan. Các bài phê bình Vật lý hiện đại, 84 (4): 1655, 2012. 10.1103/​RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

[21] C. Mora và H. Briegel. Độ phức tạp của thuật toán và sự vướng víu của các trạng thái lượng tử. Thư Đánh giá Vật lý, 95: 200503, 2005. 10.1103/​PhysRevLett.95.200503.
https: / / doi.org/ 10.1103 / PhysRevLett.95.200503

[22] C. Mora, H. Briegel và B. Kraus. Độ phức tạp lượng tử Kolmogorov và ứng dụng của nó. Tạp chí Quốc tế về Thông tin Lượng tử, 2007. 10.1142/​S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[23] M Muller. Độ phức tạp lượng tử Kolmogorov và máy Turing lượng tử. Bằng tiến sĩ. Luận văn, Đại học Kỹ thuật Berlin, 2007. 10.48550/​arXiv.0712.4377.
https: / / doi.org/ 10.48550 / arXiv.0712.4377

[24] M. Müller. Máy Turing lượng tử phổ quát mạnh mẽ và tính bất biến của độ phức tạp Kolmogorov. Giao dịch của IEEE về Lý thuyết Thông tin, 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. Một máy tính lượng tử phổ quát có thể là lượng tử hoàn toàn? Thư đánh giá vật lý, 78 (9): 1823, 1997. 10.1103/​PhysRevLett.78.1823.
https: / / doi.org/ 10.1103 / PhysRevLett.78.1823

[26] M. Nielsen và I. Chuang. Tính toán lượng tử và thông tin lượng tử. Nhà xuất bản Đại học Cambridge, 2010. 10.1017/​CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[27] Một Rastegin. Giới hạn dưới của sai số tương đối của nhân bản trạng thái hỗn hợp và các hoạt động liên quan. Tạp chí Quang học B: Quang học lượng tử và bán cổ điển, 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 và K. Bertels. Ước tính thông tin thuật toán bằng cách sử dụng điện toán lượng tử cho các ứng dụng gen. Khoa học Ứng dụng, 11(6), 2021. ISSN 2076-3417. 10.3390/​ứng dụng11062696.
https: / / doi.org/ 10.3390 / app11062696

[29] Claude Elwood Shannon. Một lý thuyết toán học về truyền thông. Tạp chí Kỹ thuật Hệ thống 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

[30] R. Solomonoff. Một lý thuyết hình thức về suy luận quy nạp, phần i. Thông tin và Kiểm soát, 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 và A. Teixeira. Chứng kiến ​​việc lẩn trốn mà không có máy trích xuất hoặc thiết bị mô phỏng. Trong F. Manea, R. Miller và D. Nowotka, các biên tập viên, Lộ trình đi thuyền trong thế giới tính toán, trang 397–409, Cham, 2018. Nhà xuất bản Quốc tế Springer. 10.1007/​978-3-319-94418-0_40.
https:/​/​doi.org/​10.1007/​978-3-319-94418-0_40

[32] K. Svozil. Lý thuyết thông tin thuật toán lượng tử. Tạp chí Khoa học Máy tính Toàn cầu, 2 (5): 311–346, tháng 1996 năm 10.3217. 002/​jucs-05-0311-XNUMX.
https://​/​doi.org/​10.3217/​jucs-002-05-0311

[33] Andreia Teixeira, Armando Matos, André Souto và Luís Antunes. Các biện pháp Entropy so với độ phức tạp Kolmogorov. Entropy, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/​e13030595.
https: / / doi.org/ 10.3390 / e13030595

[34] P. Vitányi. Độ phức tạp lượng tử Kolmogorov dựa trên mô tả cổ điển. Giao dịch của IEEE về Lý thuyết Thông tin, 47 (6): 2464–2479, 2001. 10.1109/​18.945258.
https: / / doi.org/ 10.1109 / 18.945258

[35] Paul Vitanyi. Ba cách tiếp cận để định nghĩa định lượng thông tin ở trạng thái lượng tử thuần túy riêng lẻ. Trong Kỷ yếu Hội nghị thường niên lần thứ 15 của IEEE về độ phức tạp tính toán, trang 263–270. IEEE, 2000. 10.1109/​CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

[36] AK Zvonkin và LA Levin. Sự phức tạp của các đối tượng hữu hạn và sự phát triển của các khái niệm về thông tin và tính ngẫu nhiên bằng lý thuyết thuật toán. Khảo sát Toán học Nga, 25 (6): 83, tháng 1970 năm 10.1070. 1970/​RM025v06n001269ABEHXNUMX.
https:/​/​doi.org/​10.1070/​RM1970v025n06ABEH001269

Trích dẫn

[1] Anne Broadbent, Martti Karvonen và Sébastien Lord, “Lời khuyên lượng tử không thể nhân bản”, arXiv: 2309.05155, (2023).

Các trích dẫn trên là từ SAO / NASA ADS (cập nhật lần cuối thành công 2024 / 01-18 23:13:56). Danh sách có thể không đầy đủ vì không phải tất cả các nhà xuất bản đều cung cấp dữ liệu trích dẫn phù hợp và đầy đủ.

On Dịch vụ trích dẫn của Crossref không có dữ liệu về các công việc trích dẫn được tìm thấy (lần thử cuối cùng 2024 / 01-18 23:13:55).

Bài viết này được xuất bản trong Lượng tử dưới Creative Commons Ghi công 4.0 Quốc tế (CC BY 4.0) giấy phép. Bản quyền vẫn thuộc về chủ sở hữu bản quyền gốc như các tác giả hoặc tổ chức của họ.

Dấu thời gian:

Thêm từ Tạp chí lượng tử