Publications

[24]
Gilyn, A., Hastings, M. B., and Vazirani, U. (Sub)Exponential advantage of adiabatic quantum computation with no sign problem. In Proceedings of the 53rd ACM Symposium on the Theory of Computing (STOC), 2021, pp. 1357–1369 [download pdf] Earlier version available on arXiv: 2011.09495.
[23]
Apers, S., Gilyn, A., and Jeffery, S. A unified framework of quantum walk search. In Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS), 2021, pp. 6:1–6:13. arXiv: 1912.04233
[22]
Chia, N.-H., Gilyn, A., Lin, H.-H., Lloyd, S., Tang, E., and Wang, C. Quantum-inspired algorithms for solving low-rank linear equation systems with logarithmic dependence on the dimension. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC), 2020, pp. 47:1–47:17 Earlier version available on arXiv: 1811.04909.
[21]
Ben-David, S., Childs, A. M., Gilyn, 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. arXiv: 2006.12760

[download pdf]

[20]
Kollr, B., Gilyn, A., Tkčov, I., Kiss, T., Jex, I., and Štefaňk, M. Complete classification of trapping coins for quantum walks on the two-dimensional square lattice. Physical Review A 102(1):012207, 2020. arXiv: 2002.08070 [download pdf]
[19]
Chia, N.-H., Gilyn, A., Li, T., Lin, H.-H., Tang, E., and Wang, C. Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. In Proceedings of the 52nd ACM Symposium on the Theory of Computing (STOC), 2020, p. 387–400. arXiv: 1910.06151 [download pdf]
[18]
Bannink, T., Buhrman, H., Gilyn, A., and Szegedy, M. The interaction light cone of the Discrete Bak-Sneppen, Contact and other local processes. Journal of Statistical Physics 176(6):1500–1525, 2019. arXiv: 1903.12607
[17]
Ambainis, A., Gilyn, A., Jeffery, S., and Kokainis, M. Quadratic speedup for finding marked vertices by quantum walks. In Proceedings of the 52nd ACM Symposium on the Theory of Computing (STOC), 2020, p. 412–424. arXiv: 1903.07493 [download pdf]
[16]
Gilyn, A., and Li, T. Distributional property testing in a quantum world. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS), 2020, pp. 25:1–25:19. arXiv: 1902.00814
[15]
van Apeldoorn, J., Gilyn, A., Gribling, S., and de Wolf, R. Convex optimization using quantum oracles. Quantum 4:220, 2020. arXiv: 1809.00643
[14]
Gilyn, A., Su, Y., Low, G. H., and Wiebe, N. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC), 2019, pp. 193–204. arXiv: 1806.01838
[13]
Chakraborty, S., Gilyn, A., and Jeffery, S. The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), 2019, pp. 33:1–33:14. arXiv: 1804.01973
[12]
van Apeldoorn, J., and Gilyn, A. Improvements in quantum SDP-solving with applications. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), 2019, pp. 99:1–99:15. arXiv: 1804.05058
[11]
Gilyn, A., Arunachalam, S., and Wiebe, N. Optimizing quantum optimization algorithms via faster quantum gradient computation. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019, pp. 1425–1444. arXiv: 1711.00465
[10]
van Apeldoorn, J., Gilyn, A., Gribling, S., and de Wolf, R. Quantum SDP-solvers: Better upper and lower bounds. Quantum 4:230, 2020. Earlier version in FOCS’17. arXiv: 1705.01843
[9]
Gilyn, A., and Sattath, O. On preparing ground states of gapped Hamiltonians: An efficient quantum Lovsz local lemma. In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS), 2017, pp. 439–450. arXiv: 1611.08571 [download pdf]
[8]
Gilyn, A. Testing quantum state engineering protocols via LIQUi|⟩ simulations. Tech. rep., 2nd prize winner entry at the Microsoft Quantum Challange, 2016
[7]
Gilyn, A., Kiss, T., and Jex, I. Exponential sensitivity and its cost in quantum physics. Scientific Reports 6:20076, 2016. arXiv: 1508.03191

To be peer-reviewed arXiv preprints:

[6]
Ding, J., Gheorghiu, V., Gilyn, A., Hallgren, S., and Li, J. Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems. arXiv: 2111.00405, 2021
[5]
Cornelissen, A., Bausch, J., and Gilyn, A. Scalable benchmarks for gate-based quantum computers. arXiv: 2104.10698, 2021
[4]
Gilyn, A., Song, Z., and Tang, E. An improved quantum-inspired algorithm for linear regression. arXiv: 2009.07268, 2020
[3]
Gilyn, A., Lloyd, S., Marvian, I., Quek, Y., and Wilde, M. M. Quantum algorithm for Petz recovery channels and pretty good measurements. arXiv: 2006.16924, 2020
[2]
Chao, R., Ding, D., Gilyn, A., Huang, C., and Szegedy, M. Finding angles for quantum signal processing with machine precision. arXiv: 2003.02831, 2020
[1]
van Apeldoorn, J., and Gilyn, A. Quantum algorithms for zero-sum games. arXiv: 1904.03180, 2019