ข้อควรพิจารณาเกี่ยวกับเวลาแฝงสำหรับเครื่องมือเพิ่มประสิทธิภาพแบบสุ่มในอัลกอริทึมควอนตัมแบบแปรผัน

ข้อควรพิจารณาเกี่ยวกับเวลาแฝงสำหรับเครื่องมือเพิ่มประสิทธิภาพแบบสุ่มในอัลกอริทึมควอนตัมแบบแปรผัน

โหนดต้นทาง: 2015562

Matt Menickelly1, Yunsoo Ha2, and Matthew Otten3

1Mathematics and Computer Science Division, Argonne National Laboratory, 9700 S. Cass Ave., Lemont, IL 60439
2Edward P. Fitts Department of Industrial and Systems Engineering, North Carolina State University, 915 Partners Way, Raleigh, NC 27601
3HRL Laboratories, LLC, 3011 Malibu Canyon Road, Malibu, CA 90265

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

นามธรรม

Variational quantum algorithms, which have risen to prominence in the noisy intermediate-scale quantum setting, require the implementation of a stochastic optimizer on classical hardware. To date, most research has employed algorithms based on the stochastic gradient iteration as the stochastic classical optimizer. In this work we propose instead using stochastic optimization algorithms that yield stochastic processes emulating the dynamics of classical deterministic algorithms. This approach results in methods with theoretically superior worst-case iteration complexities, at the expense of greater per-iteration sample (shot) complexities. We investigate this trade-off both theoretically and empirically and conclude that preferences for a choice of stochastic optimizer should explicitly depend on a function of both latency and shot execution times.

Variational quantum algorithms are promising candidates for solving practical problems on near-term quantum computers. However, the process of optimizing these algorithms can be computationally expensive due to the two needs to 1) perform repeated measurements (shots) on the quantum computer and 2) adjust the quantum circuit parameters. Here, we propose a new stochastic optimization algorithm called SHOALS (SHOt Adaptive Line Search) that is designed under the assumption that the time spent in optimization performing shots is dominated by the time spent in optimization performing circuit adjustments. We demonstrate that SHOALS outperforms other stochastic optimization algorithms in this setting. On the contrary, when the shot time is comparable to the circuit switching time, stochastic gradient descent algorithms are found to be more efficient. By considering the trade-offs between shot time, circuit switching time, and the efficiency of the optimization algorithm, we show that the total run time of variational quantum algorithms can be significantly reduced.

► ข้อมูล BibTeX

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

[1] Benjamin P Lanyon, James D Whitfield, Geoff G Gillett, Michael E Goggin, Marcelo P Almeida, Ivan Kassal, Jacob D Biamonte, Masoud Mohseni, Ben J Powell, Marco Barbieri, et al. “Towards quantum chemistry on a quantum computer”. Nature Chemistry 2, 106–111 (2010).
https://doi.org/10.1038/​nchem.483

[2] Ian C Cloët, Matthew R Dietrich, John Arrington, Alexei Bazavov, Michael Bishof, Adam Freese, Alexey V Gorshkov, Anna Grassellino, Kawtar Hafidi, Zubin Jacob, et al. “Opportunities for nuclear physics & quantum information science” (2019). arXiv:1903.05453.
arXiv: 1903.05453

[3] Adam Smith, MS Kim, Frank Pollmann, and Johannes Knolle. “Simulating quantum many-body dynamics on a current digital quantum computer”. npj Quantum Information 5, 1–13 (2019).
https:/​/​doi.org/​10.1038/​s41534-019-0217-0

[4] Benjamin Nachman, Davide Provasoli, Wibe A de Jong, and Christian W Bauer. “Quantum algorithm for high energy physics simulations”. Physical Review Letters 126, 062001 (2021).
https://doi.org/​10.1103/​PhysRevLett.126.062001

[5] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe และ Seth Lloyd “ควอนตัมแมชชีนเลิร์นนิง” ธรรมชาติ 549, 195–202 (2017)
https://doi.org/10.1038/​nature23474

[6] โรมัน โอรุส, ซามูเอล มูเกล และเอ็นริเก ลิซาโซ “ควอนตัมคอมพิวติ้งสำหรับการเงิน: ภาพรวมและโอกาส” บทวิจารณ์ในฟิสิกส์ 4, 100028 (2019)
https://doi.org/10.1016/​j.revip.2019.100028

