that's me (to the left)

Alexander Belov (Aleksandrs Belovs)

Accounts

• Google Scholar
• arXiv
• ORCID

Theses

• PhD Thesis
  Applications of the Adversary Method in Quantum Query Algorithms
  University of Latvia, 2013. arXiv:1402.3858
• Master's Thesis
  Welch Bounds and Quantum State Tomography
  University of Waterloo, 2008. Available here

Manuscripts

• Aleksandrs Belovs
  Tight Quantum Lower Bound for $k$-Distinctness
  preprint: arXiv:2604.05133
  
• Aleksandrs Belovs
  Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem
  preprint: arXiv:2404.19476
  
• Aleksandrs Belovs and Duyal Yolcu
  One-Way Ticket to Las Vegas and the Quantum Adversary
  preprint: arXiv:2301.02003
  • plenary talk at QIP 2023
  
• Aleksandrs Belovs and Troy Lee
  The quantum query complexity of composition with a relation
  preprint: arXiv:2004.06439
  
• Aleksandrs Belovs
  Variations on Quantum Adversary
  preprint: arXiv:1504.06943
  
• Aleksandrs Belovs
  Quantum Walks and Electric Networks
  preprint: arXiv:1302.3143
  
• Aleksandrs Belovs
  Adversary Lower Bound for Element Distinctness
  preprint: arXiv:1204.5074
  
• Aleksandrs Belovs and Troy Lee
  Quantum Algorithm for $k$-distinctness with Prior Knowledge on the Input
  preprint: arXiv:1108.3022
  

Publications

• Aleksandrs Belovs and Ansis Rosmanis
  Tight quantum lower bound for approximate counting with quantum states
  Computational Complexity 25, article number 2, 2026
  preprint: arXiv:2002.06879
  
• Vladimirs Andrejevs, Aleksandrs Belovs, and Jevgēnijs Vihrovs
  Quantum Algorithms for Hopcroft’s Problem
  ACM Transactions on Quantum Computing 7(2), article number 11, 2026
  earlier in: International Symposium on Mathematical Foundations of Computer Science (MFCS) 2024, pages 9:1–9:16
  preprint: arXiv:2405.01160
  
• Aleksandrs Belovs and Stacey Jeffery
  Space-efficient quantum error reduction without log factors
  Quantum 10, article number 2039, 2026
  preprint: arXiv:2502.09249
  
• Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, and Miklos Santha
  On the quantum time complexity of divide and conquer
  In Proceedings of the 52nd International Colloquium on Automata, Languages and Programming (ICALP),
  volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:20, 2025
  preprint: arXiv:2311.16401
  
• Andris Ambainis and Aleksandrs Belovs
  An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
  Computational Complexity 34(2), article number 14, 2025
  earlier in: IEEE Conference on Computational Complexity (CCC) 2023, pages 24:1–24:13
  preprint: arXiv:2301.09218
  • plenary talk at QIP 2024
  
• Aleksandrs Belovs, Stacey Jeffery, and Duyal Yolcu
  Taming Quantum Time Complexity
  Quantum 8, article number 1444, 2024
  preprint: arXiv:2311.15873
  
• Aleksandrs Belovs
  A Direct Reduction from the Polynomial to the Adversary Method
  In Proceedings of the 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC),
  volume 310 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:15, 2024
  preprint: arXiv:2301.10317
  
• Aleksandrs Belovs and Eric Blais
  A polynomial lower bound for testing monotonicity
  SIAM Journal on Computing 50(3), pages 406–433, 2021
  earlier in: Annual ACM Symposium on Theory of Computing (STOC) 2016, pages 1021–1032
  preprint: arXiv:1511.05053
  
• Aleksandrs Belovs, Arturo Castellanos, François Le Gall, Guillaume Malod, and Alexander A. Sherstov
  Quantum communication complexity of distribution testing
  Quantum Information and Computation 21(15-16), pages 1261–1273, 2021
  preprint: arXiv:2006.14870
  
• Aleksandrs Belovs, Eric Blais, and Abhinav Bommireddi
  Testing convexity of functions over finite domains
  In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2030–2045, 2020
  preprint: arXiv:1908.02525
  
• Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf
  Quantum Coupon Collector
  In Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC),
  volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:17, 2020
  preprint: arXiv:2002.07688
  
• Aleksandrs Belovs
  Quantum Dual Adversary for Hidden Subgroups and Beyond
  In Proceedings of the 18th International Conference on Unconventional Computation and Natural Computation (UCNC),
  volume 11493 of Lecture Notes in Computer Science (LNCS), pages 30–36, 2019
  
• Aleksandrs Belovs
  Quantum Algorithm for Distribution-Free Junta Testing
  In Proceedings of the 14th International Computer Science Symposium in Russia (CSR),
  volume 11532 of Lecture Notes in Computer Science (LNCS), pages 50–59, 2019
  preprint: arXiv:1903.08462
  
• Aleksandrs Belovs
  Quantum Algorithms for Classical Probability Distributions
  In Proceedings of the 27th Annual European Symposium on Algorithms (ESA),
  volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:11, 2019
  preprint: arXiv:1904.02192
  
• Aleksandrs Belovs and Ansis Rosmanis
  Adversary Lower Bounds for the Collision and the Set Equality Problems
  Quantum Information & Computation 18(3-4), pages 198–224, 2018
  preprint: arXiv:1310.5185
  
