Andris Ambainis
- Quantum lower bounds by quantum arguments
2000/02/24 by Andris Ambainis, Ambainis, Andris · 8 citations
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #cs.CC #quant-ph
- An Elementary Proof of the Quantum Adiabatic Theorem
2004/11/20 by Andris Ambainis, Oded Regev, Ambainis, Andris +1 · 9 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications
- Quantum computing and artificial intelligence: status and perspectives
2025/05/29 by Giovanni Acampora, Andris Ambainis, Acampora, Giovanni +75 · 6 voices · 4 citations
Computer Science · Physics and Astronomy · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Quantum Physics (quant-ph) #cs.AI #cs.LG #quant-ph
- The Need for Structure in Quantum Speedups
2009/11/05 by Scott Aaronson, Andris Ambainis, Aaronson, Scott +1 · 4 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Machine Learning and Algorithms #Complexity and Algorithms in Graphs
- Quantum Attacks on Classical Proof Systems - The Hardness of Quantum\n Rewinding
2014/04/28 by Andris Ambainis, Ansis Rosmanis, Ambainis, Andris +3 · 4 citations
Computer Science · #Cryptography and Data Security #Security and Verification in Computing #Cryptographic Implementations and Security
- Parity Oblivious d-Level Random Access Codes and Class of\n Noncontextuality Inequalities
2016/07/19 by Andris Ambainis, Manik Banik, Ambainis, Andris +7 · 3 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum-Dot Cellular Automata
- Small Pseudo-Random Families of Matrices: Derandomizing Approximate Quantum Encryption
2004/04/13 by Andris Ambainis, Adam Smith, Ambainis, Andris +1 · 2 citations
Computer Science · Physics and Astronomy · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CR #quant-ph
- Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing
2015/07/11 by Andris Ambainis, Ambainis, Andris, Aleksandrs Belovs +5 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Physics (quant-ph)
- Computing with highly mixed states
2000/03/29 by Andris Ambainis, Ambainis, Andris, Leonard J. Schulman +3 · 2 citations
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #quant-ph
- Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
2018/07/13 by Andris Ambainis, Kaspars Balodis, Ambainis, Andris +9 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Optimization and Search Problems #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
- 1-way quantum finite automata: strengths, weaknesses and generalizations
1998/02/25 by A. Ambainis, Andris Ambainis, Rūsiņš Freivalds +3 · 1 citation
Computer Science · Physics and Astronomy · #Machine Learning and Algorithms #Optimization and Search Problems #Quantum Computing Algorithms and Architecture #cs.CC #quant-ph
- Quantum Search of Spatial Regions
2003/03/09 by Scott Aaronson, Andris Ambainis, Aaronson, Scott +1 · 1 citation
Physics and Astronomy · #FOS: Physical sciences #General Relativity and Quantum Cosmology (gr-qc) #Quantum Physics (quant-ph) #gr-qc #quant-ph
- A new quantum lower bound method, with an application to strong direct product theorem for quantum search
2005/08/26 by Andris Ambainis, Ambainis, Andris · 1 citation
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph
- Parameterized Quantum Query Complexity of Graph Collision
2013/05/05 by Andris Ambainis, Kaspars Balodis, Ambainis, Andris +7 · 1 citation
Computer Science · #Quantum Computing Algorithms and Architecture #Complexity and Algorithms in Graphs #Advanced Graph Theory Research
- Exact quantum algorithms have advantage for almost all Boolean functions
2014/04/07 by Andris Ambainis, Jozef Gruska, Ambainis, Andris +3 · 1 citation
Computer Science · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum-Dot Cellular Automata
- Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
2020/07/06 by Andris Ambainis, Ambainis, Andris, Kaspars Balodis +15 · 1 citation
Computer Science · #Quantum Computing Algorithms and Architecture #Optimization and Search Problems #Machine Learning and Algorithms
- An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
2023/01/22 by Andris Ambainis, Aleksandrs Belovs, Ambainis, Andris +1 · 1 citation
Computer Science · #Quantum Computing Algorithms and Architecture #Quantum-Dot Cellular Automata #Quantum Information and Cryptography