Cổng đa qubit tối ưu theo thời gian: Độ phức tạp, giới hạn heuristic và thời gian cổng hiệu quả

Cổng đa qubit tối ưu theo thời gian: Độ phức tạp, giới hạn heuristic và thời gian cổng hiệu quả

Dấu thời gian: Ngày 13 tháng 2024 năm 8 59:XNUMX sáng
Cổng đa qubit tối ưu theo thời gian: Độ phức tạp, phỏng đoán hiệu quả và giới hạn thời gian cổng PlatoBlockchain Data Intelligence. Tìm kiếm dọc. Ái.

Pascal Baßler1, Markus Heinrich1và Martin Kliesch2

1Viện Vật lý Lý thuyết, Đại học Heinrich Heine Düsseldorf, Đức
2Viện lấy cảm hứng từ lượng tử và tối ưu hóa lượng tử, Đại học Công nghệ Hamburg, Đức

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ác tương tác vướng víu nhiều qubit phát sinh một cách tự nhiên trong một số nền tảng điện toán lượng tử và hứa hẹn những lợi thế so với các cổng hai qubit truyền thống. Đặc biệt, có thể sử dụng tương tác loại Ising đa qubit cố định cùng với cổng X qubit đơn để tổng hợp các cổng ZZ toàn cầu (cổng GZZ). Trong nghiên cứu này, trước tiên chúng tôi chỉ ra rằng việc tổng hợp các cổng lượng tử tối ưu về thời gian như vậy là NP-hard. Thứ hai, chúng tôi cung cấp cấu trúc rõ ràng của các cổng đa qubit tối ưu theo thời gian đặc biệt. Chúng có thời gian cổng không đổi và có thể được triển khai tuyến tính với nhiều lớp X-gate. Thứ ba, chúng tôi phát triển thuật toán heuristic với thời gian chạy đa thức để tổng hợp các cổng đa qubit nhanh. Thứ tư, chúng tôi rút ra giới hạn dưới và giới hạn trên về thời gian cổng GZZ tối ưu. Dựa trên cấu trúc rõ ràng của cổng GZZ và các nghiên cứu số, chúng tôi phỏng đoán rằng bất kỳ cổng GZZ nào cũng có thể được thực thi trong thời gian O($n$) cho $n$ qubit. Thuật toán tổng hợp heuristic của chúng tôi dẫn đến thời gian cổng GZZ với tỷ lệ tương tự, theo nghĩa này là tối ưu. Chúng tôi hy vọng rằng sự tổng hợp hiệu quả của chúng tôi về các cổng đa qubit nhanh sẽ cho phép thực thi các thuật toán lượng tử nhanh hơn và do đó cũng ít lỗi hơn.

► Dữ liệu BibTeX

► Tài liệu tham khảo

[1] X. Wang, A. Sørensen và K. Mølmer, Cổng đa bit cho điện toán lượng tử, Phys. Mục sư Lett. 86, 3907 (2001), arXiv:quant-ph/​0012055.
https: / / doi.org/ 10.1103 / PhysRevLett.86.3907
arXiv: quant-ph / 0012055

[2] T. Monz, P. Schindler, JT Barreiro, M. Chwalla, D. Nigg, WA Coish, M. Harlander, W. Hänsel, M. Hennrich, và R. Blatt, 14-qubit entanglement: Creation and coherence, Phys. Mục sư Lett. 106, 130506 (2011), arXiv:1009.6126.
https: / / doi.org/ 10.1103 / PhysRevLett.106.130506
arXiv: 1009.6126

[3] M. Kjaergaard, ME Schwartz, J. Braumüller, P. Krantz, JI-J. Wang, S. Gustavsson và WD Oliver, Qubit siêu dẫn: Trạng thái hoạt động hiện tại, Đánh giá thường niên về Vật lý vật chất ngưng tụ 11, 369 (2020), arXiv:1905.13641.
https: / / doi.org/ 10.1146 / annurev-conmatphys-031119-050605
arXiv: 1905.13641

[4] C. Figgatt, A. Ostrander, NM Linke, KA Landsman, D. Zhu, D. Maslov, và C. Monroe, Các phép toán vướng víu song song trên máy tính lượng tử bẫy ion vạn năng, Nature 572, 368 (2019), arXiv:1810.11948 .
https:/​/​doi.org/​10.1038/​s41586-019-1427-5
arXiv: 1810.11948

