ความซับซ้อนของควอนตัมโคลโมโกรอฟและความสัมพันธ์ของควอนตัมในเครื่องทัวริงควอนตัมที่ควบคุมเชิงกำหนด

เผยแพร่ซ้ำโดยเพลโต

ผู้ติดตาม: 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, กัมปูกรันเด, 1749-016 ลิสบัว, โปรตุเกส
⁴Departamento de Informática, Faculdade de Ciências da Universidade de Lisboa, กัมโปกรันเด, 1749-016 ลิสบัว, โปรตุเกส

พบบทความนี้ที่น่าสนใจหรือต้องการหารือ? Scite หรือแสดงความคิดเห็นใน SciRate.

นามธรรม

งานนี้นำเสนอการศึกษาความซับซ้อนของโคลโมโกรอฟสำหรับสถานะควอนตัมทั่วไปจากมุมมองของเครื่องทัวริงควอนตัมควบคุมเชิงกำหนด (dcq-TM) เราขยายโมเดล dcq-TM เพื่อรวมอินพุตและเอาต์พุตสถานะแบบผสม และกำหนดสถานะที่คำนวณได้ dcq ให้เป็นสถานะที่สามารถประมาณได้โดย dcq-TM ยิ่งไปกว่านั้น เรายังแนะนำ (แบบมีเงื่อนไข) ความซับซ้อนของโคลโมโกรอฟของสถานะควอนตัม และใช้มันเพื่อศึกษาลักษณะเฉพาะสามประการของข้อมูลอัลกอริทึมที่มีอยู่ในสถานะควอนตัม: การเปรียบเทียบข้อมูลในสถานะควอนตัมกับข้อมูลแบบคลาสสิกซึ่งเป็นอาร์เรย์ของของจริง การสำรวจขีดจำกัดของการคัดลอกสถานะควอนตัมในบริบทของความซับซ้อนของอัลกอริทึม และการศึกษาความซับซ้อนของความสัมพันธ์ในระบบควอนตัม ส่งผลให้เกิดคำจำกัดความที่รับรู้ถึงความสัมพันธ์สำหรับข้อมูลร่วมกันของอัลกอริทึมที่เป็นไปตามความสมมาตรของทรัพย์สินทางข้อมูล

► ข้อมูล 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] แอล. อันตูเนส, เอ. มาตอส, เอ. ปินโต, เอ. ซูโต้และเอ. เตเซร่า ฟังก์ชันทางเดียวโดยใช้ทฤษฎีข้อมูลอัลกอริทึมและคลาสสิก ทฤษฎีระบบคอมพิวเตอร์ 52 (1): 162–178 ม.ค. 2013 ISSN 1433-0490 10.1007/s00224-012-9418-z.
https://doi.org/10.1007/s00224-012-9418-z

[2] ดี. อาเซเวโด, เอเอ็ม โรดริเกซ, เอช. คานเฮา, เอเอ็ม คาร์วัลโญ่ และเอ. ซูโต 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 ความซับซ้อนของเอนโทรปีและควอนตัมของโคลโมโกรอฟ: ทฤษฎีบทของควอนตัมบรูดโน ชุมชน คณิตศาสตร์. Phys., 265(1): 437–461, 2006. 10.1007/s00220-006-0027-z.
https://doi.org/10.1007/s00220-006-0027-z

[4] ซี.เอช. เบนเน็ตต์ และจี. บราสซาร์ด การเข้ารหัสควอนตัม: การแจกจ่ายคีย์สาธารณะและการโยนเหรียญ ใน 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] อี. เบิร์นสไตน์ และยู. วาซิรานี. ทฤษฎีความซับซ้อนของควอนตัม วารสารสยามคอมพิวเตอร์, 26 (5): 1411–1473, 1997. 10.1137/S0097539796300921.
https://doi.org/10.1137/S0097539796300921

[6] เอ. เบอร์เธียม, ดับเบิลยู. ดาม และเอส. ลาแพลนเต้ ความซับซ้อนของควอนตัม โคลโมโกรอฟ วารสารวิทยาการคอมพิวเตอร์และระบบ, 63 (2): 201–221, 2001. 10.1006/jcss.2001.1765.
https://doi.org/10.1006/jcss.2001.1765

