📄 Quantum algorithms: A survey of applications and end-to-end complexities

Paper · 2023 · Alexander M. Dalzell, Sam McArdle, Mario Berta et al.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

🏛️ Institutions

🎓University of California, BerkeleyBerkeley · United States243 works · 251,774 citations🎓University of CopenhagenCopenhagen · Denmark117 works · 15,348 citations🏢AmazonSeattle · United States131 works · 41,785 citations🎓Yale UniversityNew Haven · United States112 works · 14,009 citations🎓RWTH Aachen UniversityAachen · Germany25 works · 5,119 citations🎓California Institute of TechnologyPasadena · United States16 works · 1,291 citations🔬National Institute of Standards and TechnologyGaithersburg · United States5 works · 492 citations🔬HUN-REN Alfréd Rényi Institute of MathematicsBudapest · Hungary2 works · 77 citations

Also on the byline: Hungarian Research Network.

🧭 Fields, topics and concepts

Cite

Cite as Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, Andras Gilyen, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang and Fernando G. S. L. Brandao. 2023. Quantum algorithms: A survey of applications and end-to-end complexities. arXiv:2310.03011.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1017/9781009639651 · arXiv 2310.03011

@misc{dalzell2023quantum,
  title = {{Quantum algorithms: A survey of applications and end-to-end complexities}},
  author = {Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, Andras Gilyen, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang and Fernando G. S. L. Brandao},
  year = {2023},
  doi = {10.1017/9781009639651},
  eprint = {2310.03011},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1017/9781009639651}
}

References