[7] จอห์น เพรสคิล. “การคำนวณควอนตัมในยุค NISQ และอนาคต” ควอนตัม 2, 79 (2018)
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[8] U Dorner, R Demkowicz-Dobrzanski, BJ Smith, JS Lundeen, W Wasilewski, K Banaszek, and IA Walmsley. “Optimal quantum phase estimation”. Physical Review Letters 102, 040403 (2009).
https://doi.org/​10.1103/​PhysRevLett.102.040403

[9] John Preskill. “Fault-tolerant quantum computation”. In Introduction to quantum computation and information. Pages 213–269. World Scientific (1998).

[10] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. “Variational quantum algorithms”. Nature Reviews PhysicsPages 1–20 (2021).
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[11] Peter JJ O'Malley, Ryan Babbush, Ian D Kivlichan, Jonathan Romero, Jarrod R McClean, Rami Barends, Julian Kelly, Pedram Roushan, Andrew Tranter, Nan Ding, และคณะ “การจำลองควอนตัมที่ปรับขนาดได้ของพลังงานโมเลกุล”. รีวิวทางกายภาพ X 6, 031007 (2016)
https://doi.org/10.1103/​PhysRevX.6.031007

[12] เซียว หยวน, ซูกูรู เอนโด, ฉี จ้าว, หยิง ลี่ และไซมอน ซี เบนจามิน “ทฤษฎีการจำลองควอนตัมแปรผัน”. ควอนตัม 3, 191 (2019)
https:/​/​doi.org/​10.22331/​q-2019-10-07-191

[13] Matthew Otten, Cristian L Cortes, and Stephen K Gray. “Noise-resilient quantum dynamics using symmetry-preserving ansatzes” (2019). arXiv:1910.06284.
arXiv: 1910.06284

[14] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow และ Jay M Gambetta “ควอนตัมไอเกนโซลเวอร์แปรผันที่มีประสิทธิภาพฮาร์ดแวร์สำหรับโมเลกุลขนาดเล็กและแม่เหล็กควอนตัม” ธรรมชาติ 549, 242–246 (2017).
https://doi.org/10.1038/​nature23879

[15] โคสุเกะ มิทาราอิ, มาโคโตะ เนโกโระ, มาซาฮิโระ คิตากาวะ และเคสุเกะ ฟูจิอิ “การเรียนรู้วงจรควอนตัม”. การตรวจร่างกาย ก 98, 032309 (2018).
https://doi.org/10.1103/​PhysRevA.98.032309

[16] Matthew Otten, Imène R Goumiri, Benjamin W Priest, George F Chapline, and Michael D Schneider. “Quantum machine learning using gaussian processes with performant quantum kernels” (2020). arXiv:2004.11280.
arXiv: 2004.11280

[17] Robert M Parrish, Edward G Hohenstein, Peter L McMahon, and Todd J Martínez. “Quantum computation of electronic transitions using a variational quantum eigensolver”. Physical Review Letters 122, 230401 (2019).
https://doi.org/​10.1103/​PhysRevLett.122.230401

[18] Kevin J Sung, Jiahao Yao, Matthew P Harrigan, Nicholas C Rubin, Zhang Jiang, Lin Lin, Ryan Babbush, and Jarrod R McClean. “Using models to improve optimizers for variational quantum algorithms”. Quantum Science and Technology 5, 044008 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb6d9

[19] Jay Gambetta, WA Braff, A Wallraff, SM Girvin, and RJ Schoelkopf. “Protocols for optimal readout of qubits using a continuous quantum nondemolition measurement”. Physical Review A 76, 012325 (2007).
https://doi.org/10.1103/​PhysRevA.76.012325

[20] Susan M Clark, Daniel Lobser, Melissa C Revelle, Christopher G Yale, David Bossert, Ashlyn D Burch, Matthew N Chow, Craig W Hogle, Megan Ivory, Jessica Pehr, et al. “Engineering the quantum scientific computing open user testbed”. IEEE Transactions on Quantum Engineering 2, 1–32 (2021).
https://doi.org/​10.1109/​TQE.2021.3096480

[21] Colin D Bruzewicz, John Chiaverini, Robert McConnell, and Jeremy M Sage. “Trapped-ion quantum computing: Progress and challenges”. Applied Physics Reviews 6, 021314 (2019).
https://doi.org/10.1063/​1.5088164

