{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T16:21:33Z","timestamp":1778516493789,"version":"3.51.4"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T00:00:00Z","timestamp":1646352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000015","name":"Department of Energy","doi-asserted-by":"crossref","award":["DE-SC0017867"],"award-info":[{"award-number":["DE-SC0017867"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Quantum Algorithm Teams Program","award":["DE-AC02-05CH11231"],"award-info":[{"award-number":["DE-AC02-05CH11231"]}]},{"name":"Google Quantum Research Award"},{"name":"NSF Quantum Leap Challenge Institute (QLCI) program","award":["OMA-2016245"],"award-info":[{"award-number":["OMA-2016245"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>\n            We demonstrate that with an optimally tuned scheduling function, adiabatic quantum computing (AQC) can readily solve a quantum linear system problem (QLSP) with\n            <jats:italic>O<\/jats:italic>\n            (\u03ba poly(log (\u03ba \u03b5))) runtime, where \u03ba is the condition number, and \u03b5 is the target accuracy. This is near optimal with respect to both \u03ba and \u03b5, and is achieved without relying on complicated amplitude amplification procedures that are difficult to implement. Our method is applicable to general non-Hermitian matrices, and the cost as well as the number of qubits can be reduced when restricted to Hermitian matrices, and further to Hermitian positive definite matrices. The success of the time-optimal AQC implies that the quantum approximate optimization algorithm (QAOA) with an optimal control protocol can also achieve the same complexity in terms of the runtime. Numerical results indicate that QAOA can yield the lowest runtime compared to the time-optimal AQC, vanilla AQC, and the recently proposed randomization method.\n          <\/jats:p>","DOI":"10.1145\/3498331","type":"journal-article","created":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T09:54:52Z","timestamp":1646387692000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":86,"title":["Quantum Linear System Solver Based on Time-optimal Adiabatic Quantum Computing and Quantum Approximate Optimization Algorithm"],"prefix":"10.1145","volume":"3","author":[{"given":"Dong","family":"An","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of California, Berkeley, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lin","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Challenge Institute of Quantum Computation, University of California, Berkeley and Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,4]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.90.015002"},{"key":"e_1_3_2_3_2","first-page":"636","volume-title":"Proceedings of the STACS\u201912 (29th Symposium on Theoretical Aspects of Computer Science)","volume":"14","author":"Ambainis Andris","year":"2012","unstructured":"Andris Ambainis. 2012. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In Proceedings of the STACS\u201912 (29th Symposium on Theoretical Aspects of Computer Science). Vol. 14. LIPIcs, Paris, France, 636\u2013647."},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"062343","DOI":"10.1103\/PhysRevA.97.062343","article-title":"Optimal control of superconducting gmon qubits using pontryagin\u2019s minimum principle: Preparing a maximally entangled state with singular bang-bang protocols","volume":"97","author":"Bao Seraph","year":"2018","unstructured":"Seraph Bao, Silken Kleer, Ruoyu Wang, and Armin Rahmani. 2018. Optimal control of superconducting gmon qubits using pontryagin\u2019s minimum principle: Preparing a maximally entangled state with singular bang-bang protocols. Phys. Rev. A 97, 6 (2018), 062343.","journal-title":"Phys. Rev. A"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.114.090502"},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1109\/FOCS.2015.54","volume-title":"Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science","author":"Berry Dominic W.","year":"2015","unstructured":"Dominic W. Berry, Andrew M. Childs, and Robin Kothari. 2015. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, Piscataway, NJ, 792\u2013809."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/2011804.2011811"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.81.032308"},{"key":"e_1_3_2_9_2","unstructured":"Carlos Bravo-Prieto Ryan LaRose M. Cerezo Yigit Subasi Lukasz Cincio and Patrick J. Coles. 2020. Variational Quantum Linear Solver. arxiv:1909.05820. Retrieved from https:\/\/arxiv.org\/abs\/1909.05820."},{"issue":"3","key":"e_1_3_2_10_2","first-page":"031086","article-title":"Reinforcement learning in different phases of quantum control","volume":"8","author":"Bukov Marin","year":"2018","unstructured":"Marin Bukov, Alexandre G.R. Day, Dries Sels, Phillip Weinberg, Anatoli Polkovnikov, and Pankaj Mehta. 2018. Reinforcement learning in different phases of quantum control. Phys. Rev. X 8, 3 (2018), 031086.","journal-title":"Phys. Rev. X"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/15\/1\/013021"},{"key":"e_1_3_2_12_2","series-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)","first-page":"33:1\u201333:14","volume":"132","author":"Chakraborty Shantanav","year":"2019","unstructured":"Shantanav Chakraborty, Andr\u00e1s Gily\u00e9n, and Stacey Jeffery. 2019. The power of block-encoded matrix powers: Improved regression techniques via faster hamiltonian simulation. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 132). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 33:1\u201333:14."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1087072"},{"issue":"1","key":"e_1_3_2_14_2","doi-asserted-by":"crossref","first-page":"011020","DOI":"10.1103\/PhysRevX.11.011020","article-title":"Theory of trotter error with commutator scaling","volume":"11","author":"Childs Andrew M.","year":"2021","unstructured":"Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. 2021. Theory of trotter error with commutator scaling. Physical Review X 11, 1 (2021), 011020.","journal-title":"Physical Review X"},{"key":"e_1_3_2_15_2","unstructured":"Edward Farhi Jeffrey Goldstone and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. arXiv:1411.4028. Retrieved from https:\/\/arxiv.org\/abs\/1411.4028."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.116.080503"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316366"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"issue":"6","key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/s11128-019-2281-y","article-title":"How quantum is the speedup in adiabatic unstructured search?","volume":"18","author":"Hen Itay","year":"2019","unstructured":"Itay Hen. 2019. How quantum is the speedup in adiabatic unstructured search?Quant. Inf. Proc. 18, 6 (2019), 162.","journal-title":"Quant. Inf. Proc."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.2798382"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-11-11-361"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/1034004"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"e_1_3_2_24_2","unstructured":"Guang Hao Low and Nathan Wiebe. 2019. Hamiltonian Simulation in the Interaction Picture. arxiv:1805.00675. Retrieved from https:\/\/arxiv.org\/abs\/1805.00675."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.1564043"},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/BF02096616","article-title":"Linear adiabatic theory exponential estimates","volume":"152","author":"Nenciu Gheorghe","year":"1993","unstructured":"Gheorghe Nenciu. 1993. Linear adiabatic theory exponential estimates. Comm. Math. Phys. 152, 3 (1993), 479\u2013496.","journal-title":"Comm. Math. Phys."},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1038\/s41534-019-0141-3","article-title":"Universal quantum control through deep reinforcement learning","volume":"5","author":"Niu Murphy Yuezhen","year":"2019","unstructured":"Murphy Yuezhen Niu, Sergio Boixo, Vadim N. Smelyanskiy, and Hartmut Neven. 2019. Universal quantum control through deep reinforcement learning. npj Quantum Info. 5, 1 (2019), 33.","journal-title":"npj Quantum Info."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.080502"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.65.042308"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/829576"},{"key":"e_1_3_2_31_2","doi-asserted-by":"crossref","first-page":"060504","DOI":"10.1103\/PhysRevLett.122.060504","article-title":"Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing","volume":"122","author":"Suba\u015f\u0131 Yi\u011fit","year":"2019","unstructured":"Yi\u011fit Suba\u015f\u0131, Rolando D. Somma, and Davide Orsucci. 2019. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing. Phys. Rev. Lett. 122, 6 (2019), 060504.","journal-title":"Phys. Rev. Lett."},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1109\/SFCS.2001.959902","volume-title":"Proceedings 42nd IEEE Symposium on Foundations of Computer Science","author":"Dam Wim van","year":"2001","unstructured":"Wim van Dam, Michele Mosca, and Umesh Vazirani. 2001. How powerful is adiabatic quantum computation? In Proceedings 42nd IEEE Symposium on Foundations of Computer Science. IEEE, Piscataway, NJ, 279\u2013287."},{"key":"e_1_3_2_33_2","first-page":"1","article-title":"Improved error-scaling for adiabatic quantum evolutions","volume":"14","author":"Wiebe Nathan","year":"2012","unstructured":"Nathan Wiebe and Nathan S. Babcock. 2012. Improved error-scaling for adiabatic quantum evolutions. New J. Phys. 14, 1 (2012), 1\u201310.","journal-title":"New J. Phys."},{"issue":"5","key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"050502","DOI":"10.1103\/PhysRevLett.120.050502","article-title":"Quantum linear system algorithm for dense matrices","volume":"120","author":"Wossnig Leonard","year":"2018","unstructured":"Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash. 2018. Quantum linear system algorithm for dense matrices. Phys. Rev. Lett. 120, 5 (2018), 050502.","journal-title":"Phys. Rev. Lett."},{"key":"e_1_3_2_35_2","article-title":"Variational algorithms for linear algebra","author":"Xu Xiaosi","year":"2021","unstructured":"Xiaosi Xu, Jinzhao Sun, Suguru Endo, Ying Li, Simon C. Benjamin, and Xiao Yuan. 2021. Variational algorithms for linear algebra. Science Bulletin in press (2021).","journal-title":"Science Bulletin"},{"key":"e_1_3_2_36_2","first-page":"021027","article-title":"Optimizing variational quantum algorithms using pontryagin\u2019s minimum principle","volume":"7","author":"Yang Zhi-Cheng","year":"2017","unstructured":"Zhi-Cheng Yang, Armin Rahmani, Alireza Shabani, Hartmut Neven, and Claudio Chamon. 2017. Optimizing variational quantum algorithms using pontryagin\u2019s minimum principle. Phys. Rev. X 7, 2 (2017), 021027.","journal-title":"Phys. Rev. X"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.476575"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498331","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498331","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498331","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:05Z","timestamp":1750188605000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498331"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,4]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3498331"],"URL":"https:\/\/doi.org\/10.1145\/3498331","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,4]]},"assertion":[{"value":"2020-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}