• Chris Cade, Ashley Montanaro, and Aleksandrs Belovs
  Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness
  Quantum Information & Computation 18(1-2), pages 18–50, 2018
  preprint: arXiv:1610.00581
  
• Aleksandrs Belovs, Gilles Brassard, Peter Hoyer, Marc Kaplan, Sophie Laplante, and Louis Salvail
  Provably secure key establishment against quantum adversaries
  In Proceedings of the 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC),
  volume 73 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:17, 2018
  preprint: arXiv:1704.08182
  
• Aleksandrs Belovs and Ansis Rosmanis
  Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
  In Proceedings of the 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC),
  volume 111 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:15, 2018
  preprint: arXiv:1712.10194
  
• Aleksandrs Belovs
  Adaptive Lower Bound for Testing Monotonicity on the Line
  In Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM),
  volume 116 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1–31:10, 2018
  preprint: arXiv:1801.08709
  
• Aleksandrs Belovs, Juan Andres Montoya, and Abuzer Yakaryılmaz
  On a Conjecture by Christian Choffrut
  International Journal of Foundations of Computer Science 28(05), pages 483–501, 2017
  earlier in: International Conference on Implementation and Application of Automata (CIAA) 2016, article number 213–223
  preprint: arXiv:1602.07967
  
• Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs
  Separations in query complexity based on pointer functions
  Journal of the ACM 64(5), article number 32, 2017
  earlier in: Annual ACM Symposium on Theory of Computing (STOC) 2016, pages 800–813
  preprint: arXiv:1506.04719
  • plenary talk at QIP 2016
  
• Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, and Siyi Yang
  On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz
  In Proceedings of the 32nd IEEE Conference on Computational Complexity (CCC),
  volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1–30:24, 2017
  preprint: arXiv:1710.08602
  
• Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de Wolf
  Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing
  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 903–922, 2016
  preprint: arXiv:1507.03126
  
• Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, and Miklos Santha
  Separations in Communication Complexity Using Cheat Sheets and Information Complexity
  In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 555–564, 2016
  preprint: arXiv:1605.01142
  
• Aleksandrs Belovs
  Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
  Computational Complexity 24(2), pages 255–293, 2015
  earlier in: IEEE Conference on Computational Complexity (CCC) 2014, pages 22–31
  preprint: arXiv:1311.6777
  • best student paper award
  
• Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, and Luca Trevisan
  Quantum lower bound for inverting a permutation with advice
  Quantum Information & Computation 15(11-12), pages 901–913, 2015
  preprint: arXiv:1408.3193
  
• Aleksandrs Belovs and Eric Blais
  Quantum Algorithm for Monotonicity Testing on the Hypercube
  Theory of Computing 11(16), pages 403–412, 2015
  preprint: arXiv:1503.02868
  
• Aleksandrs Belovs and Ansis Rosmanis
  On the Power of Non-Adaptive Learning Graphs
  Computational Complexity 23(2), pages 323–354, 2014
  earlier in: IEEE Conference on Computational Complexity (CCC) 2013, pages 44–55
  preprint: arXiv:1210.3279
  • best student paper award
  
• Aleksandrs Belovs and Robert Špalek
  Adversary Lower Bound for the $k$-sum Problem
  In Proceedings of the 4th ACM Innovations in Theoretical Computer Science conference (ITCS), pages 323–328, 2013
  preprint: arXiv:1206.6528
  
• Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez
  Time-Efficient Quantum Walks for 3-Distinctness
  In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Part I
  volume 7965 of Lecture Notes in Computer Science (LNCS), pages 105–122, 2013
  
• Aleksandrs Belovs
  Span programs for functions with constant-sized 1-certificates
  In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pages 77–84, 2012
  preprint: arXiv:1105.4024
  • plenary talk at QIP 2012
  
• Aleksandrs Belovs
  Learning-graph-based Quantum Algorithm for $k$-distinctness
  In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 207–216, 2012
  preprint: arXiv:1205.1534
  
• Aleksandrs Belovs and Ben W. Reichardt
  Span programs and quantum algorithms for $st$-connectivity and claw detection
  In Proceedings of the 20th Annual European Symposium on Algorithms (ESA),
  volume 7501 of Lecture Notes in Computer Science (LNCS), pages 193–204, 2012
  preprint: arXiv:1203.2603
  
• Aleksandrs Belovs
  Some Algebraic Properties of Machine Poset of Infinite Words
  Theoretical Informatics and Applications 42(3), pages 451–466, 2008
  
• Aleksandrs Belovs and Juris Smotrovs
  A criterion for attaining the Welch bounds with applications for mutually unbiased bases
  In Mathematical Methods in Computer Science: Essays in Memory of Thomas Beth,
  volume 5393 of Lecture Notes in Computer Science (LNCS), pages 50–69, 2008
  preprint: arXiv:0802.0855
  
• Aleksandrs Belovs, Ansis Rosmanis, and Juris Smotrovs
  Multi-letter reversible and quantum finite automata
  In Proceedings of the 11th International Conference on Developments in Language Theory (DLT),
  volume 4588 of Lecture Notes in Computer Science (LNCS), pages 60–71, 2007
  
• Aleksandrs Belovs
  Non-intersecting complexity
  In Proceedings of the 32nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM),
  volume 3831 of Lecture Notes in Computer Science (LNCS), pages 158–165, 2006