Andris Ambainis










Research papers

2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 1995 1994

List of my papers on
arXiv | DBLP | Google Scholar



A. Ambainis, A. Yakaryilmaz. Superiority of exact quantum automata for promise problems. Information Processing Letters 112(7): 289-291 (2012)

A. Ambainis, A. W. Harrow and M. B. Hastings. "Random Tensor Theory: Extending Random Matrix Theory to Mixtures of Random Product States". Communications in Mathematical Physics, 310, 25-74 (2012)

A. Ambainis. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. Proceedings of STACS 2012, to appear. Also arXiv:1010.4458.



A. Ambainis, A. M. Childs, Y.-K. Liu. Quantum Property Testing for Bounded-Degree Graphs. APPROX-RANDOM 2011: 365-376

S. Aaronson, A. Ambainis. The Need for Structure in Quantum Speedups. ICS 2011: 338-352

A. Ambainis, L. Magnin, M. Roetteler, J. Roland. Symmetry-Assisted Adversaries for Quantum State Generation. IEEE Conference on Computational Complexity 2011: 167-177

A. Ambainis. Quantum Finite Automata (invited talk). NCMA 2011: 9-13

A. Ambainis, X. Sun. New separation between s(f) and bs(f). Electronic Colloquium on Computational Complexity (ECCC) 18: 116 (2011)

A. Ambainis, A. Bačkurs, K. Balodis, D. Kravchenko, R. Ozols, J. Smotrovs, M. Virza: Quantum strategies are better than classical in almost any XOR game. arXiv:1112.3330 (2011)

A. Ambainis, A. Bačkurs, N. Nahimovs, R. Ozols, A. Rivosh: Search by quantum walks on two-dimensional grid without amplitude amplification. arXiv:1112.3337 (2011)



A. Ambainis. New Developments in Quantum Algorithms (invited talk). MFCS 2010: 1-11

A. Ambainis. Quantum algorithms for formula evaluation (invited talk) Quantum Cryptography and Computing: Theory and Implementation, Kluwer Academic Publishers. Also arXiv:1006.3651 (2010).

A. Ambainis, J. Kempe, O. Sattath. "A quantum Lovász local lemma". STOC 2010: 151-160

A. Ambainis, D. Kravchenko, N. Nahimovs, A. Rivosh. Nonlocal Quantum XOR Games for Large Number of Players. TAMC 2010, pp. 72-83.

A. Ambainis. A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search. Theory of Computing, 6:1-25, 2010. Earlier version: STOC’2006.

A. Ambainis, A.M. Childs, F. Le Gall, and S. Tani. The quantum query complexity of certification. Quantum Information and Computation, 10:181-189, 2010.