[22] โจนัส เอ็ม คูเบลอร์, แอนดรูว์ อาร์ราสมิธ, ลูคัส ซินซิโอ และแพทริค เจ โคลส์ “เครื่องมือเพิ่มประสิทธิภาพแบบปรับตัวสำหรับอัลกอริธึมการเปลี่ยนแปลงที่ประหยัดในการวัด” ควอนตัม 4, 263 (2020)
https:/​/​doi.org/​10.22331/​q-2020-05-11-263

[23] Diederik P Kingma and Jimmy Ba. “Adam: A method for stochastic optimization” (2014). arXiv:1412.6980.
arXiv: 1412.6980

[24] Trygve Helgaker, Poul Jorgensen และ Jeppe Olsen “ทฤษฎีโครงสร้างอิเล็กทรอนิกส์โมเลกุล”. จอห์น ไวลีย์ แอนด์ ซันส์ (2014).
https://doi.org/10.1002/​9781119019572

[25] Tom Schaul, Ioannis Antonoglou, and David Silver. “Unit tests for stochastic optimization”. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings. (2014). url: http:/​/​arxiv.org/​abs/​1312.6055.
arXiv: 1312.6055

[26] Hilal Asi and John C Duchi. “The importance of better models in stochastic optimization”. Proceedings of the National Academy of Sciences 116, 22924–22930 (2019).
https://doi.org/10.1073/​pnas.1908018116

[27] Billy Jin, Katya Scheinberg, and Miaolan Xie. “High probability complexity bounds for line search based on stochastic oracles” (2021). arXiv:2106.06454.
arXiv: 2106.06454

[28] Jose Blanchet, Coralia Cartis, Matt Menickelly, and Katya Scheinberg. “Convergence rate analysis of a stochastic trust-region method via supermartingales”. INFORMS Journal on Optimization 1, 92–119 (2019).
https:/​/​doi.org/​10.1287/​ijoo.2019.0016

[29] Courtney Paquette and Katya Scheinberg. “A stochastic line search method with expected complexity analysis”. SIAM Journal on Optimization 30, 349–376 (2020).
https://doi.org/10.1137​18M1216250

[30] Albert S Berahas, Liyuan Cao, and Katya Scheinberg. “Global convergence rate analysis of a generic line search algorithm with noise”. SIAM Journal on Optimization 31, 1489–1518 (2021).
https://doi.org/10.1137​19M1291832

[31] Coralia Cartis, Nicholas IM Gould, and Ph L Toint. “On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization problems”. Siam journal on optimization 20, 2833–2852 (2010).
https://doi.org/10.1137/​090774100

[32] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. “On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization”. SIAM Journal on Optimization 22, 66–86 (2012).
https://doi.org/10.1137/​100812276

[33] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. “Lower bounds for finding stationary points I”. Mathematical Programming 184, 71–120 (2020).
https://doi.org/10.1007/​s10107-019-01406-y

[34] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. ““convex until proven guilty”: Dimension-free acceleration of gradient descent on non-convex functions”. In International Conference on Machine Learning. Pages 654–663. PMLR (2017).
https://doi.org/10.5555/​3305381.3305449

[35] Chi Jin, Praneeth Netrapalli, and Michael I Jordan. “Accelerated gradient descent escapes saddle points faster than gradient descent”. In Conference On Learning Theory. Pages 1042–1085. PMLR (2018). url: https:/​/​proceedings.mlr.press/​v75/​jin18a.html.
https:/​/​proceedings.mlr.press/​v75/​jin18a.html

[36] Saeed Ghadimi and Guanghui Lan. “Stochastic first-and zeroth-order methods for nonconvex stochastic programming”. SIAM Journal on Optimization 23, 2341–2368 (2013).
https://doi.org/10.1137/​120880811

[37] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. “Lower bounds for non-convex stochastic optimization” (2019). arXiv:1912.02365.
arXiv: 1912.02365

[38] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. “Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator”. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems. Volume 31. Curran Associates, Inc. (2018). url: https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​1543843a4723ed2ab08e18053ae6dc5b-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​1543843a4723ed2ab08e18053ae6dc5b-Paper.pdf

