Quantum Goemans-Williamson Algorithm With The Hadamard Test And Approximate Amplitude Constraints

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

ผู้ติดตาม: 0

เทย์เลอร์ แอล. แพตตี้^1,2, ฌอง คอสไซฟี่², อนิมา อานันท์กุมาร^3,2และซูซาน เอฟ. เยลิน¹

¹ภาควิชาฟิสิกส์ Harvard University, Cambridge, Massachusetts 02138 ประเทศสหรัฐอเมริกา
²NVIDIA, ซานตาคลารา, แคลิฟอร์เนีย 95051, สหรัฐอเมริกา
³ภาควิชาคอมพิวเตอร์ + คณิตศาสตร์ (CMS), California Institute of Technology (Caltech), Pasadena, CA 91125 USA

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

นามธรรม

โปรแกรมแบบกึ่งกำหนดขอบเขตเป็นวิธีการปรับให้เหมาะสมพร้อมการใช้งานที่หลากหลาย เช่น การประมาณปัญหาเชิงผสมที่ยาก โปรแกรมกึ่งกำหนดแน่นอนโปรแกรมหนึ่งคืออัลกอริธึม Goemans-Williamson ซึ่งเป็นเทคนิคการผ่อนคลายจำนวนเต็มยอดนิยม เราแนะนำอัลกอริธึมควอนตัมแบบแปรผันสำหรับอัลกอริธึม Goemans-Williamson ที่ใช้เพียง $n{+}1$ qubits จำนวนการเตรียมวงจรคงที่ และค่าความคาดหวัง $text{poly}(n)$ เพื่อแก้โปรแกรมแบบกึ่งกำหนดโดยประมาณ โดยมีตัวแปรมากถึง $N=2^n$ และข้อจำกัด $M sim O(N)$ การปรับให้เหมาะสมอย่างมีประสิทธิภาพทำได้โดยการเข้ารหัสเมทริกซ์วัตถุประสงค์เป็นหน่วยที่มีการกำหนดพารามิเตอร์อย่างเหมาะสมซึ่งมีเงื่อนไขบนควิบิตเสริม ซึ่งเป็นเทคนิคที่เรียกว่าการทดสอบ Hadamard การทดสอบ Hadamard ช่วยให้เราสามารถเพิ่มประสิทธิภาพฟังก์ชันวัตถุประสงค์ได้โดยการประมาณค่าความคาดหวังเพียงค่าเดียวของ ancilla qubit แทนที่จะประเมินค่าความคาดหวังจำนวนมากแบบเอกซ์โปเนนเชียลแยกกัน ในทำนองเดียวกัน เราแสดงให้เห็นว่าข้อจำกัดการเขียนโปรแกรมกึ่งกำหนดสามารถบังคับใช้ได้อย่างมีประสิทธิภาพโดยการใช้การทดสอบ Hadamard ครั้งที่สอง เช่นเดียวกับการกำหนดจำนวนพหุนามของข้อจำกัดแอมพลิจูดสตริงของ Pauli เราแสดงให้เห็นถึงประสิทธิผลของโปรโตคอลของเราโดยคิดค้นการใช้ควอนตัมที่มีประสิทธิภาพของอัลกอริธึม Goemans-Williamson สำหรับปัญหา NP-hard ต่างๆ รวมถึง MaxCut วิธีการของเรามีประสิทธิภาพเหนือกว่าวิธีการแบบคลาสสิกที่คล้ายคลึงกันในชุดย่อยที่หลากหลายของปัญหา MaxCut ที่ได้รับการศึกษามาอย่างดีจากไลบรารี GSet

Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints PlatoBlockchain Data Intelligence. Vertical Search. Ai.

ภาพเด่น: ไดอะแกรมของ HTAAC-QSDP สำหรับอัลกอริทึม Goemans-Williamson พร้อมด้วย qubit ที่ไม่ใช่ $n=3$ ก) ปัญหาคลาสสิกของตัวแปร $N$ (นี่คือปัญหา $N$-vertex MaxCut โดยที่ $N=8$) เมทริกซ์น้ำหนัก $W$ ใช้เพื่อสร้างหน่วย $U_W$ b) การทดสอบ Hadamard ใช้เพื่อประเมินฟังก์ชันวัตถุประสงค์และข้อจำกัดด้านความสมดุลของประชากรอย่างมีประสิทธิภาพ สถานะ $n$-qubit $|psirangle = U_V|mathbf{0}rangle$ ได้รับการจัดเตรียมด้วยวงจรควอนตัมแปรผัน $U_V$ $n+1$th (เสริม) qubit เริ่มต้นเป็น $(|0rangle -i |1rangle)/sqrt{2}$ ต่อจากนั้น การทดสอบ Hadamard จะดำเนินการ: $U_W$ ถูกนำมาใช้เป็นยูนิตควบคุมที่มีเงื่อนไขบนคิวบิตเสริม ซึ่งจากนั้นจะถูกวัดเพื่อคำนวณ $langle sigma_{n+1} rangle_{W,t} = text{Im} [langle psi|U_W|psi rangle]$ หรือ $langle sigma_{n+1} rangle_{P,t} = text{Im}[langle psi|U_P|psi rangle]$. c) ข้อจำกัดข้อจำกัดด้านแอมพลิจูด $M=2^n$ SDP ถูกบังคับใช้โดยประมาณด้วยข้อจำกัดสตริงข้อความ $m sim text{poly}(n)$ Pauli เท่านั้น สิ่งเหล่านี้คำนวณโดยการรวบรวมการวัด $n$-qubit Pauli-$z$ และใช้สถิติส่วนขอบเพื่อประมาณค่าความคาดหวัง $m$

