Andris Ambainis, Ph.D. - Publications

Affiliations: 
2001 University of California, Berkeley, Berkeley, CA, United States 
Area:
Security (SEC); Theory (THY), Complexity theory

91 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2019 Ambainis A, Banik M, Chaturvedi A, Kravchenko D, Rai A. Parity oblivious d-level random access codes and class of noncontextuality inequalities Quantum Information Processing. 18. DOI: 10.1007/S11128-019-2228-3  0.559
2017 Ambainis A, Balodis K, Belovs A, Lee T, Santha M, Smotrovs J. Separations in Query Complexity Based on Pointer Functions Journal of the Acm. 64: 1-24. DOI: 10.1145/3106234  0.405
2016 Chakraborty S, Novo L, Ambainis A, Omar Y. Publisher's Note: Spatial Search by Quantum Walk is Optimal for Almost All Graphs [Phys. Rev. Lett. 116, 100501 (2016)]. Physical Review Letters. 116: 249901. PMID 27367413 DOI: 10.1103/Physrevlett.116.249901  0.489
2016 Chakraborty S, Novo L, Ambainis A, Omar Y. Spatial Search by Quantum Walk is Optimal for Almost all Graphs. Physical Review Letters. 116: 100501. PMID 27015464 DOI: 10.1103/Physrevlett.116.100501  0.55
2016 Ambainis A, Iraids J. Optimal One-shot Quantum Algorithm for EQUALITY and AND Baltic Journal of Modern Computing. 4. DOI: 10.22364/bjmc.2016.4.4.09  0.459
2016 Ambainis A. Superlinear advantage for exact quantum algorithms Siam Journal On Computing. 45: 617-631. DOI: 10.1137/130939043  0.597
2016 Ambainis A, Prūsis K, Vihrovs J, Wong TG. Oscillatory localization of quantum walks analyzed by classical electric circuits Physical Review A. 94. DOI: 10.1103/Physreva.94.062324  0.522
2016 Ambainis A, Iwama K, Nakanishi M, Nishimura H, Raymond R, Tani S, Yamashita S. Quantum Query Complexity of Almost All Functions with Fixed On-set Size Computational Complexity. 25: 723-735. DOI: 10.1007/S00037-016-0139-6  0.406
2016 Ambainis A, Belovs A, Regev O, De Wolf R. Efficient quantum algorithms for (Gapped) group testing and junta testing Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 2: 903-922.  0.474
2015 Ambainis A, Gasarch W, Srinivasan A, Utis A. Lower bounds on the deterministic and quantum communication complexity of hamming-distance problems Acm Transactions On Computation Theory. 7. DOI: 10.1145/2698587  0.536
2015 Aaronson S, Ambainis A. Forrelation: A problem that optimally separates quantum from classical computing Proceedings of the Annual Acm Symposium On Theory of Computing. 14: 307-316. DOI: 10.1137/15M1050902  0.745
2015 Banik M, Bhattacharya SS, Mukherjee A, Roy A, Ambainis A, Rai A. Limited preparation contextuality in quantum theory and its relation to the Cirel'son bound Physical Review a - Atomic, Molecular, and Optical Physics. 92. DOI: 10.1103/Physreva.92.030103  0.518
2015 Wong TG, Ambainis A. Quantum search with multiple walk steps per oracle query Physical Review a - Atomic, Molecular, and Optical Physics. 92. DOI: 10.1103/Physreva.92.022338  0.576
2015 Ambainis A, Portugal R, Nahimov N. Spatial search on grids with minimum memory Quantum Information and Computation. 15: 1233-1247.  0.442
2015 Ambainis A, Gruska J, Zheng S. Exact quantum algorithms have advantage for almost all boolean functions Quantum Information and Computation. 15: 435-452.  0.491
2015 Ambainis A, Wong TG. Correcting for potential barriers in quantum walk search Quantum Information and Computation. 15: 1365-1372.  0.501
2014 Aaronson S, Ambainis A. Theory of Computing. 10: 133-166. DOI: 10.4086/Toc.2014.V010A006  0.736
2014 Ambainis A, Rosmanis A, Unruh D. Quantum attacks on classical proof systems: The hardness of quantum rewinding Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 474-483. DOI: 10.1109/FOCS.2014.57  0.528
2014 Ambainis A. On physical problems that are slightly more difficult than QMA Proceedings of the Annual Ieee Conference On Computational Complexity. 32-43. DOI: 10.1109/CCC.2014.12  0.35
2014 Ambainis A, de Wolf R. How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions? Computational Complexity. 23: 305-322. DOI: 10.1007/S00037-014-0083-2  0.605
2014 Aaronson S, Ambainis A, Balodis K, Bavarian M. Weak parity Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8572: 26-38. DOI: 10.1007/978-3-662-43948-7_3  0.462
2014 Ambainis A. Recent developments in quantum algorithms and complexity Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8614: 1-4. DOI: 10.1007/978-3-319-09704-6_1  0.487
2014 Ambainis A, Montanaro A. Quantum algorithms for search with wildcards and combinatorial group testing Quantum Information and Computation. 14: 439-453.  0.425
2013 Ambainis A, Iraids J, Smotrovs J. Exact quantum query complexity of EXACT and THRESHOLD Leibniz International Proceedings in Informatics, Lipics. 22: 263-269. DOI: 10.4230/LIPIcs.TQC.2013.263  0.52
2013 Ambainis A, Iraids J. Provable advantage for quantum strategies in random symmetric XOR games Leibniz International Proceedings in Informatics, Lipics. 22: 146-156. DOI: 10.4230/LIPIcs.TQC.2013.146  0.374
2013 Ambainis A, Backurs A, Smotrovs J, De Wolf R. Optimal quantum query bounds for almost all boolean functions Leibniz International Proceedings in Informatics, Lipics. 20: 446-453. DOI: 10.4230/LIPIcs.STACS.2013.446  0.449
2013 Ambainis A, Kravchenko D, Nahimov N, Rivosh A, Virza M. On symmetric nonlocal games Theoretical Computer Science. 494: 36-48. DOI: 10.1016/J.Tcs.2013.03.011  0.481
2013 Ambainis A, Iraids J, Kravchenko D, Virza M. Advantage of quantum strategies in random symmetric XOR games Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7721: 57-68. DOI: 10.1007/978-3-642-36046-6_7  0.368
2013 Ambainis A, Bačkurs A, Nahimovs N, Rivosh A. Grover's algorithm with errors Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7721: 180-189. DOI: 10.1007/978-3-642-36046-6_17  0.404
2013 Ambainis A, Bačkurs A, Balodis K, Škuškovniks A, Smotrovs J, Virza M. Worst case analysis of non-local games Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7741: 121-132. DOI: 10.1007/978-3-642-35843-2_12  0.315
2013 Ambainis A, Bačkurs A, Nahimovs N, Ozols R, Rivosh A. Search by quantum walks on two-dimensional grid without amplitude amplification Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7582: 87-97. DOI: 10.1007/978-3-642-35656-8_7  0.333
2012 Ambainis A. Variable time amplitude amplification and quantum algorithms for linear Algebra problems Leibniz International Proceedings in Informatics, Lipics. 14: 636-647. DOI: 10.4230/LIPIcs.STACS.2012.636  0.4
2012 Ambainis A, Kempe J, Sattath O. A quantum Lovász Local Lemma Journal of the Acm. 59. DOI: 10.1145/2371656.2371659  0.386
2012 Ambainis A, Yakaryilmaz A. Superiority of exact quantum automata for promise problems Information Processing Letters. 112: 289-291. DOI: 10.1016/J.Ipl.2012.01.001  0.534
2012 Ambainis A, Harrow AW, Hastings MB. Random Tensor Theory: Extending Random Matrix Theory to Mixtures of Random Product States Communications in Mathematical Physics. 310: 25-74. DOI: 10.1007/S00220-011-1411-X  0.37
2012 Ambainis A, Bačkurs A, Balodis K, Kravčenko D, Ozols R, Smotrovs J, Virza M. Quantum strategies are better than classical in almost any XOR game Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7391: 25-37. DOI: 10.1007/978-3-642-31594-7_3  0.388
2011 Ambainis A, Magnin L, Roetteler M, Roland J. Symmetry-assisted adversaries for quantum state generation Proceedings of the Annual Ieee Conference On Computational Complexity. 167-177. DOI: 10.1109/CCC.2011.24  0.478
2011 Ambainis A, Childs AM, Liu YK. Quantum property testing for bounded-degree graphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6845: 365-376. DOI: 10.1007/978-3-642-22935-0_31  0.582
2010 Ambainis A. Theory of Computing. 6: 1-25. DOI: 10.4086/Toc.2010.V006A001  0.466
2010 Ambainis A, Childs AM, Reichardt BW, Špalek R, Zhang S. Any AND-OR formula of size N can be evaluated in time N 1/2+0(1) on a quantum computer Siam Journal On Computing. 39: 2513-2530. DOI: 10.1109/Focs.2007.57  0.757
2010 Ambainis A. Quantum search with variable times Theory of Computing Systems. 47: 786-807. DOI: 10.1007/s00224-009-9219-1  0.42
2010 Ambainis A. New developments in quantum algorithms Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6281: 1-11. DOI: 10.1007/978-3-642-15155-2_1  0.621
2010 Ambainis A, Kravchenko D, Nahimovs N, Rivosh A. Nonlocal quantum XOR games for large number of players Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6108: 72-83. DOI: 10.1007/978-3-642-13562-0_8  0.458
2010 Ambainis A, Childs AM, le Gall F, Tani S. The quantum query complexity of certification Quantum Information and Computation. 10: 0181-0189.  0.481
2009 Ambainis A, Bouda J, Winter A. Nonmalleable encryption of quantum information Journal of Mathematical Physics. 50. DOI: 10.1063/1.3094756  0.387
2009 Ambainis A, Nahimovs N. Improved constructions of quantum automata Theoretical Computer Science. 410: 1916-1922. DOI: 10.1016/J.Tcs.2009.01.027  0.478
2009 Ambainis A, Špalek R, De Wolf R. A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs Algorithmica (New York). 55: 422-461. DOI: 10.1007/S00453-007-9022-9  0.511
2008 Ambainis A, Iwama K, Nakanishi M, Nishimura H, Raymond R, Tani S, Yamashita S. Quantum query complexity of boolean functions with small on-sets Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5369: 907-918. DOI: 10.1007/978-3-540-92182-0_79  0.371
2008 Ambainis A, Rivosh A. Quantum walks with multiple or moving marked locations Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4910: 485-496.  0.523
2008 Ambainis A. Quantum random walks - New method for designing quantum algorithms Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4910: 1-4.  0.521
2007 Ambainis A. Quantum walk algorithm for element distinctness Siam Journal On Computing. 37: 210-239. DOI: 10.1137/S0097539705447311  0.598
2007 Ambainis A, Childs AM, Reichardt BW, Špalek R, Zhang S. Any AND-OR formula of size N can be evaluated in time N1/2+o(1) on a quantum computer Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 363-372. DOI: 10.1109/FOCS.2007.4389507  0.715
2007 Ambainis A, Emerson J. Quantum t-designs: T-wise independence in the quantum world Proceedings of the Annual Ieee Conference On Computational Complexity. 129-140. DOI: 10.1109/CCC.2007.26  0.413
2007 Ambainis A, Iwama K, Kawachi A, Raymond R, Yamashita S. Improved algorithms for quantum identification of Boolean oracles Theoretical Computer Science. 378: 41-53. DOI: 10.1016/J.Tcs.2006.12.013  0.538
2006 Ambainis A, Schulman LJ, Vazirani U. Computing with highly mixed states Journal of the Acm. 53: 507-531. DOI: 10.1145/1147954.1147962  0.715
2006 Ambainis A, Gottesman D. The minimum distance problem for two-way entanglement purification Ieee Transactions On Information Theory. 52: 748-753. DOI: 10.1109/TIT.2005.862089  0.441
2006 Ambainis A. Polynomial degree vs. quantum query complexity Journal of Computer and System Sciences. 72: 220-238. DOI: 10.1016/J.Jcss.2005.06.006  0.631
2006 Ambainis A, Beaudry M, Golovkins M, Kikusts A, Mercer M, Therien D. Algebraic results on quantum automata Theory of Computing Systems. 39: 165-188. DOI: 10.1007/S00224-005-1263-X  0.514
2006 Ambainis A, Gasarch W, Srinivasan A, Utis A. Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4288: 628-637. DOI: 10.1007/11940128_63  0.482
2006 Ambainis A, Iwama K, Kawachi A, Raymond R, Yamashita S. Quantum identification of boolean oracles Topics in Applied Physics. 102: 3. DOI: 10.1007/11683858_1  0.425
2006 Ambainis A, Špalek R. Quantum algorithms for matching and network flows Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 3884: 172-183. DOI: 10.1007/11672142_13  0.358
2005 Ambainis A. Theory of Computing. 1: 37-46. DOI: 10.4086/Toc.2005.V001A003  0.535
2005 Ambainis A, Kempe J, Rivosh A. Coins make quantum walks faster Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 1099-1108.  0.544
2004 Ambainis A. Quantum search algorithms Acm Sigact News. 35: 22-35. DOI: 10.1145/992287.992296  0.574
2004 Ambainis A. A new protocol and lower bounds for quantum coin flipping Journal of Computer and System Sciences. 68: 398-416. DOI: 10.1016/J.Jcss.2003.07.010  0.558
2004 Ambainis A, Shi Y. Distributed construction of quantum fingerprints Quantum Information and Computation. 4: 146-151.  0.458
2004 Ambainis A, Smith A. Small pseudo-random families of matrices: derandomizing approximate quantum encryption Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 3122: 249-260.  0.447
2004 Ambainis A, Buhrman H, Dodis Y, Röhrig H. Multiparty quantum coin flipping Proceedings of the Annual Ieee Conference On Computational Complexity. 19: 250-259.  0.49
2004 Ambainis A, Yang K. Towards the classical communication complexity of entanglement distillation protocols with incomplete information Proceedings of the Annual Ieee Conference On Computational Complexity. 19: 305-319.  0.354
2003 Brun TA, Carteret HA, Ambainis A. Quantum to classical transition for random walks. Physical Review Letters. 91: 130602. PMID 14525294 DOI: 10.1103/Physrevlett.91.130602  0.585
2003 Aaronson S, Ambainis A. Quantum search of spatial regions Annual Symposium On Foundations of Computer Science - Proceedings. 200-209. DOI: 10.4086/Toc.2005.V001A004  0.727
2003 AMBAINIS A. QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS International Journal of Quantum Information. 1: 507-518. DOI: 10.1142/S0219749903000383  0.611
2003 Ambainis A, Schulman LJ, Ta-Shma A, Vazirani U, Wigderson A. The quantum communication complexity of sampling Siam Journal On Computing. 32: 1570-1585. DOI: 10.1137/S009753979935476  0.703
2003 Brun TA, Carteret HA, Ambainis A. Quantum walks driven by many coins Physical Review a - Atomic, Molecular, and Optical Physics. 67: 523171-5231717. DOI: 10.1103/Physreva.67.052317  0.526
2003 Brun TA, Carteret HA, Ambainis A. Quantum random walks with decoherent coins Physical Review a - Atomic, Molecular, and Optical Physics. 67: 032304/1-032304/9. DOI: 10.1103/Physreva.67.032304  0.577
2003 Ambainis A, Ķikusts A. Exact results for accepting probabilities of quantum automata Theoretical Computer Science. 295: 3-25. DOI: 10.1016/S0304-3975(02)00393-6  0.397
2003 Brun TA, Carteret HA, Ambainis A. Quantum to Classical Transition for Random Walks Physical Review Letters. 91: 1306021-1306024.  0.48
2002 Ambainis A, Nayak A, Ta-Shma A, Vazirani U. Dense quantum coding and quantum finite automata Journal of the Acm. 49: 496-511. DOI: 10.1145/581771.581773  0.761
2002 Ambainis A, Watrous J. Two-way finite automata with quantum and classical states Theoretical Computer Science. 287: 299-311. DOI: 10.1016/S0304-3975(02)00138-X  0.563
2002 Ambainis A, Bloch SA, Schweizer DL. Delayed binary search, or playing twenty questions with a procrastinator Algorithmica (New York). 32: 641-650. DOI: 10.1007/S00453-001-0097-4  0.307
2002 Ambainis A. Quantum lower bounds by quantum arguments Journal of Computer and System Sciences. 64: 750-767. DOI: 10.1006/jcss.2002.1826  0.516
2002 Travaglione BC, Nielsen MA, Wiseman HM, Ambainis A. ROM-based computation: Quantum versus classical Quantum Information and Computation. 2: 324-332.  0.472
2002 Ambainis A, Smith A, Yang K. Extracting quantum entanglement (general entanglement purifications protocols) Proceedings of the Annual Ieee Conference On Computational Complexity. 103-112.  0.469
2001 Ambainis A, De Wolf R. Average-case quantum query complexity Journal of Physics a: Mathematical and General. 34: 6741-6754. DOI: 10.1088/0305-4470/34/35/302  0.566
2001 Ambainis A, Buhrman H, Gasarch W, Kalyanasundaram B, Torenvliet L. The Communication Complexity of Enumeration, Elimination, and Selection Journal of Computer and System Sciences. 63: 148-185. DOI: 10.1006/Jcss.2001.1761  0.325
2001 Ambainis A, Bach E, Nayak A, Vishwanath A, Watrous J. One-dimensional quantum walks Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 37-49.  0.467
2001 Aharonov D, Ambainis A, Kempe J, Vazirani U. Quantum walks on graphs Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 50-59.  0.712
1999 Ambainis A. A note on quantum black-box complexity of almost all Boolean functions Information Processing Letters. 71: 5-7. DOI: 10.1016/S0020-0190(99)00079-4  0.51
1999 Ambainis A, Bonner R, Freivalds R, Ķikusts A. Probabilities to accept languages by quantum finite automata Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1627: 174-183. DOI: 10.1007/3-540-48686-0_17  0.323
1999 Ambainis A, Bonner R, Freivalds R, Golovkins M, Karpinski M. Quantum finite multitape automata Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1725: 340-348. DOI: 10.1007/3-540-47849-3_21  0.477
1999 Ambainis A, Nayak A, Ta-Shma A, Vazirani U. Dense quantum coding and a lower bound for 1-way quantum automata Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 376-383.  0.754
Show low-probability matches.