[39] Shiro Tamiya and Hayata Yamasaki. “Stochastic gradient line bayesian optimization: Reducing measurement shots in optimizing parameterized quantum circuits” (2021). arXiv:2111.07952.
https:/​/​doi.org/​10.1038/​s41534-022-00592-6
arXiv: 2111.07952

[40] Pascual Jordan and Eugene Paul Wigner. “über das paulische äquivalenzverbot”. In The Collected Works of Eugene Paul Wigner. Pages 109–129. Springer (1993).

[41] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac และ Nathan Killoran “การประเมินการไล่ระดับสีเชิงวิเคราะห์บนฮาร์ดแวร์ควอนตัม” การทบทวนทางกายภาพ A 99, 032331 (2019)
https://doi.org/10.1103/​PhysRevA.99.032331

[42] Joonho Lee, William J Huggins, Martin Head-Gordon, and K Birgitta Whaley. “Generalized unitary coupled cluster wave functions for quantum computation”. Journal of Chemical Theory and Computation 15, 311–324 (2018).
https://doi.org/10.1021/​acs.jctc.8b01004

[43] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. “A variational eigenvalue solver on a photonic quantum processor”. Nature Communications 5, 1–7 (2014). url: https:/​/​doi.org/​10.1038/​ncomms5213.
https://doi.org/10.1038/​ncomms5213

[44] Ilya G Ryabinkin, Tzu-Ching Yen, Scott N Genin และ Artur F Izmaylov “วิธีคลัสเตอร์แบบคู่ควบคู่: วิธีการที่เป็นระบบสำหรับเคมีควอนตัมบนคอมพิวเตอร์ควอนตัม” วารสารทฤษฎีเคมีและการคำนวณ 14, 6317–6326 (2018)
https://doi.org/10.1021/​acs.jctc.8b00932

[45] Ho Lun Tang, VO Shkolnikov, George S Barron, Harper R Grimsley, Nicholas J Mayhall, Edwin Barnes, and Sophia E Economou. “qubit-ADAPT-VQE: An adaptive algorithm for constructing hardware-efficient ansätze on a quantum processor”. PRX Quantum 2, 020310 (2021).
https://doi.org/10.1103/​PRXQuantum.2.020310

[46] Dmitry A. Fedorov, Yuri Alexeev, Stephen K. Gray, and Matthew Otten. “Unitary Selective Coupled-Cluster Method”. Quantum 6, 703 (2022).
https:/​/​doi.org/​10.22331/​q-2022-05-02-703

[47] Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi, and Frederic T Chong. “$ o (n^3) $ measurement cost for variational quantum eigensolver on molecular Hamiltonians”. IEEE Transactions on Quantum Engineering 1, 1–24 (2020).
https://doi.org/​10.1109/​TQE.2020.3035814

[48] Ruobing Chen, Matt Menickelly, and Katya Scheinberg. “Stochastic optimization using a trust-region method and random models”. Mathematical Programming 169, 447–487 (2018).
https:/​/​doi.org/​10.1007/​s10107-017-1141-8

[49] Léon Bottou, Frank E Curtis, and Jorge Nocedal. “Optimization methods for large-scale machine learning”. Siam Review 60, 223–311 (2018).
https://doi.org/10.1137​16M1080173

[50] Yoel Drori and Ohad Shamir. “The complexity of finding stationary points with stochastic gradient descent”. In International Conference on Machine Learning. Pages 2658–2667. PMLR (2020). url: https:/​/​proceedings.mlr.press/​v119/​drori20a.html.
https:/​/​proceedings.mlr.press/​v119/​drori20a.html

[51] Cong Fang, Zhouchen Lin, and Tong Zhang. “Sharp analysis for nonconvex SGD escaping from saddle points”. In Conference on Learning Theory. Pages 1192–1234. PMLR (2019). url: https:/​/​proceedings.mlr.press/​v99/​fang19a.html.
https:/​/​proceedings.mlr.press/​v99/​fang19a.html

[52] S Reddi, Manzil Zaheer, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. “Adaptive methods for nonconvex optimization”. In Proceedings of 32nd Conference on Neural Information Processing Systems (NIPS 2018). (2018). url: https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​90365351ccc7437a1309dc64e4db32a3-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​90365351ccc7437a1309dc64e4db32a3-Paper.pdf