สรุปยอดนิยม

โปรแกรมกึ่งกำหนดขอบเขตช่วยให้เราประมาณปัญหายากๆ ได้มากมาย รวมถึงปัญหา NP-hard โปรแกรมกึ่งกำหนดแน่นอนโปรแกรมหนึ่งคืออัลกอริธึม Goemans-Williamson ซึ่งสามารถแก้ปัญหายาก ๆ เช่น MaxCut เราแนะนำอัลกอริธึมควอนตัมแบบแปรผันสำหรับอัลกอริธึม Goemans-Williamson ที่ใช้เพียง $n{+}1$ qubits จำนวนการเตรียมวงจรคงที่ และจำนวนพหุนามของค่าคาดหวัง เพื่อประมาณแก้โปรแกรมกึ่งกำหนดด้วยจำนวนเอ็กซ์โพเนนเชียลของ ตัวแปรและข้อจำกัด เราเข้ารหัสปัญหาลงในวงจรควอนตัม (หรือหน่วยเดียว) และอ่านออกมาในคิวบิตเสริมเดี่ยว ซึ่งเป็นเทคนิคที่เรียกว่าการทดสอบ Hadamard ในทำนองเดียวกัน เราแสดงให้เห็นว่าข้อจำกัดของปัญหาสามารถบังคับใช้ได้โดย 1) การทดสอบ Hadamard ครั้งที่สอง และ 2) จำนวนพหุนามของข้อจำกัดสตริงของ Pauli เราแสดงให้เห็นถึงประสิทธิผลของโปรโตคอลของเราโดยคิดค้นการใช้ควอนตัมที่มีประสิทธิภาพของอัลกอริธึม Goemans-Williamson สำหรับปัญหา NP-hard ต่างๆ รวมถึง MaxCut วิธีการของเรามีประสิทธิภาพเหนือกว่าวิธีการแบบคลาสสิกที่คล้ายคลึงกันในชุดย่อยที่หลากหลายของปัญหา MaxCut ที่ได้รับการศึกษามาเป็นอย่างดี

► ข้อมูล BibTeX

