A. Ambainis

Most-cited papers

Challenges and opportunities in quantum optimization
Amira Abbas, A. Ambainis, Brandon Augustino, Andreas Bärtschi +42 more
2023Nature Reviews Physics396 citations Open access
Semantic Scholar
Variable time amplitude amplification and quantum algorithms for linear algebra problems
A. Ambainis
2012Symposium on Theoretical Aspects of Computer Science198 citations
Semantic Scholar
Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding
A. Ambainis, A. Rosmanis, Dominique Unruh
2014IEEE Annual Symposium on Foundations of Computer Science175 citations
Semantic Scholar
Quantum security proofs using semi-classical oracles
A. Ambainis, Michael Hamburg, Dominique Unruh
2019IACR Cryptology ePrint Archive157 citations
Semantic Scholar
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
S. Aaronson, A. Ambainis
2014Symposium on the Theory of Computing154 citations Open access
Semantic Scholar
Spatial Search by Quantum Walk is Optimal for Almost all Graphs.
Shantanav Chakraborty, Leonardo Novo, A. Ambainis, Y. Omar
2015Physical Review Letters145 citations Open access
Semantic Scholar
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
A. Ambainis, K. Balodis, Janis Iraids, M. Kokainis +2 more
2018ACM-SIAM Symposium on Discrete Algorithms110 citations
Semantic Scholar
Understanding Quantum Algorithms via Query Complexity
A. Ambainis
2017International Congress of Mathematicans85 citations Open access
Semantic Scholar
Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method
A. Ambainis, Yuval Filmus, F. Le Gall
2014Symposium on the Theory of Computing85 citations
Semantic Scholar
Quadratic speedup for finding marked vertices by Quantum walks
A. Ambainis, A. Gilyén, S. Jeffery, M. Kokainis
2019Symposium on the Theory of Computing81 citations Open access
Semantic Scholar
Parity oblivious d-level random access codes and class of noncontextuality inequalities
A. Ambainis, Manik Banik, Anubhav Chaturvedi, Dmitry Kravchenko +1 more
2016Quantum Information Processing75 citations Open access
Semantic Scholar
Separations in query complexity based on pointer functions
A. Ambainis, K. Balodis, Aleksandrs Belovs, Troy Lee +2 more
2015Symposium on the Theory of Computing74 citations Open access
Semantic Scholar
Quantum Optimization: Potential, Challenges, and the Path Forward
Amira Abbas, A. Ambainis, Brandon Augustino, Andreas Baertschi +42 more
202369 citations Open access
Semantic Scholar
Superiority of exact quantum automata for promise problems
A. Ambainis, A. Yakaryılmaz
2011Information Processing Letters64 citations Open access
Semantic Scholar
Superlinear advantage for exact quantum algorithms
A. Ambainis
2012Symposium on the Theory of Computing63 citations Open access
Semantic Scholar
Automata and Quantum Computing
A. Ambainis, A. Yakaryılmaz
2015Handbook of Automata Theory62 citations Open access
Semantic Scholar
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing
A. Ambainis, Aleksandrs Belovs, O. Regev, R. de Wolf
2015ACM-SIAM Symposium on Discrete Algorithms52 citations
Semantic Scholar
Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification
A. Ambainis, A. Backurs, N. Nahimovs, Raitis Ozols +1 more
2011Theory of Quantum Computation, Communication, and Cryptography50 citations Open access
Semantic Scholar
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
A. Ambainis, M. Kokainis
2017Symposium on the Theory of Computing41 citations Open access
Semantic Scholar
Limited preparation contextuality in quantum theory and its relation to the Cirel'son bound
Manik Banik, S. S. Bhattacharya, Amit Mukherjee, Arup Roy +2 more
201537 citations Open access
Semantic Scholar
On Physical Problems that are Slightly More Difficult than QMA
A. Ambainis
2013Cybersecurity and Cyberforensics Conference35 citations
Semantic Scholar
Nearly optimal separations between communication (or query) complexity and partitions
A. Ambainis, M. Kokainis, Robin Kothari
2015Cybersecurity and Cyberforensics Conference32 citations Open access
Semantic Scholar
Quantum search with multiple walk steps per oracle query
Thomas G. Wong, A. Ambainis
201531 citations Open access
Semantic Scholar
Exact quantum query complexity of EXACT and THRESHOLD
A. Ambainis, Janis Iraids, Juris Smotrovs
2013Theory of Quantum Computation, Communication, and Cryptography31 citations
Semantic Scholar
Separations in Query Complexity Based on Pointer Functions
A. Ambainis, K. Balodis, Aleksandrs Belovs, Troy Lee +2 more
2017Journal of the ACM29 citations Open access
Semantic Scholar
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
S. Aaronson, A. Ambainis, Janis Iraids, M. Kokainis +1 more
2015Cybersecurity and Cyberforensics Conference29 citations
Semantic Scholar
New separation between s(f) and bs(f)
A. Ambainis, Xiaoming Sun
2011Electron. Colloquium Comput. Complex.29 citations
Semantic Scholar
Tighter Relations between Sensitivity and Other Complexity Measures
A. Ambainis, Mohammad Bavarian, Yi-Han Gao, Jieming Mao +2 more
2014International Colloquium on Automata, Languages and Programming28 citations
Semantic Scholar
Exact quantum algorithms have advantage for almost all Boolean functions
A. Ambainis, J. Gruska, Shenggen Zheng
2014Quantum information & computation27 citations Open access
Semantic Scholar
Quantum algorithms for search with wildcards and combinatorial group testing
A. Ambainis, Ashley Montanaro
2012Quantum information & computation26 citations Open access
Semantic Scholar
Sensitivity Versus Certificate Complexity of Boolean Functions
A. Ambainis, Krisjanis Prusis, J. Vihrovs
2015Computer Science Symposium in Russia25 citations
Semantic Scholar
Spatial search on grids with minimum memory
A. Ambainis, R. Portugal, Nikolay Nahimov
2013Quantum information & computation25 citations Open access
Semantic Scholar
Quantum speedup for track reconstruction in particle accelerators
D. Magano, Ajay Kumar, M. Kālis, A. Locāns +9 more
2021Physical Review D23 citations Open access
Semantic Scholar
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
A. Ambainis, K. Balodis, Janis Iraids, K. Khadiev +5 more
2020International Symposium on Mathematical Foundations of Computer Science22 citations
Semantic Scholar
Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
F. Ablayev, A. Ambainis, K. Khadiev, A. Khadieva
2017Conference on Current Trends in Theory and Practice of Informatics21 citations Open access
Semantic Scholar
Quantum computing and artificial intelligence: status and perspectives
Giovanni Acampora, A. Ambainis, N. Ares, L. Banchi +35 more
2025arXiv.org20 citations
Semantic Scholar
Quantum Finite Automata
A. Ambainis
2011Workshop on Non-Classical Models for Automata and Applications20 citations
Semantic Scholar
Grover's Algorithm with Errors
A. Ambainis, A. Backurs, N. Nahimovs, Alexander Rivosh
2012Doctoral Workshop on Mathematical and Engineering Methods in Computer Science17 citations
Semantic Scholar
Quantum Strategies Are Better Than Classical in Almost Any XOR Game
A. Ambainis, A. Backurs, K. Balodis, Dmitrijs Kravčenko +3 more
2011International Colloquium on Automata, Languages and Programming16 citations Open access
Semantic Scholar
Quantum algorithms for computational geometry problems
A. Ambainis, N. Larka
2020Theory of Quantum Computation, Communication, and Cryptography15 citations
Semantic Scholar
Oscillatory localization of quantum walks analyzed by classical electric circuits
A. Ambainis, Krivsjanis Prusis, J. Vihrovs, Thomas G. Wong
201615 citations Open access
Semantic Scholar
Size of Sets with Small Sensitivity: A Generalization of Simon's Lemma
A. Ambainis, J. Vihrovs
2014Theory and Applications of Models of Computation13 citations Open access
Semantic Scholar
How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?
A. Ambainis, R. de Wolf
2012Computational Complexity13 citations Open access
Semantic Scholar
Exact quantum query complexity of EXACTk, ln
A. Ambainis, Jānis Iraids, Daniel Nagaj
2016arXiv.org12 citations
Semantic Scholar
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity
A. Ambainis, Krisjanis Prusis
2014International Symposium on Mathematical Foundations of Computer Science12 citations Open access
Semantic Scholar
A random-walk benchmark for single-electron circuits
D. Reifert, M. Kokainis, A. Ambainis, Vyacheslavs Kashcheyevs +1 more
2020Nature Communications11 citations Open access
Semantic Scholar
Nonlocal Quantum XOR Games for Large Number of Players
A. Ambainis, Dmitry Kravchenko, N. Nahimovs, Alexander Rivosh
2010Theory and Applications of Models of Computation11 citations
Semantic Scholar
Improved Algorithm and Lower Bound for Variable Time Quantum Search
A. Ambainis, M. Kokainis, J. Vihrovs
2023Theory of Quantum Computation, Communication, and Cryptography10 citations Open access
Semantic Scholar
A hybrid quantum-classical approach for inference on restricted Boltzmann machines
M. Kalis, A. Locāns, Rolands Sikovs, Hassan Naseri +1 more
2023Quantum Machine Intelligence10 citations Open access
Semantic Scholar
Quantum algorithms for formula evaluation
A. Ambainis
2010Quantum Cryptography and Computing10 citations
Semantic Scholar