pith. sign in

Andris Ambainis

Identifiers

  • name variant Andris Ambainis 0.60 · backfill

Papers (91)

  1. A sharp interaction-degree threshold for simulating QAOA quant-ph · 2026 · author #2
  2. Quadratic speedup for finding marked vertices by quantum walks quant-ph · 2019 · author #1
  3. On Block Sensitivity and Fractional Block Sensitivity cs.CC · 2018 · author #1
  4. Quantum Speedups for Exponential-Time Dynamic Programming Algorithms quant-ph · 2018 · author #1
  5. Understanding Quantum Algorithms via Query Complexity quant-ph · 2017 · author #1
  6. All Classical Adversary Methods are Equivalent for Total Functions cs.CC · 2017 · author #1
  7. Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test cs.CC · 2017 · author #2
  8. Strong supremacy of quantum systems as communication resource quant-ph · 2017 · author #3
  9. Optimal one-shot quantum algorithm for EQUALITY and AND quant-ph · 2017 · author #1
  10. Exact quantum query complexity of $\rm{EXACT}_{k,l}^n$ quant-ph · 2016 · author #1
  11. Parity Oblivious d-Level Random Access Codes and Class of Noncontextuality Inequalities quant-ph · 2016 · author #1
  12. Full Characterization of Oscillatory Localization of Quantum Walks quant-ph · 2016 · author #1
  13. Oscillatory Localization of Quantum Walks Analyzed by Classical Electric Circuits quant-ph · 2016 · author #1
  14. Almost quadratic gap between partition complexity and query/communication complexity cs.CC · 2015 · author #1
  15. Polynomials, Quantum Query Complexity, and Grothendieck's Inequality quant-ph · 2015 · author #2
  16. Spatial search by quantum walk is optimal for almost all graphs quant-ph · 2015 · author #3
  17. Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing cs.CC · 2015 · author #1
  18. Automata and Quantum Computing cs.FL · 2015 · author #1
  19. Limited preparation contextuality in quantum theory and its relation to the Cirel'son bound quant-ph · 2015 · author #5
  20. Separations in Query Complexity Based on Pointer Functions cs.CC · 2015 · author #1
  21. Correcting for Potential Barriers in Quantum Walk Search quant-ph · 2015 · author #1
  22. Sensitivity versus Certificate Complexity of Boolean Functions cs.CC · 2015 · author #1
  23. Quantum Search with Multiple Walk Steps per Oracle Query quant-ph · 2015 · author #2
  24. Forrelation: A Problem that Optimally Separates Quantum from Classical Computing quant-ph · 2014 · author #2
  25. Tighter Relations Between Sensitivity and Other Complexity Measures cs.CC · 2014 · author #1
  26. Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma cs.CC · 2014 · author #1
  27. Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding quant-ph · 2014 · author #1
  28. Exact quantum algorithms have advantage for almost all Boolean functions cs.CC · 2014 · author #1
  29. A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity cs.CC · 2014 · author #1
  30. On physical problems that are slightly more difficult than QMA quant-ph · 2013 · author #1
  31. Spatial Search on Grids with Minimum Memory quant-ph · 2013 · author #1
  32. Weak Parity cs.CC · 2013 · author #2
  33. New upper bound on block sensitivity and certificate complexity in terms of sensitivity cs.CC · 2013 · author #1
  34. Parameterized Quantum Query Complexity of Graph Collision quant-ph · 2013 · author #1
  35. Provable Advantage for Quantum Strategies in Random Symmetric XOR Games quant-ph · 2013 · author #1
  36. Exact quantum query complexity of EXACT and THRESHOLD quant-ph · 2013 · author #1
  37. Superlinear advantage for exact quantum algorithms quant-ph · 2012 · author #1
  38. Quantum algorithms for search with wildcards and combinatorial group testing quant-ph · 2012 · author #1
  39. Search by quantum walks on two-dimensional grid without amplitude amplification quant-ph · 2011 · author #1
  40. Quantum strategies are better than classical in almost any XOR game quant-ph · 2011 · author #1
  41. Worst case analysis of non-local games quant-ph · 2011 · author #1
  42. New separation between $s(f)$ and $bs(f)$ cs.CC · 2011 · author #1
  43. Superiority of exact quantum automata for promise problems cs.CC · 2011 · author #1
  44. Quantum property testing for bounded-degree graphs quant-ph · 2010 · author #1
  45. Symmetry-assisted adversaries for quantum state generation quant-ph · 2010 · author #1
  46. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations quant-ph · 2010 · author #1
  47. New Developments in Quantum Algorithms quant-ph · 2010 · author #1
  48. Quantum algorithms for formula evaluation quant-ph · 2010 · author #1
  49. A Quantum Lovasz Local Lemma quant-ph · 2009 · author #1
  50. The Need for Structure in Quantum Speedups quant-ph · 2009 · author #2
  51. Random tensor theory: extending random matrix theory to random product states quant-ph · 2009 · author #1
  52. Limits on entropic uncertainty relations for 3 and more MUBs quant-ph · 2009 · author #1
  53. The quantum query complexity of certification quant-ph · 2009 · author #1
  54. Quantum Random Access Codes with Shared Randomness quant-ph · 2008 · author #1
  55. Non-malleable encryption of quantum information quant-ph · 2008 · author #1
  56. Improved constructions of quantum automata quant-ph · 2008 · author #1
  57. A nearly optimal discrete query quantum algorithm for evaluating NAND formulas quant-ph · 2007 · author #1
  58. Quantum t-designs: t-wise independence in the quantum world quant-ph · 2007 · author #1
  59. Quantum search with variable times quant-ph · 2006 · author #1
  60. A new quantum lower bound method, with an application to strong direct product theorem for quantum search quant-ph · 2005 · author #1
  61. Quantum search algorithms quant-ph · 2005 · author #1
  62. Probabilistic and Team PFIN-type Learning: General Properties cs.LG · 2005 · author #1
  63. Robust Quantum Algorithms for Oracle Identification quant-ph · 2004 · author #1
  64. Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance cs.CC · 2004 · author #1
  65. An Elementary Proof of the Quantum Adiabatic Theorem quant-ph · 2004 · author #1
  66. Small Pseudo-Random Families of Matrices: Derandomizing Approximate Quantum Encryption quant-ph · 2004 · author #1
  67. Quantum walks and their algorithmic applications quant-ph · 2004 · author #1
  68. Quantum Identification of Boolean Oracles quant-ph · 2004 · author #1
  69. Coins Make Quantum Walks Faster quant-ph · 2004 · author #1
  70. Quantum walk algorithm for element distinctness quant-ph · 2003 · author #1
  71. The Minimum Distance Problem for Two-Way Entanglement Purification quant-ph · 2003 · author #1
  72. Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range quant-ph · 2003 · author #1
  73. Polynomial degree vs. quantum query complexity quant-ph · 2003 · author #1
  74. Distributed construction of quantum fingerprints quant-ph · 2003 · author #1
  75. Multiparty Quantum Coin Flipping quant-ph · 2003 · author #1
  76. Quantum Search of Spatial Regions quant-ph · 2003 · author #2
  77. Cryptographic Randomized Response Techniques cs.CC · 2003 · author #1
  78. Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information quant-ph · 2002 · author #1
  79. Lower bound for a class of weak quantum coin flipping protocols quant-ph · 2002 · author #1
  80. A New Protocol and Lower Bounds for Quantum Coin Flipping quant-ph · 2002 · author #1
  81. Extracting Quantum Entanglement (General Entanglement Purification Protocols) quant-ph · 2001 · author #1
  82. Exact results for accepting probabilities of quantum automata quant-ph · 2001 · author #1
  83. Quantum Walks On Graphs quant-ph · 2000 · author #2
  84. On the class of languages recognizable by 1-way quantum finite automata quant-ph · 2000 · author #1
  85. Computing with highly mixed states quant-ph · 2000 · author #1
  86. Quantum lower bounds by quantum arguments quant-ph · 2000 · author #1
  87. Quantum finite multitape automata quant-ph · 1999 · author #1
  88. Probabilities to accept languages by quantum finite automata quant-ph · 1999 · author #1
  89. Probabilistic Inductive Inference:a Survey cs.LG · 1999 · author #1
  90. A better lower bound for quantum algorithms searching an ordered list quant-ph · 1999 · author #1
  91. A note on quantum black-box complexity of almost all Boolean functions quant-ph · 1998 · author #1