[7] ก.ชัยทิน. เกี่ยวกับความยาวของโปรแกรมสำหรับการคำนวณลำดับไบนารี่จำกัด เจ. พลอากาศเอก, 13 (4), 1966. 10.1145/321356.321363.
https://doi.org/10.1145/321356.321363

[8] ดี. เยอรมัน. ทฤษฎีควอนตัม หลักการเชิร์ช-ทัวริง และคอมพิวเตอร์ควอนตัมสากล ราชสมาคมแห่งลอนดอน Proceedings Series A, 400 (1818): 97–117, 1985 10.1098/rspa.1985.0070
https://doi.org/10.1098/rspa.1985.0070

[9] พี. กาซ. เอนโทรปีอัลกอริทึมควอนตัม วารสารฟิสิกส์ A: คณิตศาสตร์และทั่วไป 34 (35): 6859, 2001. 10.1088/0305-4470/34/35/312.
https://doi.org/10.1088/0305-4470/34/35/312

[10] ปีเตอร์ กรุนวาลด์ และพอล วิทันยี ทฤษฎีสารสนเทศอัลกอริทึม หน้า 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] อ. โคลโมโกรอฟ. สามแนวทางในการนิยามข้อมูลเชิงปริมาณ ปัญหาการส่งข้อมูล 1 (1) 1965 10.1080/00207166808803030.
https://doi.org/10.1080/00207166808803030

[13] ที. ลี และ เอ. โรมาชเชนโก ทบทวนความสมมาตรที่จำกัดขอบเขตของทรัพยากรแล้ว วิทยาการคอมพิวเตอร์เชิงทฤษฎี, 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] หมิง ลี่ และพอล เอ็มบี วิทันยี บทนำเกี่ยวกับความซับซ้อนของโคลโมโกรอฟและการประยุกต์ ฉบับที่ 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 พิมพ์ล่วงหน้า quant-ph/9806054, 1998 10.48550/arXiv.quant-ph/9806054
https://doi.org/10.48550/arXiv.quant-ph/9806054
arXiv:ปริมาณ-ph/9806054

[16] พี. มาเตอุส, เอ. เซอร์นาดาส และ เอ. ซูโต ความอเนกประสงค์ของเครื่องทัวริงควอนตัมพร้อมการควบคุมเชิงกำหนด วารสารลอจิกและการคำนวณ 27 (1): 1–19 2017 10.1093/logcom/exv008
https:///doi.org/10.1093/logcom/exv008

[17] ต. มิยาเดระ. ความซับซ้อนของควอนตัมโคลโมโกรอฟและทฤษฎีบทการรบกวนข้อมูล เอนโทรปี 13 (4): 778–789, 2011. ISSN 1099-4300 10.3390/e13040778.
https://doi.org/10.3390/e13040778

[18] ที. มิยาเดระ และ เอช. อิมาอิ. ความซับซ้อนของควอนตัมโคลโมโกรอฟและการกระจายคีย์ควอนตัม ฟิสิกส์ รายได้ A, 79: 012324, ม.ค. 2009 10.1103/PhysRevA.79.012324
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] คาวาน โมดี, อาฮารอน โบรดัทช์, ฮิวโก เคเบิล, โทมัสซ์ ปาเทเร็ก และวลัตโก เวดราล ขอบเขตควอนตัมคลาสสิกสำหรับความสัมพันธ์: ความไม่ลงรอยกันและการวัดที่เกี่ยวข้อง บทวิจารณ์ฟิสิกส์สมัยใหม่ 84 (4): 1655 2012 10.1103/RevModPhys.84.1655
https://doi.org/10.1103/RevModPhys.84.1655

[21] ซี. โมรา และ เอช. บรีเกล ความซับซ้อนของอัลกอริทึมและความยุ่งเหยิงของสถานะควอนตัม จดหมายทบทวนทางกายภาพ, 95: 200503, 2005. 10.1103/PhysRevLett.95.200503.
https://doi.org/10.1103/PhysRevLett.95.200503