375 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. [1] Gharibian, S. Quantum complexity theory. https://groups.uni-paderborn.de/fg-qi/data/QCT_Maste rfile.pdf, accessed: 2024-11-19. (2024). ↗
2. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Consolidated bibliography Aaronson, S. “Read the fine print.” Nat. Phys. 11 (2015), 291–293 (cited on page 271). find
3. Aaronson, S. “Shadow tomography of quantum states.” In: STOC (2018), 325–338. arXiv:1711.01053 (cited on pages 307, 308). — [arXiv:1711.01053](https://arxiv.org/abs/1711.01053) find
4. Aaronson, S. “Open problems related to quantum query complexity.” ACM Trans. Quantum Comput. 2 (2021). arXiv:2109.06917 (cited on page 279). — [arXiv:2109.06917](https://arxiv.org/abs/2109.06917) find
5. Aaronson, S., Chen, X., Hazan, E., Kale, S., and Nayak, A. “Online learning of quantum states.” J. Stat. Mech. Theory Exp. 2019 (2019), 124019. arXiv:1802.09025 (cited on page 307). — [arXiv:1802.09025](https://arxiv.org/abs/1802.09025) find
6. Aaronson, S. and Gottesman, D. “Improved simulation of stabilizer circuits.” Phys. Rev. A 70 (2004), 052328. arXiv:quant-ph/0406196 (cited on page 340). — [arXiv:quant-ph/0406196](https://arxiv.org/abs/quant-ph/0406196) find
7. Abbas, A., Ambainis, A., Augustino, B., et al. “Challenges and opportunities in quantum optimization.” Nat. Rev. Phys. 6 (2024), 718–735. arXiv:2312.02279 (cited on pages 72, 89). — [arXiv:2312.02279](https://arxiv.org/abs/2312.02279) find
8. Adachi, S. H. and Henderson, M. P. “Application of quantum annealing to training of deep neural networks.” arXiv:1510.06356 (2015) (cited on page 174). — [arXiv:1510.06356](https://arxiv.org/abs/1510.06356) find
9. Aggarwal, D., Brennen, G., Lee, T., Santha, M., and Tomamichel, M. “Quantum attacks on bitcoin, and how to protect against them.” Ledger 3 (2018). arXiv:1710.10377 (cited on pages 116, 121). — [arXiv:1710.10377](https://arxiv.org/abs/1710.10377) find
10. Agrawal, A. A., Wilson, T. L., Saadatmand, S., Hodson, M. J., Mutus, J. Y., Caesura, A., Johnson, P. D., and Kemper, A. F. “Quantifying fault tolerant simulation of strongly correlated systems using the Fermi–Hubbard model.” arXiv:2406.06511 (2024) (cited on page 15). — [arXiv:2406.06511](https://arxiv.org/abs/2406.06511) find
11. Aharonov, D. and Ben-Or, M. “Fault-tolerant quantum computation with constant error rate.” SIAM J. Comp. 38 (2008), 1207–1282. Earlier version in STOC’97 . arXiv:quant-ph/9906129 (cited on page 329). — [arXiv:quant-ph/9906129](https://arxiv.org/abs/quant-ph/9906129) find
12. Aharonov, D., Ben-Or, M., Impagliazzo, R., and Nisan, N. “Limitations of noisy reversible computation.” arXiv:quant-ph/9611028 (1996) (cited on page 298). — [arXiv:quant-ph/9611028](https://arxiv.org/abs/quant-ph/9611028) find
13. Aharonov, D. and Ta-Shma, A. “Adiabatic quantum state generation.” SIAM J. Comp. 37 (2007), 47–82. Earlier version in STOC’03 . arXiv:quant-ph/0301023 (cited on pages 224, 225). — [arXiv:quant-ph/0301023](https://arxiv.org/abs/quant-ph/0301023) find
14. Akhalwaya, I. Y., Connolly, A., Guichard, R., Herbert, S., Kargi, C., Krajenbrink, A., Lubasch, M., Keever, C. M., Sorci, J., Spranger, M., and Williams, I. “A modular engine for quantum Monte Carlo integration.” arXiv:2308.06081 (2023) (cited on page 153). — [arXiv:2308.06081](https://arxiv.org/abs/2308.06081) find
15. Akhalwaya, I. Y., Ubaru, S., Clarkson, K. L., Squillante, M. S., Jejjala, V., He, Y.-H., Naidoo, K., Kalantzis, V., and Horesh, L. “Exponential advantage on noisy quantum computers.” arXiv:2209.09371 (2022) (cited on page 185). — [arXiv:2209.09371](https://arxiv.org/abs/2209.09371) find
16. Alagic, G., Apon, D., Cooper, D., et al. Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. Tech. rep. NISTIR 8413. National Institute of Standards and Technology (2022) (cited on page 114). find
17. Albash, T. and Lidar, D. A. “Adiabatic quantum computation.” Rev. Mod. Phys. 90 (2018), 015002. arXiv:1611.04471 (cited on pages 82, 86, 265–267). — [arXiv:1611.04471](https://arxiv.org/abs/1611.04471) find
18. Alexis, M., Lin, L., Mnatsakanyan, G., Thiele, C., and Wang, J. “Infinite quantum signal processing for arbitrary Szegő functions.” arXiv:2407.05634 (2024) (cited on pages 209, 218). — [arXiv:2407.05634](https://arxiv.org/abs/2407.05634) find
19. Alexis, M., Mnatsakanyan, G., and Thiele, C. “Quantum signal processing and nonlinear Fourier analysis.” Rev. Mat. Complut. 37 (2024), 655–694. arXiv:2310.12683 (cited on pages 209, 218). — [arXiv:2310.12683](https://arxiv.org/abs/2310.12683) find
20. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Aliferis, P., Gottesman, D., and Preskill, J. “Quantum accuracy threshold for concatenated distance-3 codes.” Quantum Inf. Comput. 6 (2006), 97–165. arXiv:quant-ph/0504218 (cited on pages 328–331). — [arXiv:quant-ph/0504218](https://arxiv.org/abs/quant-ph/0504218) find
21. Aliferis, P., Gottesman, D., and Preskill, J. “Accuracy threshold for postselected quantum computation.” Quantum Inf. Comput. 8 (2008), 181–244. arXiv:quant-ph/0703264 (cited on page 330). — [arXiv:quant-ph/0703264](https://arxiv.org/abs/quant-ph/0703264) find
22. Altaisky, M. “Quantum neural network.” arXiv:quant-ph/0107012 (2001) (cited on page 300). — [arXiv:quant-ph/0107012](https://arxiv.org/abs/quant-ph/0107012) find
23. Altshuler, B., Krovi, H., and Roland, J. “Anderson localization makes adiabatic quantum optimization fail.” Proc. Natl. Acad. Sci. 107 (2010), 12446–12450. arXiv:0912.0746 (cited on pages 83, 267). — [arXiv:0912.0746](https://arxiv.org/abs/0912.0746) find
24. Ambainis, A. “Quantum walk algorithm for element distinctness.” SIAM J. Comp. 37 (2007), 210–239. Earlier version in FOCS’04 . arXiv:quant-ph/0311001 (cited on page 77). — [arXiv:quant-ph/0311001](https://arxiv.org/abs/quant-ph/0311001) find
25. Ambainis, A. “Quantum search algorithms.” SIGACT News 35 (2004), 22–35. arXiv:quant-ph/0504012 (cited on page 74). — [arXiv:quant-ph/0504012](https://arxiv.org/abs/quant-ph/0504012) find
26. Ambainis, A. “Variable time amplitude amplification and quantum algorithms for linear algebra problems.” In: STACS (2012), 636–647. arXiv:1010.4458 (cited on pages 127, 288). — [arXiv:1010.4458](https://arxiv.org/abs/1010.4458) find
27. Ambainis, A., Balodis, K., Iraids, J., Kokainis, M., Prūsis, K., and Vihrovs, J. “Quantum speedups for exponential-time dynamic programming algorithms.” In: SODA (2019), 1783–1793. arXiv:1807.05209 (cited on pages 77, 273). — [arXiv:1807.05209](https://arxiv.org/abs/1807.05209) find
28. Ambainis, A. and Kokainis, M. “Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games.” In: STOC (2017), 989–1002. arXiv:1704.06774 (cited on page 77). — [arXiv:1704.06774](https://arxiv.org/abs/1704.06774) find
29. Ambainis, A., Kokainis, M., and Vihrovs, J. “Improved algorithm and lower bound for variable time quantum search.” arXiv:2302.06749 (2023) (cited on page 288). — [arXiv:2302.06749](https://arxiv.org/abs/2302.06749) find
30. Amin, M. H., Andriyash, E., Rolfe, J., Kulchytskyy, B., and Melko, R. “Quantum Boltzmann machine.” Phys. Rev. X 8 (2018), 021050. arXiv:1601.02036 (cited on pages 172, 175, 263). — [arXiv:1601.02036](https://arxiv.org/abs/1601.02036) find
31. An, D., Childs, A. M., and Lin, L. “Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters.” arXiv:2312.03916 (2023) (cited on pages 127, 129). — [arXiv:2312.03916](https://arxiv.org/abs/2312.03916) find
32. An, D., Fang, D., and Lin, L. “Time-dependent unbounded Hamiltonian simulation with vector norm scaling.” Quantum 5 (2021), 459. arXiv:2012.13105 (cited on page 224). — [arXiv:2012.13105](https://arxiv.org/abs/2012.13105) find
33. An, D. and Lin, L. “Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm.” ACM Trans. Quantum Comput. 3 (2022). arXiv:1909.05500 (cited on pages 127, 267, 288, 290). — [arXiv:1909.05500](https://arxiv.org/abs/1909.05500) find
34. An, D., Linden, N., Liu, J.-P., Montanaro, A., Shao, C., and Wang, J. “Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance.” Quantum 5 (2021), 481. arXiv:2012.06283 (cited on pages 123, 154). — [arXiv:2012.06283](https://arxiv.org/abs/2012.06283) find
35. An, D., Liu, J.-P., Wang, D., and Zhao, Q. “A theory of quantum differential equation solvers: Limitations and fast-forwarding.” arXiv:2211.05246 (2022) (cited on page 129). — [arXiv:2211.05246](https://arxiv.org/abs/2211.05246) find
36. An, D., Liu, J.-P., and Lin, L. “Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost.” Phys. Rev. Lett. 131 (2023), 150603. arXiv:2303.01029 (cited on page 127). — [arXiv:2303.01029](https://arxiv.org/abs/2303.01029) find
37. An, D. and Trivisa, K. “Quantum algorithms for linear and non-linear fractional reaction–diffusion equations.” arXiv:2310.18900 (2023) (cited on page 131). — [arXiv:2310.18900](https://arxiv.org/abs/2310.18900) find
38. Andersen, E. D. and Andersen, K. D. “The Mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm.” In: High Performance Optimization (2000), 197–232 (cited on pages 98, 310). find
39. Anschuetz, E., Olson, J., Aspuru-Guzik, A., and Cao, Y. “Variational quantum factoring.” In: Quantum Technology and Optimization Problems (2019), 74–85. arXiv:1808.08927 (cited on pages 115, 300). — [arXiv:1808.08927](https://arxiv.org/abs/1808.08927) find
40. Anschuetz, E. R. and Cao, Y. “Realizing quantum Boltzmann machines through eigenstate thermalization.” arXiv:1903.01359 (2019) (cited on page 172). — [arXiv:1903.01359](https://arxiv.org/abs/1903.01359) find
41. Anschuetz, E. R. and Kiani, B. T. “Quantum variational algorithms are swamped with traps.” Nat. Commun. 13 (2022), 7760. arXiv:2205.05786 (cited on page 298). — [arXiv:2205.05786](https://arxiv.org/abs/2205.05786) find
42. Anwar, H., Brown, B. J., Campbell, E. T., and Browne, D. E. “Fast decoders for qudit topological codes.” New J. Phys. 16 (2014), 063038. arXiv:1311.4895 (cited on page 335). — [arXiv:1311.4895](https://arxiv.org/abs/1311.4895) find
43. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Aoki, H., Tsuji, N., Eckstein, M., Kollar, M., Oka, T., and Werner, P. “Nonequilibrium dynamical mean-field theory and its applications.” Rev. Mod. Phys. 86 (2014), 779–837. arXiv:1310.5329 (cited on… — [arXiv:1310.5329](https://arxiv.org/abs/1310.5329) find
44. Aoki, Y., Blum, T., Colangelo, G., Collins, S., Morte, M. D., Dimopoulos, P., Dürr, S., Feng, X., Fukaya, H., Golterman, M., et al. “FLAG review 2021.” Eur. Phys. J. C 82 (2022), 869. arXiv:2111.09849 (cited on page 60). van Apeldoorn, J., Cornelissen, A., Gilyén, A., and Nannicini, G. “Quantum to… — [arXiv:2111.09849](https://arxiv.org/abs/2111.09849) find
45. Apers, S., Gilyén, A., and Jeffery, S. “A unified framework of quantum walk search.” In: STACS (2021), 6:1–6:13. arXiv:1912.04233 (cited on page 252). — [arXiv:1912.04233](https://arxiv.org/abs/1912.04233) find
46. Apers, S. and Gribling, S. “Quantum speedups for linear programming via interior point methods.” arXiv:2311.03215 (2023) (cited on pages 96, 100, 257, 310, 312, 313, 315). — [arXiv:2311.03215](https://arxiv.org/abs/2311.03215) find
47. Apers, S., Gribling, S., Sen, S., and Szabó, D. “A (simple) classical algorithm for estimating Betti numbers.” Quantum 7 (2023), 1202. arXiv:2211.09618 (cited on pages 184, 185). — [arXiv:2211.09618](https://arxiv.org/abs/2211.09618) find
48. Apers, S. and Wolf, R. de. “Quantum speedup for graph sparsification, cut approximation and Laplacian solving.” In: FOCS (2020), 637–648. arXiv:1911.07306 (cited on page 289). — [arXiv:1911.07306](https://arxiv.org/abs/1911.07306) find
49. Arad, I. and Landau, Z. “Quantum computation and the evaluation of tensor networks.” SIAM J. Comp. 39 (2010), 3089–3121. arXiv:0805.0040 (cited on pages 322–324). — [arXiv:0805.0040](https://arxiv.org/abs/0805.0040) find
50. Argüello-Luengo, J., González-Tudela, A., Shi, T., Zoller, P., and Cirac, J. I. “Analogue quantum chemistry simulation.” Nature 574 (2019), 215–218. arXiv:1807.09228 (cited on page 47). — [arXiv:1807.09228](https://arxiv.org/abs/1807.09228) find
51. Arora, S., Hazan, E., and Kale, S. “Fast algorithms for approximate semidefinite programming using the multiplicative weights update method.” In: FOCS (2005), 339–348 (cited on pages 94, 99). find
52. Arora, S., Hazan, E., and Kale, S. “The multiplicative weights update method: a meta-algorithm and applications.” Theory Comput. 8 (2012), 121–164 (cited on pages 94, 317, 318, 320). find
53. Arora, S. and Kale, S. “A combinatorial, primal-dual approach to semidefinite programs.” In: STOC (2007), 227–236 (cited on pages 94, 99). find
54. Arovas, D. P., Berg, E., Kivelson, S. A., and Raghu, S. “The Hubbard model.” Annu. Rev. Condens. Matter Phys. 13 (2022), 239–274. arXiv:2103.12097 (cited on page 11). — [arXiv:2103.12097](https://arxiv.org/abs/2103.12097) find
55. Arrasmith, A., Holmes, Z., Cerezo, M., and Coles, P. J. “Equivalence of quantum barren plateaus to cost concentration and narrow gorges.” Quantum Sci. Technol. 7 (2022), 045015. arXiv:2104.05868 (cited on page 298). — [arXiv:2104.05868](https://arxiv.org/abs/2104.05868) find
56. Arrazola, J. M., Delgado, A., Bardhan, B. R., and Lloyd, S. “Quantum-inspired algorithms in practice.” Quantum 4 (2020), 307. arXiv:1905.10415 (cited on page 166). — [arXiv:1905.10415](https://arxiv.org/abs/1905.10415) find
57. Arunachalam, S., Gheorghiu, V., Jochym-O’Connor, T., Mosca, M., and Srinivasan, P. V. “On the robustness of bucket brigade quantum RAM.” New J. Phys. 17 (2015), 123010. arXiv:1502.03450 (cited on pages 272, 274). — [arXiv:1502.03450](https://arxiv.org/abs/1502.03450) find
58. Arute, F., Arya, K., Babbush, R., et al. “Observation of separated dynamics of charge and spin in the Fermi– Hubbard model.” arXiv:2010.07965 (2020) (cited on page 18). — [arXiv:2010.07965](https://arxiv.org/abs/2010.07965) find
59. Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G., Buell, D. A., et al. “Quantum supremacy using a programmable superconducting processor.” Nature 574 (2019), 505–510 (cited on page 324). find
60. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Ashikhmin, A., Lai, C. Y., and Brun, T. A. “Quantum data-syndrome codes.” IEEE J. Sel. Areas Commun. 38 (2020), 449–462. arXiv:1907.01393 (cited on page 336). — [arXiv:1907.01393](https://arxiv.org/abs/1907.01393) find
61. Aspuru-Guzik, A., Dutoi, A. D., Love, P. J., and Head-Gordon, M. “Simulated quantum computation of molecular energies.” Science 309 (2005), 1704–1707. arXiv:0604193 (cited on page 36). find
62. Atas, Y. Y., Zhang, J., Lewis, R., Jahanpour, A., Haase, J. F., and Muschik, C. A. “SU(2) hadrons on a quantum computer via a variational approach.” Nat. Commun. 12 (2021), 6499. arXiv:2102.08920 (cited on page 63). — [arXiv:2102.08920](https://arxiv.org/abs/2102.08920) find
63. Augustino, B., Leng, J., Nannicini, G., Terlaky, T., and Wu, X. “A quantum central path algorithm for linear optimization.” arXiv:2311.03977 (2023) (cited on pages 97, 310, 312, 315). — [arXiv:2311.03977](https://arxiv.org/abs/2311.03977) find
64. Augustino, B., Nannicini, G., Terlaky, T., and Zuluaga, L. F. “Quantum interior point methods for semidefinite optimization.” Quantum 7 (2023), 1110. arXiv:2112.06025 (cited on pages 95, 96, 311–313, 315). — [arXiv:2112.06025](https://arxiv.org/abs/2112.06025) find
65. Augustino, B., Nannicini, G., Terlaky, T., and Zuluaga, L. “Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer.” arXiv:2301.04237 (2023) (cited on pages 97, 320). — [arXiv:2301.04237](https://arxiv.org/abs/2301.04237) find
66. Augustino, B., Terlaky, T., and Zuluaga, L. F. An inexact-feasible quantum interior point method for second-order cone optimization. Tech. rep. 21T-009. Department of Industrial and Systems Engineering, Lehigh University (2022) (cited on pages 95, 144, 311, 312). find
67. Babbush, R., Berry, D. W., Kivlichan, I. D., Wei, A. Y., Love, P. J., and Aspuru-Guzik, A. “Exponentially more precise quantum simulation of fermions in second quantization.” New J. Phys. 18 (2016), 033032. arXiv:1506.01020 (cited on pages 40, 234). — [arXiv:1506.01020](https://arxiv.org/abs/1506.01020) find
68. Babbush, R., Berry, D. W., Sanders, Y. R., Kivlichan, I. D., Scherer, A., Wei, A. Y., Love, P. J., and Aspuru-Guzik, A. “Exponentially more precise quantum simulation of fermions in the configuration interaction representation.” Quantum Sci. Technol. 3 (2017), 015006. arXiv:1506.01029 (cited on page… — [arXiv:1506.01029](https://arxiv.org/abs/1506.01029) find
69. Babbush, R., Berry, D. W., McClean, J. R., and Neven, H. “Quantum simulation of chemistry with sublinear scaling in basis size.” npj Quant. Inf. 5 (2019), 92. arXiv:1807.09802 (cited on pages 43, 47). — [arXiv:1807.09802](https://arxiv.org/abs/1807.09802) find
70. Babbush, R., Berry, D. W., and Neven, H. “Quantum simulation of the Sachdev–Ye–Kitaev model by asymmetric qubitization.” Phys. Rev. A 99 (2019), 040301. arXiv:1806.02793 (cited on pages 31–33). — [arXiv:1806.02793](https://arxiv.org/abs/1806.02793) find
71. Babbush, R., Berry, D. W., Kothari, R., Somma, R. D., and Wiebe, N. “Exponential quantum speedup in simulating coupled classical oscillators.” arXiv:2303.13012 (2023) (cited on pages 127, 133). — [arXiv:2303.13012](https://arxiv.org/abs/2303.13012) find
72. Babbush, R., Gidney, C., Berry, D. W., Wiebe, N., McClean, J., Paler, A., Fowler, A., and Neven, H. “Encoding electronic spectra in quantum circuits with linear T complexity.” Phys. Rev. X 8 (2018), 041015. arXiv:1805.03662 (cited on pages 12, 14–16, 40, 45, 200, 201, 206, 233, 237, 272, 273, 278). — [arXiv:1805.03662](https://arxiv.org/abs/1805.03662) find
73. Babbush, R., Huggins, W. J., Berry, D. W., Ung, S. F., Zhao, A., Reichman, D. R., Neven, H., Baczewski, A. D., and Lee, J. “Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods.” Nat. Commun. 14 (2023), 4058. arXiv:2301.01203 (cited on pages 41, 43, 4… — [arXiv:2301.01203](https://arxiv.org/abs/2301.01203) find
74. Babbush, R., McClean, J., Wecker, D., Aspuru-Guzik, A., and Wiebe, N. “Chemical basis of Trotter–Suzuki errors in quantum chemistry simulation.” Phys. Rev. A 91 (2015), 022311. arXiv:1410.8159 (cited on page 226). — [arXiv:1410.8159](https://arxiv.org/abs/1410.8159) find
75. Babbush, R., McClean, J. R., Newman, M., Gidney, C., Boixo, S., and Neven, H. “Focus beyond quadratic speedups for error-corrected quantum advantage.” PRX Quantum 2 (2021), 010103. arXiv:2011.04149 (cited on pages 75, 80, 84, 85, 148). — [arXiv:2011.04149](https://arxiv.org/abs/2011.04149) find
76. Babbush, R., Wiebe, N., Mcclean, J., Mcclain, J., Neven, H., and Chan, G. K.-L. “Low-depth quantum simulation of materials.” Phys. Rev. X 8 (2018), 011044. arXiv:1706.00023 (cited on page 39). — [arXiv:1706.00023](https://arxiv.org/abs/1706.00023) find
77. Bădescu, C. and O’Donnell, R. “Improved quantum data analysis.” In: STOC arXiv:2011.10908 (cited on page 307). (2021), 1398–1411. — [arXiv:2011.10908](https://arxiv.org/abs/2011.10908) find
78. Bagherimehrab, M., Nakaji, K., Wiebe, N., and Aspuru-Guzik, A. “Fast quantum algorithm for differential equations.” arXiv:2306.11802 (2023) (cited on pages 129, 290). — [arXiv:2306.11802](https://arxiv.org/abs/2306.11802) find
79. Bagherimehrab, M., Sanders, Y. R., Berry, D. W., Brennen, G. K., and Sanders, B. C. “Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory.” PRX Quantum 3 (2022), 020364. arXiv:2110.05708 (cited on page 60). — [arXiv:2110.05708](https://arxiv.org/abs/2110.05708) find
80. Baiardi, A., Stein, C. J., Barone, V., and Reiher, M. “Vibrational density matrix renormalization group.” J. Chem. Theory Comput. 13 (2017), 3764–3777. arXiv:1703.09313 (cited on page 55). — [arXiv:1703.09313](https://arxiv.org/abs/1703.09313) find
81. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Baker, J. S. and Radha, S. K. “Wasserstein solution quality and the quantum approximate optimization algorithm: A portfolio optimization case study.” arXiv:2202.06782 (2022) (cited on page 147). — [arXiv:2202.06782](https://arxiv.org/abs/2202.06782) find
82. Bakshi, A. and Tang, E. “An improved classical singular value transformation for quantum machine learning.” In: SODA (2024), 2398–2453. arXiv:2303.01492 (cited on page 166). — [arXiv:2303.01492](https://arxiv.org/abs/2303.01492) find
83. Banaszek, K., Cramer, M., and Gross, D. “Focus on quantum tomography.” New J. Phys. 15 (2013), 125020 (cited on page 308). find
84. Banchi, L., Pereira, J., and Pirandola, S. “Generalization in quantum machine learning: A quantum information standpoint.” PRX Quantum 2 (2021), 040321. arXiv:2102.08991 (cited on page 191). — [arXiv:2102.08991](https://arxiv.org/abs/2102.08991) find
85. Banegas, G. and Bernstein, D. J. “Low-communication parallel quantum multi-target preimage search.” In: SAC (2018), 325–335. ePrint:2017/789 (cited on page 119). find
86. Banuls, M.-C., Pérez-Garcı́a, D., Wolf, M. M., Verstraete, F., and Cirac, J. I. “Sequentially generated states for the study of two-dimensional systems.” Phys. Rev. A 77 (2008), 052306. arXiv:0802.2472 (cited on page 324). — [arXiv:0802.2472](https://arxiv.org/abs/0802.2472) find
87. Bañuls, M. C., Blatt, R., Catani, J., et al. “Simulating lattice gauge theories within quantum technologies.” Eur. Phys. J. D 74 (2020), 165. arXiv:1911.00003 (cited on pages 59, 63). — [arXiv:1911.00003](https://arxiv.org/abs/1911.00003) find
88. Banuls, M. C., Cichy, K., Cirac, J. I., Jansen, K., and Kühn, S. “Tensor networks and their use for lattice gauge theories.” In: LATTICE (2019), 022. arXiv:1810.12838 (cited on page 63). — [arXiv:1810.12838](https://arxiv.org/abs/1810.12838) find
89. Bao, N., Hayden, P., Salton, G., and Thomas, N. “Universal quantum computation by scattering in the Fermi– Hubbard model.” New J. Phys. 17 (2015), 093028. arXiv:1409.3585 (cited on page 18). — [arXiv:1409.3585](https://arxiv.org/abs/1409.3585) find
90. Barahona, F. “On the computational complexity of Ising spin glass models.” J. Phys. A 15 (1982), 3241–3253 (cited on page 26). find
91. Barker, E. Recommendation for Key Management: Part 1—General. Tech. rep. SP 800-57 Part 1 Rev. 5. National Institute of Standards and Technology (2020) (cited on page 120). find
92. Barker, E. and Dang, Q. Recommendation for Key Management, Part 3: Application-Specific Key Management Guidance. Tech. rep. SP 800-57 Part 3 Rev. 1. National Institute of Standards and Technology (2015) (cited on page 113). find
93. Barmes, I. and Bosch, B. Quantum computers and the bitcoin blockchain. https://deloitte.com/nl/nl/page s/innovatie/artikelen/quantum- computers- and- the- bitcoin- blockchain.html, accessed: 2023-09-30. ↗
94. Deloitte (2019) (cited on page 116). find
95. Barmes, I., Bosch, B., and Verdonk, M. Quantum risk to the Ethereum blockchain—a bump in the road or a brick wall? https://deloitte.com/nl/nl/pages/risk/articles/quantum-risk-to-the-ethereum-blockchain .html, accessed: 2023-09-30. ↗
96. Deloitte (2022) (cited on page 116). find
97. Barone, V., Alessandrini, S., Biczysko, M., Cheeseman, J. R., Clary, D. C., McCoy, A. B., DiRisio, R. J., Neese, F., Melosso, M., and Puzzarini, C. “Computational molecular spectroscopy.” Nat. Rev. Methods Primers 1 (2021), 38 (cited on page 55). find
98. Barrett, B. R., Navratil, P., and Vary, J. P. “Ab initio no core shell model.” Prog. part. nucl. phys. 69 (2013), 131–181 (cited on pages 67, 69). find
99. Bärtschi, A., Caravelli, F., Coffrin, C., Colina, J., Eidenbenz, S., Jayakumar, A., Lawrence, S., Lee, M., Lokhov, A. Y., Mishra, A., et al. “Potential applications of quantum computing at Los Alamos National Laboratory.” arXiv:2406.06625 (2024) (cited on pages 11, 23). — [arXiv:2406.06625](https://arxiv.org/abs/2406.06625) find
100. Bauer, B., Bravyi, S., Motta, M., and Chan, G. K.-L. “Quantum algorithms for quantum chemistry and quantum materials science.” Chem. Rev. 120 (2020), 12685–12717. arXiv:2001.03685 (cited on page 36). — [arXiv:2001.03685](https://arxiv.org/abs/2001.03685) find
101. Bauer, C. W., Davoudi, Z., Klco, N., and Savage, M. J. “Quantum simulation of fundamental particles and forces.” Nat. Rev. Phys. 5 (2023), 420–432 (cited on pages 59, 62, 63). find
102. Bauer, C. W., Davoudi, Z., Balantekin, A. B., et al. “Quantum simulation for high-energy physics.” PRX Quantum 4 (2023), 027001. arXiv:2204.03381 (cited on pages 59, 60, 62, 63, 68). — [arXiv:2204.03381](https://arxiv.org/abs/2204.03381) find
103. Bauer, C. W., Nachman, B., and Freytsis, M. “Simulating collider physics on quantum computers using effective field theories.” Phys. Rev. Lett. 127 (2021), 212001. arXiv:2102.05044 (cited on page 61). — [arXiv:2102.05044](https://arxiv.org/abs/2102.05044) find
104. Bausch, J. “Fast black-box quantum state preparation.” Quantum 6 (2022). arXiv:2009.10709 (cited on page 279). — [arXiv:2009.10709](https://arxiv.org/abs/2009.10709) find
105. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Bausch, J., Senior, A. W., Heras, F. J. H., et al. “Learning to decode the surface code with a recurrent, transformer-based neural network.” arXiv:2310.05900 (2023) (cited on page 336). — [arXiv:2310.05900](https://arxiv.org/abs/2310.05900) find
106. Beane, S., Detmold, W., Orginos, K., and Savage, M. “Nuclear physics from lattice QCD.” Prog. Part. Nuc. Phys. 66 (2011), 1–40. arXiv:1004.2935 (cited on page 67). — [arXiv:1004.2935](https://arxiv.org/abs/1004.2935) find
107. Beaudrap, N. de and Horsman, D. “The ZX calculus is a language for surface code lattice surgery.” Quantum 4 (2020), 218. arXiv:1704.08670 (cited on page 344). — [arXiv:1704.08670](https://arxiv.org/abs/1704.08670) find
108. Beauregard, S. “Circuit for Shor’s algorithm using 2n+3 qubits.” Quantum Inf. Comput. 3 (2003), 175–185. arXiv:quant-ph/0205095 (cited on page 113). — [arXiv:quant-ph/0205095](https://arxiv.org/abs/quant-ph/0205095) find
109. Beck, D., Carlson, J., Davoudi, Z., et al. “Quantum information science and technology for nuclear physics: input into U.S. long-range planning, 2023.” arXiv:2303.00113 (2023) (cited on pages 59, 69). — [arXiv:2303.00113](https://arxiv.org/abs/2303.00113) find
110. Beckman, D., Chari, A. N., Devabhaktuni, S., and Preskill, J. “Efficient networks for quantum factoring.” Phys. Rev. A 54 (1996), 1034–1063. arXiv:quant-ph/9602016 (cited on page 114). — [arXiv:quant-ph/9602016](https://arxiv.org/abs/quant-ph/9602016) find
111. Beer, K., Bondarenko, D., Farrelly, T., Osborne, T. J., Salzmann, R., Scheiermann, D., and Wolf, R. “Training deep quantum neural networks.” Nat. Commun. 11 (2020), 808. arXiv:1902.10445 (cited on page 300). — [arXiv:1902.10445](https://arxiv.org/abs/1902.10445) find
112. Bellonzi, N., Kunitsa, A., Cantin, J. T., Campos-Gonzalez-Angulo, J. A., Radin, M. D., Zhou, Y., Johnson, P. D., Martı́nez-Martı́nez, L. A., Jangrouei, M. R., Brahmachari, A. S., et al. “Feasibility of accelerating homogeneous catalyst discovery with fault-tolerant quantum computers.” arXiv:2406.063… — [arXiv:2406.06335](https://arxiv.org/abs/2406.06335) find
113. Ben-Or, M., Gottesman, D., and Hassidim, A. “Quantum refrigerator.” arXiv:1301.1995 (2013) (cited on page 298). — [arXiv:1301.1995](https://arxiv.org/abs/1301.1995) find
114. Bender, M., Bernard, R., Bertsch, G., et al. “Future of nuclear fission theory.” J. Phys. G 47 (2020), 113002. arXiv:2005.10216 (cited on pages 67, 69). — [arXiv:2005.10216](https://arxiv.org/abs/2005.10216) find
115. Benedetti, M., Fiorentini, M., and Lubasch, M. “Hardware-efficient variational quantum algorithms for time evolution.” Phys. Rev. Res. 3 (2021), 033083. arXiv:2009.12361 (cited on page 299). — [arXiv:2009.12361](https://arxiv.org/abs/2009.12361) find
116. Benedetti, M., Garcia-Pintos, D., Perdomo, O., Leyton-Ortega, V., Nam, Y., and Perdomo-Ortiz, A. “A generative modeling approach for benchmarking and training shallow quantum circuits.” npj Quant. Inf. 5 (2019), 1–9. arXiv:1801.07686 (cited on page 300). — [arXiv:1801.07686](https://arxiv.org/abs/1801.07686) find
117. Benedetti, M., Lloyd, E., Sack, S., and Fiorentini, M. “Parameterized quantum circuits as machine learning models.” Quantum Sci. Technol. 4 (2019), 043001. arXiv:1906.07682 (cited on page 192). — [arXiv:1906.07682](https://arxiv.org/abs/1906.07682) find
118. Benedetti, M., Realpe-Gómez, J., Biswas, R., and Perdomo-Ortiz, A. “Quantum-assisted learning of hardware-embedded probabilistic graphical models.” Phys. Rev. X 7 (2017), 041052. arXiv:1609.02542 (cited on page 174). — [arXiv:1609.02542](https://arxiv.org/abs/1609.02542) find
119. Benioff, P. “The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines.” J. Stat. Phys. 22 (1980), 563–591 (cited on page 4). find
120. Bennett, C. H., Bernstein, E., Brassard, G., and Vazirani, U. “Strengths and weaknesses of quantum computing.” SIAM J. Comp. 26 (1997), 1510–1523. arXiv:quant-ph/9701001 (cited on page 76). — [arXiv:quant-ph/9701001](https://arxiv.org/abs/quant-ph/9701001) find
121. Bennett, C. H. and Brassard, G. “Quantum cryptography: public key distribution and coin tossing.” Theor. Comput. Sci. 560 (2014), 7–11. arXiv:2003.06557 (cited on page 109). find
122. Bergholm, V., Izaac, J., Schuld, M., et al. “Pennylane: automatic differentiation of hybrid quantum-classical computations.” arXiv:1811.04968. https://pennylane.ai/codebook, accessed: 2024-12-01 (2018) (cited on page 347). van den Berg, E. and Temme, K. “Circuit optimization of Hamiltonian simulatio… — [arXiv:1811.04968](https://arxiv.org/abs/1811.04968) ↗
123. Bermudez, A., Xu, X., Nigmatullin, R., et al. “Assessing the progress of trapped-ion processors towards fault-tolerant quantum computation.” Phys. Rev. X 7 (2017), 041061. arXiv:1705.02771 (cited on page 328). — [arXiv:1705.02771](https://arxiv.org/abs/1705.02771) find
124. Bernstein, D. J., Biasse, J.-F., and Mosca, M. “A low-resource quantum factoring algorithm.” In: PQCrypto (2017), 330–346. ePrint:2017/352 (cited on page 114). find
125. Bernstein, D. J., Engels, S., Lange, T., Niederhagen, R., Paar, C., Schwabe, P., and Zimmermann, R. “Faster elliptic-curve discrete logarithms on FPGAs.” ePrint:2016/382 (2016) (cited on page 114). find
126. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Bernstein, D. J. and Lange, T. “Post-quantum cryptography.” Nature 549 (2017), 188–194. ePrint:2017/314 (cited on pages 110, 113, 119–121). find
127. Bernstein, E. and Vazirani, U. “Quantum complexity theory.” SIAM J. Comp. 26 (1997), 1411–1473. Earlier version in STOC’93 . (cited on pages 4, 294). find
128. Berntson, B. K. and Sünderhauf, C. “Complementary polynomials in quantum signal processing.” arXiv:2406.04246 (2024) (cited on pages 209, 218). — [arXiv:2406.04246](https://arxiv.org/abs/2406.04246) find
129. Berry, D. W. “High-order quantum algorithm for solving linear differential equations.” J. Phys. A 47 (2014), 105301. arXiv:1010.2745 (cited on pages 127, 129). — [arXiv:1010.2745](https://arxiv.org/abs/1010.2745) find
130. Berry, D. W., Ahokas, G., Cleve, R., and Sanders, B. C. “Efficient quantum algorithms for simulating sparse Hamiltonians.” Commun. Math. Phys. 270 (2007), 359–371. arXiv:quant-ph/0508139 (cited on pages 129, 225, 229, 233, 237). — [arXiv:quant-ph/0508139](https://arxiv.org/abs/quant-ph/0508139) find
131. Berry, D. W. and C. S. Costa, P. “Quantum algorithm for time-dependent differential equations using Dyson series.” Quantum 8 (2024), 1369. arXiv:2212.03544 (cited on pages 126, 129). — [arXiv:2212.03544](https://arxiv.org/abs/2212.03544) find
132. Berry, D. W. and Childs, A. M. “Black-box Hamiltonian simulation and unitary implementation.” Quantum Inf. Comput. 12 (2012), 29–62. arXiv:0910.4157 (cited on page 222). — [arXiv:0910.4157](https://arxiv.org/abs/0910.4157) find
133. Berry, D. W., Childs, A. M., Cleve, R., Kothari, R., and Somma, R. D. “Exponential improvement in precision for simulating sparse Hamiltonians.” In: STOC (2014), 283–292. arXiv:1312.1414 (cited on pages 196, 232, 252). — [arXiv:1312.1414](https://arxiv.org/abs/1312.1414) find
134. Berry, D. W., Childs, A. M., Cleve, R., Kothari, R., and Somma, R. D. “Simulating Hamiltonian dynamics with a truncated Taylor series.” Phys. Rev. Lett. 114 (2015), 090502. arXiv:1412.4687 (cited on pages 232, 233, 253). — [arXiv:1412.4687](https://arxiv.org/abs/1412.4687) find
135. Berry, D. W., Childs, A. M., and Kothari, R. “Hamiltonian simulation with nearly optimal dependence on all parameters.” In: FOCS (2015), 792–809. arXiv:1501.01715 (cited on pages 196, 222, 253). — [arXiv:1501.01715](https://arxiv.org/abs/1501.01715) find
136. Berry, D. W., Childs, A. M., Ostrander, A., and Wang, G. “Quantum algorithm for linear differential equations with exponentially improved dependence on precision.” Commun. Math. Phys. 356 (2017), 1057–1081. arXiv:1701.03684 (cited on pages 126, 129, 132). — [arXiv:1701.03684](https://arxiv.org/abs/1701.03684) find
137. Berry, D. W., Childs, A. M., Su, Y., Wang, X., and Wiebe, N. “Time-dependent Hamiltonian simulation with L 1 -norm scaling.” Quantum 4 (2020), 254. arXiv:1906.07115 (cited on pages 229, 232, 234). — [arXiv:1906.07115](https://arxiv.org/abs/1906.07115) find
138. Berry, D. W., Gidney, C., Motta, M., McClean, J. R., and Babbush, R. “Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization.” Quantum 3 (2019), 208. arXiv:1902.02134 (cited on pages 40, 41, 44, 45, 200, 272, 273, 278). — [arXiv:1902.02134](https://arxiv.org/abs/1902.02134) find
139. Berry, D. W., Kieferová, M., Scherer, A., Sanders, Y. R., Low, G. H., Wiebe, N., Gidney, C., and Babbush, R. “Improved techniques for preparing eigenstates of fermionic Hamiltonians.” npj Quant. Inf. 4 (2018), 22. arXiv:1711.10460 (cited on pages 14, 40, 42, 212, 214, 245). — [arXiv:1711.10460](https://arxiv.org/abs/1711.10460) find
140. Berry, D. W., Rubin, N. C., Elnabawy, A. O., Ahlers, G., DePrince III, A. E., Lee, J., Gogolin, C., and Babbush, R. “Quantum simulation of realistic materials in first quantization using non-local pseudopotentials.” arXiv:2312.07654 (2023) (cited on page 45). — [arXiv:2312.07654](https://arxiv.org/abs/2312.07654) find
141. Berry, D. W., Su, Y., Gyurik, C., King, R., Basso, J., Barba, A. D. T., Rajput, A., Wiebe, N., Dunjko, V., and Babbush, R. “Analyzing prospects for quantum advantage in topological data analysis.” PRX Quantum 5 (2024), 010319. arXiv:2209.13581 (cited on pages 42, 183–185, 216, 245). — [arXiv:2209.13581](https://arxiv.org/abs/2209.13581) find
142. Berry, D. W., Tong, Y., Khattar, T., White, A., Kim, T. I., Boixo, S., Lin, L., Lee, S., Chan, G. K.-L., Babbush, R., and Rubin, N. C. “Rapid initial state preparation for the quantum simulation of strongly correlated molecules.” arXiv:2409.11748 (2024) (cited on pages 41, 42, 45, 47, 245). — [arXiv:2409.11748](https://arxiv.org/abs/2409.11748) find
143. Beullens, W. “Breaking rainbow takes a weekend on a laptop.” In: CRYPTO (2022), 464–479. ePrint:2022/214 (cited on page 115). find
144. Beverland, M. E., Kubica, A., and Svore, K. M. “Cost of universality: a comparative study of the overhead of state distillation and code switching with color codes.” PRX Quantum 2 (2021), 020341. arXiv:2101.02211 (cited on pages 341, 342, 344). — [arXiv:2101.02211](https://arxiv.org/abs/2101.02211) find
145. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Beverland, M. E., Murali, P., Troyer, M., Svore, K. M., Hoeffler, T., Kliuchnikov, V., Low, G. H., Soeken, M., Sundaram, A., and Vaschillo, A. “Assessing requirements to scale to practical quantum ad… — [arXiv:2211.07629](https://arxiv.org/abs/2211.07629) find
146. Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. “Noisy intermediate-scale quantum algorithms.” Rev. Mod. Phys. 94 (2022), 015004. arXiv:2101.08448 (cited on page 300). — [arXiv:2101.08448](https://arxiv.org/abs/2101.08448) find
147. Bhaskar, M. K., Hadfield, S., Papageorgiou, A., and Petras, I. “Quantum algorithms and circuits for scientific computing.” Quantum Inf. Comput. 16 (2016). arXiv:1511.08253 (cited on page 279). — [arXiv:1511.08253](https://arxiv.org/abs/1511.08253) find
148. Biamonte, J. and Bergholm, V. “Tensor networks in a nutshell.” arXiv:1708.00006 (2017) (cited on pages 322, 325). — [arXiv:1708.00006](https://arxiv.org/abs/1708.00006) find
149. Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., and Lloyd, S. “Quantum machine learning.” Nature 549 (2017), 195–202. arXiv:1611.09347 (cited on pages 157, 167). — [arXiv:1611.09347](https://arxiv.org/abs/1611.09347) find
150. Bilgin, E. and Boixo, S. “Preparing thermal states of quantum systems by dimension reduction.” Phys. Rev. Lett. 105 (2010), 170405. arXiv:1008.4162 (cited on page 263). — [arXiv:1008.4162](https://arxiv.org/abs/1008.4162) find
151. Binder, S., Ekström, A., Hagen, G., Papenbrock, T., and Wendt, K. A. “Effective field theory in the harmonic oscillator basis.” Phys. Rev. C 93 (2016), 044332. arXiv:1512.03802 (cited on page 68). — [arXiv:1512.03802](https://arxiv.org/abs/1512.03802) find
152. Bittel, L. and Kliesch, M. “Training variational quantum algorithms is NP-hard.” Phys. Rev. Lett. 127 (2021), 120502. arXiv:2101.07267 (cited on page 298). — [arXiv:2101.07267](https://arxiv.org/abs/2101.07267) find
153. Blais, A., Grimsmo, A. L., Girvin, S. M., and Wallraff, A. “Circuit quantum electrodynamics.” Rev. Mod. Phys. 93 (2021), 025005. arXiv:2005.12667 (cited on page 334). — [arXiv:2005.12667](https://arxiv.org/abs/2005.12667) find
154. Blanchet, J., Szegedy, M., and Wang, G. “Quadratic speed-up in infinite variance quantum Monte Carlo.” arXiv:2401.07497 (2024) (cited on page 153). — [arXiv:2401.07497](https://arxiv.org/abs/2401.07497) find
155. Bloch, I., Dalibard, J., and Nascimbène, S. “Quantum simulations with ultracold quantum gases.” Nat. Phys. 8 (2012), 267–276 (cited on pages 22, 27). find
156. Blunt, N. S., Camps, J., Crawford, O., Izsák, R., Leontica, S., Mirani, A., Moylett, A. E., Scivier, S. A., Sünderhauf, C., Schopf, P., Taylor, J. M., and Holzmann, N. “Perspective on the current state-of-the-art of quantum computing for drug discovery applications.” J. Chem. Theory Comput. 18 (20… — [arXiv:2206.00551](https://arxiv.org/abs/2206.00551) find
157. Blunt, N. S., Caune, L., Izsák, R., Campbell, E. T., and Holzmann, N. “Statistical phase estimation and error mitigation on a superconducting quantum processor.” PRX Quantum 4 (2023), 040341. arXiv:2304.05126 (cited on page 299). — [arXiv:2304.05126](https://arxiv.org/abs/2304.05126) find
158. Bogdanov, A., Khovratovich, D., and Rechberger, C. “Biclique cryptanalysis of the full AES.” In: ASIACRYPT (2011), 344–371. ePrint:2011/449 (cited on page 120). find
159. Boixo, S., Knill, E., and Somma, R. D. “Fast quantum algorithms for traversing paths of eigenstates.” arXiv:1005.3034 (2010) (cited on pages 247, 267). — [arXiv:1005.3034](https://arxiv.org/abs/1005.3034) find
160. Boixo, S. and Somma, R. D. “Necessary condition for the quantum adiabatic approximation.” Phys. Rev. A 81 (2010), 032308. arXiv:0911.1362 (cited on page 266). — [arXiv:0911.1362](https://arxiv.org/abs/0911.1362) find
161. Bolte, J., Boustany, R., Pauwels, E., and Pesquet-Popescu, B. “Nonsmooth automatic differentiation: A cheap gradient principle and other complexity results.” arXiv:2206.01730 (2022) (cited on pages 103, 106, 295). — [arXiv:2206.01730](https://arxiv.org/abs/2206.01730) find
162. Bolusani, S., Besançon, M., Bestuzheva, K., et al. “The SCIP optimization suite 9.0.” arXiv:2402.17702 (2024) (cited on page 98). — [arXiv:2402.17702](https://arxiv.org/abs/2402.17702) find
163. Bombı́n, H. “Gauge color codes: Optimal transversal gates and gauge fixing in topological stabilizer codes.” New J. Phys. 17 (2015), 083002. arXiv:1311.0879 (cited on page 342). — [arXiv:1311.0879](https://arxiv.org/abs/1311.0879) find
164. Bombı́n, H. “Single-shot fault-tolerant quantum error correction.” Phys. Rev. X arXiv:1404.5504 (cited on page 336). 5 (2015), 031043. — [arXiv:1404.5504](https://arxiv.org/abs/1404.5504) find
165. Bombı́n, H. “2D quantum computation with 3D topological codes.” arXiv:1810.09571 (2018) (cited on page 342). — [arXiv:1810.09571](https://arxiv.org/abs/1810.09571) find
166. Bombı́n, H., Dawson, C., Liu, Y.-H., Nickerson, N., Pastawski, F., and Roberts, S. “Modular decoding: Parallelizable real-time decoding for quantum computers.” arXiv:2303.04846 (2023) (cited on page 335). — [arXiv:2303.04846](https://arxiv.org/abs/2303.04846) find
167. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Bombı́n, H. and Martin-Delgado, M. “Exact topological quantum order in D = 3 and beyond: branyons and brane-net condensates.” Phys. Rev. B 75 (2007), 075103. arXiv:cond-mat/0607736 (cited on page 337… — [arXiv:cond-mat/0607736](https://arxiv.org/abs/cond-mat/0607736) find
168. Bombı́n, H. and Martin-Delgado, M. A. “Topological quantum distillation.” Phys. Rev. Lett. 97 (2006), 180501. arXiv:quant-ph/0605138 (cited on page 337). — [arXiv:quant-ph/0605138](https://arxiv.org/abs/quant-ph/0605138) find
169. Bombı́n, H. G. D.-C. and Poulin, D. “Universal topological phase of two-dimensional stabilizer codes.” New J. Phys. 14 (2012), 073048. arXiv:1103.4606 (cited on page 337). — [arXiv:1103.4606](https://arxiv.org/abs/1103.4606) find
170. Bonfà, P., Frassineti, J., Isah, M. M., Onuorah, I. J., and Sanna, S. “UNDI: an open-source library to simulate muon-nuclear interactions in solids.” Comput. Phys. Commun. 260 (2021), 107719 (cited on pages 23, 27). find
171. Bonilla Ataides, J. P., Tuckett, D. K., Bartlett, S. D., Flammia, S. T., and Brown, B. J. “The XZZX surface code.” Nat. Commun. 12 (2021), 2172. arXiv:2009.07851 (cited on page 336). — [arXiv:2009.07851](https://arxiv.org/abs/2009.07851) find
172. Bosse, J. L. and Montanaro, A. “Probing ground-state properties of the kagome antiferromagnetic Heisenberg model using the variational quantum eigensolver.” Phys. Rev. B 105 (2022), 094409. arXiv:2108.08086 (cited on page 27). — [arXiv:2108.08086](https://arxiv.org/abs/2108.08086) find
173. Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thomé, E., and Zimmermann, P. “Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment.” In: CRYPTO (2020), 62–91. arXiv:2006.06197 (cited on pages 113–115). — [arXiv:2006.06197](https://arxiv.org/abs/2006.06197) find
174. Bouland, A., van Dam, W., Joorati, H., Kerenidis, I., and Prakash, A. “Prospects and challenges of quantum finance.” arXiv:2011.06492 (2020) (cited on pages 141, 154). — [arXiv:2011.06492](https://arxiv.org/abs/2011.06492) find
175. Bouland, A., Dandapani, A., and Prakash, A. “A quantum spectral method for simulating stochastic processes, with applications to Monte Carlo.” arXiv:2303.06719 (2023) (cited on page 155). — [arXiv:2303.06719](https://arxiv.org/abs/2303.06719) find
176. Bouland, A., Getachew, Y. M., Jin, Y., Sidford, A., and Tian, K. “Quantum speedups for zero-sum games via improved dynamic Gibbs sampling.” In: ICML (2023), 2932–2952. arXiv:2301.03763 (cited on pages 91, 96, 97, 320). — [arXiv:2301.03763](https://arxiv.org/abs/2301.03763) find
177. Boulebnane, S. and Montanaro, A. “Solving Boolean satisfiability problems with the quantum approximate optimization algorithm.” PRX Quantum 5 (2024), 030348. arXiv:2208.06909 (cited on pages 80, 82, 299). — [arXiv:2208.06909](https://arxiv.org/abs/2208.06909) find
178. Boyd, S. and Vandenberghe, L. Convex Optimization. Cambridge University Press (2004) (cited on pages 311, 315). find
179. Brandão, F. G. S. L., Kalev, A., Li, T., Lin, C. Y.-Y., Svore, K. M., and Wu, X. “Quantum SDP solvers: large speedups, optimality, and applications to quantum learning.” In: ICALP (2019), 27:1–27:14. arXiv:1710.02581 (cited on pages 96, 262, 320). — [arXiv:1710.02581](https://arxiv.org/abs/1710.02581) find
180. Brandão, F. G. S. L., Kueng, R., and França, D. S. “Faster quantum and classical SDP approximations for quadratic binary optimization.” Quantum 6 (2022), 625. arXiv:1909.04613 (cited on pages 97, 320). — [arXiv:1909.04613](https://arxiv.org/abs/1909.04613) find
181. Brandão, F. G. S. L. and Svore, K. M. “Quantum speed-ups for solving semidefinite programs.” In: FOCS (2017), 415–426. arXiv:1609.05537 (cited on pages 95, 96, 262, 319, 320). — [arXiv:1609.05537](https://arxiv.org/abs/1609.05537) find
182. Brandhofer, S., Braun, D., Dehn, V., Hellstern, G., Hüls, M., Ji, Y., Polian, I., Bhatia, A. S., and Wellens, T. “Benchmarking the performance of portfolio optimization with QAOA.” Quantum Inf. Process. 22 (2023), 1–27. arXiv:2207.10555 (cited on page 147). van den Brand, J., Lee, Y. T., Sidford, A… — [arXiv:2207.10555](https://arxiv.org/abs/2207.10555) find
183. Brassard, G., Høyer, P., Mosca, M., and Tapp, A. “Quantum amplitude amplification and estimation.” In: Quantum computation and quantum information: A millennium volume (2002), 53–74. arXiv:quant-ph/0005055 (cited on pages 44, 45, 246, 251, 255–257). — [arXiv:quant-ph/0005055](https://arxiv.org/abs/quant-ph/0005055) find
184. Bravo-Prieto, C., LaRose, R., Cerezo, M., Subaşı, Y., Cincio, L., and Coles, P. “Variational quantum linear solver.” arXiv:1909.05820 (2019) (cited on page 299). — [arXiv:1909.05820](https://arxiv.org/abs/1909.05820) find
185. Bravyi, S. “Monte Carlo simulation of stoquastic Hamiltonians.” Quantum Inf. Comput. 15 (2015), 1122–1140. arXiv:1402.2295 (cited on page 84). — [arXiv:1402.2295](https://arxiv.org/abs/1402.2295) find
186. Bravyi, S., Chowdhury, A., Gosset, D., and Wocjan, P. “Quantum Hamiltonian complexity in thermal equilibrium.” Nat. Phys. 18 (2022), 1367–1370. arXiv:2110.15466 (cited on page 325). — [arXiv:2110.15466](https://arxiv.org/abs/2110.15466) find
187. Bravyi, S. and Cross, A. “Doubled color codes.” arXiv:1509.03239 (2015) (cited on page 342). — [arXiv:1509.03239](https://arxiv.org/abs/1509.03239) find
188. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Bravyi, S., Englbrecht, M., König, R., and Peard, N. “Correcting coherent errors with surface codes.” npj Quant. Inf. 4 (2018) (cited on page 336). find
189. Bravyi, S. and Kitaev, A. “Universal quantum computation with ideal Clifford gates and noisy ancillas.” Phys. Rev. A 71 (2005), 022316. arXiv:quant-ph/0403025 (cited on pages 330, 341). — [arXiv:quant-ph/0403025](https://arxiv.org/abs/quant-ph/0403025) find
190. Bravyi, S., Kliesch, A., Koenig, R., and Tang, E. “Obstacles to variational quantum optimization from symmetry protection.” Phys. Rev. Lett. 125 (2020), 260505. arXiv:1910.08980 (cited on page 299). — [arXiv:1910.08980](https://arxiv.org/abs/1910.08980) find
191. Bravyi, S., Suchara, M., and Vargo, A. “Efficient algorithms for maximum likelihood decoding in the surface code.” Phys. Rev. A 90 (2014), 032326. arXiv:1405.4883 (cited on page 335). — [arXiv:1405.4883](https://arxiv.org/abs/1405.4883) find
192. Bravyi, S. and Terhal, B. “Complexity of stoquastic frustration-free Hamiltonians.” SIAM J. Comp. 39 (2010), 1462–1485. arXiv:0806.1746 (cited on page 84). — [arXiv:0806.1746](https://arxiv.org/abs/0806.1746) find
193. Bravyi, S. B. and Kitaev, A. Y. “Quantum codes on a lattice with boundary.” arXiv:quant-ph/9811052 (1998) (cited on page 334). — [arXiv:quant-ph/9811052](https://arxiv.org/abs/quant-ph/9811052) find
194. Bravyi, S. B. and Kitaev, A. Y. “Fermionic quantum computation.” Ann. Phys. 298 (2002), 210–226. arXiv:quant-ph/0003137 (cited on page 299). — [arXiv:quant-ph/0003137](https://arxiv.org/abs/quant-ph/0003137) find
195. Brenner, S. C. and Scott, L. R. The mathematical theory of finite element methods. Springer (2008) (cited on page 129). find
196. Breuckmann, N. P., Duivenvoorden, K., Michels, D., and Terhal, B. M. “Local decoders for the 2D and 4D toric code.” Quantum Inf. Comput. 17 (2017), 0181. arXiv:1609.00510 (cited on page 336). — [arXiv:1609.00510](https://arxiv.org/abs/1609.00510) find
197. Breuckmann, N. P. and Eberhardt, J. N. “Balanced product quantum codes.” IEEE Trans. Inf. Theory 67 (2021), 6653–6674. arXiv:2012.09271 (cited on page 330). — [arXiv:2012.09271](https://arxiv.org/abs/2012.09271) find
198. Bridgeman, J. C. and Chubb, C. T. “Hand-waving and interpretive dance: An introductory course on tensor networks.” J. Phys. A 50 (2017), 223001. arXiv:1603.03039 (cited on page 325). — [arXiv:1603.03039](https://arxiv.org/abs/1603.03039) find
199. Bridgeman, J. C., Kubica, A., and Vasmer, M. “Lifting topological codes: three-dimensional subsystem codes from two-dimensional anyon models.” PRX Quantum 5 (2024). arXiv:2305.06365 (cited on page 336). — [arXiv:2305.06365](https://arxiv.org/abs/2305.06365) find
200. Browaeys, A. and Lahaye, T. “Many-body physics with individually controlled Rydberg atoms.” Nat. Phys. 16 (2020), 132–142. arXiv:2002.07413 (cited on page 336). — [arXiv:2002.07413](https://arxiv.org/abs/2002.07413) find
201. Brown, A. R., Gharibyan, H., Leichenauer, S., Lin, H. W., Nezami, S., Salton, G., Susskind, L., Swingle, B., and Walter, M. “Quantum gravity in the lab. I. Teleportation by size and traversable wormholes.” PRX Quantum 4 (2023), 010320. arXiv:1911.06314 (cited on page 32). — [arXiv:1911.06314](https://arxiv.org/abs/1911.06314) find
202. Brown, B. J. “Conservation laws and quantum error correction: towards a generalised matching decoder.” IEEE BITS Inf. Theory Mag. (2023), 1–12. arXiv:2207.06428 (cited on page 337). — [arXiv:2207.06428](https://arxiv.org/abs/2207.06428) find
203. Brown, B. J., Laubscher, K., Kesselring, M. S., and Wootton, J. R. “Poking holes and cutting corners to achieve Clifford gates with the surface code.” Phys. Rev. X 7 (2017), 021029. arXiv:1609.04673 (cited on pages 341, 342). — [arXiv:1609.04673](https://arxiv.org/abs/1609.04673) find
204. Brüstle, N. and Wiebe, N. “Quantum and classical algorithms for nonlinear unitary dynamics.” arXiv:2407.07685 (2024) (cited on page 131). — [arXiv:2407.07685](https://arxiv.org/abs/2407.07685) find
205. Bruzewicz, C. D., Chiaverini, J., McConnell, R., and Sage, J. M. “Trapped-ion quantum computing: progress and challenges.” Appl. Phys. Rev. 6 (2019), 021314. arXiv:1904.04178 (cited on page 328). — [arXiv:1904.04178](https://arxiv.org/abs/1904.04178) find
206. Buhrman, H., Patro, S., and Speelman, F. “A framework of quantum strong exponential-time hypotheses.” In: STACS (2021), 19:1–19:19. arXiv:1911.05686 (cited on page 76). — [arXiv:1911.05686](https://arxiv.org/abs/1911.05686) find
207. Bürgisser, P., Franks, C., Garg, A., Oliveira, R., Walter, M., and Wigderson, A. “Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes.” In: FOCS (2018), 883–897. arXiv:1804.04739 (cited on page 103). von Burg, V., Low, G. H., Häner, T., Steiger, D. S., Reiher, M., Roet… — [arXiv:1804.04739](https://arxiv.org/abs/1804.04739) find
208. Byrnes, T. and Yamamoto, Y. “Simulating lattice gauge theories on a quantum computer.” Phys. Rev. A 73 (2006), 022328. arXiv:quant-ph/0510027 (cited on page 61). — [arXiv:quant-ph/0510027](https://arxiv.org/abs/quant-ph/0510027) find
209. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Cade, C. and Crichigno, P. M. “Complexity of supersymmetric systems and the cohomology problem.” arXiv:2107.00011 (2021) (cited on page 185). — [arXiv:2107.00011](https://arxiv.org/abs/2107.00011) find
210. Cade, C., Folkertsma, M., Niesen, I., and Weggemans, J. “Quantifying Grover speed-ups beyond asymptotic analysis.” Quantum 7 (2023), 1133. arXiv:2203.04975 (cited on page 75). — [arXiv:2203.04975](https://arxiv.org/abs/2203.04975) find
211. Cade, C., Folkertsma, M., Niesen, I., and Weggemans, J. “Quantum algorithms for community detection and their empirical run-times.” arXiv:2203.06208 (2022) (cited on page 75). — [arXiv:2203.06208](https://arxiv.org/abs/2203.06208) find
212. Cade, C., Mineh, L., Montanaro, A., and Stanisic, S. “Strategies for solving the Fermi–Hubbard model on near-term quantum computers.” Phys. Rev. B 102 (2020), 235122. arXiv:1912.06007 (cited on pages 13, 18). — [arXiv:1912.06007](https://arxiv.org/abs/1912.06007) find
213. Cai, Z. “Resource estimation for quantum variational simulations of the Hubbard model.” Phys. Rev. Appl. 14 (2020), 014059. arXiv:1910.02719 (cited on page 18). — [arXiv:1910.02719](https://arxiv.org/abs/1910.02719) find
214. Calabrese, P. and Cardy, J. “Evolution of entanglement entropy in one-dimensional systems.” J. Stat. Mech. Theory Exp. (2005), 04010. arXiv:cond-mat/0503393 (cited on page 26). — [arXiv:cond-mat/0503393](https://arxiv.org/abs/cond-mat/0503393) find
215. Calabro, C., Impagliazzo, R., and Paturi, R. “The complexity of satisfiability of small depth circuits.” In: Parameterized and Exact Computation (2009), 75–85 (cited on page 76). find
216. Calderbank, A. R. and Shor, P. W. “Good quantum error-correcting codes exist.” Phys. Rev. A 54 (1996), 1098– 1105. arXiv:quant-ph/9512032 (cited on page 330). — [arXiv:quant-ph/9512032](https://arxiv.org/abs/quant-ph/9512032) find
217. Campbell, E. “Random compiler for fast Hamiltonian simulation.” Phys. Rev. Lett. 123 (2019). arXiv:1811.08017 (cited on pages 42, 229, 230). — [arXiv:1811.08017](https://arxiv.org/abs/1811.08017) find
218. Campbell, E., Khurana, A., and Montanaro, A. “Applying quantum algorithms to constraint satisfaction problems.” Quantum 3 (2019), 167. arXiv:1810.05582 (cited on pages 75, 77, 80, 148). — [arXiv:1810.05582](https://arxiv.org/abs/1810.05582) find
219. Campbell, E. T. “A theory of single-shot error correction for adversarial noise.” Quantum Sci. Technol. 4 (2019), 025006. arXiv:1805.09271 (cited on page 336). — [arXiv:1805.09271](https://arxiv.org/abs/1805.09271) find
220. Campbell, E. T. “Early fault-tolerant simulations of the Hubbard model.” Quantum Sci. Technol. 7 (2021), 015007. arXiv:2012.09238 (cited on pages 12, 14–16, 25, 226). — [arXiv:2012.09238](https://arxiv.org/abs/2012.09238) find
221. Campbell, E. T., Terhal, B. M., and Vuillot, C. “Roads towards fault-tolerant universal quantum computation.” Nature 549 (2017), 172–179. arXiv:1612.07330 (cited on page 331). — [arXiv:1612.07330](https://arxiv.org/abs/1612.07330) find
222. Camps, D., Lin, L., Van Beeumen, R., and Yang, C. “Explicit quantum circuits for block encodings of certain sparse matrices.” SIAM J. Matrix Anal. Appl. 45 (2024), 801–827. arXiv:2203.10236 (cited on page 200). — [arXiv:2203.10236](https://arxiv.org/abs/2203.10236) find
223. Cao, Y., Papageorgiou, A., Petras, I., Traub, J., and Kais, S. “Quantum algorithm and circuit design solving the poisson equation.” New J. Phys. 15 (2013), 013021. arXiv:1207.2485 (cited on page 126). — [arXiv:1207.2485](https://arxiv.org/abs/1207.2485) find
224. Cao, Y., Romero, J., Olson, J. P., et al. “Quantum chemistry in the age of quantum computing.” Chem. Rev. 119 (2019), 10856–10915. arXiv:1812.09976 (cited on page 36). — [arXiv:1812.09976](https://arxiv.org/abs/1812.09976) find
225. Carbone, A., Cipollone, A., Barbieri, C., Rios, A., and Polls, A. “Self-consistent Green’s functions formalism with three-body interactions.” Phys. Rev. C 88 (2013), 054326. arXiv:1310.3688 (cited on pages 67, 69). — [arXiv:1310.3688](https://arxiv.org/abs/1310.3688) find
226. Carena, M., Lamm, H., Li, Y.-Y., and Liu, W. “Lattice renormalization of quantum simulations.” Phys. Rev. D 104 (2021), 094519. arXiv:2107.01166 (cited on page 62). — [arXiv:2107.01166](https://arxiv.org/abs/2107.01166) find
227. Carlson, J., Gandolfi, S., Pederiva, F., Pieper, S. C., Schiavilla, R., Schmidt, K. E., and Wiringa, R. B. “Quantum Monte Carlo methods for nuclear physics.” Rev. Mod. Phys. 87 (2015), 1067. arXiv:1412.3081 (cited on pages 67, 69). — [arXiv:1412.3081](https://arxiv.org/abs/1412.3081) find
228. Carlson, J., Savage, M. J., Gerber, R., et al. Nuclear Physics Exascale Requirements Review: An Office of Science review sponsored jointly by Advanced Scientific Computing Research and Nuclear Physics, June 15–17, 2016, Gaithersburg, Maryland. Tech. rep. OSTI 1906717. U.S. Department of Energy Offic… find
229. Caro, M. C., Gil-Fuster, E., Meyer, J. J., Eisert, J., and Sweke, R. “Encoding-dependent generalization bounds for parametrized quantum circuits.” Quantum 5 (2021), 582. arXiv:2106.03880 (cited on page 189). — [arXiv:2106.03880](https://arxiv.org/abs/2106.03880) find
230. Caro, M. C., Huang, H.-Y., Cerezo, M., Sharma, K., Sornborger, A., Cincio, L., and Coles, P. J. “Generalization in quantum machine learning from few training data.” Nat. Commun. 13 (2022), 4919. arXiv:2111.05292 (cited on page 189). — [arXiv:2111.05292](https://arxiv.org/abs/2111.05292) find
231. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Caro, M. C., Huang, H.-Y., Ezzell, N., Gibbs, J., Sornborger, A. T., Cincio, L., Coles, P. J., and Holmes, Z. “Out-of-distribution generalization for learning quantum dynamics.” Nat. Commun. 14 (2023… — [arXiv:2204.10268](https://arxiv.org/abs/2204.10268) find
232. Carrington Jr, T. “Perspective: computing (ro-)vibrational spectra of molecules with more than four atoms.” J. Chem. Phys. 146 (2017), 120902 (cited on page 55). find
233. Casares, P. A. M., Campos, R., and Martin-Delgado, M. A. “TFermion: a non-Clifford gate cost assessment library of quantum phase estimation algorithms for quantum chemistry.” Quantum 6 (2022), 768. arXiv:2110.05899 (cited on page 44). — [arXiv:2110.05899](https://arxiv.org/abs/2110.05899) find
234. Castryck, W. and Decru, T. “An efficient key recovery attack on SIDH.” In: EUROCRYPT (2023), 423–447. ePrint:2022/975 (cited on page 115). find
235. Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., McClean, J. R., Mitarai, K., Yuan, X., Cincio, L., and Coles, P. J. “Variational quantum algorithms.” Nat. Rev. Phys. (2021), 625–644. arXiv:2012.09265 (cited on pages 192, 300). — [arXiv:2012.09265](https://arxiv.org/abs/2012.09265) find
236. Cerezo, M., Larocca, M., Garcı́a-Martı́n, D., Diaz, N., Braccia, P., Fontana, E., Rudolph, M. S., Bermejo, P., Ijaz, A., Thanasilp, S., et al. “Does provable absence of barren plateaus imply classical simulability? Or, why we need to rethink variational quantum computing.” arXiv:2312.09121 (2023) (c… — [arXiv:2312.09121](https://arxiv.org/abs/2312.09121) find
237. Cerezo, M., Sone, A., Volkoff, T., Cincio, L., and Coles, P. J. “Cost function dependent barren plateaus in shallow parametrized quantum circuits.” Nat. Commun. 12 (2021), 1–12. arXiv:2001.00550 (cited on page 298). — [arXiv:2001.00550](https://arxiv.org/abs/2001.00550) find
238. Cerezo, M., Verdon, G., Huang, H.-Y., Cincio, L., and Coles, P. J. “Challenges and opportunities in quantum machine learning.” Nat. Comput. Sci. 2 (2022), 567–576. arXiv:2303.09491 (cited on pages 157, 192). — [arXiv:2303.09491](https://arxiv.org/abs/2303.09491) find
239. Cerjan, C. Numerical grid methods and their application to Schrödinger’s equation. Springer Science & Business Media (1993) (cited on page 39). find
240. Chakrabarti, S., Childs, A. M., Li, T., and Wu, X. “Quantum algorithms and lower bounds for convex optimization.” Quantum 4 (2020), 221. arXiv:1809.01731 (cited on pages 102, 103, 295). — [arXiv:1809.01731](https://arxiv.org/abs/1809.01731) find
241. Chakrabarti, S., Krishnakumar, R., Mazzola, G., Stamatopoulos, N., Woerner, S., and Zeng, W. J. “A threshold for quantum advantage in derivative pricing.” Quantum 5 (2021), 463. arXiv:2012.03819 (cited on pages 153, 155). — [arXiv:2012.03819](https://arxiv.org/abs/2012.03819) find
242. Chakrabarti, S., Minssen, P., Yalovetzky, R., and Pistoia, M. “Universal quantum speedup for branch-and-bound, branch-and-cut, and tree-search algorithms.” arXiv:2210.03210 (2022) (cited on pages 77, 144, 145, 147). — [arXiv:2210.03210](https://arxiv.org/abs/2210.03210) find
243. Chakraborty, S., Gilyén, A., and Jeffery, S. “The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation.” In: ICALP (2019), 33:1–33:14. arXiv:1804.01973 (cited on pages 127, 161, 196, 202, 247, 278, 282, 287–289). — [arXiv:1804.01973](https://arxiv.org/abs/1804.01973) find
244. Chamberland, C. and Cross, A. W. “Fault-tolerant magic state preparation with flag qubits.” Quantum 3 (2019), 143. arXiv:1811.00566 (cited on page 342). — [arXiv:1811.00566](https://arxiv.org/abs/1811.00566) find
245. Chamberland, C., Goncalves, L., Sivarajah, P., Peterson, E., and Grimberg, S. “Techniques for combining fast local decoders with global decoders under circuit-level noise.” Quantum Sci. Technol. 8 (2023), 045011. arXiv:2208.01178 (cited on page 336). — [arXiv:2208.01178](https://arxiv.org/abs/2208.01178) find
246. Chamberland, C., Noh, K., Arrangoiz-Arriola, P., et al. “Building a fault-tolerant quantum computer using concatenated cat codes.” PRX Quantum 3 (2022), 010329. arXiv:2012.04108 (cited on page 342). — [arXiv:2012.04108](https://arxiv.org/abs/2012.04108) find
247. Chan, G. K.-L. “Spiers memorial lecture: quantum chemistry, classical heuristics, and quantum advantage.” Faraday Discuss. 254 (2024), 11–52. arXiv:2407.11235 (cited on page 47). — [arXiv:2407.11235](https://arxiv.org/abs/2407.11235) find
248. Chan, H. H. S., Meister, R., Jones, T., Tew, D. P., and Benjamin, S. C. “Grid-based methods for chemistry simulations on a quantum computer.” Sci. Adv. 9 (2023), eabo7484. arXiv:2202.05864 (cited on page 39). — [arXiv:2202.05864](https://arxiv.org/abs/2202.05864) find
249. Chao, R., Ding, D., Gilyén, A., Huang, C., and Szegedy, M. “Finding angles for quantum signal processing with machine precision.” arXiv:2003.02831 (2020) (cited on pages 209, 214, 218, 237). — [arXiv:2003.02831](https://arxiv.org/abs/2003.02831) find
250. Chao, R. and Reichardt, B. W. “Flag fault-tolerant error correction for any stabilizer code.” PRX Quantum 1 (2020). arXiv:1912.09549 (cited on page 330). — [arXiv:1912.09549](https://arxiv.org/abs/1912.09549) find
251. Chen, C.-F. and Brandão, F. G. S. L. “Average-case speedup for product formulas.” Commun. Math. Phys. 405 (2024), 32. arXiv:2111.05324 (cited on page 226). — [arXiv:2111.05324](https://arxiv.org/abs/2111.05324) find
252. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Chen, C.-F. and Brandão, F. G. S. L. “Fast thermalization from the eigenstate thermalization hypothesis.” arXiv:2112.07646 (2021) (cited on pages 32, 259, 261). — [arXiv:2112.07646](https://arxiv.org/abs/2112.07646) find
253. Chen, C.-F., Huang, H.-Y., Kueng, R., and Tropp, J. A. “Concentration for random product formulas.” PRX Quantum 2 (2021). arXiv:2008.11751 (cited on pages 229, 230). — [arXiv:2008.11751](https://arxiv.org/abs/2008.11751) find
254. Chen, C.-F., Kastoryano, M. J., Brandão, F. G. S. L., and Gilyén, A. “Quantum thermal state preparation.” arXiv:2303.18224 (2023) (cited on pages 32, 43, 245, 247, 259, 261, 262). — [arXiv:2303.18224](https://arxiv.org/abs/2303.18224) find
255. Chen, C.-F., Kastoryano, M. J., and Gilyén, A. “An efficient and exact noncommutative quantum Gibbs sampler.” arXiv:2311.09207 (2023) (cited on pages 247, 259, 261, 262). — [arXiv:2311.09207](https://arxiv.org/abs/2311.09207) find
256. Chen, C.-F., Lucas, A., and Yin, C. “Speed limits and locality in many-body quantum dynamics.” Rep. Prog. Phys. 86 (2023), 116001. arXiv:2303.07386 (cited on page 23). — [arXiv:2303.07386](https://arxiv.org/abs/2303.07386) find
257. Chen, J., Stoudenmire, E., and White, S. R. “Quantum Fourier transform has small entanglement.” PRX Quantum 4 (2023), 040318. arXiv:2210.08468 (cited on page 241). — [arXiv:2210.08468](https://arxiv.org/abs/2210.08468) find
258. Chen, L., Jordan, S., Liu, Y.-K., Moody, D., Peralta, R., Perlner, R., and Smith-Tone, D. Report on Post-Quantum Cryptography. Tech. rep. NISTIR 8105. National Institute of Standards and Technology (2016) (cited on page 115). find
259. Chen, M.-H., Yu, C.-H., Gao, J.-L., Yu, K., Lin, S., Guo, G.-D., and Li, J. “Quantum algorithm for Gaussian process regression.” Phys. Rev. A 106 (2022), 012406. arXiv:2106.06701 (cited on page 161). — [arXiv:2106.06701](https://arxiv.org/abs/2106.06701) find
260. Chen, S., Cotler, J., Huang, H.-Y., and Li, J. “Exponential separations between learning with and without quantum memory.” In: FOCS (2022), 574–585. arXiv:2111.05881 (cited on page 192). — [arXiv:2111.05881](https://arxiv.org/abs/2111.05881) find
261. Chen, Y., Gilyén, A., and de Wolf, R. “A quantum speed-up for approximating the top eigenvectors of a matrix.” In: SODA (2025). Accepted, arXiv:2405.14765 (cited on page 306). — [arXiv:2405.14765](https://arxiv.org/abs/2405.14765) find
262. Chen, Y. and de Wolf, R. “Quantum algorithms and lower bounds for linear regression with norm constraints.” In: ICALP (2023), 38:1–38:21. arXiv:2110.13086 (cited on page 290). — [arXiv:2110.13086](https://arxiv.org/abs/2110.13086) find
263. Chen, Z.-Y., Xue, C., Chen, S.-M., Lu, B.-H., Wu, Y.-C., Ding, J.-C., Huang, S.-H., and Guo, G.-P. “Quantum approach to accelerate finite volume method on steady computational fluid dynamics problems.” Quantum Inf. Process. 21 (2022), 137. arXiv:2102.03557 (cited on page 123). — [arXiv:2102.03557](https://arxiv.org/abs/2102.03557) find
264. Chen, Z.-Y., Xue, C., Sun, T.-P., Liu, H.-Y., Zhuang, X.-N., Dou, M.-H., Zou, T.-R., Fang, Y., Wu, Y.-C., and Guo, G.-P. “An efficient and error-resilient protocol for quantum random access memory with generalized data size.” arXiv:2303.05207 (2023) (cited on page 272). — [arXiv:2303.05207](https://arxiv.org/abs/2303.05207) find
265. Chepurko, N., Clarkson, K., Horesh, L., Lin, H., and Woodruff, D. “Quantum-inspired algorithms from randomized numerical linear algebra.” In: ICML (2022), 3879–3900. arXiv:2011.04125 (cited on page 166). — [arXiv:2011.04125](https://arxiv.org/abs/2011.04125) find
266. Chia, N.-H., Gilyén, A. P., Li, T., Lin, H.-H., Tang, E., and Wang, C. “Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning.” J. ACM 69 (2022), 1–72. Earlier version in STOC’20 . arXiv:1910.06151 (cited on pages 159, 160, 162, 164–167, 289). — [arXiv:1910.06151](https://arxiv.org/abs/1910.06151) find
267. Chiang, C.-F. and Wocjan, P. “Quantum algorithm for preparing thermal Gibbs states-detailed analysis.” In: Quantum Cryptography and Computing (2010), 138–147. arXiv:1001.1130 (cited on page 260). — [arXiv:1001.1130](https://arxiv.org/abs/1001.1130) find
268. Chiesa, A., Tacchino, F., Grossi, M., Santini, P., Tavernelli, I., Gerace, D., and Carretta, S. “Quantum hardware simulating four-dimensional inelastic neutron scattering.” Nat. Phys. 15 (2019), 455–459. arXiv:1809.07974 (cited on page 22). — [arXiv:1809.07974](https://arxiv.org/abs/1809.07974) find
269. Childs, A., Jao, D., and Soukharev, V. “Constructing elliptic curve isogenies in quantum subexponential time.” J. Math. Cryptol. 8 (2014), 1–29. arXiv:1012.4019 (cited on page 115). — [arXiv:1012.4019](https://arxiv.org/abs/1012.4019) find
270. Childs, A. M. “On the relationship between continuous- and discrete-time quantum walk.” Commun. Math. Phys. 294 (2010), 581–603. arXiv:0810.0312 (cited on page 222). — [arXiv:0810.0312](https://arxiv.org/abs/0810.0312) find
271. Childs, A. M. Lecture notes on quantum algorithms. https://cs.umd.edu/~amchilds/qa/, accessed: 2024-12-01. (2022) (cited on pages 252, 347). ↗
272. Childs, A. M. and van Dam, W. “Quantum algorithms for algebraic problems.” Rev. Mod. Phys. 82 (2010), 1–52. arXiv:0812.0380 (cited on pages 112, 241). — [arXiv:0812.0380](https://arxiv.org/abs/0812.0380) find
273. Childs, A. M. and Kothari, R. “Simulating sparse Hamiltonians with star decompositions.” In: TQC (2011), 94–103. arXiv:1003.3683 (cited on pages 225, 229, 233). — [arXiv:1003.3683](https://arxiv.org/abs/1003.3683) find
274. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Childs, A. M., Kothari, R., and Somma, R. D. “Quantum algorithm for systems of linear equations with exponentially improved dependence on precision.” SIAM J. Comp. 46 (2017), 1920–1950. arXiv:1511.02… — [arXiv:1511.02306](https://arxiv.org/abs/1511.02306) find
275. Childs, A. M., Leng, J., Li, T., Liu, J.-P., and Zhang, C. “Quantum simulation of real-space dynamics.” Quantum 6 (2022), 860. arXiv:2203.17006 (cited on pages 39, 106). — [arXiv:2203.17006](https://arxiv.org/abs/2203.17006) find
276. Childs, A. M. and Liu, J.-P. “Quantum spectral methods for differential equations.” Commun. Math. Phys. 375 (2020), 1427–1457. arXiv:1901.00961 (cited on page 127). — [arXiv:1901.00961](https://arxiv.org/abs/1901.00961) find
277. Childs, A. M., Liu, J.-P., and Ostrander, A. “High-precision quantum algorithms for partial differential equations.” Quantum 5 (2021), 574. arXiv:2002.07868 (cited on page 126). — [arXiv:2002.07868](https://arxiv.org/abs/2002.07868) find
278. Childs, A. M., Maslov, D., Nam, Y., Ross, N. J., and Su, Y. “Toward the first quantum simulation with quantum speedup.” Proc. Natl. Acad. Sci. 115 (2018), 9456–9461. arXiv:1711.10980 (cited on pages 25, 26, 200, 206, 226, 233, 234, 237, 238). — [arXiv:1711.10980](https://arxiv.org/abs/1711.10980) find
279. Childs, A. M., Ostrander, A., and Su, Y. “Faster quantum simulation by randomization.” Quantum 3 (2019), 182. arXiv:1805.08385 (cited on page 226). — [arXiv:1805.08385](https://arxiv.org/abs/1805.08385) find
280. Childs, A. M. and Su, Y. “Nearly optimal lattice simulation by product formulas.” Phys. Rev. Lett. 123 (2019), 050503. arXiv:1901.00564 (cited on pages 13, 24). — [arXiv:1901.00564](https://arxiv.org/abs/1901.00564) find
281. Childs, A. M., Su, Y., Tran, M. C., Wiebe, N., and Zhu, S. “Theory of Trotter error with commutator scaling.” Phys. Rev. X 11 (2021). arXiv:1912.08854 (cited on pages 24, 25, 224–226). — [arXiv:1912.08854](https://arxiv.org/abs/1912.08854) find
282. Childs, A. M. and Wiebe, N. “Hamiltonian simulation using linear combinations of unitary operations.” Quantum Inf. Comput. 12 (2012), 901–924. arXiv:1202.5822 (cited on pages 196, 200, 205). — [arXiv:1202.5822](https://arxiv.org/abs/1202.5822) find
283. Cho, C. H., Berry, D. W., and Hsieh, M.-H. “Doubling the order of approximation via the randomized product formula.” arXiv:2210.11281 (2022) (cited on page 226). — [arXiv:2210.11281](https://arxiv.org/abs/2210.11281) find
284. Chowdhury, A. N. and Somma, R. D. “Quantum algorithms for Gibbs sampling and hitting-time estimation.” Quantum Inf. Comput. 17 (2017), 41–64. arXiv:1603.02940 (cited on pages 260, 261). — [arXiv:1603.02940](https://arxiv.org/abs/1603.02940) find
285. Chowdhury, A. N., Somma, R. D., and Subaşı, Y. “Computing partition functions in the one-clean-qubit model.” Phys. Rev. A 103 (2021), 032422. arXiv:1910.11842 (cited on page 324). — [arXiv:1910.11842](https://arxiv.org/abs/1910.11842) find
286. Chubb, C. T. “General tensor network decoding of 2D Pauli codes.” arXiv:2101.04125 (2021) (cited on page 335). — [arXiv:2101.04125](https://arxiv.org/abs/2101.04125) find
287. Ciavarella, A., Klco, N., and Savage, M. J. “Trailhead for quantum simulation of SU(3) Yang–Mills lattice gauge theory in the local multiplet basis.” Phys. Rev. D 103 (2021), 094501. arXiv:2101.10227 (cited on pages 61, 62). — [arXiv:2101.10227](https://arxiv.org/abs/2101.10227) find
288. Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., and Wossnig, L. “Quantum machine learning: A classical perspective.” Proc. R. Soc. A 474 (2018), 20170551. arXiv:1707.08561 (cited on pages 157, 167, 274). — [arXiv:1707.08561](https://arxiv.org/abs/1707.08561) find
289. Cirstoiu, C., Holmes, Z., Iosue, J., Cincio, L., Coles, P. J., and Sornborger, A. “Variational fast forwarding for quantum simulation beyond the coherence time.” npj Quant. Inf. 6 (2020), 82. arXiv:1910.04292 (cited on page 299). — [arXiv:1910.04292](https://arxiv.org/abs/1910.04292) find
290. Clader, B. D., Dalzell, A. M., Stamatopoulos, N., Salton, G., Berta, M., and Zeng, W. J. “Quantum resources required to block-encode a matrix of classical data.” IEEE Trans. Quantum Eng. 3 (2022), 1–23. arXiv:2206.03505 (cited on pages 146, 201, 283, 284, 288). — [arXiv:2206.03505](https://arxiv.org/abs/2206.03505) find
291. Clader, B. D., Jacobs, B. C., and Sprouse, C. R. “Preconditioned quantum linear system algorithm.” Phys. Rev. Lett. 110 (2013), 250504. arXiv:1301.2340 (cited on pages 123, 125, 129, 132, 290). — [arXiv:1301.2340](https://arxiv.org/abs/1301.2340) find
292. Cleve, R., Ekert, A., Macchiavello, C., and Mosca, M. “Quantum algorithms revisited.” Proc. R. Soc. A 454 (1998), 339–354. arXiv:quant-ph/9708016 (cited on pages 243, 247). — [arXiv:quant-ph/9708016](https://arxiv.org/abs/quant-ph/9708016) find
293. Cleve, R. and Wang, C. “Efficient quantum algorithms for simulating Lindblad evolution.” In: ICALP (2017), 17:1–17:14. arXiv:1612.09512 (cited on page 253). — [arXiv:1612.09512](https://arxiv.org/abs/1612.09512) find
294. Cleve, R. and Watrous, J. “Fast parallel circuits for the quantum Fourier transform.” In: FOCS (2000), 526–536. arXiv:quant-ph/0006004 (cited on page 112). — [arXiv:quant-ph/0006004](https://arxiv.org/abs/quant-ph/0006004) find
295. Clinton, L., Bausch, J., and Cubitt, T. “Hamiltonian simulation algorithms for near-term quantum hardware.” Nat. Commun. 12 (2021), 4989. arXiv:2003.06886 (cited on pages 13, 14, 18). — [arXiv:2003.06886](https://arxiv.org/abs/2003.06886) find
296. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Clinton, L., Cubitt, T., Flynn, B., Gambetta, F. M., Klassen, J., Montanaro, A., Piddock, S., Santos, R. A., and Sheridan, E. “Towards near-term quantum simulation of materials.” Nat. Commun. 15 (202… — [arXiv:2205.15256](https://arxiv.org/abs/2205.15256) find
297. Coecke, B. and Kissinger, A. Picturing Quantum Processes. Cambridge University Press (2017) (cited on page 344). find
298. Cohen, L. Z., Kim, I. H., Bartlett, S. D., and Brown, B. J. “Low-overhead fault-tolerant quantum computing using long-range connectivity.” Sci. Adv. 8 (2022) (cited on page 343). find
299. Cohen, M. B., Lee, Y. T., and Song, Z. “Solving linear programs in the current matrix multiplication time.” J. ACM 68 (2021). arXiv:1810.07896 (cited on pages 92, 94, 98). — [arXiv:1810.07896](https://arxiv.org/abs/1810.07896) find
300. Commeau, B., Cerezo, M., Holmes, Z., Cincio, L., Coles, P. J., and Sornborger, A. “Variational Hamiltonian diagonalization for dynamical quantum simulation.” arXiv:2009.02559 (2020) (cited on page 299). — [arXiv:2009.02559](https://arxiv.org/abs/2009.02559) find
301. Cong, I., Choi, S., and Lukin, M. D. “Quantum convolutional neural networks.” Nat. Phys. 15 (2019), 1273–1278. arXiv:1810.03787 (cited on page 300). — [arXiv:1810.03787](https://arxiv.org/abs/1810.03787) find
302. Coppersmith, D., Gamarnik, D., Hajiaghayi, M., and Sorkin, G. B. “Random MAX SAT, random MAX CUT, and their phase transitions.” Rand. Struct. Algorithms 24 (2004), 502–545. Earlier version in SODA’03. arXiv:math/0306047 (cited on page 81). — [arXiv:math/0306047](https://arxiv.org/abs/math/0306047) find
303. Cornelissen, A. and Hamoudi, Y. “A sublinear-time quantum algorithm for approximating partition functions.” In: SODA (2023), 1245–1264. arXiv:2207.08643 (cited on page 256). — [arXiv:2207.08643](https://arxiv.org/abs/2207.08643) find
304. Cornelissen, A., Hamoudi, Y., and Jerbi, S. “Near-optimal quantum algorithms for multivariate mean estimation.” In: STOC (2022), 33–43. arXiv:2111.09787 (cited on pages 96, 257, 312). — [arXiv:2111.09787](https://arxiv.org/abs/2111.09787) find
305. Cornelissen, A. and Jerbi, S. “Quantum algorithms for multivariate Monte Carlo estimation.” arXiv:2107.03410 (2021) (cited on page 153). — [arXiv:2107.03410](https://arxiv.org/abs/2107.03410) find
306. Cornuejols, G. and Tütüncü, R. Optimization methods in finance. Cambridge University Press (2006) (cited on page 145). find
307. Costa, P. C., Jordan, S., and Ostrander, A. “Quantum algorithm for simulating the wave equation.” Phys. Rev. A 99 (2019), 012323 (cited on page 127). find
308. Costa, P. C., An, D., Sanders, Y. R., Su, Y., Babbush, R., and Berry, D. W. “Optimal scaling quantum linear-systems solver via discrete adiabatic theorem.” PRX Quantum 3 (2022), 040303. arXiv:2111.08152 (cited on pages 127, 132, 146, 267, 287, 288, 290). — [arXiv:2111.08152](https://arxiv.org/abs/2111.08152) find
309. Costa, P. C. S., An, D., Babbush, R., and Berry, D. “The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver.” arXiv:2312.07690 (2023) (cited on pages 287, 288). — [arXiv:2312.07690](https://arxiv.org/abs/2312.07690) find
310. Costa, P. C. S., Schleich, P., Morales, M. E. S., and Berry, D. W. “Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling.” arXiv:2312.09518 (2023) (cited on pages 130, 131). — [arXiv:2312.09518](https://arxiv.org/abs/2312.09518) find
311. Cotler, J. S., Gur-Ari, G., Hanada, M., Polchinski, J., Saad, P., Shenker, S. H., Stanford, D., Streicher, A., and Tezuka, M. “Black holes and random matrices.” J. High Energy Phys. 2017 (2017), 1–54. arXiv:1611.04650 (cited on pages 31, 33). — [arXiv:1611.04650](https://arxiv.org/abs/1611.04650) find
312. Cramer, M., Plenio, M. B., Flammia, S. T., Somma, R., Gross, D., Bartlett, S. D., Landon-Cardinal, O., Poulin, D., and Liu, Y.-K. “Efficient quantum state tomography.” Nat. Commun. 1 (2010), 149. arXiv:1101.4366 (cited on page 305). — [arXiv:1101.4366](https://arxiv.org/abs/1101.4366) find
313. Cramer, R., Ducas, L., and Wesolowski, B. “Short Stickelberger class relations and application to Ideal-SVP.” In: EUROCRYPT (2017), 324–348. ePrint:2016/885 (cited on page 115). find
314. Crichigno, M. and Kohler, T. “Clique homology is QMA1-hard.” arXiv:2209.11793 (2022) (cited on page 185). — [arXiv:2209.11793](https://arxiv.org/abs/2209.11793) find
315. Criger, B. and Ashraf, I. “Multi-path summation for decoding 2d topological codes.” Quantum 2 (2018), 102. arXiv:1709.02154 (cited on page 335). — [arXiv:1709.02154](https://arxiv.org/abs/1709.02154) find
316. Crooks, G. E. “Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition.” arXiv:1905.13311 (2019) (cited on page 298). — [arXiv:1905.13311](https://arxiv.org/abs/1905.13311) find
317. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Crosson, E. and Harrow, A. W. “Simulated quantum annealing can be exponentially faster than classical simulated annealing.” In: FOCS (2016), 714–723. arXiv:1601.03030 (cited on page 84). — [arXiv:1601.03030](https://arxiv.org/abs/1601.03030) find
318. Crosson, E. and Lidar, D. “Prospects for quantum enhancement with diabatic quantum annealing.” Nat. Rev. Phys. 3 (2021), 466–489. arXiv:2008.09913 (cited on page 267). — [arXiv:2008.09913](https://arxiv.org/abs/2008.09913) find
319. Crosson, E. and Slezak, S. “Classical simulation of high temperature quantum Ising models.” arXiv:2002.02232 (2020) (cited on page 84). — [arXiv:2002.02232](https://arxiv.org/abs/2002.02232) find
320. Cunningham, J. and Roland, J. “Eigenpath traversal by poisson-distributed phase randomisation.” arXiv:2406.03972 (2024) (cited on pages 288, 290). — [arXiv:2406.03972](https://arxiv.org/abs/2406.03972) find
321. Daley, A. J., Bloch, I., Kokail, C., Flannigan, S., Pearson, N., Troyer, M., and Zoller, P. “Practical quantum advantage in quantum simulation.” Nature 607 (2022), 667–676 (cited on pages 17, 18). find
322. Dalzell, A. M. “A shortcut to an optimal quantum linear system solver.” arXiv:2406.12086 (2024) (cited on pages 97, 127, 132, 146, 161, 288–290). — [arXiv:2406.12086](https://arxiv.org/abs/2406.12086) find
323. Dalzell, A. M., Clader, B. D., Salton, G., Berta, M., Lin, C. Y.-Y., Bader, D. A., Stamatopoulos, N., Schuetz, M. J. A., Brandão, F. G. S. L., Katzgraber, H. G., and Zeng, W. J. “End-to-end resource analysis for quantum interior-point methods and portfolio optimization.” PRX Quantum 4 (2023), 04032… — [arXiv:2211.12489](https://arxiv.org/abs/2211.12489) find
324. Dalzell, A. M., McArdle, S., Berta, M., et al. Quantum Algorithms: A Survey of Applications and End-to-end Complexities. Cambridge University Press (2025). arXiv:2310.03011 (cited on page 6). — [arXiv:2310.03011](https://arxiv.org/abs/2310.03011) find
325. Dalzell, A. M., Pancotti, N., Campbell, E. T., and Brandão, F. G. “Mind the gap: achieving a super-Grover quantum speedup by jumping to the end.” In: STOC (2023), 1131–1144. arXiv:2212.01513 (cited on pages 72, 80, 83–85, 247). — [arXiv:2212.01513](https://arxiv.org/abs/2212.01513) find
326. Damm, C., Holzer, M., and McKenzie, P. “The complexity of tensor calculus.” Comput. Complex. 11 (2002), 54–89 (cited on page 322). find
327. Darmawan, A. S. and Poulin, D. “Tensor-network simulations of the surface code under realistic noise.” Phys. Rev. Lett. 119 (2017), 040502. arXiv:1607.06460 (cited on page 335). — [arXiv:1607.06460](https://arxiv.org/abs/1607.06460) find
328. Davoudi, Z., Detmold, W., Shanahan, P., Orginos, K., Parreno, A., Savage, M. J., and Wagman, M. L. “Nuclear matrix elements from lattice QCD for electroweak and beyond-Standard-Model processes.” Phys. Rep. 900 (2021), 1–74 (cited on pages 60, 67). find
329. Davoudi, Z., Neil, E. T., Bauer, C. W., Bhattacharya, T., Blum, T., Boyle, P., Brower, R. C., Catterall, S., Christ, N. H., Cirigliano, V., et al. “Report of the Snowmass 2021 topical group on lattice gauge theory.” Proceedings of the US Community Study on the Future of Particle Physics (Snowmass 20… — [arXiv:2209.10758](https://arxiv.org/abs/2209.10758) find
330. Davoudi, Z., Shaw, A. F., and Stryker, J. R. “General quantum algorithms for Hamiltonian simulation with applications to a non-abelian lattice gauge theory.” Quantum 7 (2023), 1213. arXiv:2212.14030 (cited on pages 61, 62). — [arXiv:2212.14030](https://arxiv.org/abs/2212.14030) find
331. De Palma, G., Marvian, M., Rouzé, C., and França, D. S. “Limitations of variational quantum algorithms: a quantum optimal transport approach.” PRX Quantum 4 (2023), 010309. arXiv:2204.03455 (cited on page 298). — [arXiv:2204.03455](https://arxiv.org/abs/2204.03455) find
332. Dean, D. J. “Beyond the nuclear shell model.” Phys. Today 60 (2007), 48–53 (cited on page 67). find
333. Delfosse, N. and Nickerson, N. H. “Almost-linear time decoding algorithm for topological codes.” Quantum 5 (2021), 595. arXiv:1709.06218 (cited on page 335). — [arXiv:1709.06218](https://arxiv.org/abs/1709.06218) find
334. Delfosse, N., Reichardt, B. W., and Svore, K. M. “Beyond single-shot fault-tolerant quantum error correction.” IEEE Trans. Inf. Theory 68 (2022), 287–301. arXiv:2002.05180 (cited on page 336). — [arXiv:2002.05180](https://arxiv.org/abs/2002.05180) find
335. Delgado, A., Casares, P. A. M., Reis, R. dos, Zini, M. S., Campos, R., Cruz-Hernández, N., Voigt, A.-C., Lowe, A., Jahangiri, S., Martin-Delgado, M. A., Mueller, J. E., and Arrazola, J. M. “Simulating key properties of lithium-ion batteries with a fault-tolerant quantum computer.” Phys. Rev. A 106… — [arXiv:2204.11890](https://arxiv.org/abs/2204.11890) find
336. Delgado, A., Hamilton, K. E., Date, P., et al. “Quantum computing for data analysis in high-energy physics.” arXiv:2203.08805 (2022) (cited on page 59). — [arXiv:2203.08805](https://arxiv.org/abs/2203.08805) find
337. Deng, C., Sun, F., Qian, X., Lin, J., Wang, Z., and Yuan, B. “TIE: energy-efficient tensor train-based inference engine for deep neural network.” In: ISCA (2019), 264–278 (cited on page 324). find
338. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Dennis, E., Kitaev, A., Landahl, A., and Preskill, J. “Topological quantum memory.” J. Math. Phys. 43 (2002), 4452–4505. arXiv:quant-ph/0110143 (cited on pages 328, 334–337). — [arXiv:quant-ph/0110143](https://arxiv.org/abs/quant-ph/0110143) find
339. Derby, C., Klassen, J., Bausch, J., and Cubitt, T. “Compact fermion to qubit mappings.” Phys. Rev. B 104 (2021), 035118. arXiv:2003.06939 (cited on page 12). — [arXiv:2003.06939](https://arxiv.org/abs/2003.06939) find
340. Derrida, B. “Random-energy model: limit of a family of disordered models.” Phys. Rev. Lett. 45 (1980), 79–82 (cited on pages 23, 81). find
341. Deutsch, D. “Quantum theory, the Church–Turing principle and the universal quantum computer.” Proc. R. Soc. A 400 (1985), 97–117 (cited on page 4). find
342. Deutsch, D. and Jozsa, R. “Rapid solution of problems by quantum computation.” Proc. R. Soc. A 439 (1992), 553–558 (cited on page 4). find
343. Devoret, M. H. and Schoelkopf, R. J. “Superconducting circuits for quantum information: An outlook.” Science 339 (2013), 1169–1174 (cited on page 334). find
344. Di Matteo, O., Gheorghiu, V., and Mosca, M. “Fault-tolerant resource estimation of quantum random-access memories.” IEEE Trans. Quantum Eng. 1 (2020), 1–13. arXiv:1902.01329 (cited on pages 271, 272, 288). — [arXiv:1902.01329](https://arxiv.org/abs/1902.01329) find
345. DiVincenzo, D. P. and Aliferis, P. “Effective fault-tolerant quantum computation with slow measurements.” Phys. Rev. Lett. 98 (2007) (cited on page 330). find
346. Ding, C., Bao, T.-Y., and Huang, H.-L. “Quantum-inspired support vector machine.” IEEE Trans. Neural Netw. Learn. Syst. 33 (2022), 7210–7222. arXiv:1906.08902 (cited on page 164). — [arXiv:1906.08902](https://arxiv.org/abs/1906.08902) find
347. Ding, Z., Chen, C.-F., and Lin, L. “Single-ancilla ground state preparation via Lindbladians.” Phys. Rev. Res. 6 (2024), 033147. arXiv:2308.15676 (cited on pages 43, 262). — [arXiv:2308.15676](https://arxiv.org/abs/2308.15676) find
348. Dinur, I., Evra, S., Livne, R., Lubotzky, A., and Mozes, S. “Locally testable codes with constant rate, distance, and locality.” In: STOC (2022), 357–374. arXiv:2111.04808 (cited on page 330). — [arXiv:2111.04808](https://arxiv.org/abs/2111.04808) find
349. Dodin, I. Y. and Startsev, E. A. “On applications of quantum computing to plasma simulations.” Phys. Plasmas 28 (2021), 092101. arXiv:2005.14369 (cited on pages 123, 131). — [arXiv:2005.14369](https://arxiv.org/abs/2005.14369) find
350. Domahidi, A., Chu, E., and Boyd, S. “ECOS: an SOCP solver for embedded systems.” In: ECC (2013), 3071–3076 (cited on pages 98, 310). find
351. Dong, Y., Gross, J., and Niu, M. Y. “Beyond Heisenberg limit quantum metrology through quantum signal processing.” arXiv:2209.11207 (2022) (cited on page 210). — [arXiv:2209.11207](https://arxiv.org/abs/2209.11207) find
352. Dong, Y., Lin, L., and Tong, Y. “Ground-state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices.” PRX Quantum 3 (2022), 040305. arXiv:2204.05955 (cited on page 41). — [arXiv:2204.05955](https://arxiv.org/abs/2204.05955) find
353. Dong, Y., Lin, L., Ni, H., and Wang, J. “Infinite quantum signal processing.” arXiv:2209.10162 (2022) (cited on pages 209, 218). — [arXiv:2209.10162](https://arxiv.org/abs/2209.10162) find
354. Dong, Y., Lin, L., Ni, H., and Wang, J. “Robust iterative method for symmetric quantum signal processing in all parameter regimes.” arXiv:2307.12468 (2023) (cited on pages 209, 218). — [arXiv:2307.12468](https://arxiv.org/abs/2307.12468) find
355. Dong, Y., Meng, X., Whaley, K. B., and Lin, L. “Efficient phase-factor evaluation in quantum signal processing.” Phys. Rev. A 103 (2021), 042419. arXiv:2002.11649 (cited on pages 209, 214, 216–218, 237, 288). — [arXiv:2002.11649](https://arxiv.org/abs/2002.11649) find
356. Doriguello, J. F., Luongo, A., Bao, J., Rebentrost, P., and Santha, M. “Quantum algorithm for stochastic optimal stopping problems with applications in finance.” In: TQC (2022), 2:1–2:24. arXiv:2111.15332 (cited on pages 153, 257). — [arXiv:2111.15332](https://arxiv.org/abs/2111.15332) find
357. Du, Y., Hsieh, M.-H., Liu, T., and Tao, D. “Expressive power of parametrized quantum circuits.” Phys. Rev. Res. 2 (2020), 033125. arXiv:1810.11922 (cited on page 300). — [arXiv:1810.11922](https://arxiv.org/abs/1810.11922) find
358. Dua, A., Kubica, A., Jiang, L., Flammia, S. T., and Gullans, M. J. “Clifford-deformed surface codes.” PRX Quantum 5 (2024). arXiv:2201.07802 (cited on page 336). — [arXiv:2201.07802](https://arxiv.org/abs/2201.07802) find
359. Duclos-Cianci, G. and Poulin, D. “Fast decoders for topological quantum codes.” Phys. Rev. Lett. 104 (2010), 050504. arXiv:0911.0581 (cited on page 335). — [arXiv:0911.0581](https://arxiv.org/abs/0911.0581) find
360. Dukalski, M. “Toward an application of quantum computing in geophysics.” In: Fifth EAGE Workshop on High Performance Computing for Upstream (2021), 1–5 (cited on page 123). find
361. Quantum algorithms: A survey of applications and end-to-end complexities ▷ Consolidated bibliography Dumitrescu, E. F., McCaskey, A. J., Hagen, G., Jansen, G. R., Morris, T. D., Papenbrock, T., Pooser, R. C., Dean, D. J., and Lougovski, P. “Cloud quantum computing of an atomic nucleus.” Phys. Rev. L… — [arXiv:1801.03897](https://arxiv.org/abs/1801.03897) find
362. Dürr, C., Heiligman, M., Høyer, P., and Mhalla, M. “Quantum query complexity of some graph problems.” SIAM J. Comp. 35 (2006), 1310–1328. Earlier version in ICALP’04 . arXiv:quant-ph/0401091 (cited on page 76). — [arXiv:quant-ph/0401091](https://arxiv.org/abs/quant-ph/0401091) find
363. Dürr, C. and Høyer, P. “A quantum algorithm for finding the minimum.” arXiv:quant-ph/9607014 (1996) (cited on pages 74, 96). — [arXiv:quant-ph/9607014](https://arxiv.org/abs/quant-ph/9607014) find
364. Dürr, S., Fodor, Z., Frison, J., Hoelbling, C., Hoffmann, R., Katz, S. D., Krieg, S., Kurth, T., Lellouch, L., Lippert, T., Szabo, K. K., and Vulvert, G. “Ab initio determination of light hadron masses.” Science 322 (2008), 1224–1227. arXiv:0906.3599 (cited on page 67). — [arXiv:0906.3599](https://arxiv.org/abs/0906.3599) find
365. Eastin, B. and Knill, E. “Restrictions on transversal encoded quantum gate sets.” Phys. Rev. Lett. 102 (2009), 110502. arXiv:0811.4262 (cited on pages 330, 343). — [arXiv:0811.4262](https://arxiv.org/abs/0811.4262) find
366. Ebadi, S., Wang, T. T., Levine, H., et al. “Quantum phases of matter on a 256-atom programmable quantum simulator.” Nature 595 (2021), 227. arXiv:2012.12281 (cited on page 27). — [arXiv:2012.12281](https://arxiv.org/abs/2012.12281) find
367. Edmonds, J. “Paths, trees, and flowers.” Can. J. Math. 17 (1965), 449–467 (cited on page 335). find
368. Elben, A., Flammia, S. T., Huang, H.-Y., Kueng, R., Preskill, J., Vermersch, B., and Zoller, P. “The randomized measurement toolbox.” Nat. Rev. Phys. 5 (2023), 9–24. arXiv:2203.11374 (cited on pages 307, 308). — [arXiv:2203.11374](https://arxiv.org/abs/2203.11374) find
369. Elenewski, J. E., Camara, C. M., and Kalev, A. “Prospects for NMR spectral prediction on fault-tolerant quantum computers.” arXiv:2406.09340 (2024) (cited on pages 23, 26). — [arXiv:2406.09340](https://arxiv.org/abs/2406.09340) find
370. Elfving, V. E., Broer, B. W., Webber, M., Gavartin, J., Halls, M. D., Lorton, K. P., and Bochevarov, A. “How will quantum computers provide an industrially relevant computational advantage in quantum chemistry?” arXiv:2009.12472 (2020) (cited on page 44). — [arXiv:2009.12472](https://arxiv.org/abs/2009.12472) find
371. Elgart, A. and Hagedorn, G. A. “A note on the switching adiabatic theorem.” J. Math. Phys. 53 (2012), 102202. arXiv:1204.2318 (cited on page 266). — [arXiv:1204.2318](https://arxiv.org/abs/1204.2318) find
372. Engel, A., Smith, G., and Parker, S. E. “Quantum algorithm for the Vlasov equation.” Phys. Rev. A 100 (2019), 062315. arXiv:1907.09418 (cited on page 123). — [arXiv:1907.09418](https://arxiv.org/abs/1907.09418) find
373. Engineering, S. and (SEAR), A. iMessage with PQ3: the new state of the art in quantum-secure messaging at scale. https://security.apple.com/blog/imessage-pq3/, accessed: 2024-06-05. ↗
374. Apple (2024) (cited on page 115). find
375. Fang, D., Lin, L., and Tong, Y. “Time-marching based quantum solvers for time-dependent linear differential equations.” Quantum 7 (2023), 955. arXiv:2208.06941 (cited on pages 127, 129, 204). — [arXiv:2208.06941](https://arxiv.org/abs/2208.06941) find

Updated 3 November 2026

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/dalzell-2023-quantum-algorithms-survey-applications-end/