A. Ambainis. Quantum search with variable times. Theory of Computing Systems, 47(3): 786-807, 2010 (special issue for the best papers of STACS'2008).

A. Ambainis. Limits on entropic uncertainty relations. Quantum Information and Computation, 10:848-858, 2010.

A. Ambainis, A. Childs, B. Reichardt, R. Spalek, S. Zhang, "Any AND-OR formula of size N can be evaluated in time O(N^{1/2+epsilon}) on a quantum computer". SIAM Journal on Computing, 39(6): 2513-2530, 2010. Earlier version of this paper at FOCS'07.



A. Ambainis, R. Spalek, R. de Wolf. A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs. Algorithmica, 55: 422-461, 2009. Earlier version: STOC’2006.

A. Ambainis, N. Nahimovs. "Improved Constructions of Quantum Automata". Theoretical Computer Science, 410: 1916-1922, 2009. Earlier version: TQC’2008.

A. Ambainis, J. Bouda, A. Winter. Nonmalleable encryption of quantum information. Journal of Mathematical Physics. 50: 42106-42113, 2009.



A. Ambainis, A. Rivosh: Quantum Walks with Multiple or Moving Marked Locations. SOFSEM 2008: 485-496

A. Ambainis. Probabilistic PFIN-type learning: general properties. Journal of Computer and System Sciences, 74: 457-489, 2008. Earlier version: COLT’1996.

A. Ambainis. Quantum random walks - new method for designing quantum algorithms (invited talk). Proceedings of the Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pp.1-4, Novy Smokovec, Slovakia, January 2008.

A. Ambainis, K. Iwama, M. Nakanishi, H. Nishimura, R. Raymond, S. Tani, S. Yamashita. Quantum Query Complexity of Boolean Functions with Small On-Sets. Proceedings of ISAAC’2008, pp. 907-918.

A. Ambainis. Quantum Algorithm for Search on Grids. Encyclopedia of Algorithms 2008

A. Ambainis. Quantum Algorithm for Element Distinctness. Encyclopedia of Algorithms 2008



A. Ambainis. "Quantum walk algorithm for element distinctness". SIAM Journal on Computing, 37:210-239, 2007. Also quant-ph/0311001 and FOCS'04.

A. Ambainis, K. Iwama, A. Kawachi, R. Raymond, S. Yamashita, "Improved algorithms for quantum identification of Boolean oracles", Theoretical Computer Science, vol. 278 (2007), pp. 41-53. Earlier versions: quant-ph/0411204, and SWAT'06.

A. Ambainis, J. Emerson. "Quantum t-designs: t-wise independence in the quantum world". Proceedings of Complexity'07, pages 129-140. Also quant-ph/0701126.



A. Ambainis, L. Schulman, U. Vazirani. "Quantum computing with highly mixed states". Journal of the ACM, 53(2006),  pages 507-531. (Earlier versions at STOC'2000 and quant-ph/0003136.)

A. Ambainis. “Polynomial degree vs. quantum query complexity”. Journal of Computer and System Sciences, 72 (2006), pages 220-238. (Also FOCS'03 and quant-ph/0305028.)

A. Ambainis, M. Beaudry, M. Golovkins, A. Kikusts, M. Mercer, D. Therien. "Algebraic results on quantum automata". Theory of Computing Systems, 39(2006), pages 165-188. Earlier version in STACS'04. Postscript.

A. Ambainis, D. Gottesman. "Two-way entanglement purification for finite block size". IEEE Transactions on Information Theory, 52 (2006), pages 748-753. quant-ph/0310097

A. Ambainis, R. Spalek. "Quantum algorithms for matching and network flows". Proceedings of STACS'06, Lecture Notes in Computer Science, 3884 (2006), pages 172-183. quant-ph/0508205

A. Ambainis, W. Gasarch, A. Srinavasan, A. Utis. "Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance". Proceedings of ISAAC'06, Lecture Notes in Computer Science, 4288 (2007), pages 628-637. Also cs.CC/0411076



A. Ambainis, J. Kempe, A. Rivosh. "Coins make quantum walks faster". Proceedings of SODA'05, pp. 1099-1108. Also quant-ph/0402107.

S. Aaronson, A. Ambainis. “Quantum search of spatial regions”, Theory of Computing, vol. 1(2005), pages 47-79. (Also FOCS'03 and quant-ph/0303041.)

A. Ambainis. “Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range”. Theory of Computing, vol. 1 (2005), pages 37-46. quant-ph/0305179



A. Ambainis. "A new protocol and lower bounds for quantum coin flipping". Journal of Computer and System Sciences, 68(2004), pages 398-416. Also STOC'01 and quant-ph/0204022.

A. Ambainis. "Quantum query algorithms and lower bounds" (survey article). Proceedings of FOTFS III, Trends on Logic, vol. 23 (2004), pp. 15-32.Postscript.

A. Ambainis, M. Jakobssen, H. Lipmaa. “Cryptographic randomized response techniques”, Proceedings of PKC'04, pages 425-438, cs.CC/0302025.

A. Ambainis, Y. Shi. “Distributed constructions of quantum fingerprints”, Quantum Information and Computation, 4(2004), pages 146-151. quant-ph/0305022

A. Ambainis, K. Yang. "Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information". Proceedings of Complexity'04, pages 305-319. quant-ph/0207090.

A. Ambainis, H. Buhrman, Y. Dodis, H. Rohrig.“Multiparty quantum coin flipping”. Proceedings of Complexity'04, pages 250-259. quant-ph/0304112.

A. Ambainis. "Quantum search algorithms" (survey). SIGACT News, vol. 35 (2004), issue 2, pages 22-35. Also quant-ph/0504012.

A. Ambainis, O. Regev. "A simple proof of quantum adiabatic theorem". quant-ph/0411152

A. Ambainis, A. Smith. "Small pseudo-random families of matrices: derandomizing approximate quantum encryption", Proceedings of RANDOM'04, pages 249-260. Also  quant-ph/0404075.

A. Ambainis, K. Iwama, A. Kawachi, H. Masuda, R. Putra, S. Yamashita. "Quantum identification of Boolean oracles". Proceedings of STACS'04, pages 105-116. quant-ph/0403056

A. Ambainis, J. Case, S. Jain, M. Suraj. "Parsimony hierarchies for inductive inference". Journal of Symbolic Logic, 649(2004), pages  287-327.



T. Brun, H. Carteret, A. Ambainis. "Quantum random walks with decoherent coins", Physical Review A, 67 (2003), article 032304. Also quant-ph/0210180.

T. Brun, H. Carteret, A. Ambainis. "Quantum Walks driven by many coins", Physical Review A, 67 (2003), article 052317. Also quant-ph/0210161.

T. Brun, H. Carteret, A. Ambainis. "The quantum to classical transition for random walks", Physical Review Letters, 51 (2003), article 130602. quant-ph/0208195.

A. Ambainis. "Quantum walks and their algorithmic applications". International Journal of Quantum Information, 1(2003), pages 507-518. quant-ph/0403120

A. Ambainis, L. Schulman, A. Ta-Shma, U. Vazirani, A. Wigderson. "Quantum communication complexity of sampling". Journal version, SIAM Journal on Computing, 32(2003):1570-1585. (Earlier version: FOCS'98.)

A. Ambainis, A. Kikusts. "Exact results for accepting probabilities of quantum automata". Theoretical Computer Science, 295(2003), pages 3-25. (Earlier versions:  MFCS'01 and quant-ph/0109136.)



A. Ambainis. "Quantum lower bounds by quantum arguments". Journal of Computer and System Sciences, 64(2002), pages 750-767. Postcript of journal version (Earlier versions at STOC'2000 and quant-ph/0002066.)

A. Ambainis, A. Nayak, A. Ta-Shma, U. Vazirani. "Quantum dense coding and quantum finite automata". Journal of ACM, 49 (2002), pages 496-511. (Earlier versions: STOC'99 and quant-ph/9804043.)

A. Ambainis, A. Smith, K. Yang. "Extracting Quantum Entanglement (General Entanglement Purification Protocols)". Proceedings of Complexity'2002, pages 103-112. Earlier version at quant-ph/0110010.

A. Ambainis, J. Watrous. "Two-way finite automata with quantum and classical states". Theoretical Computer Science, 287 (2002), pages 299-311. Also cs.CC/9911009.

B. Travaglione, M. Nielsen, H. Wiseman, A. Ambainis. "ROM-based computation: quantum versus classical". Quantum Information and Computation, 2(2002), pages 324-332. Also quant-ph/0109016.

A. Ambainis. "Lower bound for a class of weak quantum coin flipping protocols". quant-ph/0204063.

A. Ambainis, S. Bloch, D. Schweizer. "Delayed binary search, or Playing twenty questions with a procrastinator". Algorithmica, 32(2002), pages 641-651. (Earlier version at SODA'99.) Gzipped postscript.



D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani. "Quantum walks on graphs". Proceedings of STOC'01, pages 50-59. Postscript of the conference version. Earlier version at quant-ph/0012090.

A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, J. Watrous. "One dimensional quantum walks". Proceedings of STOC'01, pages 37-49. Gzipped postscript.

A. Ambainis, R. de Wolf. "Average-case quantum query complexity". Journal of Physics A, 34(2001), page 6741-6754. (Earlier version at STACS'2000.) Also quant-ph/9904079.

A. Ambainis, A. Kikusts, M. Valdats. "On the class of languages recognizable by 1-way quantum finite automata". Proceedings of STACS'2001, Lecture Notes in Computer Science 2010(2001), pages 75-86. Full version at quant-ph/0009004.

A. Ambainis, H. Buhrman, W. Gasarch, B. Kalyanasundaram, L. Torenvliet. "The communication complexity of enumeration, elimination, and selection". Journal of Computer and System Sciences, 63(2001), pages 148-185. (Earlier version at Complexity'2000.) Gzipped postscript.

A. Ambainis, K. Apsitis, R. Freivalds, W. Gasarch, C.H. Smith. "Hierarchies of probabilistic and team FIN-learning." Theoretical Computer Science, 261(2001), pages 91-117. (Earlier version in proceedings of ALT'97 with the title "Team learning as a game".) Gzipped postscript.

A. Ambainis, "On learning formulas in limit and with assurance". Information Processing Letters, 77(2001), pages 9-11.Postscript.

A. Ambainis, "Probabilistic inductive inference: a survey". Theretical Computer Science, 264(2001), pages 155-167. Also available at cs.LG/9902026.



A. Ambainis, M. Mosca, A. Tapp, R. de Wolf. "Private quantum channels". Proceedings of FOCS'2000, pages 547-553. Gzipped postscript.

A. Ambainis, S. V. Lokam. "Improved Upper Bounds on the Simultaneous Messages Complexity of the Generalize Addressing Function". Proceedings of LATIN'2000, Lecture Notes in Computer Science, 2136(2001), pages 135-147. Gzipped postscript.

A. Ambainis, "How rich is the structure of the intrinsic complexity of learning?". Information Processing Letters, 75(2000), pages 109-112. Postscript.

A. Ambainis, K. Apsitis, J. Smotrovs. "Team learning and quasi-closedness in inductive inference". Manuscript, 2000.Gzipped postscript.



A. Ambainis, R. Bonner, R. Freivalds, A. Kikusts. "Probabilities to accept languages by quantum finite automata". Proceedings of COCOON'99, Lecture Notes in Computer Science, 1627(1999), pages 174-183. Also quant-ph/9904066.

A. Ambainis. "A note on quantum black-box complexity of almost all Boolean functions". Information Processing Letters, 71(1999), pages 5-7. Also quant-ph/9811080.

A. Ambainis, "A better lower bound for quantum algorithms searching an ordered list". Proceedings of FOCS'99, pages 352-357. Also quant-ph/9902053.

A. Ambainis, R. Bonner, R. Freivalds, M. Golovkins, M. Karpinski. "Quantum finite multitape automata". Proceedings of SOFSEM'99, Lecture Notes in Computer Science, 1725(1999), pages 340-348. Also quant-ph/9905026.

A. Ambainis, R. Bonner, R. Freivalds, A. Kikusts. "Probabilities to accept languages by quantum finite automata". Proceedings of COCOON'99, Lecture Notes in Computer Science, 1627(1999), pages 174-183. Also quant-ph/9904066.

A. Ambainis, R. Freivalds, C. H. Smith, "Inductive inference with procrastination: back to definitions". Fundamenta Informaticae, 40(1999), pages 1-16. (Earlier version in proceedings of STACS'96 with the title "General inductive inference types based on linearly-ordered sets") Gzipped postscript.

A. Ambainis, S. Jain and A. Sharma, "Ordinal mind change complexity of language identification."Theoretical Computer Science, 220(1999), pages 323-343. (Earlier version : EuroCOLT'97).

E. Allender, A. Ambainis, D. Barrington, S. Datta, H. LeThanh. "Bounded depth arithmetic circuits: counting and closure". Proceedings of ICALP'99, Lecture Notes in Computer Science, 1644(1999), pages 149-158. Also ECCC TR99-012.

A. Ambainis, W. Gasarch. "Squares in a square: an on-line question". Manuscript, 1999. Gzipped postscript.



A. Ambainis, R. Freivalds. "1-way quantum finite automata: strengths, weaknesses and generalizations." Proceedings of FOCS'98, pages 332-341. Full version available at quant-ph/9802062.

A. Ambainis, D. Barrington, H. LeThanh. "On counting AC0 circuits with negative constants". Proceedings of MFCS'98, Lecture Notes in Computer Science, 1450(1998), pages 419-427. Also ECCC TR98-020.



A. Ambainis. "Upper bound on the communication complexity of private information retrieval". Proceedings of ICALP'97, Lecture Notes in Computer Science, 1256(1997), pages 401-407. Postscript.

A. Ambainis, R. Freivalds, M. Karpinski. "Weak and strong recognition by 2-way randomized automata". Proceedings of the Workshop on Randomization and Approximation Methods in Computer Science (RANDOM'97), Lecture Notes in Computer Science, 1269(1997), pages 175-185. Gzipped postscript.

A. Ambainis, R. Desper, M. Farach, S. Kannan, "Nearly tight bounds on the learnability of evolution". Proceedings of FOCS'97, pages 524-533.



A. Ambainis. "Upper bounds on multiparty communication complexity of shifts". Proceedings of STACS'96, Lecture Notes in Computer Science, 1046 (1996), pages 631-642.

A. Ambainis. "Communication complexity in 3-computer model". Algorithmica, 16(1996), pages 298-301.

A. Ambainis. "The complexity of probabilistic versus deterministic finite automata". Proceedings of ISAAC'96, Lecture Notes in Computer Science, 1178(1996), pages 233-237. Gzipped postscript.

A. Ambainis, R. Freivalds, J. Smotrovs, "Inevitable gaps between upper and lower inductive inference complexity bounds". Proceedings of the Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU'96) , pages 833-839.

A. Ambainis, R. Freivalds, "Transformations that preserve learnability". Proceedings of ALT'96, Lecture Notes in Computer Science, 1160(1996), pages 299-311. Gzipped postscript.


A. Ambainis, "Power of procrastination in inductive inference: how it depends on used ordinal notations". Proceedings of EuroCOLT'95, Lecture Notes in Computer Science, 904(1995), pages 99-111.

A. Ambainis, "Optimization problem in inductive inference". In K.P.Jantke, S. Lange (eds.) "Algorithmic Learning for Knowledge-Based Systems", Lecture Notes in Computer Science, 961(1995), pages 96-107.

A. Ambainis, "Application of Kolmogorov complexity to inductive inference with limited memory". Proceedings of ALT'95, Lecture Notes in Computer Science, 997 (1995), pages 313- 318. Gzipped postscript.



A. Ambainis, J. Smotrovs, "Enumerable classes of total recursive functions: complexity of inductive inference". Proceedings of AII'94, Lecture Notes in Computer Science, 872(1994), pages 10-25.