[5] Y. Lu, S. Zhang, K. Zhang, W. Chen, Y. Shen, J. Zhang, J.-N. Zhang và K. Kim, Các cổng vướng víu toàn cầu có thể mở rộng trên các qubit ion tùy ý, Nature 572, 363 (2019), arXiv:1901.03508.
https:/​/​doi.org/​10.1038/​s41586-019-1428-4
arXiv: 1901.03508

[6] P. Baßler, M. Zipper, C. Cedzich, M. Heinrich, PH Huber, M. Johanning và M. Kliesch, Tổng hợp và biên dịch với các cổng đa qubit tối ưu theo thời gian, Quantum 7, 984 (2023), arXiv :2206.06387.
https:/​/​doi.org/​10.22331/​q-2023-04-20-984
arXiv: 2206.06387

[7] F. Barahona và AR Mahjoub, Trên hình cắt đa giác, Lập trình toán học 36, 157 (1986).
https: / / doi.org/ 10.1007 / BF02592023

[8] MR Garey và DS Johnson, Máy tính và tính khó chữa, Tập. 29 (WH Freeman và Company, New York, 2002).

[9] MJ Bremner, A. Montanaro và DJ Shepherd, Độ phức tạp trong trường hợp trung bình so với mô phỏng gần đúng của các phép tính lượng tử chuyển tiếp, Phys. Linh mục Lett. 117, 080501 (2016), arXiv:1504.07999.
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501
arXiv: 1504.07999

[10] J. Allcock, J. Bao, JF Doriguello, A. Luongo và M. Santha, Các mạch có độ sâu không đổi cho các Cổng được điều khiển thống nhất và các hàm Boolean ứng dụng vào các mạch bộ nhớ lượng tử, arXiv:2308.08539 (2023).
arXiv: 2308.08539

[11] S. Bravyi, D. Maslov và Y. Nam, Triển khai các hoạt động của Clifford với chi phí không đổi và nhân rộng các cổng được kiểm soát bằng cách sử dụng các tương tác toàn cầu, Phys. Mục sư Lett. 129, 230501 (2022), arXiv:2207.08691.
https: / / doi.org/ 10.1103 / PhysRevLett.129.230501
arXiv: 2207.08691

[12] S. Bravyi và D. Maslov, các mạch không có Hadamard phơi bày cấu trúc của nhóm Clifford, IEEE Trans. thông tin liên lạc Lý thuyết 67, 4546 (2021), arXiv:2003.09412.
https: / / doi.org/ 10.1109 / TIT.2021.3081415
arXiv: 2003.09412

[13] D. Maslov và B. Zindorf, Tối ưu hóa độ sâu của mạch CZ, CNOT và Clifford, Giao dịch IEEE về Kỹ thuật lượng tử 3, 1 (2022), arxiv:2201.05215.
https: / / doi.org/ 10.1109 / TQE.2022.3180900
arXiv: 2201.05215

[14] S. Boyd và L. Vandenberghe, Tối ưu hóa lồi (Nhà xuất bản Đại học Cambridge, 2009).

[15] E. Rich, Các lớp vấn đề FP và FNP, trong Automata, Tính toán và độ phức tạp: Lý thuyết và ứng dụng (Pearson Education, 2007) trang 510–511.
https://​/​www.cs.utexas.edu/​~ear/​cs341/​automatabook/​AutomataTheoryBook.pdf

[16] M. Johanning, Chuỗi ion tuyến tính cách đều, Appl. Vật lý. B 122, 71 (2016).
https:/​/​doi.org/​10.1007/​s00340-016-6340-0

[17] M. Laurent và S. Poljak, Về sự giãn bán xác định dương của đa giác bị cắt, Đại số tuyến tính và các ứng dụng của nó 223-224, 439 (1995).
https:/​/​doi.org/​10.1016/​0024-3795(95)00271-R

[18] MM Deza và M. Laurent, Hình học của các vết cắt và số liệu, tái bản lần thứ nhất, Thuật toán và Tổ hợp (Springer Berlin Heidelberg, 1).
https:/​/​doi.org/​10.1007/​978-3-642-04295-9

