Andris Ambainis
#17,717
Most Influential Person Now
Latvian scientist
Andris Ambainis's AcademicInfluence.com Rankings
Andris Ambainiscomputer-science Degrees
Computer Science
#809
World Rank
#837
Historical Rank
Database
#3516
World Rank
#3663
Historical Rank
Download Badge
Computer Science
Andris Ambainis's Degrees
- PhD Computer Science University of Latvia
Similar Degrees You Can Earn
Why Is Andris Ambainis Influential?
(Suggest an Edit or Addition)According to Wikipedia, Andris Ambainis is a Latvian computer scientist active in the fields of quantum information theory and quantum computing. Education and career Ambainis has held past positions at the Institute for Advanced Study at Princeton, New Jersey and the Institute for Quantum Computing at the University of Waterloo. He is currently a professor in the Faculty of Computing at the University of Latvia.
Andris Ambainis's Published Works
Number of citations in a given year to any of this author's works
Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author
Published Works
- Quantum walk algorithm for element distinctness (2003) (823)
- Quantum walks on graphs (2000) (666)
- One-dimensional quantum walks (2001) (569)
- QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS (2003) (524)
- Quantum lower bounds by quantum arguments (2000) (421)
- Coins make quantum walks faster (2004) (334)
- 1-way quantum finite automata: strengths, weaknesses and generalizations (1998) (268)
- Quantum search of spatial regions (2003) (247)
- Private quantum channels (2000) (239)
- Dense quantum coding and quantum finite automata (2002) (209)
- Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer (2007) (201)
- Upper Bound on Communication Complexity of Private Information Retrieval (1997) (195)
- Polynomial degree vs. quantum query complexity (2003) (173)
- Quantum search algorithms (2004) (159)
- Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding (2014) (154)
- Quantum walks driven by many coins (2002) (146)
- Quantum t-designs: t-wise Independence in the Quantum World (2007) (144)
- Dense quantum coding and a lower bound for 1-way quantum automata (1998) (142)
- Quantum to classical transition for random walks. (2002) (140)
- A new protocol and lower bounds for quantum coin flipping (2001) (138)
- Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range (2003) (118)
- Spatial Search by Quantum Walk is Optimal for Almost all Graphs. (2015) (114)
- Quantum random walks with decoherent coins (2002) (114)
- The quantum communication complexity of sampling (1998) (107)
- The Need for Structure in Quantum Speedups (2009) (107)
- Forrelation: A Problem that Optimally Separates Quantum from Classical Computing (2014) (105)
- Variable time amplitude amplification and quantum algorithms for linear algebra problems (2012) (100)
- An Elementary Proof of the Quantum Adiabatic Theorem (2004) (85)
- Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption (2004) (85)
- Two-way finite automata with quantum and classical state (1999) (84)
- Quantum security proofs using semi-classical oracles (2019) (82)
- Multiparty quantum coin flipping (2003) (81)
- Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations (2010) (81)
- Algebraic Results on Quantum Automata (2004) (79)
- Quantum Random Access Codes with Shared Randomness (2008) (71)
- Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method (2014) (64)
- Superiority of exact quantum automata for promise problems (2011) (64)
- Separations in query complexity based on pointer functions (2015) (62)
- ANY AND-OR FORMULA OF SIZE N CAN BE EVALUATED IN TIME N ON A QUANTUM COMPUTER∗ (2010) (57)
- Quantum Speedups for Exponential-Time Dynamic Programming Algorithms (2018) (56)
- Understanding Quantum Algorithms via Query Complexity (2017) (55)
- On the Class of Languages Recognizable by 1-Way Quantum Finite Automata (2000) (54)
- Superlinear advantage for exact quantum algorithms (2012) (52)
- Symmetry-Assisted Adversaries for Quantum State Generation (2010) (52)
- Quantum Algorithms for Matching and Network Flows (2005) (52)
- Improved constructions of quantum automata (2008) (52)
- Quantum Identification of Boolean Oracles (2004) (49)
- Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification (2011) (48)
- A better lower bound for quantum algorithms searching an ordered list (1999) (46)
- Cryptographic Randomized Response Techniques (2003) (45)
- A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs (2005) (45)
- Quantum Search with Variable Times (2006) (45)
- Communication complexity in a 3-computer model (1996) (42)
- Computing with highly mixed states (2000) (42)
- Automata and Quantum Computing (2015) (41)
- Quantum query algorithms and lower bounds (2001) (37)
- A nearly optimal discrete query quantum algorithm for evaluating NAND formulas (2007) (35)
- Probabilities to Accept Languages by Quantum Finite Automata (1999) (35)
- Quadratic speedup for finding marked vertices by Quantum walks (2019) (35)
- Parity oblivious d-level random access codes and class of noncontextuality inequalities (2016) (35)
- Ordinal Mind Change Complexity of Language Identification (1997) (34)
- The Complexity of Probabilistic versus Deterministic Finite Automata (1996) (33)
- Quantum lower bounds for collision and element distinctness with small range (2003) (32)
- Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing (2015) (32)
- Nearly tight bounds on the learnability of evolution (1997) (32)
- Average-Case Quantum Query Complexity (1999) (31)
- Quantum search with multiple walk steps per oracle query (2015) (30)
- Exact results for accepting probabilities of quantum automata (2001) (29)
- Exact quantum query complexity of EXACT and THRESHOLD (2013) (29)
- Nonmalleable encryption of quantum information (2008) (29)
- Limited preparation contextuality in quantum theory and its relation to the Cirel'son bound (2015) (29)
- A quantum Lovász local lemma (2009) (29)
- New separation between s(f) and bs(f) (2011) (27)
- Bounded Depth Arithmetic Circuits: Counting and Closure (1999) (27)
- Quantum Random Walks - New Method for Designing Quantum Algorithms (2008) (26)
- Tighter Relations between Sensitivity and Other Complexity Measures (2014) (26)
- A Note on Quantum Black-Box Complexity of Almost all Boolean Functions (1998) (25)
- Spatial search on grids with minimum memory (2013) (25)
- Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test (2017) (25)
- Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games (2017) (24)
- On Physical Problems that are Slightly More Difficult than QMA (2013) (23)
- Inductive Inference with Procrastination: Back to Definitions (1999) (23)
- Sensitivity Versus Certificate Complexity of Boolean Functions (2015) (23)
- Exact quantum algorithms have advantage for almost all Boolean functions (2014) (23)
- ROM-based computation: quantum versus classical (2001) (22)
- On Counting AC0 Circuits with Negative Constants (1998) (21)
- A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search (2005) (21)
- Improved algorithms for quantum identification of Boolean oracles (2006) (21)
- Quantum algorithms for search with wildcards and combinatorial group testing (2012) (20)
- The minimum distance problem for two-way entanglement purification (2003) (20)
- Polynomials, Quantum Query Complexity, and Grothendieck's Inequality (2015) (20)
- Lower bound for a class of weak quantum coin flipping protocols (2002) (20)
- Random Tensor Theory: Extending Random Matrix Theory to Mixtures of Random Product States (2009) (20)
- Quantum Finite Automata (2011) (19)
- Quantum Walks with Multiple or Moving Marked Locations (2008) (19)
- Quantum Property Testing for Bounded-Degree Graphs (2010) (18)
- Upper Bounds on Multiparty Communication Complexity of Shifts (1996) (18)
- Separations in Query Complexity Based on Pointer Functions (2015) (17)
- Delayed Binary Search, or Playing Twenty Questions with a Procrastinator (2002) (17)
- Imroved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function (2000) (16)
- Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language (2020) (16)
- Oscillatory localization of quantum walks analyzed by classical electric circuits (2016) (15)
- Quantum Strategies Are Better Than Classical in Almost Any XOR Game (2011) (15)
- New Developments in Quantum Algorithms (2010) (15)
- The quantum query complexity of certification (2009) (14)
- The communication complexity of enumeration, elimination, and selection (2000) (14)
- Size of Sets with Small Sensitivity: A Generalization of Simon's Lemma (2014) (13)
- Nonlocal Quantum XOR Games for Large Number of Players (2010) (12)
- How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions? (2012) (12)
- A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity (2014) (12)
- Parsimony hierarchies for inductive inference (2004) (11)
- Quantum algorithms for formula evaluation (2010) (11)
- Extracting quantum entanglement (general entanglement purification protocols) (2001) (11)
- Computing with highly mixed states (extended abstract) (2000) (10)
- Optimal quantum query bounds for almost all Boolean functions (2012) (10)
- Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size (2009) (9)
- Probabilistic inductive inference: a survey (1999) (9)
- Exact quantum query complexity of EXACTk, ln (2016) (9)
- Probabilistic and team PFIN-type learning: general properties (2005) (9)
- Quantum Finite Multitape Automata (1999) (8)
- Quantum Query Complexity of Boolean Functions with Small On-Sets (2008) (8)
- Limits on entropic uncertainty relations for 3 and more MUBs (2009) (8)
- Grover's Algorithm with Errors (2012) (8)
- Analysis of the extended hitting time and its properties (2014) (8)
- A random-walk benchmark for single-electron circuits (2020) (7)
- Effects of Kolmogorov Complexity Present in Inductive Inference as Well (1997) (7)
- Parameterized Quantum Query Complexity of Graph Collision (2013) (7)
- The power of procrastination in inductive inference: How it depends on used ordinal notations (1995) (7)
- Transformations that Preserve Learnability (1996) (7)
- Quantum speedup for track reconstruction in particle accelerators (2021) (7)
- Limits on entropic uncertainty relations (2010) (6)
- Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems (2004) (6)
- Exact query complexity of some special classes of Boolean functions (2014) (6)
- Distributed construction of quantum fingerprints (2003) (6)
- Correcting for potential barriers in quantum walk search (2015) (6)
- On the space efficiency of one way quantum finite automata (1998) (6)
- Optimal Classical Random Access Codes Using Single d-level Systems (2015) (6)
- A quantum lovász local lemma (2010) (5)
- General Inductive Inference Types Based on Linearly-Ordered Sets (1996) (5)
- Towards the classical communication complexity of entanglement distillation protocols with incomplete information (2002) (5)
- Quantum algorithms for computational geometry problems (2020) (5)
- Advantage of Quantum Strategies in Random Symmetric XOR Games (2012) (5)
- Playing twenty questions with a procrastinator (1999) (5)
- All Classical Adversary Methods Are Equivalent for Total Functions (2017) (5)
- Hierarchies of probabilistic and team FIN-learning (2001) (5)
- Extracting Quantum Entanglement (2002) (4)
- Fast Matrix Multiplication: Limitations of the Laser Method (2014) (4)
- Quantum Algorithm for Element Distinctness (2008) (4)
- Application of Kolmogorov Complexity to Inductive Inference with Limited Memory (1995) (4)
- New upper bound on block sensitivity and certificate complexity in terms of sensitivity (2013) (4)
- Strong supremacy of quantum systems as communication resource (2017) (3)
- Enumerable Classes of Total Recursive Functions: Complexity of Inductive Inference (1994) (3)
- Quantum Search of Spatial Regions ( Extended Abstract ) ∗ (2003) (3)
- Almost quadratic gap between partition complexity and query/communication complexity (2015) (3)
- Exact Quantum Query Complexity of \text EXACT_k, l^n (2016) (3)
- Weak Parity (2013) (3)
- On Block Sensitivity and Fractional Block Sensitivity (2018) (3)
- On symmetric nonlocal games (2013) (3)
- Size of Quantum Versus Deterministic Finite Automata (2003) (2)
- Quantum Lower Bounds for 2D-Grid and Dyck Language (2019) (2)
- Recent Developments in Quantum Algorithms and Complexity (2014) (2)
- Provable Advantage for Quantum Strategies in Random Symmetric XOR Games (2013) (2)
- Team Learning as a Game (1997) (2)
- On quantum versus classical query complexity (2021) (2)
- Two-Way Entanglement Purification for Finite Block Size (2009) (2)
- Quantum Algorithm for Search on Grids (2008) (1)
- Quantum Lower Bounds by Quantum Arguments1 (2007) (1)
- Quantum algorithms a decade after shor (2004) (1)
- Quantum Query Complexity of Almost All Functions with Fixed On-set Size (2016) (1)
- Publisher's Note: Spatial Search by Quantum Walk is Optimal for Almost All Graphs [Phys. Rev. Lett. 116, 100501 (2016)]. (2016) (1)
- An Elementary Proof of the Adiabatic Theorem (2006) (1)
- Investigating Quantum Speedup for Track Reconstruction: Classical and Quantum Computational Complexity Analysis (2021) (1)
- Weak and Strong Recognition by 2-way Randomized Automata (1997) (1)
- Optimal one-shot quantum algorithm for EQUALITY and AND (2016) (1)
- An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree (2023) (1)
- Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems (2006) (1)
- Quantum Direct Product Theorems for Symmetric Functions and Time-Space Tradeoffs (2005) (1)
- Worst Case Analysis of Non-local Games (2011) (1)
- Oscillatory Localization of Quantum Walks by Classical Electric Circuits (2016) (1)
- Random Tensor Theory: Extending Random Matrix Theory to Mixtures of Random Product States (2012) (0)
- Andris Ambainis Derandomizing Approximate Quantum Encryption (2005) (0)
- Randomization in Learning Theory (2007) (0)
- Inductive inference and constructive ordinals (1997) (0)
- Optimization Problem in Inductive Inference (1995) (0)
- Tight Bounds on the Learnability of Evolution (2007) (0)
- Quantum bounds for 2D-grid and Dyck language (2023) (0)
- On Block Sensitivity and Fractional Block Sensitivity (2018) (0)
- Extracting Quantum Entanglement ( General Entanglement Purification Protocols ) 4 (2002) (0)
- Cs 860: Quantum Algorithms and Complexity Quantum Lower Bounds (0)
- Team Learning and Quasi-Closedness inInductive Inference ? (2000) (0)
- Quantum Complexity for Vector Domination Problem (2023) (0)
- How rich is the structure of the intrinsic complexity of learning (2000) (0)
- A hybrid quantum-classical approach for inference on restricted Boltzmann machines (2023) (0)
- 1.1 Background (1995) (0)
- C C ] 2 0 N ov 2 00 4 Lower bounds on the Deterministic and Quantum Communication Complexity of HAM ( a ) n (2008) (0)
- Rūsiņš Mārtiņš Freivalds (1942–2016), Latvian computer scientist (2016) (0)
- Parity oblivious d-level random access codes and class of noncontextuality inequalities (2019) (0)
- Session details: Session 10B (2007) (0)
- Derandomizing Approximate Quantum Encryption Derandomizing Approximate Quantum Encryption (2005) (0)
- Quantum entanglement, quantum communication and the limits of quantum computing (2001) (0)
- A random-walk benchmark for single-electron circuits (2021) (0)
- CS 860 : Quantum Algorithms and Complexity Spring 2006 Lecture 15 — June 20 (2006) (0)
- A note about claw function with a small range (2021) (0)
- Limited preparation contextuality in quantum theory leads to Cirel'son bound (2015) (0)
- Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture (2022) (0)
- CS 860 Lecture 12 — June 13 Spring 2006 2 Lower Bound For Triangle Problem (0)
- On learning formulas in the limit and with assurance (2001) (0)
- Towards the Communication Complexity of Entanglement Distillation Protocols (2002) (0)
- J ul 2 01 8 Automata and Quantum Computing (0)
- The quantum query complexity of combinatorial group testing (2012) (0)
- A ug 2 01 6 Exact quantum query complexity of EXACT nk , l (2016) (0)
- Quantum Query Complexity of Almost All Functions with Fixed On-set Size (2016) (0)
- On the Coppersmith – Winograd method (2014) (0)
- How Rich Is The Structure ofIntrinsic Complexity of Learning ? (0)
- Full Characterization of Oscillatory Localization of Quantum Walks (2016) (0)
- Better algorithms for search by quantum walks on two-dimensional grid (2012) (0)
- Four Collaborations with Rūsiņš Freivalds (2016) (0)
- Lower bounds on the Deterministic and Quantum Communication Complexity of HAMna (2004) (0)
- 2 2 0 Se p 20 02 The quantum to classical transition for random walks (2008) (0)
- Improved Algorithm and Lower Bound for Variable Time Quantum Search (2023) (0)
- Strong dispersion property for the quantum walk on the hypercube (2022) (0)
This paper list is powered by the following services:
Other Resources About Andris Ambainis
What Schools Are Affiliated With Andris Ambainis?
Andris Ambainis is affiliated with the following schools:
