{\rtf1\ansi\deff0\deftab360 {\fonttbl {\f0\fswiss\fcharset0 Arial} {\f1\froman\fcharset0 Times New Roman} {\f2\fswiss\fcharset0 Verdana} {\f3\froman\fcharset2 Symbol} } {\colortbl; \red0\green0\blue0; } {\info {\author Biblio 7.x}{\operator }{\title Biblio RTF Export}} \f1\fs24 \paperw11907\paperh16839 \pgncont\pgndec\pgnstarts1\pgnrestart A. Bapat, Childs, A. M., Gorshkov, A. V., and Schoute, E., ?Advantages and limitations of quantum routing?, PRX Quantum, vol. 4, no. 010313, 2023.\par \par S. Chakrabarti, Childs, A. M., Hung, S. - H., Li, T., Wang, C., and Wu, X., ?Quantum algorithm for estimating volumes of convex bodies?, ACM Transactions on Quantum Computing, vol. 4, 2023.\par \par D. An, Childs, A. M., and Lin, L., ?Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters?, 2023.\par \par A. M. Childs, Coudron, M., and Gilani, A. Shiraz, ?Quantum Algorithms and the Power of Forgetting?, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), vol. 251, p. 37:1--37:22, 2023.\par \par J. D. Watson, Bringewatt, J., Shaw, A. F., Childs, A. M., Gorshkov, A. V., and Davoudi, Z., ?Quantum Algorithms for Simulating Nuclear Effective Field Theories?, 2023.\par \par A. M. Childs, Fu, H., Leung, D., Li, Z., Ozols, M., and Vyas, V., ?Streaming quantum state purification?, 2023.\par \par Y. - A. Chen, Childs, A. M., Hafezi, M., Jiang, Z., Kim, H., and Xu, Y., ?Efficient Product Formulas for Commutators and Applications to Quantum Simulation?, Physical Review Research, vol. 4, 2022.\par \par Q. Zhao, Zhou, Y., Shaw, A. F., Li, T., and Childs, A. M., ?Hamiltonian simulation with random inputs?, Phys. Rev. Lett. 129, 270502, vol. 129, no. 270502, 2022.\par \par A. Y. Guo, Deshpande, A., Chu, S. - K., Eldredge, Z., Bienias, P., Devulapalli, D., Su, Y., Childs, A. M., and Gorshkov, A. V., ?Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions?, Phys. Rev. Research, vol. 4, no. L042016, 2022.\par \par A. M. Childs, Li, T., Liu, J. - P., Wang, C., and Zhang, R., ?Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants?, Advances in Neural Information Processing Systems (NeurIPS 2022), vol. 35, no. 23205, 2022.\par \par A. M. Childs, Kothari, R., Kovacs-Deak, M., Sundaram, A., and Wang, D., ?Quantum divide and conquer?, 2022.\par \par D. Devulapalli, Schoute, E., Bapat, A., Childs, A. M., and Gorshkov, A. V., ?Quantum Routing with Teleportation?, 2022.\par \par A. M. Childs, Leng, J., Li, T., Liu, J. - P., and Zhang, C., ?Quantum simulation of real-space dynamics?, Quantum, vol. 6, p. 860, 2022.\par \par A. W. Young, Eckner, W. J., Schine, N., Childs, A. M., and Kaufman, A. M., ?Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice?, Science, vol. 377, no. 6608, pp. 885-889, 2022.\par \par J. - P. Liu, Kolden, H. \'d8ie, Krovi, H. K., Loureiro, N. F., Trivisa, K., and Childs, A. M., ?Efficient quantum algorithm for dissipative nonlinear differential equations?, Proceedings of the National Academy of Sciences, vol. 118, 2021.\par \par A. M. Childs, Liu, J. - P., and Ostrander, A., ?High-precision quantum algorithms for partial differential equations?, Quantum 5, 574, vol. 5, no. 574, 2021.\par \par D. Wang, You, X., Li, T., and Childs, A. M., ?Quantum exploration algorithms for multi-armed bandits?, Proceedings of the 35th Conference on Artificial Intelligence (AAAI 2021), vol. 35, no. 11, pp. 10102-10110, 2021.\par \par A. M. Childs, Hung, S. - H., and Li, T., ?Quantum query complexity with matrix-vector products?, Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Leibniz International Proceedings in Informatics, vol. 198, pp. 55:1-55:19, 2021.\par \par A. M. Childs, Hung, S. - H., and Li, T., ?Quantum Query Complexity with Matrix-Vector Products?, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 2021.\par \par A. Bapat, Childs, A. M., Gorshkov, A. V., King, S., Schoute, E., and Shastri, H., ?Quantum routing with fast reversals?, Quantum, vol. 5, 2021.\par \par A. M. Childs, Su, Y., Tran, M. C., Wiebe, N., and Zhu, S., ?Theory of Trotter Error with Commutator Scaling?, Phys. Rev. X, vol. 11, no. 1, p. 49, 2021.\par \par A. M. Childs and Wang, D., ?Can graph properties have exponential quantum speedup??, 2020.\par \par M. C. Tran, Chu, S. - K., Su, Y., Childs, A. M., and Gorshkov, A. V., ?Destructive Error Interference in Product-Formula Lattice Simulation?, Phys. Rev. Lett. , vol. 124, no. 220502, 2020.\par \par A. Bapat, Schoute, E., Gorshkov, A. V., and Childs, A. M., ?Nearly optimal time-independent reversal of a spin chain?, accepted for publication in Physical Review Research, 2020.\par \par G. Alagic, Childs, A. M., Grilo, A. B., and Hung, S. - H., ?Non-interactive classical verification of quantum computation?, Theory of Cryptography Conference (TCC), vol. Lecture Notes in Computer Science 12552, pp. 153-180, 2020.\par \par S. Chakrabarti, Childs, A. M., Li, T., and Wu, X., ?Quantum algorithms and lower bounds for convex optimization?, Quantum, vol. 4, no. 221, 2020.\par \par S. Arunachalam, Belovs, A., Childs, A. M., Kothari, R., Rosmanis, A., and de Wolf, R., ?Quantum Coupon Collector?, Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Leibniz International Proceedings in Informatics, vol. 158, pp. 10:1-10:17, 2020.\par \par A. M. Childs and Liu, J. - P., ?Quantum spectral methods for differential equations?, Commun. Math. Phys. , vol. 375, pp. 1427-1457, 2020.\par \par A. Y. Guo, Tran, M. C., Childs, A. M., Gorshkov, A. V., and Gong, Z. - X., ?Signaling and Scrambling with Strongly Long-Range Interactions?, Physical Review A, vol. 102, no. 010401(R), 2020.\par \par S. Ben-David, Childs, A. M., Gilyen, A., Kretschmer, W., Podder, S., and Wang, D., ?Symmetries, graph properties, and quantum speedups?, in Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020), pp. 649?660 (2020), 2020.\par \par D. W. Berry, Childs, A. M., Su, Y., Wang, X., and Wiebe, N., ?Time-dependent Hamiltonian simulation with L1-norm scaling?, Quantum, vol. 4, no. 254, 2020.\par \par A. M. Childs, Schoute, E., and Unsal, C. M., ?Circuit Transformations for Quantum Architectures?, Proceedings of TQC 2019, LIPIcs, vol. 135 , no. 3, 2019.\par \par A. M. Childs, Ostrander, A., and Su, Y., ?Faster quantum simulation by randomization?, Quantum , vol. 3, no. 182, 2019.\par \par M. C. Tran, Guo, A. Y., Su, Y., Garrison, J. R., Eldredge, Z., Foss-Feig, M., Childs, A. M., and Gorshkov, A. V., ?Locality and digital quantum simulation of power-law interactions?, Phys. Rev. X 9, 031006, vol. 9, no. 031006, 2019.\par \par A. M. Childs and Su, Y., ?Nearly optimal lattice simulation by product formulas?, Phys. Rev. Lett. , vol. 123, no. 050503, 2019.\par \par Y. Nam, Ross, N. J., Su, Y., Childs, A. M., and Maslov, D., ?Automated optimization of large quantum circuits with continuous parameters?, npj:Quantum Information, vol. 4, no. 23, 2018.\par \par J. Chen, Childs, A. M., and Hung, S. - H., ?Quantum algorithm for multivariate polynomial interpolation?, Proceedings of The Royal Society A, vol. 474, no. 2209, 2018.\par \par A. M. Childs, Maslov, D., Nam, Y., Ross, N. J., and Su, Y., ?Toward the first quantum simulation with quantum speedup?, Proceedings of the National Academy of Sciences, vol. 115 , pp. 9456-9461, 2018.\par \par A. M. Childs and Li, T., ?Efficient simulation of sparse Markovian quantum dynamics?, Quantum Information and Computation, vol. 17, pp. 901-947, 2017.\par \par D. W. Berry, Childs, A. M., Ostrander, A., and Wang, G., ?Quantum algorithm for linear differential equations with exponentially improved dependence on precision?, Communications in Mathematical Physics, vol. 356, no. 3, pp. 1057-1081, 2017.\par \par A. M. Childs, Kothari, R., and Somma, R. D., ?Quantum algorithm for systems of linear equations with exponentially improved dependence on precision?, SIAM Journal on Computing, vol. 46, no. 6, pp. 1920-1950, 2017.\par \par A. M. Childs, Gosset, D., and Webb, Z., ?Complexity of the XY antiferromagnet at fixed magnetization?, Quantum Information and Computation, vol. 16, no. 1-2, pp. 1-18, 2016.\par \par A. M. Childs, van Dam, W., Hung, S. - H., and Shparlinski, I. E., ?Optimal quantum algorithm for polynomial interpolation?, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), vol. 55, p. 16:1--16:13, 2016.\par \par A. M. Childs and Young, J., ?Optimal state discrimination and unstructured search in nonlinear quantum mechanics?, Physical Review A, vol. 93, no. 2, p. 022314, 2016.\par \par D. W. Berry, Childs, A. M., and Kothari, R., ?Hamiltonian simulation with nearly optimal dependence on all parameters?, Proceedings of the 56th IEEE Symposium on Foundations of Computer Science, pp. 792-809, 2015.\par \par A. M. Childs, Gosset, D., Nagaj, D., Raha, M., and Webb, Z., ?Momentum switches?, Quantum Information and Computation, vol. 15, no. 7-8, pp. 601-621, 2015.\par \par D. W. Berry, Childs, A. M., Cleve, R., Kothari, R., and Somma, R. D., ?Simulating Hamiltonian dynamics with a truncated Taylor series?, Physical Review Letters, vol. 114, no. 9, p. 090502, 2015.\par \par A. M. Childs, Gosset, D., and Webb, Z., ?The Bose-Hubbard model is QMA-complete?, Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), vol. 8572, pp. 308-319, 2014.\par \par D. J. Brod and Childs, A. M., ?The computational power of matchgates and the XY interaction on arbitrary graphs?, Quantum Information and Computation, vol. 14, no. 11-12, pp. 901-916, 2014.\par \par A. M. Childs, Jao, D., and Soukharev, V., ?Constructing elliptic curve isogenies in quantum subexponential time?, Journal of Mathematical Cryptology, vol. 8, no. 1, pp. 1 - 29, 2014.\par \par D. W. Berry, Childs, A. M., Cleve, R., Kothari, R., and Somma, R. D., ?Exponential improvement in precision for simulating sparse Hamiltonians?, Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014), pp. 283-292, 2014.\par \par A. M. Childs and Ivanyos, G., ?Quantum computation of discrete logarithms in semigroups?, Journal of Mathematical Cryptology, vol. 8, no. 4, 2014.\par \par A. M. Childs and Ge, Y., ?Spatial search by continuous-time quantum walks on crystal lattices?, Physical Review A, vol. 89, no. 5, 2014.\par \par A. M. Childs, Kothari, R., Ozols, M., and Roetteler, M., ?Easy and hard functions for the Boolean hidden shift problem?, Proceedings of TQC 2013, vol. 22, pp. 50-79, 2013.\par \par A. M. Childs, Leung, D., Mancinska, L., and Ozols, M., ?A framework for bounding nonlocality of state discrimination?, Communications in Mathematical Physics, vol. 323, no. 3, pp. 1121 - 1153, 2013.\par \par A. M. Childs, Leung, D., Mancinska, L., and Ozols, M., ?Interpolatability distinguishes LOCC from separable von Neumann measurements?, Journal of Mathematical Physics, vol. 54, no. 11, p. 112204, 2013.\par \par A. M. Childs and Wiebe, N., ?Product Formulas for Exponentials of Commutators?, Journal of Mathematical Physics, vol. 54, no. 6, p. 062202, 2013.\par \par A. M. Childs, Jeffery, S., Kothari, R., and Magniez, F., ?A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates?, 2013.\par \par A. M. Childs, Gosset, D., and Webb, Z., ?Universal computation by multi-particle quantum walk?, Science, vol. 339, no. 6121, pp. 791 - 794, 2013.\par \par A. M. Childs and Wiebe, N., ?Hamiltonian Simulation Using Linear Combinations of Unitary Operations?, Quantum Information and Computation, vol. 12, no. 11-12, pp. 901-924, 2012.\par \par A. M. Childs and Gosset, D., ?Levinson's theorem for graphs II?, Journal of Mathematical Physics, vol. 53, no. 10, p. 102207, 2012.\par \par A. M. Childs, Kimmel, S., and Kothari, R., ?The quantum query complexity of read-many formulas?, Lecture Notes in Computer Science, vol. 7501, pp. 337-348, 2012.\par \par A. M. Childs and Strouse, D. J., ?Levinson's theorem for graphs?, Journal of Mathematical Physics, vol. 52, no. 8, p. 082102, 2011.\par \par A. M. Childs and Kothari, R., ?Quantum query complexity of minor-closed graph properties?, Proc. 28th Symposium on Theoretical Aspects of Computer Science (STACS 2011), Leibniz International Proceedings in Informatics, vol. 9, pp. 661-672, 2011.\par \par A. M. Childs, Leung, D., Mancinska, L., and Ozols, M., ?Characterization of universal two-qubit Hamiltonians?, 2010.\par \par A. M. Childs and van Dam, W., ?Quantum algorithms for algebraic problems?, Reviews of Modern Physics, vol. 82, no. 1, pp. 1 - 52, 2010.\par \par A. Ambainis, Childs, A. M., and Liu, Y. - K., ?Quantum property testing for bounded-degree graphs?, Proc. RANDOM, pp. 365-376, 2010.\par \par A. M. Childs, ?On the relationship between continuous- and discrete-time quantum walk?, Communications in Mathematical Physics, vol. 294, no. 2, pp. 581 - 603, 2010.\par \par A. M. Childs and Kothari, R., ?Simulating sparse Hamiltonians with star decompositions?, 2010.\par \par D. W. Berry and Childs, A. M., ?Black-box Hamiltonian simulation and unitary implementation?, 2009.\par \par A. M. Childs, Cleve, R., Jordan, S. P., and Yeung, D., ?Discrete-query quantum algorithm for NAND trees?, Theory of Computing, vol. 5, no. 1, pp. 119 - 123, 2009.\par \par A. M. Childs and Kothari, R., ?Limitations on the simulation of non-sparse Hamiltonians?, 2009.\par \par A. Ambainis, Childs, A. M., Le Gall, F., and Tani, S., ?The quantum query complexity of certification?, 2009.\par \par A. M. Childs, ?Universal computation by quantum walk?, Physical Review Letters, vol. 102, no. 18, 2009.\par \par A. M. Childs, Reichardt, B. W., Spalek, R., and Zhang, S., ?Every NAND formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer?, 2007.\par \par A. M. Childs, Landahl, A. J., and Parrilo, P. A., ?Improved quantum algorithms for the ordered search problem via semidefinite programming?, Physical Review A, vol. 75, no. 3, 2007.\par \par M. Aschbacher, Childs, A. M., and Wocjan, P., ?The limitations of nice mutually unbiased bases?, Journal of Algebraic Combinatorics, vol. 25, no. 2, pp. 111 - 123, 2007.\par \par A. M. Childs and Lee, T., ?Optimal quantum adversary lower bounds for ordered search?, 2007.\par \par A. M. Childs, Schulman, L. J., and Vazirani, U. V., ?Quantum algorithms for hidden nonlinear structures?, 2007.\par \par A. M. Childs, Leung, D. W., and Lo, H. - K., ?Two-way quantum communication channels?, International Journal of Quantum Information, vol. 04, no. 01, pp. 63 - 83, 2006.\par \par A. M. Childs, Harrow, A. W., and Wocjan, P., ?Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem?, 2006.\par \par D. Bacon, Childs, A. M., and van Dam, W., ?From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups?, 2005.\par \par D. Bacon, Childs, A. M., and van Dam, W., ?Optimal measurements for the dihedral hidden subgroup problem?, 2005.\par \par A. M. Childs and van Dam, W., ?Quantum algorithm for a generalized hidden shift problem?, 2005.\par \par A. M. Childs and Wocjan, P., ?On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems?, 2005.\par \par A. M. Childs, Leung, D. W., and Nielsen, M. A., ?Unified derivations of measurement-based schemes for quantum computation?, Physical Review A, vol. 71, no. 3, 2005.\par \par A. M. Childs, Leung, D. W., and Vidal, G., ?Reversible simulation of bipartite product Hamiltonians?, IEEE Transactions on Information Theory, vol. 50, no. 6, pp. 1189 - 1197, 2004.\par \par A. M. Childs and Goldstone, J., ?Spatial search and the Dirac equation?, Physical Review A, vol. 70, no. 4, 2004.\par \par A. M. Childs and Goldstone, J., ?Spatial search by quantum walk?, Physical Review A, vol. 70, no. 2, 2004.\par \par A. M. Childs, Haselgrove, H. L., and Nielsen, M. A., ?Lower bounds on the complexity of simulating quantum gates?, Physical Review A, vol. 68, no. 5, 2003.\par \par A. M. Childs and Eisenberg, J. M., ?Quantum algorithms for subset finding?, 2003.\par \par A. M. Childs, Leung, D. W., Verstraete, F., and Vidal, G., ?Asymptotic entanglement capacity of the Ising and anisotropic Heisenberg interactions?, 2002.\par \par A. M. Childs, Cleve, R., Deotto, E., Farhi, E., Gutmann, S., and Spielman, D. A., ?Exponential algorithmic speedup by quantum walk?, 2002.\par \par A. M. Childs, Deotto, E., Farhi, E., Goldstone, J., Gutmann, S., and Landahl, A. J., ?Quantum search by measurement?, Physical Review A, vol. 66, no. 3, 2002.\par \par M. A. Nielsen, Bremner, M. J., Dodd, J. L., Childs, A. M., and Dawson, C. M., ?Universal simulation of Hamiltonian dynamics for qudits?, Physical Review A, vol. 66, no. 2, 2002.\par \par A. M. Childs, Patterson, R. B., and MacKay, D. J. C., ?Exact sampling from non-attractive distributions using summary states?, Physical Review E, vol. 63, no. 3, 2001.\par \par A. M. Childs, Farhi, E., and Gutmann, S., ?An example of the difference between quantum and classical random walks?, Quantum Information Processing, vol. 1, no. 1/2, pp. 35 - 43, 2001.\par \par A. M. Childs, Chuang, I. L., and Leung, D. W., ?Realization of quantum process tomography in NMR?, Physical Review A, vol. 64, no. 1, 2001.\par \par A. M. Childs, Farhi, E., and Preskill, J., ?Robustness of adiabatic quantum computation?, Physical Review A, vol. 65, no. 1, 2001.\par \par A. M. Childs, ?Secure assisted quantum computation?, 2001.\par \par D. Bacon, Childs, A. M., Chuang, I. L., Kempe, J., Leung, D. W., and Zhou, X., ?Universal simulation of Markovian quantum dynamics?, Physical Review A, vol. 64, no. 6, 2001.\par \par A. M. Childs, Farhi, E., Goldstone, J., and Gutmann, S., ?Finding cliques by quantum adiabatic evolution?, 2000.\par \par A. M. Childs, Preskill, J., and Renes, J., ?Quantum information and precision measurement?, Journal of Modern Optics, vol. 47, no. 2-3, pp. 155 - 176, 2000.\par \par A. M. Childs and Chuang, I. L., ?Universal quantum computation with two-level trapped ions?, Physical Review A, vol. 63, no. 1, 2000.\par \par }