1Khoa Khoa học Máy tính, Đại học Columbia
2Viện Điện toán Lượng tử và Trường Khoa học Máy tính, Đại học Waterloo
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
Bài báo này liên quan đến các khía cạnh lý thuyết phức tạp của một công thức chung của lý thuyết trò chơi lượng tử mô hình hóa các tương tác chiến lược giữa các tác nhân hợp lý xử lý và trao đổi thông tin lượng tử. Cụ thể, chúng tôi chứng minh rằng bài toán tính toán tìm điểm cân bằng Nash gần đúng trong một lớp rộng các trò chơi lượng tử, giống như bài toán tương tự đối với các trò chơi cổ điển, được đưa vào (và do đó hoàn chỉnh cho) lớp phức tạp PPAD. Đóng góp kỹ thuật chính của chúng tôi, tạo điều kiện thuận lợi cho việc đưa vào này, là sự mở rộng của các phương pháp trước đó trong lý thuyết trò chơi điện toán cho các không gian chiến lược được đặc trưng bởi các chương trình bán xác định.
Hình ảnh nổi bật: Sơ đồ tương tác thể hiện trò chơi lượng tử nhiều lượt.
► Dữ liệu BibTeX
► Tài liệu tham khảo
[1] David Meyer. “Chiến lược lượng tử”. Thư đánh giá vật lý 82, 1052–1055 (1999).
https: / / doi.org/ 10.1103 / PhysRevLett.82.1052
[2] Jens Eisert, Martin Wilkens và Maciej Lewenstein. “Trò chơi lượng tử và chiến lược lượng tử”. Thư đánh giá vật lý 83, 3077–3080 (1999).
https: / / doi.org/ 10.1103 / PhysRevLett.83.3077
[3] John von Neumann và Oskar Morgenstern. “Lý thuyết trò chơi và hành vi kinh tế”. Nhà xuất bản Đại học Princeton. (1953). ấn bản thứ ba.
https: / / doi.org/ 10.1515 / 9781400829460
[4] John Nash. “Điểm cân bằng trong trò chơi n người”. Kỷ yếu của Viện Hàn lâm Khoa học Quốc gia 36, 48–49 (1950).
https: / / doi.org/ 10.1073 / pnas.36.1.48
[5] John Nash. “Trò chơi không hợp tác”. luận án tiến sĩ. Trường Đại học Princeton. (1950).
[6] Hong Guo, Juheng Zhang, và Gary Koehler. “Một cuộc khảo sát về các trò chơi lượng tử”. Hệ thống Hỗ trợ Quyết định 46, 318–332 (2008).
https:///doi.org/10.1016/j.dss.2008.07.001
[7] Steven van Enk và Rob Pike. “Các quy tắc cổ điển trong trò chơi lượng tử”. Tạp chí Vật lý A 66, 024306 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.66.024306
[8] Kim Sơn Vũ. “Một biểu diễn toán học mới của lý thuyết trò chơi I”. Bản thảo chưa xuất bản, arXiv:quant-ph/0404159 (2004).
arXiv: quant-ph / 0404159
[9] Kim Sơn Vũ. “Một biểu diễn toán học mới của lý thuyết trò chơi II”. Bản thảo chưa xuất bản, arXiv:quant-ph/0405183 (2004).
arXiv: quant-ph / 0405183
[10] Shengyu Zhang. “Lý thuyết trò chơi chiến lược lượng tử”. Trong Kỷ yếu của Hội nghị Khoa học Máy tính Lý thuyết Đổi mới lần thứ 3. Trang 39–59. (2012).
https: / / doi.org/ 10.1145 / 2090236.2090241
[11] Gus Gutoski và John Watrous. “Hướng tới một lý thuyết chung về trò chơi lượng tử”. Trong Kỷ yếu của Hội nghị chuyên đề ACM thường niên lần thứ 39 về Lý thuyết máy tính. Trang 565–574. (2007).
https: / / doi.org/ 10.1145 / 1250790.1250873
[12] Giulio Chiribella, Giacomo D'Ariano và Paolo Perinotti. “Kiến trúc mạch lượng tử”. Thư đánh giá vật lý 101, 060401 (2008).
https: / / doi.org/ 10.1103 / PhysRevLett.101.060401
[13] Giulio Chiribella, Giacomo D'Ariano và Paolo Perinotti. “Khung lý thuyết cho các mạng lượng tử”. Tạp chí Vật lý A 80, 022339 (2009).
https: / / doi.org/ 10.1103 / PhysRevA.80.022339
[14] Constantinos Daskalakis, Paul Goldberg, và Christos Papadimitriou. “Sự phức tạp của việc tính toán cân bằng Nash”. Tạp chí SIAM về Điện toán 39, 195–259 (2009).
https: / / doi.org/ 10.1137 / 070699652
[15] Xi Chen, Xiaotie Deng, và Shang-Hua Teng. “Giải quyết sự phức tạp của tính toán cân bằng Nash hai người chơi”. Tạp chí ACM 56, 14 (2009).
https: / / doi.org/ 10.1145 / 1516512.1516516
[16] Christos Papadimitriou. “Về sự phức tạp của lập luận chẵn lẻ và các bằng chứng tồn tại kém hiệu quả khác”. Tạp chí Khoa học Máy tính và Hệ thống 48, 498–532 (1994).
https://doi.org/10.1016/S0022-0000(05)80063-7
[17] Kousha Etessami và Mihalis Yannakakis. “Về độ phức tạp của cân bằng Nash và các điểm cố định khác”. Tạp chí SIAM về Điện toán 39, 2531–2597 (2010).
https: / / doi.org/ 10.1137 / 080720826
[18] Kathleen Gibbons, Matthew Hoffman và William Wootters. “Không gian pha rời rạc dựa trên trường hữu hạn”. Tạp chí Vật lý A 70, 062101 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.062101
[19] David Gross. “Định lý Hudson cho các hệ lượng tử hữu hạn chiều”. Tạp chí Vật lý Toán học 47, 122107 (2006).
https: / / doi.org/ 10.1063 / 1.2393152
[20] Sanjeev Arora và Boaz Barak. “Độ phức tạp tính toán: Một cách tiếp cận hiện đại”. Nhà xuất bản Đại học Cambridge. (2009).
https: / / doi.org/ 10.1017 / CBO9780511804090
[21] Michael Nielsen và Isaac Chuang. “Tính toán lượng tử và thông tin lượng tử”. Nhà xuất bản Đại học Cambridge. (2000).
https: / / doi.org/ 10.1017 / CBO9780511976667
[22] Đánh dấu Wilde. “Lý thuyết thông tin lượng tử”. Nhà xuất bản Đại học Cambridge. (2017). Phiên bản thứ hai.
https: / / doi.org/ 10.1017 / 9781316809976
[23] John Watrous. “Lý thuyết thông tin lượng tử”. Nhà xuất bản Đại học Cambridge. (2018).
https: / / doi.org/ 10.1017 / 9781316848142
[24] Glen Bredon. “Cấu trúc liên kết và hình học”. Tập 139 của Văn bản Cao học về Toán học. lò xo. (1993).
https://doi.org/10.1007/978-1-4757-6848-0
[25] Irving Glicksberg. “Một sự tổng quát hóa hơn nữa của định lý điểm bất động Kakutani, với ứng dụng cho các điểm cân bằng Nash”. Kỷ yếu của Hiệp hội Toán học Hoa Kỳ 3, 170–174 (1952).
https: / / doi.org/ 10.2307 / 2032478
[26] John Nash. “Trò chơi không hợp tác”. Biên niên sử toán học, sê-ri thứ hai 54, 286–295 (1951).
https: / / doi.org/ 10.2307 / 1969529
[27] Martin Grötschel, Laszlo Lovász và Alexander Schrijver. “Các thuật toán hình học và tối ưu hóa tổ hợp”. Springer–Verlag. (1988).
https://doi.org/10.1007/978-3-642-78240-4
[28] Carlton Lemke và Joseph Howson. “Điểm cân bằng của trò chơi bimatrix”. Tạp chí của Hiệp hội Toán học Công nghiệp và Ứng dụng 12, 413–423 (1964).
https: / / doi.org/ 10.1137 / 0112033
Trích dẫn
[1] Constantin Ickstadt, Thorsten Theobald và Elias Tsigaridas, “Trò chơi nửa xác định”, arXiv: 2202.12035.
[2] Rafael Frongillo, “Khai thác thông tin lượng tử”, arXiv: 2203.07469.
[3] Rahul Jain, Georgios Piliouras và Ryann Sim, “Cập nhật trọng số phép nhân ma trận trong trò chơi tổng bằng không lượng tử: Định luật bảo toàn & sự tái diễn”, arXiv: 2211.01681.
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 2022 / 12-24 16:09:05). 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 2022 / 12-24 16:09:03).
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ọ.