@article{Patti2023quantumgoemans, doi = {10.22331/q-2023-07-12-1057}, url = {https://doi.org/10.22331/q-2023-07-12-1057}, title = {ควอนตัม { G}oemans-{W}illiamson {A}อัลกอริทึมกับ {H}adamard {T}est และ {A}ประมาณ {A}ความกว้าง {C}onstraints} ผู้แต่ง = {Patti, Taylor L. และ Kossaifi, Jean และ Anandkumar, Anima และ Yelin, Susanne F.}, วารสาร = {{Quantum}}, issn = {2521-327X}, ผู้เผยแพร่ = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}} , ปริมาณ = {7}, หน้า = {1057}, เดือน = กรกฎาคม, ปี = {2023} }

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

[1] สตีเฟน พี. บอยด์ และลีเวน แวนเดนเบิร์กเฮ “การเพิ่มประสิทธิภาพนูน” สำนักพิมพ์เคมบริดจ์ (2004)
https://doi.org/10.1017/CBO9780511804441

[2] มิเชล เอ็กซ์. โกแมนส์. “การเขียนโปรแกรมกึ่งกำหนดในการเพิ่มประสิทธิภาพเชิงผสม” การเขียนโปรแกรมทางคณิตศาสตร์ 79, 143–161 (1997)
https://doi.org/10.1007/BF02614315

[3] ลีเวน แวนเดนเบิร์ก และสตีเฟน บอยด์ “การประยุกต์โปรแกรมกึ่งกำหนดทิศทาง” คณิตศาสตร์เชิงตัวเลขประยุกต์ 29, 283–299 (1999)
https://doi.org/10.1016/S0168-9274(98)00098-1

[4] Wenjun Li, Yang Ding, Yongjie Yang, R. Simon Sherratt, Jong Hyuk Park และ Jin Wang “อัลกอริธึมที่กำหนดพารามิเตอร์ของปัญหา np-hard พื้นฐาน: แบบสำรวจ” วิทยาศาสตร์คอมพิวเตอร์และสารสนเทศที่มีมนุษย์เป็นศูนย์กลาง 10, 29 (2020)
https://doi.org/10.1186/s13673-020-00226-w

[5] คริสตอฟ เฮล์มเบิร์ก. “การเขียนโปรแกรมกึ่งกำหนดสำหรับการเพิ่มประสิทธิภาพเชิงผสม” Konrad-Zuse-Zentrum ขน Informationstechnik เบอร์ลิน (2000).
https://doi.org/10.1007/BF02614315

[6] มิเชล เอ็กซ์. โกแมนส์ และเดวิด พี. วิลเลียมสัน “อัลกอริธึมการประมาณที่ได้รับการปรับปรุงสำหรับปัญหาการตัดสูงสุดและความพึงพอใจโดยใช้การเขียนโปรแกรมกึ่งกำหนด” เจ. ACM 42, 1115–1145 (1995)
https://doi.org/10.1145/227683.227684

[7] ฟลอเรียน เอ. โพทรา และสตีเฟน เจ. ไรท์ “วิธีการจุดภายใน”. วารสารคณิตศาสตร์และคณิตศาสตร์ประยุกต์ 124, 281–302 (2000)
https://doi.org/10.1016/S0377-0427(00)00433-7

[8] ห่าวเทียน เจียง, ทารุน คาทูเรีย, หยิน ทัด ลี, สวาตี ปัทมนาพัน และจ้าวซ่ง “วิธีจุดภายในที่เร็วขึ้นสำหรับการเขียนโปรแกรมกึ่งกำหนด” ในปี 2020 การประชุมสัมมนาประจำปี IEEE ครั้งที่ 61 เกี่ยวกับรากฐานของวิทยาการคอมพิวเตอร์ (FOCS) หน้า 910–918. อีอีอี (2020)
https://doi.org/10.1109/FOCS46700.2020.00089

[9] ไป่เหอ ฮวง, ซุ่นฮวา เจียง, จ้าวซ่ง, รันโจว เถา และ จางรุ่ยเจ๋อ “การแก้ปัญหา sdp เร็วขึ้น: กรอบงาน ipm ที่แข็งแกร่งและการใช้งานที่มีประสิทธิภาพ” ในปี 2022 การประชุมสัมมนาประจำปี IEEE ครั้งที่ 63 เกี่ยวกับรากฐานของวิทยาการคอมพิวเตอร์ (FOCS) หน้า 233–244. อีอีอี (2022)
https://doi.org/10.1109/FOCS54457.2022.00029

[10] เดวิด พี. วิลเลียมสัน และ เดวิด บี. ชมอยส์ “การออกแบบอัลกอริธึมการประมาณค่า” สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. (2011)
https://doi.org/10.1017/CBO9780511921735

[11] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn และคณะ “การเพิ่มประสิทธิภาพควอนตัมโดยใช้อัลกอริธึมการแปรผันบนอุปกรณ์ควอนตัมระยะใกล้” วิทยาศาสตร์และเทคโนโลยีควอนตัม 3, 030503 (2018).
https://doi.org/10.10882058-9565/aab822

[12] เอ็ดเวิร์ด ฟาร์ฮี, เจฟฟรีย์ โกลด์สโตน, แซม กัตมันน์ และไมเคิล ซิพเซอร์ “การคำนวณควอนตัมโดยวิวัฒนาการอะเดียแบติก” (2000) arXiv:ปริมาณ-ph/0001106.
arXiv:ปริมาณ-ph/0001106

[13] ทามีม อัลบัช และดาเนียล เอ. ลิดาร์ “การคำนวณควอนตัมอะเดียแบติก”. รายได้ Mod ฟิสิกส์ 90, 015002 (2018).
https://doi.org/10.1103/RevModPhys.90.015002

[14] Sepehr Ebadi, Alexander Keesling, Madelyn Cain, Tout T Wang, Harry Levine, Dolev Bluvstein, Giulia Semeghini, Ahmed Omran, JG Liu, Rhine Samajdar และคณะ “การหาค่าเหมาะที่สุดควอนตัมของเซตอิสระสูงสุดโดยใช้อาร์เรย์อะตอมของริดเบิร์ก” วิทยาศาสตร์ 376, 1209–1215 (2022)
https://doi.org/10.1126/science.abo6587

[15] ทาดาชิ คาโดวากิ และ ฮิเดโตชิ นิชิโมริ “การหลอมควอนตัมในแบบจำลอง ising ตามขวาง”. ฟิสิกส์ รายได้ E 58, 5355–5363 (1998)
https://doi.org/10.1103/PhysRevE.58.5355

[16] เอลิซาเบธ กิ๊บนีย์. “การอัพเกรด D-wave: วิธีที่นักวิทยาศาสตร์ใช้คอมพิวเตอร์ควอนตัมที่เป็นข้อถกเถียงมากที่สุดในโลก” ธรรมชาติ 541 (2017)
https:///doi.org/10.1038/541447b

[17] เอ็ดเวิร์ด ฟาร์ฮี, เจฟฟรีย์ โกลด์สโตน และแซม กัตมันน์ “อัลกอริธึมการหาค่าเหมาะที่สุดโดยประมาณควอนตัม” อาร์เอ็กซ์ (2014) arXiv:1411.4028.
https://doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028

[18] ฮวน เอ็ม อาร์ราโซลา, วิลล์ เบิร์กโฮล์ม, คามิล บราดเลอร์, โธมัส อาร์ บรอมลีย์, แมตต์ เจ คอลลินส์, อิช ดานด์, อัลแบร์โต ฟูมากัลลี, โธมัส เกอร์ริทส์, อังเดร กูสเซฟ, ลูคัส จี เฮลท์ และคณะ “วงจรควอนตัมที่มีโฟตอนจำนวนมากบนชิปนาโนโฟโตนิกที่ตั้งโปรแกรมได้” ธรรมชาติ 591, 54–60 (2021)
https://doi.org/10.1038/s41586-021-03202-1

[19] เฟอร์นันโด จีเอสแอล บรันเดา, อามีร์ คาเลฟ, ตงหยาง ลี, เซดริก เยน-หยู ลิน, คริสต้า เอ็ม. สวอร์ และเซียวตี้ วู “ตัวแก้ปัญหา SDP ควอนตัม: การเร่งความเร็วขนาดใหญ่ การเพิ่มประสิทธิภาพ และการใช้งานเพื่อการเรียนรู้ควอนตัม” งานสัมมนานานาชาติเรื่องออโต ภาษา และการเขียนโปรแกรมครั้งที่ 46 (ICALP 2019) 132, 27:1–27:14 (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.27

[20] โยรัน ฟาน อาเพลดูร์น และอันดราส กิลีเยน “การปรับปรุงการแก้ปัญหาควอนตัม sdp ด้วยแอปพลิเคชัน” ในการประชุมสัมมนานานาชาติเรื่องออโต ภาษา และการเขียนโปรแกรมครั้งที่ 46 (2019)
https://doi.org/10.4230/LIPICS.ICALP.2019.99

[21] โยรัน ฟาน อาเพลดูร์น, อันดราส กิเลียน, แซนเดอร์ กริบลิง และโรนัลด์ เดอ วูล์ฟ “ตัวแก้ปัญหา Quantum sdp: ขอบเขตบนและล่างที่ดีกว่า” ควอนตัม 4, 230 (2020)
https://doi.org/10.22331/q-2020-02-14-230

[22] เฟอร์นันโด GSL Brandão และ Krysta M. Svore “การเร่งความเร็วควอนตัมสำหรับการแก้โปรแกรมกึ่งกำหนด” ในปี 2017 การประชุมสัมมนาประจำปี IEEE ครั้งที่ 58 เกี่ยวกับรากฐานของวิทยาการคอมพิวเตอร์ (FOCS) หน้า 415–426. (2017)
https://doi.org/10.1109/FOCS.2017.45

[23] Fernando GS L. Brandão, Richard Kueng และ Daniel Stilck França “ควอนตัมที่เร็วขึ้นและการประมาณ SDP แบบคลาสสิกสำหรับการเพิ่มประสิทธิภาพไบนารีกำลังสอง” ควอนตัม 6, 625 (2022)
https://doi.org/10.22331/q-2022-01-20-625

[24] ดรูมิล พาเทล, แพทริค เจ. โคลส์ และมาร์ก เอ็ม. ไวลด์ “อัลกอริธึมควอนตัมแบบแปรผันสำหรับการเขียนโปรแกรมกึ่งกำหนด” (2021) arXiv:2112.08859.
arXiv: 2112.08859

[25] Anirban N. Chowdhury, Guang Hao Low และ Nathan Wiebe “อัลกอริธึมควอนตัมแปรผันสำหรับการเตรียมสถานะควอนตัมกิบส์” (2020) arXiv:2002.00055.
arXiv: 2002.00055

[26] เทย์เลอร์ แอล แพตตี, โอมาร์ ชีฮับ, คาดิเจห์ นาจาฟี และซูซาน เอฟ เยลิน “Markov chain monte carlo ปรับปรุงอัลกอริธึมควอนตัมแปรผัน” วิทยาศาสตร์และเทคโนโลยีควอนตัม 8, 015019 (2022)
https:///doi.org/10.1088/2058-9565/aca821

[27] โหยวเล่อ หวาง, กว่างซี ลี่ และซิน หวาง “การเตรียมสถานะควอนตัมกิ๊บส์แบบแปรผันด้วยซีรีส์เทย์เลอร์ที่ถูกตัดทอน” การตรวจสอบทางกายภาพใช้แล้ว 16, 054035 (2021)
https://doi.org/10.1103/PhysRevApplied.16.054035

[28] ซานจีฟ อาโรรา, เอลาด ฮาซาน และซัตเยน เคล “วิธีการอัพเดตตุ้มน้ำหนักแบบคูณ: เมตาอัลกอริธึมและการประยุกต์” ทฤษฎีคอมพิวเตอร์ 8, 121–164 (2012)
https://doi.org/10.4086/toc.2012.v008a006

[29] อิออร์ดานิส เคเรนิดิส และอนุพัม ปรากาช “วิธีจุดภายในควอนตัมสำหรับ lps และ sdps” ธุรกรรม ACM ในคอมพิวเตอร์ควอนตัม 1 (2020)
https://doi.org/10.1145/3406306

[30] แบรนดอน ออกัสติโน, จาโกโม นันนิซินี, ทามาส เทอร์ลากี และหลุยส์ เอฟ. ซูลัวกา “วิธีจุดภายในควอนตัมสำหรับการปรับให้เหมาะสมแบบกึ่งแน่นอน” (2022) arXiv:2112.06025.
arXiv: 2112.06025

[31] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio และ Patrick J. Coles “อัลกอริทึมควอนตัมแบบแปรผัน”. ธรรมชาติทบทวนฟิสิกส์ 3, 625–644 (2021)
https://doi.org/10.1038/s42254-021-00348-9

[32] คีชอร์ ภารตี, โทเบียส เฮาก์, วลัตโก เวดราล และเหลียง-ชวน กเว็ก “อัลกอริธึมควอนตัมระดับกลางที่มีเสียงดังสำหรับการเขียนโปรแกรมกึ่งกำหนด” ฟิสิกส์ ฉบับที่ 105, 052445 (2022)
https://doi.org/10.1103/PhysRevA.105.052445

[33] เลนนาร์ท บิตเทล และมาร์ติน คลิช “การฝึกอบรมอัลกอริธึมควอนตัมแบบแปรผันนั้นยาก np” ฟิสิกส์ สาธุคุณเลตต์. 127, 120502 (2021)
https://doi.org/10.1103/PhysRevLett.127.120502

[34] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush และ Hartmut Neven “ที่ราบสูงแห้งแล้งในภูมิทัศน์การฝึกอบรมโครงข่ายประสาทควอนตัม” การสื่อสารธรรมชาติ 9, 4812 (2018)
https://doi.org/10.1038/s41467-018-07090-4

[35] Carlos Ortiz Marrero, Mária Kieferová และ Nathan Wiebe “ที่ราบสูงแห้งแล้งที่ชักนำให้พัวพัน” PRX ควอนตัม 2, 040316 (2021)
https://doi.org/10.1103/PRXQuantum.2.040316

[36] Taylor L. Patti, Khadijeh Najafi, Xun Gao และ Susanne F. Yelin “พัวพันวางแผนการบรรเทาที่ราบสูงที่แห้งแล้ง” ฟิสิกส์ รายได้ Res. 3, 033090 (2021)
https://doi.org/10.1103/PhysRevResearch.3.033090

[37] อาเธอร์ เพซาห์, เอ็ม. เซเรโซ, แซมสัน หวัง, ไทเลอร์ โวลคอฟฟ์, แอนดรูว์ ที. ซอร์นบอร์เกอร์ และแพทริค เจ. โคลส์ “การไม่มีที่ราบสูงแห้งแล้งในโครงข่ายประสาทเทียมแบบควอนตัม” ฟิสิกส์ ฉบับที่ X 11, 041011 (2021)
https://doi.org/10.1103/PhysRevX.11.041011

[38] โดริต อาฮารอนอฟ, วอห์น โจนส์ และเซฟ แลนเดา “อัลกอริทึมควอนตัมพหุนามสำหรับการประมาณพหุนามโจนส์” อัลกอริทึม 55, 395–421 (2009)
https://doi.org/10.1007/s00453-008-9168-0

[39] ผู้บัญชาการเคลย์ตัน ดับเบิลยู. “ปัญหาการตัดสูงสุด ปัญหาการตัดสูงสุด ปัญหาการตัดสูงสุด” หน้า 1991–1999. สปริงเกอร์สหรัฐอเมริกา บอสตัน, แมสซาชูเซตส์ (2009)
https://doi.org/10.1007/978-0-387-74759-0_358

[40] สตีเวน เจ. เบนสัน, หยินหยู เยบ และซยง จาง “การเขียนโปรแกรมเชิงเส้นและกึ่งกำหนดขอบเขตแบบผสมสำหรับการเพิ่มประสิทธิภาพเชิงผสมและกำลังสอง” วิธีการปรับให้เหมาะสมและซอฟต์แวร์ 11, 515–544 (1999)
https://doi.org/10.1080/10556789908805761

[41] ชางฮุย ชอย และ หยินหยู เย่ “การแก้โปรแกรมกึ่งกำหนดกระจัดกระจายโดยใช้อัลกอริธึมสเกลคู่พร้อมตัวแก้ปัญหาแบบวนซ้ำ” ต้นฉบับ, ภาควิชาวิทยาการจัดการ, มหาวิทยาลัยไอโอวา, ไอโอวาซิตี, ไอโอวา 52242 (2000) URL: web.stanford.edu/ yye/yye/cgsdp1.pdf.
https:///web.stanford.edu/~yye/yye/cgsdp1.pdf

[42] แองเจลิกา วีเกล. “ไลบรารี Biq mac – ชุดของอินสแตนซ์การเขียนโปรแกรม max-cut และ quadratic 0-1 ที่มีขนาดกลาง” อัลเพน-เอเดรีย-มหาวิทยาลัยคลาเกนฟูร์ท (2007) URL: biqmac.aau.at/biqmaclib.pdf
https:///biqmac.aau.at/biqmaclib.pdf

[43] สเตฟาน เอช. ชมิเอตา. “ไลบรารีไดแมคส์ของโปรแกรมกึ่งกำหนดกำลังสอง-เชิงเส้นแบบผสม” ความท้าทายในการดำเนินการ DIMACS ครั้งที่ 7 (2007) URL: http:///archive.dimacs.rutgers.edu.
http:///archive.dimacs.rutgers.edu

[44] โยชิกิ มัตสึดะ. “การเปรียบเทียบปัญหาการตัดสูงสุดบนเครื่องแยกไปสองทางจำลอง” ปานกลาง (2019) url: medium.com/toshiba-sbm/benchmarking-the-max-cut-problem-on-the-simulated-bifurcation-machine-e26e1127c0b0.
https:///medium.com/toshiba-sbm/benchmarking-the-max-cut-problem-on-the-simulated-bifurcation-machine-e26e1127c0b0

[45] อาร์เอ็ม คาร์ป “การลดหย่อนในปัญหาเชิงผสม”. สปริงเกอร์สหรัฐอเมริกา บอสตัน แมสซาชูเซตส์ (1972)

[46] ดิมิทรี พี. เบิร์ตเซคาส. “การเพิ่มประสิทธิภาพแบบจำกัดและวิธีการตัวคูณลากรองจ์” สำนักพิมพ์วิชาการ. (1982)
https://doi.org/10.1016/C2013-0-10366-2

[47] จี เมาโร ดาเรียโน่, มัตเตโอ จีเอ ปารีส และมัสซิมิเลียโน่ เอฟ ซัคคี่ “การตรวจเอกซเรย์ควอนตัม”. ความก้าวหน้าในการถ่ายภาพและฟิสิกส์อิเล็กตรอน 128, 206–309 (2003)
https://doi.org/10.48550/arXiv.quant-ph/0302028
arXiv:ปริมาณ-ph/0302028

[48] อเลสซานโดร บิซิโอ, จูลิโอ ชิริเบลล่า, จาโกโม เมาโร ดาเรียโน, สเตฟาโน ฟัคคินี่ และเปาโล เปรินอตติ “เอกซเรย์ควอนตัมที่เหมาะสมที่สุด” วารสาร IEEE ของหัวข้อที่เลือกใน Quantum Electronics 15, 1646–1660 (2009)
https://doi.org/10.1109/JSTQE.2009.2029243

[49] แม็กซ์ เอส. คาซนาดี และแดเนียล เอฟวี เจมส์ “กลยุทธ์เชิงตัวเลขสำหรับเอกซเรย์ควอนตัม: ทางเลือกสู่การปรับให้เหมาะสมที่สุด” ฟิสิกส์ ฉบับที่ 79, 022109 (2009)
https://doi.org/10.1103/PhysRevA.79.022109

[50] ฮาเวียร์ เปญา. “การบรรจบกันของวิธีลำดับที่หนึ่งผ่านคอนจูเกตนูน” จดหมายวิจัยการดำเนินงาน 45, 561–564 (2017)
https://doi.org/10.1016/j.orl.2017.08.013

[51] อลัน ฟรีซ และ มาร์ค เจอร์รัม “ปรับปรุงอัลกอริธึมการประมาณสำหรับ maxk-cut และ max bisection” อัลกอริทึม 18, 67–81 (1997)
https://doi.org/10.1007/BF02523688

[52] คลาร์ก เดวิด ทอมป์สัน. “ทฤษฎีความซับซ้อนของ vlsi” วิทยานิพนธ์ระดับปริญญาเอก มหาวิทยาลัยคาร์เนกี้เมลลอน (1980) URL: dl.acm.org/doi/10.5555/909758.
https:///dl.acm.org/doi/10.5555/909758

[53] ชู มิน ลี และ เฟลิป มันยา “Maxsat ข้อจำกัดแบบแข็งและแบบอ่อน” ในคู่มือความพึงพอใจ หน้า 903–927. สื่อ IOS (2021)
https://doi.org/10.3233/978-1-58603-929-5-613

[54] นิโคลัส เจ. ไฮแฮม. “การคำนวณเมทริกซ์สหสัมพันธ์ที่ใกล้ที่สุด - ปัญหาจากการเงิน” วารสาร IMA ของการวิเคราะห์เชิงตัวเลข 22, 329–343 (2002)
https://doi.org/10.1093/imanum/22.3.329

[55] ทาดาโยชิ ฟูชิกิ. “การประมาณค่าเมทริกซ์สหสัมพันธ์กึ่งนิยามเชิงบวกโดยใช้โปรแกรมกึ่งนิยามกำลังสองนูนนูน” การคำนวณทางประสาท 21, 2028–2048 (2009)
https:///doi.org/10.1162/neco.2009.04-08-765

[56] ทอดด์ เอ็มเจ. “การศึกษาทิศทางการค้นหาในวิธีจุดภายในปฐมภูมิ-คู่สำหรับการเขียนโปรแกรมกึ่งกำหนด” วิธีการปรับให้เหมาะสมและซอฟต์แวร์ 11, 1–46 (1999)
https://doi.org/10.1080/10556789908805745

[57] โรเจอร์ เฟลทเชอร์. “ฟังก์ชั่นการลงโทษ”. การเขียนโปรแกรมทางคณิตศาสตร์ สถานะของศิลปะ: บอนน์ 1982 หน้า 87–114 (1983)
https://doi.org/10.1007/978-3-642-68874-4_5

[58] โรเบิร์ต เอ็ม ฟรอยด์. “วิธีการลงโทษและอุปสรรคสำหรับการเพิ่มประสิทธิภาพที่มีข้อจำกัด” เอกสารบรรยาย, สถาบันเทคโนโลยีแมสซาชูเซตส์ (2004) url: ocw.mit.edu/courses/15-084j-nonlinear-programming-spring-2004.
https:///ocw.mit.edu/courses/15-084j-nonlinear-programming-spring-2004

[59] เอริก ริคาร์โด้ อันชูตซ์. “จุดวิกฤตในแบบจำลองกำเนิดควอนตัม” ในการประชุมนานาชาติเรื่องการนำเสนอการเรียนรู้ (2022) URL: openreview.net/forum?id=2f1z55GVQN.
https:///openreview.net/forum?id=2f1z55GVQN

[60] อาเมียร์ เบ็ค. “วิธีการลำดับแรกในการเพิ่มประสิทธิภาพ” สยาม (2017)
https://doi.org/10.1137/1.9781611974997

[61] ซานจีฟ อาโรรา และ สัตเยน เคล “แนวทางเชิงผสมผสาน ปฐมภูมิ-คู่ สำหรับโปรแกรมกึ่งกำหนดขอบเขต” เจ. ACM 63 (2016)
https://doi.org/10.1145/2837020

[62] เทย์เลอร์ แอล. แพตตี, ฌอง คอสไซฟี, ซูซาน เอฟ. เยลิน และอานิมา อานันด์คูมาร์ “เทนเซอร์ลีควอนตัม: การเรียนรู้ของเครื่องควอนตัมด้วยวิธีเทนเซอร์” (2021) arXiv:2112.10239.
arXiv: 2112.10239

[63] ฌอง คอสไซฟี, ยานนิส ปานากากิส, อานิมา อานันด์กุมาร์ และมาจา ปานติก “เทนเซอร์: การเรียนรู้เทนเซอร์ในหลาม” วารสารการวิจัยการเรียนรู้ของเครื่อง 20, 1–6 (2019) URL: http:///jmlr.org/papers/v20/18-277.html.
http:///jmlr.org/papers/v20/18-277.html

[64] ทีมงานคิวควอนตัม “Nvidia/cuquantum: cuquantum v22.11” (2022)

[65] ดีเดริก พี. คิงมา และจิมมี่ บา “อดัม: วิธีการเพิ่มประสิทธิภาพสุ่ม” (2017) arXiv:1412.6980.
arXiv: 1412.6980

[66] บราฮิม เชาราร์. “อัลกอริธึมเวลาเชิงเส้นสำหรับตัวแปรของปัญหาการตัดสูงสุดในกราฟขนานแบบอนุกรม” ความก้าวหน้าในการวิจัยการดำเนินงาน (2017)
https://doi.org/10.1155/2017/1267108

[67] ยูรี มาคารีเชฟ. “ข้อพิสูจน์สั้นๆ เกี่ยวกับเกณฑ์ระนาบกราฟของ Kuratowski” วารสารทฤษฎีกราฟ 25, 129–131 (1997)
<a href="https://doi.org/10.1002/(SICI)1097-0118(199706)25:23.0.CO;2-O”>https://doi.org/10.1002/(SICI)1097-0118(199706)25:2<129::AID-JGT4>3.0.CO;2-O

[68] เบลา โบลโลบาส. “วิวัฒนาการของกราฟสุ่ม—องค์ประกอบขนาดยักษ์” หน้า 130–159. เคมบริดจ์ศึกษาในวิชาคณิตศาสตร์ขั้นสูง สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. (2001) ฉบับที่ 2
https://doi.org/10.1017/CBO9780511814068.008

[69] ซานจีฟ อาโรรา, เดวิด คาร์เกอร์ และมาเร็ค คาร์ปินสกี้ “รูปแบบการประมาณเวลาพหุนามสำหรับกรณีหนาแน่นของปัญหา np-hard” วารสารวิทยาการคอมพิวเตอร์และระบบ 58, 193–210 (1999)
https://doi.org/10.1006/jcss.1998.1605

[70] ริค เดอร์เรตต์. “กราฟสุ่มแอร์โดส-เรนยี” หน้า 27–69. Cambridge Series ในวิชาคณิตศาสตร์เชิงสถิติและความน่าจะเป็น สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. (2006)
https://doi.org/10.1017/CBO9780511546594.003

[71] แกรี่ ชาร์ตรานด์ และปิง จาง “ทฤษฎีกราฟโครมาติก”. เทย์เลอร์และฟรานซิส (2008)
https://doi.org/10.1201/9781584888017

[72] จอห์น ฟาน เดอ เวเทอริง “แคลคูลัส Zx สำหรับนักวิทยาศาสตร์คอมพิวเตอร์ควอนตัมที่ทำงาน” (2020) arXiv:2012.13966.
arXiv: 2012.13966

[73] อเล็กซานเดอร์ คาวแทน, ซิลาส ดิลเคส, รอสส์ ดันแคน, วิล ซิมมอนส์ และเซยอน ซิวาราจาห์ "การสังเคราะห์อุปกรณ์เฟสสำหรับวงจรตื้น" การดำเนินการทางอิเล็กทรอนิกส์ในวิทยาการคอมพิวเตอร์เชิงทฤษฎี 318, 213–228 (2020)
https://doi.org/10.4204/eptcs.318.13

[74] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe และ Shuchen Zhu “ทฤษฎีความคลาดเคลื่อนของทรอตเตอร์กับสเกลของคอมมิวเตเตอร์”. ฟิสิกส์ รายได้ X 11, 011020 (2021)
https://doi.org/10.1103/PhysRevX.11.011020

[75] โจเซฟ ดับเบิลยู บริทตัน, ไบรอัน ซี ซอว์เยอร์, อดัม ซี คีธ, ซีซี โจเซฟ หวัง, เจมส์ เค ฟรีริกส์, แฮร์มันน์ อูยส์, ไมเคิล เจ เบียร์คัก และจอห์น เจ โบลินเจอร์ “ออกแบบปฏิสัมพันธ์ไอซิ่งสองมิติในเครื่องจำลองควอนตัมไอออนที่ดักจับด้วยการหมุนนับร้อยครั้ง” ธรรมชาติ 484, 489–492 (2012)
https://doi.org/10.1038/nature10981

[76] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, Soonwon Choi, Alexander S Zibrov, Manuel Endres, Markus Greiner และคณะ “สำรวจไดนามิกของร่างกายหลายส่วนบนเครื่องจำลองควอนตัม 51 อะตอม” ธรรมชาติ 551, 579–584 (2017)
https://doi.org/10.1038/nature24622

[77] เกออร์เก-โซริน ปาราอานู. “ความคืบหน้าล่าสุดในการจำลองควอนตัมโดยใช้วงจรตัวนำยิ่งยวด” วารสารฟิสิกส์อุณหภูมิต่ำ 175, 633–654 (2014)
https://doi.org/10.1007/s10909-014-1175-8

[78] คัตสึกิ ฟูจิซาวะ, ฮิโตชิ ซาโตะ, ซาโตชิ มัตสึโอกะ, โทชิโอะ เอ็นโดะ, มาโกโตะ ยามาชิตะ และมาโฮะ นากาตะ “ตัวแก้ปัญหาทั่วไปประสิทธิภาพสูงสำหรับปัญหาการเขียนโปรแกรมกึ่งกำหนดขนาดใหญ่มาก” ใน SC '12: การดำเนินการของการประชุมนานาชาติเกี่ยวกับคอมพิวเตอร์ประสิทธิภาพสูง ระบบเครือข่าย การจัดเก็บ และการวิเคราะห์ หน้า 1–11. (2012)
https://doi.org/10.1109/SC.2012.67

[79] เอเดรียน เอส. ลูอิส และไมเคิล แอล. โอเวอร์ตัน “การเพิ่มประสิทธิภาพค่าลักษณะเฉพาะ” แอกตา นูเมริกา 5, 149–190 (1996)
https://doi.org/10.1017/S0962492900002646

[80] เซียวซี ซู, จินจ้าว ซุน, ซูกุรุ เอ็นโดะ, หยิง ลี่, ไซมอน ซี. เบนจามิน และเซียว หยวน “อัลกอริธึมการเปลี่ยนแปลงของพีชคณิตเชิงเส้น” กระดานข่าววิทยาศาสตร์ 66, 2181–2188 (2021)
https://doi.org/10.1016/j.scib.2021.06.023

อ้างโดย

ไม่สามารถดึงข้อมูล Crossref อ้างโดย data ระหว่างความพยายามครั้งสุดท้าย 2023-07-12 14:07:40 น.: ไม่สามารถดึงข้อมูลที่อ้างถึงสำหรับ 10.22331 / q-2023-07-12-1057 จาก Crossref นี่เป็นเรื่องปกติหาก DOI ได้รับการจดทะเบียนเมื่อเร็วๆ นี้ บน อบต./นาซ่าโฆษณา ไม่พบข้อมูลอ้างอิงงาน (ความพยายามครั้งสุดท้าย 2023-07-12 14:07:40)

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

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

ประทับเวลา: กรกฎาคม 12, 2023

ประทับเวลา: กรกฎาคม 14, 2022

อัลกอริทึม Quantum Goemans-Williamson พร้อมการทดสอบ Hadamard และข้อจำกัดแอมพลิจูดโดยประมาณ

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

นามธรรม

สรุปยอดนิยม

► ข้อมูล BibTeX

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

อ้างโดย

เพิ่มเติมจาก วารสารควอนตัม

nonlocality ถาวรในสภาพแวดล้อม ultracold-atom

ทฤษฎีที่มีประสิทธิผลเทียบกับ Floquet สำหรับออสซิลเลเตอร์พาราเมตริกของ Kerr

การวัดการซ้อนทับเชิงสัมพันธ์ด้วยไม้บรรทัดควอนตัมวัสดุ

การผลิตเอนโทรปีพัวพันในเครือข่ายประสาทควอนตัม

การจำลองทฤษฎีเกจและระบบโบโซนิกที่แม่นยำอย่างพิสูจน์ได้

รหัสการเข้าถึงแบบสุ่มผ่านความซ้ำซ้อนตามบริบทควอนตัม

การปรับให้เหมาะสมตามสถานะเริ่มต้นของการทำงานของประตูควบคุมด้วยควอนตัมคอมพิวเตอร์

ตัดวงจรควอนตัมอย่างรวดเร็วด้วยการวัดแบบสุ่ม

การกำหนดลักษณะโดเมนเวลาทางสถิติของนาฬิกาออปติคัลที่ไม่ใช่คาบ

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

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

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

การติดต่อ

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