[22] ซี. โมรา, เอช. บรีเกล และบี. เคราส์ ความซับซ้อนของควอนตัม โคลโมโกรอฟ และการประยุกต์ วารสารนานาชาติด้านข้อมูลควอนตัม, 2007. 10.1142/S0219749907003171.
https://doi.org/10.1142/S0219749907003171

[23] เอ็ม มุลเลอร์. ความซับซ้อนของควอนตัม โคลโมโกรอฟ และเครื่องทัวริงควอนตัม ปริญญาเอก วิทยานิพนธ์ มหาวิทยาลัยเทคนิคแห่งเบอร์ลิน 2007 10.48550/arXiv.0712.4377
https://doi.org/10.48550/arXiv.0712.4377

[24] เอ็ม. มุลเลอร์. เครื่องจักรทัวริงควอนตัมที่เป็นสากลอย่างมากและความแปรปรวนของความซับซ้อนของโคลโมโกรอฟ ธุรกรรม IEEE เกี่ยวกับทฤษฎีสารสนเทศ, 54 (2): 763–780, 2008 ISSN 0018-9448 10.1109/TIT.2007.913263.
https://doi.org/10.1109/TIT.2007.913263

[25] จอห์น เอ็ม. ไมเยอร์ส. คอมพิวเตอร์ควอนตัมสากลสามารถเป็นควอนตัมได้เต็มที่หรือไม่? จดหมายทบทวนทางกายภาพ, 78 (9): 1823, 1997. 10.1103/PhysRevLett.78.1823.
https://doi.org/10.1103/PhysRevLett.78.1823

[26] เอ็ม. นีลเซ่น และ ไอ.จวง. การคำนวณควอนตัมและข้อมูลควอนตัม สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์, 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] เอ. ซาร์การ์, ซี. อัล-อาร์ส และเค. เบอร์เทลส์ การประมาณข้อมูลอัลกอริทึมโดยใช้การคำนวณควอนตัมสำหรับการใช้งานด้านจีโนมิกส์ วิทยาศาสตร์ประยุกต์, 11(6), 2021. ISSN 2076-3417. 10.3390/app11062696.
https://doi.org/10.3390/app11062696

[29] คล็อด เอลวูด แชนนอน. ทฤษฎีทางคณิตศาสตร์ของการสื่อสาร วารสารทางเทคนิคของ Bell System, 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] อาร์. โซโลมอนอฟ. ทฤษฎีทางการของการอนุมานอุปนัย ตอนที่ 7 ข้อมูลและการควบคุม, 1 (1964), 10.1016. 0019/S9958-64(90223)2-XNUMX.
https://doi.org/10.1016/S0019-9958(64)90223-2

[31] เอ. ซูโต, แอล. อันตูเนส, พี. มาเตอุส และ เอ. เตเซรา พยานซ่อนตัวโดยไม่มีเครื่องสกัดหรือเครื่องจำลอง ใน F. Manea, R. Miller และ 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] เค. สโวซิล. ทฤษฎีข้อมูลอัลกอริทึมควอนตัม 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 มาตรการเอนโทรปีเทียบกับความซับซ้อนของโคลโมโกรอฟ เอนโทรปี 13 (3): 595–611, 2011 ISSN 1099-4300 10.3390/e13030595.
https://doi.org/10.3390/e13030595

[34] ป. วิทันยี. ความซับซ้อนของควอนตัม โคลโมโกรอฟ ตามคำอธิบายแบบคลาสสิก ธุรกรรม IEEE เกี่ยวกับทฤษฎีสารสนเทศ 47 (6): 2464–2479, 2001 10.1109/18.945258
https://doi.org/10.1109/18.945258

[35] พอล วิตันยี. แนวทางสามประการในการนิยามข้อมูลเชิงปริมาณในสถานะควอนตัมบริสุทธิ์แต่ละรายการ ในการประชุม IEEE ประจำปีครั้งที่ 15 เรื่องความซับซ้อนในการคำนวณ หน้า 263–270 มาตรฐาน IEEE, 2000. 10.1109/CCC.2000.856757.
https://doi.org/10.1109/CCC.2000.856757

[36] เอเค ซวอนคิน และแอลเอ เลวิน ความซับซ้อนของวัตถุอันจำกัดและการพัฒนาแนวความคิดเกี่ยวกับข้อมูลและความสุ่มโดยใช้ทฤษฎีอัลกอริทึม Russian Mathematical Surveys, 25 (6): 83, ธ.ค. 1970. 10.1070/RM1970v025n06ABEH001269.
https://doi.org/10.1070/RM1970v025n06ABEH001269

อ้างโดย

(1) Anne Broadbent, Martti Karvonen และSébastien Lord, “คำแนะนำควอนตัมที่ไม่สามารถโคลนได้”, arXiv: 2309.05155, (2023).

การอ้างอิงข้างต้นมาจาก are อบต./นาซ่าโฆษณา (ปรับปรุงล่าสุดสำเร็จ 2024-01-18 23:13:56 น.) รายการอาจไม่สมบูรณ์เนื่องจากผู้จัดพิมพ์บางรายไม่ได้ให้ข้อมูลอ้างอิงที่เหมาะสมและครบถ้วน

On บริการอ้างอิงของ Crossref ไม่พบข้อมูลอ้างอิงงาน (ความพยายามครั้งสุดท้าย 2024-01-18 23:13:55)

บทความนี้เผยแพร่ใน Quantum ภายใต้ the ครีเอทีฟคอมมอนส์แบบแสดงที่มา 4.0 สากล (CC BY 4.0) ใบอนุญาต ลิขสิทธิ์ยังคงอยู่กับผู้ถือลิขสิทธิ์ดั้งเดิม เช่น ผู้เขียนหรือสถาบันของพวกเขา

เนื้อหาที่ขับเคลื่อนด้วย SEO และการเผยแพร่ประชาสัมพันธ์ รับการขยายวันนี้
PlatoData.Network Vertical Generative Ai เพิ่มพลังให้กับตัวเอง เข้าถึงได้ที่นี่.
เพลโตไอสตรีม. Web3 อัจฉริยะ ขยายความรู้ เข้าถึงได้ที่นี่.
เพลโตESG. คาร์บอน, คลีนเทค, พลังงาน, สิ่งแวดล้อม แสงอาทิตย์, การจัดการของเสีย. เข้าถึงได้ที่นี่.
เพลโตสุขภาพ เทคโนโลยีชีวภาพและข่าวกรองการทดลองทางคลินิก เข้าถึงได้ที่นี่.
ที่มา: https://quantum-journal.org/papers/q-2024-01-18-1230/

ประทับเวลา: January 18, 2024

ประทับเวลา: เมษายน 13, 2023

เผยแพร่ซ้ำโดยเพลโต

นามธรรม

► ข้อมูล BibTeX

► ข้อมูลอ้างอิง

อ้างโดย

ไปสู่กรอบทั่วไปของเกณฑ์มาตรฐานแบบสุ่มที่รวมสัญญาณรบกวนที่ไม่ใช่ของมาร์กอฟ

สัมผัสมิติสิ่งแวดล้อมผ่านความสัมพันธ์เชิงเวลา

ความสัมพันธ์ถูกจำกัดโดยการวัดแบบผสม

พลวัตของดุลยภาพสากลของแบบจำลอง Sachdev-Ye-Kitaev

วิชาเอกต่อเนื่องในพื้นที่เฟสควอนตัม

เกี่ยวกับค่าสัมประสิทธิ์การหดตัว คำสั่งบางส่วน และการประมาณความจุสำหรับช่องควอนตัม

การเพิ่มประสิทธิภาพควอนตัมพาริตี: คอมไพเลอร์

เพิ่มประสิทธิภาพเครือข่ายควอนตัม

เฟรมที่เป็นกลางซึ่งกันและกัน

แก้ปัญหาเครื่องตรวจจับโฟตอนเดี่ยว

เพิ่มการเข้ารหัสที่ไม่ขึ้นกับอุปกรณ์ด้วย nonlocity แบบไตรภาคี

เกี่ยวกับเรา

การค้นหาแนวตั้ง & Ai

ระบบปฏิบัติการ

การติดต่อ

ลงชื่อเข้าใช้