1Centre for Quantum Software and Information, University of Technology Sydney, Sydney, Australia
2University of Chinese Academy of Sciences, Beijing, China
3Graduate School of Mathematics, Nagoya University, Nagoya, Japan
4Department of Computer Science and Technology, Tsinghua University, Beijing, China
5State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We study how parallelism can speed up quantum simulation. A parallel quantum algorithm is proposed for simulating the dynamics of a large class of Hamiltonians with good sparse structures, called uniform-structured Hamiltonians, including various Hamiltonians of practical interest like local Hamiltonians and Pauli sums. Given the oracle access to the target sparse Hamiltonian, in both query and gate complexity, the running time of our parallel quantum simulation algorithm measured by the quantum circuit depth has a doubly (poly-)logarithmic dependence $operatorname{polylog}log(1/epsilon)$ on the simulation precision $epsilon$. This presents an $textit{exponential improvement}$ over the dependence $operatorname{polylog}(1/epsilon)$ of previous optimal sparse Hamiltonian simulation algorithm without parallelism. To obtain this result, we introduce a novel notion of parallel quantum walk, based on Childs’ quantum walk. The target evolution unitary is approximated by a truncated Taylor series, which is obtained by combining these quantum walks in a parallel way. A lower bound $Omega(log log (1/epsilon))$ is established, showing that the $epsilon$-dependence of the gate depth achieved in this work cannot be significantly improved.
Our algorithm is applied to simulating three physical models: the Heisenberg model, the Sachdev-Ye-Kitaev model and a quantum chemistry model in second quantization. By explicitly calculating the gate complexity for implementing the oracles, we show that on all these models, the total gate depth of our algorithm has a $operatorname{polylog}log(1/epsilon)$ dependence in the parallel setting.
► BibTeX data
► References
[1] Richard P. Feynman. “Simulating physics with computers”. International Journal of Theoretical Physics 21, 467–488 (1982).
https://doi.org/10.1007/BF02650179
[2] Seth Lloyd. “Universal quantum simulators”. Science 273, 1073–1078 (1996).
https://doi.org/10.1126/science.273.5278.1073
[3] Andrew M. Childs, Robin Kothari, and Rolando D. Somma. “Quantum algorithm for systems of linear equations with exponentially improved dependence on precision”. SIAM Journal on Computing 46, 1920–1950 (2017).
https://doi.org/10.1137/16M1087072
[4] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. “Quantum SDP-solvers: Better upper and lower bounds”. Quantum 4, 230 (2020).
https://doi.org/10.22331/q-2020-02-14-230
[5] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A quantum approximate optimization algorithm” (2014). arXiv:1411.4028.
arXiv:1411.4028
[6] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. “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 ’19). Volume 132, pages 33:1–33:14. (2019).
https://doi.org/10.4230/LIPIcs.ICALP.2019.33
[7] Guang Hao Low and Isaac L. Chuang. “Hamiltonian simulation by qubitization”. Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163
[8] Andrew M. Childs. “On the relationship between continuous- and discrete-time quantum walk”. Communications in Mathematical Physics 294, 581–603 (2009).
https://doi.org/10.1007/s00220-009-0930-1
[9] Dominic W. Berry and Andrew M. Childs. “Black-box Hamiltonian simulation and unitary implementation”. Quantum Information & Computation 12, 29–62 (2012).
https://doi.org/10.26421/QIC12.1-2-4
[10] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. “Hamiltonian simulation with nearly optimal dependence on all parameters”. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’15). Pages 792–809. (2015).
https://doi.org/10.1109/FOCS.2015.54
[11] Lucas Lamata, Adrian Parra-Rodriguez, Mikel Sanz, and Enrique Solano. “Digital-analog quantum simulations with superconducting circuits”. Advances in Physics: X 3, 1457981 (2018).
https://doi.org/10.1080/23746149.2018.1457981
[12] Dorit Aharonov and Amnon Ta-Shma. “Adiabatic quantum state generation”. SIAM Journal on Computing 37, 47–82 (2007).
https://doi.org/10.1137/060648829
[13] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. “Efficient quantum algorithms for simulating sparse Hamiltonians”. Communications in Mathematical Physics 270, 359–371 (2006).
https://doi.org/10.1007/s00220-006-0150-x
[14] Nathan Wiebe, Dominic W. Berry, Peter Høyer, and Barry C. Sanders. “Higher order decompositions of ordered operator exponentials”. Journal of Physics A: Mathematical and Theoretical 43, 065203 (2010).
https://doi.org/10.1088/1751-8113/43/6/065203
[15] Andrew M. Childs and Robin Kothari. “Simulating sparse Hamiltonians with star decompositions”. In Theory of Quantum Computation, Communication, and Cryptography (TQC ’10). Pages 94–103. Springer Berlin Heidelberg (2011).
https://doi.org/10.1007/978-3-642-18073-6_8
[16] Andrew M. Childs and Nathan Wiebe. “Hamiltonian simulation using linear combinations of unitary operations”. Quantum Information & Computation 12, 901–924 (2012).
https://doi.org/10.26421/QIC12.11-12-1
[17] Guang Hao Low, Vadym Kliuchnikov, and Nathan Wiebe. “Well-conditioned multiproduct Hamiltonian simulation” (2019). arXiv:1907.11679.
arXiv:1907.11679
[18] Andrew M. Childs and Yuan Su. “Nearly optimal lattice simulation by product formulas”. Physical Review Letters 123, 050503 (2019).
https://doi.org/10.1103/PhysRevLett.123.050503
[19] Earl Campbell. “Random compiler for fast Hamiltonian simulation”. Physical Review Letters 123, 070503 (2019).
https://doi.org/10.1103/PhysRevLett.123.070503
[20] Andrew M. Childs, Aaron Ostrander, and Yuan Su. “Faster quantum simulation by randomization”. Quantum 3, 182 (2019).
https://doi.org/10.22331/q-2019-09-02-182
[21] Yingkai Ouyang, David R. White, and Earl T. Campbell. “Compilation by stochastic Hamiltonian sparsification”. Quantum 4, 235 (2020).
https://doi.org/10.22331/q-2020-02-27-235
[22] Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng, and Joel A. Tropp. “Concentration for random product formulas”. PRX Quantum 2, 040305 (2021).
https://doi.org/10.1103/PRXQuantum.2.040305
[23] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell. “Nearly tight Trotterization of interacting electrons”. Quantum 5, 495 (2021).
https://doi.org/10.22331/q-2021-07-05-495
[24] Paul K. Faehrmann, Mark Steudtner, Richard Kueng, Mária Kieferová, and Jens Eisert. “Randomizing multi-product formulas for improved Hamiltonian simulation”. Quantum 6, 806 (2022).
https://doi.org/10.22331/q-2022-09-19-806
[25] Matthew Hagan and Nathan Wiebe. “Composite quantum simulations”. Quantum 7, 1181 (2023).
https://doi.org/10.22331/q-2023-11-14-1181
[26] Chien Hung Cho, Dominic W. Berry, and Min-Hsiu Hsieh. “Doubling the order of approximation via the randomized product formula” (2022). arXiv:2210.11281.
arXiv:2210.11281
[27] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran. “Complexity of implementing Trotter steps”. PRX Quantum 4, 020323 (2023).
https://doi.org/10.1103/PRXQuantum.4.020323
[28] Pei Zeng, Jinzhao Sun, Liang Jiang, and Qi Zhao. “Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations” (2022). arXiv:2212.04566.
arXiv:2212.04566
[29] Gumaro Rendon, Jacob Watkins, and Nathan Wiebe. “Improved error scaling for Trotter simulations through extrapolation” (2022). arXiv:2212.14144.
arXiv:2212.14144
[30] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. “Simulating Hamiltonian dynamics with a truncated Taylor series”. Physical Review Letters 114, 090502 (2015).
https://doi.org/10.1103/PhysRevLett.114.090502
[31] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. “Exponential improvement in precision for simulating sparse Hamiltonians”. In Proceedings of the 46th Annual ACM SIGACT Symposium on Theory of Computing (STOC ’14). Pages 283–292. (2014).
https://doi.org/10.1145/2591796.2591854
[32] Robin Kothari. “Efficient algorithms in quantum query complexity”. PhD thesis. University of Waterloo. (2014). url: http://hdl.handle.net/10012/8625.
http://hdl.handle.net/10012/8625
[33] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. “Quantum algorithm for linear systems of equations”. Physical Review Letters 103, 150502 (2009).
https://doi.org/10.1103/PhysRevLett.103.150502
[34] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. “Methodology of resonant equiangular composite quantum gates”. Physical Review X 6, 041067 (2016).
https://doi.org/10.1103/PhysRevX.6.041067
[35] Guang Hao Low and Isaac L. Chuang. “Optimal Hamiltonian simulation by quantum signal processing”. Physical Review Letters 118, 010501 (2017).
https://doi.org/10.1103/PhysRevLett.118.010501
[36] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. “Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics”. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC ’19). Page 193–204. (2019).
https://doi.org/10.1145/3313276.3316366
[37] Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low. “Quantum algorithm for simulating real time evolution of lattice Hamiltonians”. SIAM Journal on Computing 0, FOCS18–250–FOCS18–284 (2018).
https://doi.org/10.1137/18M1231511
[38] Guang Hao Low and Nathan Wiebe. “Hamiltonian simulation in the interaction picture” (2019). arXiv:1805.00675.
arXiv:1805.00675
[39] Guang Hao Low. “Hamiltonian simulation with nearly optimal dependence on spectral norm”. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC ’19). Pages 491–502. (2019).
https://doi.org/10.1145/3313276.3316386
[40] John M. Martyn, Yuan Liu, Zachary E. Chin, and Isaac L. Chuang. “Efficient fully-coherent quantum signal processing algorithms for real-time dynamics simulation”. The Journal of Chemical Physics 158, 024106 (2023).
https://doi.org/10.1063/5.0124385
[41] Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs. “Hamiltonian simulation with random inputs”. Physical Review Letters 129, 270502 (2022).
https://doi.org/10.1103/PhysRevLett.129.270502
[42] Richard Cleve and John Watrous. “Fast parallel circuits for the quantum Fourier transform”. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS ’00). Pages 526–536. (2000).
https://doi.org/10.1109/SFCS.2000.892140
[43] Peter W. Shor. “Algorithms for quantum computation: discrete logarithms and factoring”. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’94). Pages 124–134. (1994).
https://doi.org/10.1109/SFCS.1994.365700
[44] Paul Pham and Krysta M. Svore. “A 2D nearest-neighbor quantum architecture for factoring in polylogarithmic depth”. Quantum Information & Computation 13, 937–962 (2013).
https://doi.org/10.26421/QIC13.11-12-3
[45] Martin Rötteler and Rainer Steinwandt. “A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth ${O}(log^2 n)$”. Quantum Information & Computation 14, 888–900 (2014).
https://doi.org/10.26421/QIC14.9-10-11
[46] Lov K. Grover. “A fast quantum mechanical algorithm for database search”. In Proceedings of the 28th Annual ACM SIGACT Symposium on Theory of Computing (STOC ’96). Pages 212–219. (1996).
https://doi.org/10.1145/237814.237866
[47] Christof Zalka. “Grover’s quantum searching algorithm is optimal”. Physical Review A 60, 2746–2751 (1999).
https://doi.org/10.1103/PhysRevA.60.2746
[48] Robert M. Gingrich, Colin P. Williams, and Nicolas J. Cerf. “Generalized quantum search with parallelism”. Physical Review A 61, 052313 (2000).
https://doi.org/10.1103/PhysRevA.61.052313
[49] Lov K. Grover and Jaikumar Radhakrishnan. “Quantum search for multiple items using parallel queries” (2004). arXiv:quant-ph/0407217.
arXiv:quant-ph/0407217
[50] Stacey Jeffery, Frédéric Magniez, and Ronald de Wolf. “Optimal parallel quantum query algorithms”. Algorithmica 79, 509–529 (2017).
https://doi.org/10.1007/s00453-016-0206-z
[51] Paul Burchard. “Lower bounds for parallel quantum counting” (2019). arXiv:1910.04555.
arXiv:1910.04555
[52] Tudor Giurgica-Tiron, Iordanis Kerenidis, Farrokh Labib, Anupam Prakash, and William Zeng. “Low depth algorithms for quantum amplitude estimation”. Quantum 6, 745 (2022).
https://doi.org/10.22331/q-2022-06-27-745
[53] Frederic Green, Steven Homer, and Christopher Pollett. “On the complexity of quantum ACC”. In Proceedings 15th Annual IEEE Conference on Computational Complexity (CCC ’00). Pages 250–262. (2000).
https://doi.org/10.1109/CCC.2000.856756
[54] Cristopher Moore and Martin Nilsson. “Parallel quantum computation and quantum codes”. SIAM Journal on Computing 31, 799–815 (2002).
https://doi.org/10.1137/S0097539799355053
[55] Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett. “Counting, fanout and the complexity of quantum ACC”. Quantum Information & Computation 2, 35–65 (2002).
https://doi.org/10.26421/QIC2.1-3
[56] Barbara M. Terhal and David P. DiVincenzo. “Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games”. Quantum Information & Computation 4, 134–145 (2004).
https://doi.org/10.26421/QIC4.2-5
[57] Stephen Fenner, Frederic Green, Steven Homer, and Yong Zhang. “Bounds on the power of constant-depth quantum circuits”. In Proceedings of the 15th International Conference on Fundamentals of Computation Theory (FCT ’05). Pages 44–55. (2005).
https://doi.org/10.1007/11537311_5
[58] Peter Høyer and Robert Špalek. “Quantum fan-out is powerful”. Theory of Computing 1, 81–103 (2005).
https://doi.org/10.4086/toc.2005.v001a005
[59] Debajyoti Bera, Frederic Green, and Steven Homer. “Small depth quantum circuits”. SIGACT News 38, 35–50 (2007).
https://doi.org/10.1145/1272729.1272739
[60] Yasuhiro Takahashi and Seiichiro Tani. “Collapse of the hierarchy of constant-depth exact quantum circuits”. Computational Complexity 25, 849–881 (2016).
https://doi.org/10.1007/s00037-016-0140-0
[61] Matthew Coudron and Sanketh Menda. “Computations with greater quantum depth are strictly more powerful (relative to an oracle)”. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC ’20). Pages 889–901. (2020).
https://doi.org/10.1145/3357713.3384269
[62] Nai-Hui Chia, Kai-Min Chung, and Ching-Yi Lai. “On the need for large quantum depth”. Journal of the ACM 70 (2023).
https://doi.org/10.1145/3570637
[63] Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, and Jialin Zhang. “Optimal space-depth trade-off of CNOT circuits in quantum logic synthesis”. In Proceedings of the 31st Annual ACM SIAM Symposium on Discrete Algorithms (SODA ’20). Pages 213–229. (2020).
https://doi.org/10.1137/1.9781611975994.13
[64] Sergey Bravyi, David Gosset, and Robert König. “Quantum advantage with shallow circuits”. Science 362, 308–311 (2018).
https://doi.org/10.1126/science.aar3106
[65] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. “Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits”. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC ’19). Pages 515–526. (2019).
https://doi.org/10.1145/3313276.3316404
[66] François Le Gall. “Average-case quantum advantage with shallow circuits”. In Proceedings of the 34th Computational Complexity Conference (CCC ’19). Pages 1–20. (2019).
https://doi.org/10.4230/LIPIcs.CCC.2019.21
[67] Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel. “Quantum advantage with noisy shallow circuits”. Nature Physics 16, 1040–1045 (2020).
https://doi.org/10.1038/s41567-020-0948-z
[68] Yihui Quek, Mark M. Wilde, and Eneet Kaur. “Multivariate trace estimation in constant quantum depth” Quantum, 8 (2024).
https://doi.org/10.22331/q-2024-01-10-1220
[69] Richard Jozsa. “An introduction to measurement based quantum computation” (2005). arXiv:quant-ph/0508124.
arXiv:quant-ph/0508124
[70] Anne Broadbent and Elham Kashefi. “Parallelizing quantum circuits”. Theoretical Computer Science 410, 2489–2510 (2009).
https://doi.org/10.1016/j.tcs.2008.12.046
[71] Dan Browne, Elham Kashefi, and Simon Perdrix. “Computational depth complexity of measurement-based quantum computation”. In Theory of Quantum Computation, Communication, and Cryptography (TQC ’10). Volume 6519, pages 35–46. (2011).
https://doi.org/10.1007/978-3-642-18073-6_4
[72] Robert Beals, Stephen Brierley, Oliver Gray, Aram W. Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, and Mark Stather. “Efficient distributed quantum computing”. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 469, 20120686 (2013).
https://doi.org/10.1098/rspa.2012.0686
[73] Mingsheng Ying and Yuan Feng. “An algebraic language for distributed quantum computing”. IEEE Transactions on Computers 58, 728–743 (2009).
https://doi.org/10.1109/TC.2009.13
[74] Mingsheng Ying, Li Zhou, and Yangjia Li. “Reasoning about parallel quantum programs” (2019). arXiv:1810.11334.
arXiv:1810.11334
[75] Rahul Nandkishore and David A. Huse. “Many-body localization and thermalization in quantum statistical mechanics”. Annual Review of Condensed Matter Physics 6, 15–38 (2015).
https://doi.org/10.1146/annurev-conmatphys-031214-014726
[76] David J. Luitz, Nicolas Laflorencie, and Fabien Alet. “Many-body localization edge in the random-field Heisenberg chain”. Physical Review B 91, 081103 (2015).
https://doi.org/10.1103/PhysRevB.91.081103
[77] Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. “Toward the first quantum simulation with quantum speedup”. Proceedings of the National Academy of Sciences 115, 9456–9461 (2018).
https://doi.org/10.1073/pnas.1801723115
[78] Subir Sachdev and Jinwu Ye. “Gapless spin-fluid ground state in a random quantum Heisenberg magnet”. Physical Review Letters 70, 3339–3342 (1993).
https://doi.org/10.1103/PhysRevLett.70.3339
[79] Alexei Y. Kitaev. “A simple model of quantum holography”. Talks at KITP, April 7, 2015 and May 27, 2015.
[80] Juan Maldacena and Douglas Stanford. “Remarks on the Sachdev-Ye-Kitaev model”. Physical Review D 94, 106002 (2016).
https://doi.org/10.1103/PhysRevD.94.106002
[81] Laura García-Álvarez, Íñigo Luis Egusquiza, Lucas Lamata, Adolfo del Campo, Julian Sonner, and Enrique Solano. “Digital quantum simulation of minimal AdS/CFT”. Physical Review Letters 119, 040501 (2017).
https://doi.org/10.1103/PhysRevLett.119.040501
[82] Man-Hong Yung, James D. Whitfield, Sergio Boixo, David G. Tempel, and Alán Aspuru-Guzik. “Introduction to quantum algorithms for physics and chemistry”. In Advances in Chemical Physics. Pages 67–106. John Wiley & Sons, Inc. (2014).
https://doi.org/10.1002/9781118742631.ch03
[83] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. “Quantum algorithms for quantum chemistry and quantum materials science”. Chemical Reviews 120, 12685–12717 (2020).
https://doi.org/10.1021/acs.chemrev.9b00829
[84] Ryan Babbush, Dominic W. Berry, Ian D. Kivlichan, Annie Y. Wei, Peter J. Love, and Alán Aspuru-Guzik. “Exponentially more precise quantum simulation of fermions in second quantization”. New Journal of Physics 18, 033032 (2016).
https://doi.org/10.1088/1367-2630/18/3/033032
[85] Ryan Babbush, Dominic W. Berry, and Hartmut Neven. “Quantum simulation of the Sachdev-Ye-Kitaev model by asymmetric qubitization”. Physical Review A 99, 040301 (2019).
https://doi.org/10.1103/PhysRevA.99.040301
[86] Ryan Babbush, Dominic W. Berry, Yuval R. Sanders, Ian D. Kivlichan, Artur Scherer, Annie Y. Wei, Peter J. Love, and Alán Aspuru-Guzik. “Exponentially more precise quantum simulation of fermions in the configuration interaction representation”. Quantum Science and Technology 3, 015006 (2017).
https://doi.org/10.1088/2058-9565/aa9463
[87] Ryan Babbush, Nathan Wiebe, Jarrod McClean, James McClain, Hartmut Neven, and Garnet Kin-Lic Chan. “Low-depth quantum simulation of materials”. Physic Review X 8, 011044 (2018).
https://doi.org/10.1103/PhysRevX.8.011044
[88] Ian D. Kivlichan, Jarrod McClean, Nathan Wiebe, Craig Gidney, Alán Aspuru-Guzik, Garnet Kin-Lic Chan, and Ryan Babbush. “Quantum simulation of electronic structure with linear depth and connectivity”. Physical Review Letters 120, 110501 (2018).
https://doi.org/10.1103/PhysRevLett.120.110501
[89] Ryan Babbush, Dominic W. Berry, Jarrod R. McClean, and Hartmut Neven. “Quantum simulation of chemistry with sublinear scaling in basis size”. npj Quantum Information 5 (2019).
https://doi.org/10.1038/s41534-019-0199-y
[90] Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush. “Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization”. Quantum 3, 208 (2019).
https://doi.org/10.22331/q-2019-12-02-208
[91] Charles H. Bennett. “Logical reversibility of computation”. IBM Journal of Research and Development 17, 525–532 (1973).
https://doi.org/10.1147/rd.176.0525
[92] Michael A. Nielsen and Isaac L. Chuang. “Quantum computation and quantum information: 10th anniversary edition”. Cambridge University Press. (2010).
https://doi.org/10.1017/CBO9780511976667
[93] Lov K. Grover and Terry Rudolph. “Creating superpositions that correspond to efficiently integrable probability distributions” (2002). arXiv:quant-ph/0208112.
arXiv:quant-ph/0208112
[94] Yosi Atia and Dorit Aharonov. “Fast-forwarding of Hamiltonians and exponentially precise measurements”. Nature Communications 8 (2017).
https://doi.org/10.1038/s41467-017-01637-7
[95] Shouzhen Gu, Rolando D. Somma, and Burak Şahinoğlu. “Fast-forwarding quantum evolution”. Quantum 5, 577 (2021).
https://doi.org/10.22331/q-2021-11-15-577
[96] Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha. “Search via quantum walk”. SIAM Journal on Computing 40, 142–164 (2011).
https://doi.org/10.1137/090745854
[97] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. “Quantum state preparation with optimal circuit depth: implementations and applications”. Physical Review Letters 129, 230504 (2022).
https://doi.org/10.1103/PhysRevLett.129.230504
[98] Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. “Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis”. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 42, 3301–3314 (2023).
https://doi.org/10.1109/TCAD.2023.3244885
[99] Gregory Rosenthal. “Query and depth upper bounds for quantum unitaries via Grover search” (2021). arXiv:2111.07992.
arXiv:2111.07992
[100] Pei Yuan and Shengyu Zhang. “Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits”. Quantum 7, 956 (2023).
https://doi.org/10.22331/q-2023-03-20-956
[101] Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, and Yu-Ching Shen. “On the impossibility of general parallel fast-forwarding of Hamiltonian simulation”. In Proceedings of the Conference on Proceedings of the 38th Computational Complexity Conference (CCC ’23). Pages 1–45. (2023).
https://doi.org/10.4230/LIPIcs.CCC.2023.33
[102] Mihir Bellare and Phillip Rogaway. “Random oracles are practical: A paradigm for designing efficient protocols”. In Proceedings of the 1st ACM Conference on Computer and Communications Security (CCC ’93). Pages 62–73. (1993).
https://doi.org/10.1145/168588.168596
[103] Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. “Random oracles in a quantum world”. In Proceedings of the 17th International Conference on the Theory and Application of Cryptology and Information Security. Pages 41–69. (2011).
https://doi.org/10.1007/978-3-642-25385-0_3
[104] Seth Lloyd. “Coherent quantum feedback”. Physical Review A 62, 022108 (2000).
https://doi.org/10.1103/PhysRevA.62.022108
[105] John Gough and Matthew R. James. “The series product and its application to quantum feedforward and feedback networks”. IEEE Transactions on Automatic Control 54, 2530–2544 (2009).
https://doi.org/10.1109/TAC.2009.2031205
[106] Qisheng Wang, Riling Li, and Mingsheng Ying. “Equivalence checking of sequential quantum circuits”. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 41, 3143–3156 (2022).
https://doi.org/10.1109/TCAD.2021.3117506
[107] Bobak T. Kiani, Giacomo De Palma, Dirk Englund, William Kaminsky, Milad Marvian, and Seth Lloyd. “Quantum advantage for differential equation analysis”. Physical Review A 105, 022415 (2022).
https://doi.org/10.1103/PhysRevA.105.022415
[108] Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, and Guoming Wang. “Quantum algorithm for linear differential equations with exponentially improved dependence on precision”. Communications in Mathematical Physics 365, 1057–1081 (2017).
https://doi.org/10.1007/s00220-017-3002-y
[109] Mária Kieferová, Artur Scherer, and Dominic W. Berry. “Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series”. Physical Review A 99, 042314 (2019).
https://doi.org/10.1103/PhysRevA.99.042314
[110] Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, and Nathan Wiebe. “Time-dependent Hamiltonian simulation with ${L}^{1}$-norm scaling”. Quantum 4, 254 (2020).
https://doi.org/10.22331/q-2020-04-20-254
[111] Yi-Hsiang Chen, Amir Kalev, and Itay Hen. “Quantum algorithm for time-dependent Hamiltonian simulation by permutation expansion”. PRX Quantum 2, 030342 (2021).
https://doi.org/10.1103/PRXQuantum.2.030342
[112] András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe. “Optimizing quantum optimization algorithms via faster quantum gradient computation”. In Proceedings of the 30th Annual ACM SIAM Symposium on Discrete Algorithms (SODA ’19). Pages 1425–1444. (2019).
https://doi.org/10.1137/1.9781611975482.87
[113] Iordanis Kerenidis and Anupam Prakash. “A quantum interior point method for LPs and SDPs”. ACM Transactions on Quantum Computing 1, 1–32 (2020).
https://doi.org/10.1145/3406306
[114] John H. Reif. “Logarithmic depth circuits for algebraic functions”. SIAM Journal on Computing 15, 231–242 (1986).
https://doi.org/10.1137/0215017
[115] Mario Szegedy. “Quantum speed-up of Markov chain based algorithms”. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’04). Pages 32–41. (2004).
https://doi.org/10.1109/FOCS.2004.53
[116] Rolando D. Somma, Gerardo Ortiz, James E. Gubernatis, Emanuel Knill, and Raymond Laflamme. “Simulating physical phenomena by quantum networks”. Physical Review A 65, 042323 (2002).
https://doi.org/10.1103/PhysRevA.65.042323
[117] Iordanis Kerenidis and Anupam Prakash. “Quantum recommendation systems”. In 8th Innovations in Theoretical Computer Science Conference (ITCS ’17). Volume 67, pages 49:1–49:21. (2017).
https://doi.org/10.4230/LIPIcs.ITCS.2017.49
[118] Dmitry A. Abanin and Zlatko Papić. “Recent progress in many-body localization”. Annalen der Physik 529, 1700169 (2017).
https://doi.org/10.1002/andp.201700169
[119] Fabien Alet and Nicolas Laflorencie. “Many-body localization: An introduction and selected topics”. Comptes Rendus Physique 19, 498–525 (2018).
https://doi.org/10.1016/j.crhy.2018.03.003
[120] Philip W. Anderson. “Absence of diffusion in certain random lattices”. Physical Review 109, 1492–1505 (1958).
https://doi.org/10.1103/PhysRev.109.1492
[121] Dmitry A. Abanin, Ehud Altman, Immanuel Bloch, and Maksym Serbyn. “Colloquium: Many-body localization, thermalization, and entanglement”. Reviews of Modern Physics 91, 021001 (2019).
https://doi.org/10.1103/RevModPhys.91.021001
[122] Joseph Polchinski and Vladimir Rosenhaus. “The spectrum in the Sachdev-Ye-Kitaev model”. Journal of High Energy Physics 2016, 1–25 (2016).
https://doi.org/10.1007/JHEP04(2016)001
[123] Vladimir Rosenhaus. “An introduction to the SYK model”. Journal of Physics A: Mathematical and Theoretical 52, 323001 (2019).
https://doi.org/10.1088/1751-8121/ab2ce1
[124] George E. P. Box and Mervin E. Muller. “A note on the generation of random normal deviates”. The Annals of Mathematical Statistics 29, 610–611 (1958).
https://doi.org/10.1214/aoms/1177706645
[125] Shenglong Xu, Leonard Susskind, Yuan Su, and Brian Swingle. “A sparse model of quantum holography” (2020). arXiv:2008.02303.
arXiv:2008.02303
[126] Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, Sukin Sim, Libor Veis, and Alán Aspuru-Guzik. “Quantum chemistry in the age of quantum computing”. Chemical Reviews 119, 10856–10915 (2019).
https://doi.org/10.1021/acs.chemrev.8b00803
[127] 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 (2014).
https://doi.org/10.1038/ncomms5213
[128] Google AI Quantum and Collaborators, Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, et al. “Hartree-Fock on a superconducting qubit quantum computer”. Science 369, 1084–1089 (2020).
https://doi.org/10.1126/science.abb9811
Cited by
[1] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan, “Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications”, Physical Review Letters 129 23, 230504 (2022).
[2] Kouhei Nakaji, Shumpei Uno, Yohichi Suzuki, Rudy Raymond, Tamiya Onodera, Tomoki Tanaka, Hiroyuki Tezuka, Naoki Mitsuda, and Naoki Yamamoto, “Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicators”, Physical Review Research 4 2, 023136 (2022).
[3] Pei Yuan and Shengyu Zhang, “Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits”, Quantum 7, 956 (2023).
[4] John M. Martyn, Yuan Liu, Zachary E. Chin, and Isaac L. Chuang, “Efficient Fully-Coherent Quantum Signal Processing Algorithms for Real-Time Dynamics Simulation”, arXiv:2110.11327, (2021).
[5] Qisheng Wang and Zhicheng Zhang, “Fast Quantum Algorithms for Trace Distance Estimation”, arXiv:2301.06783, (2023).
[6] Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, and Yu-Ching Shen, “On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation”, arXiv:2305.12444, (2023).
[7] Xiao-Ming Zhang and Xiao Yuan, “On circuit complexity of quantum access models for encoding classical data”, arXiv:2311.11365, (2023).
[8] Gregory Boyd, “Low-Overhead Parallelisation of LCU via Commuting Operators”, arXiv:2312.00696, (2023).
The above citations are from SAO/NASA ADS (last updated successfully 2024-01-20 23:46:27). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref’s cited-by service no data on citing works was found (last attempt 2024-01-20 23:46:26).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
- Source: https://quantum-journal.org/papers/q-2024-01-15-1228/
