Publications (refereed)

[20]
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. To appear. arXiv: 2006.12760
[19]
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]
[18]
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]
[17]
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
[16]
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]
[15]
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
[14]
van Apeldoorn, J., Gilyn, A., Gribling, S., and de Wolf, R. Convex optimization using quantum oracles. Quantum 4:220, 2020. arXiv: 1809.00643
[13]
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
[12]
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
[11]
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
[10]
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
[9]
van Apeldoorn, J., Gilyn, A., Gribling, S., and de Wolf, R. Quantum SDP-solvers: Better upper and lower bounds. In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS), 2017, pp. 403–414. arXiv: 1705.01843 [download pdf]
[8]
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]
[7]
Gilyn, A. Testing quantum state engineering protocols via LIQUi|⟩ simulations. Tech. rep., 2nd prize winner entry at the Microsoft Quantum Challange, 2016
[6]
Gilyn, A., Kiss, T., and Jex, I. Exponential sensitivity and its cost in quantum physics. Scientific Reports 6:20076, 2015. arXiv: 1508.03191

To be peer-reviewed arXiv preprints:

[5]
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
[4]
Chao, R., Ding, D., Gilyn, A., Huang, C., and Szegedy, M. Finding angles for quantum signal processing with machine precision. arXiv: 2003.02831, 2020
[3]
Apers, S., Gilyn, A., and Jeffery, S. A unified framework of quantum walk search. arXiv: 1912.04233, 2019
[2]
van Apeldoorn, J., and Gilyn, A. Quantum algorithms for zero-sum games. arXiv: 1904.03180, 2019
[1]
Gilyn, A., Lloyd, S., and Tang, E. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. arXiv: 1811.04909, 2018