[53] Léon Bottou and Olivier Bousquet. “The tradeoffs of large scale learning”. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems. Volume 20. Curran Associates, Inc. (2007). url: https:/​/​proceedings.neurips.cc/​paper/​2007/​file/​0d3180d672e08b4c5312dcdafdf6ef36-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2007/​file/​0d3180d672e08b4c5312dcdafdf6ef36-Paper.pdf

[54] Peter J Karalekas, Nikolas A Tezak, Eric C Peterson, Colm A Ryan, Marcus P da Silva, and Robert S Smith. “A quantum-classical cloud platform optimized for variational hybrid algorithms”. Quantum Science and Technology 5, 024003 (2020).
https://doi.org/10.1088/​2058-9565/​ab7559

[55] H-J Briegel, Tommaso Calarco, Dieter Jaksch, Juan Ignacio Cirac, and Peter Zoller. “Quantum computing with neutral atoms”. Journal of modern optics 47, 415–451 (2000).
https://doi.org/10.1080/​09500340008244052

[56] เซอร์เกย์ บราวี, เจย์ เอ็ม แกมเบ็ตตา, อันโตนิโอ เมซซากาโป และคริสตัน เทมเม “การลดลงของ qubits เพื่อจำลอง Hamiltonians fermionic” (2017) arXiv:1701.08213.
arXiv: 1701.08213

[57] MD SAJID ANIS, Héctor Abraham, AduOffei, Rochisha Agarwal, Gabriele Agliardi, Merav Aharoni, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, Thomas Alexander, Matthew Amy, Sashwat Anagolum, Eli Arbel, Abraham Asfaw, Anish Athalye, Artur Avkhadiev, et al. “Qiskit: An open-source framework for quantum computing” (2021).

[58] Ciyou Zhu, Richard H Byrd, Peihuang Lu, and Jorge Nocedal. “Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization”. ACM Transactions on Mathematical Software (TOMS) 23, 550–560 (1997).
https://doi.org/10.1145/​279232.279236

[59] Raghu Bollapragada, Richard Byrd, and Jorge Nocedal. “Adaptive sampling strategies for stochastic optimization”. SIAM Journal on Optimization 28, 3312–3343 (2018).
https://doi.org/10.1137​17M1154679

[60] Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi, and Ping Tak Peter Tang. “A progressive batching L-BFGS method for machine learning”. In International Conference on Machine Learning. Pages 620–629. PMLR (2018). url: https:/​/​proceedings.mlr.press/​v80/​bollapragada18a.html.
https:/​/​proceedings.mlr.press/​v80/​bollapragada18a.html

[61] Raghu Pasupathy, Peter Glynn, Soumyadip Ghosh, and Fatemeh S Hashemi. “On sampling rates in simulation-based recursions”. SIAM Journal on Optimization 28, 45–73 (2018).
https://doi.org/10.1137/​140951679

[62] Andrew Arrasmith, Lukasz Cincio, Rolando D. Somma และ Patrick J Coles “การสุ่มตัวอย่างผู้ปฏิบัติงานสำหรับการเพิ่มประสิทธิภาพช็อตประหยัดในอัลกอริธึมแปรผัน” (2020) arXiv:2004.06252.
arXiv: 2004.06252

[63] Yangyang Xu and Wotao Yin. “Block stochastic gradient iteration for convex and nonconvex optimization”. SIAM Journal on Optimization 25, 1686–1716 (2015).
https://doi.org/10.1137/​140983938

อ้างโดย

[1] Matt Menickelly, Stefan M. Wild, and Miaolan Xie, “A Stochastic Quasi-Newton Method in the Absence of Common Random Numbers”, arXiv: 2302.09128, (2023).

[2] Kosuke Ito, “Latency-aware adaptive shot allocation for run-time efficient variational quantum algorithms”, arXiv: 2302.04422, (2023).

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

ไม่สามารถดึงข้อมูล Crossref อ้างโดย data ระหว่างความพยายามครั้งล่าสุด 2023-03-16 18:30:43 น.: ไม่สามารถดึงข้อมูลที่อ้างถึงสำหรับ 10.22331/q-2023-03-16-949 จาก Crossref นี่เป็นเรื่องปกติหาก DOI ได้รับการจดทะเบียนเมื่อเร็วๆ นี้

ประทับเวลา:

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