Mentions

  • 1211.0721 #1 · backfill · confidence 0.70 Andris Ambainis
  • 1210.1148 #1 · backfill · confidence 0.70 Andris Ambainis
  • 1112.3337 #1 · backfill · confidence 0.70 Andris Ambainis
  • 1112.3330 #1 · backfill · confidence 0.70 Andris Ambainis
  • 1112.2856 #1 · backfill · confidence 0.70 Andris Ambainis
  • 2605.22758 #2 · arxiv_oai · confidence 0.70 Andris Ambainis
  • 1108.3494 #1 · backfill · confidence 0.70 Andris Ambainis
  • 1101.3837 #1 · backfill · confidence 0.70 Andris Ambainis
  • 1012.3174 #1 · backfill · confidence 0.70 Andris Ambainis
  • 1012.2112 #1 · backfill · confidence 0.70 Andris Ambainis
  • 1010.4458 #1 · backfill · confidence 0.70 Andris Ambainis
  • 1006.4014 #1 · backfill · confidence 0.70 Andris Ambainis
  • 1006.3651 #1 · backfill · confidence 0.70 Andris Ambainis
  • 0911.1696 #1 · backfill · confidence 0.70 Andris Ambainis
  • 0911.0996 #2 · backfill · confidence 0.70 Andris Ambainis
  • 0910.0472 #1 · backfill · confidence 0.70 Andris Ambainis
  • 0909.3720 #1 · backfill · confidence 0.70 Andris Ambainis
  • 0903.1291 #1 · backfill · confidence 0.70 Andris Ambainis
  • 0810.2937 #1 · backfill · confidence 0.70 Andris Ambainis
  • 0808.0353 #1 · backfill · confidence 0.70 Andris Ambainis
  • 0805.1686 #1 · backfill · confidence 0.70 Andris Ambainis
  • 0704.3628 #1 · backfill · confidence 0.70 Andris Ambainis

Frequent Coauthors