[19] ME-Nagy, M. Laurent và A. Varvitsiotis, Độ phức tạp của bài toán hoàn thiện ma trận bán xác định dương với ràng buộc thứ hạng, Nhà xuất bản Quốc tế Springer, 105 (2013), arXiv:1203.6602.
https:/​/​doi.org/​10.1007/​978-3-319-00200-2_7
arXiv: 1203.6602

[20] REAC Paley, Về ma trận trực giao, Tạp chí Toán học và Vật lý 12, 311 (1933).
https: / / doi.org/ 10.1002 / sapm1933121311

[21] A. Hedayat và WD Wallis, ma trận Hadamard và các ứng dụng của chúng, Biên niên sử thống kê 6, 1184 (1978).
https: / / doi.org/ 10.1214 / aos / 1176344370

[22] H. Kharaghani và B. Tayfeh-Rezaie, Ma trận Hadamard bậc 428, Tạp chí Thiết kế Tổ hợp 13, 435 (2005).
https://​/​doi.org/​10.1002/​jcd.20043

[23] D. Ž. Đoković, O. Golubitsky, và IS Kotsireas, Một số mệnh đề mới của ma trận Hadamard và Skew-Hadamard, Tạp chí Thiết kế tổ hợp 22, 270 (2014), arXiv:1301.3671.
https://​/​doi.org/​10.1002/​jcd.21358
arXiv: 1301.3671

[24] J. Cohn, M. Motta và RM Parrish, Đường chéo hóa bộ lọc lượng tử với người Hamilton nhân hệ số kép được nén, PRX Quantum 2, 040352 (2021), arXiv:2104.08957.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040352
arXiv: 2104.08957

[25] DA Spielman và S.-H. Teng, Phân tích thuật toán được làm mịn: Tại sao thuật toán đơn hình thường mất thời gian đa thức, Tạp chí ACM 51, 385 (2004), arXiv:cs/​0111050.
https: / / doi.org/ 10.1145 / 990308.990310
arXiv: cs / 0111050

[26] S. Diamond và S. Boyd, CVXPY: Ngôn ngữ lập mô hình nhúng Python để tối ưu hóa lồi, J. Mach. Học hỏi. Res. 17, 1 (2016), arXiv:1603.00943.
arXiv: 1603.00943
http: / / jmlr.org/ paper / v17 ​​/ 15-408.html

[27] A. Agrawal, R. Verschueren, S. Diamond, và S. Boyd, Một hệ thống viết lại cho các bài toán tối ưu lồi, J. Control Decis. 5, 42 (2018), arXiv:1709.04494.
https: / / doi.org/ 10.1080 / 23307706.2017.1397554
arXiv: 1709.04494

[28] Free Software Foundation, GLPK (GNU Linear Programming Kit) (2012), phiên bản: 0.4.6.
https://​/​www.gnu.org/​software/​glpk/​

[29] AT Phillips và JB Rosen, Một thuật toán song song để giảm thiểu toàn cục bậc hai lõm bị ràng buộc, Lập trình toán học 42, 421 (1988).
https: / / doi.org/ 10.1007 / BF01589415

[30] M. Dür, R. Horst, và M. Locatelli, Xem lại các điều kiện tối ưu toàn cục cần và đủ để tối đa hóa lồi, Tạp chí Phân tích và Ứng dụng Toán học 217, 637 (1998).
https://​/​doi.org/​10.1006/​jmaa.1997.5745

[31] MS Bazaraa, HD Sherali và CM Shetty, Lập trình phi tuyến: lý thuyết và thuật toán, tái bản lần thứ 3 (John wiley & sons, 2013).
https: / / doi.org/ 10.1002 / 0471787779

[32] MA Hanson, Invexity and the Kuhn–Tucker Theorem, Tạp chí Phân tích và Ứng dụng Toán học 236, 594 (1999).
https://​/​doi.org/​10.1006/​jmaa.1999.6484

Trích dẫn

Không thể tìm nạp Crossref trích dẫn bởi dữ liệu trong lần thử cuối cùng 2024 / 03-13 13:00:52: Không thể tìm nạp dữ liệu được trích dẫn cho 10.22331 / q-2024-03-13-1279 từ Crossref. Điều này là bình thường nếu DOI đã được đăng ký gần đây. Trên SAO / NASA ADS 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 / 03-13 13:00:52).

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ử