Umesh V. Vazirani

Roger A. Strauch Professor of EECS
Director, Berkeley Quantum Computation Center (BQIC)
671 Soda Hall
Computer Science Division
University of California at Berkeley
Berkeley, CA 94720, U.S.A.
(510) 642-0572
my_last_name@cs.berkeley.edu




Contents: Selected Publications / Courses / Students

Selected Publications
  1. A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device with Z. Brakerski, P. Christiano, U. Mahadev, T. Vidick, arXiv:1804.00640

  2. Quantum Supremacy and the Complexity of Random Circuit Sampling with A. Bouland, B. Fefferman, C. Nirkhe, arXiv:1803.04402

  3. Approximate low-weight check codes and circuit lower bounds for noisy ground states with C. Nirkhe, H. Yuen, arXiv:1802.07419

  4. Rigorous RG algorithms and area laws for low energy eigenstates in 1D with I.Arad, Z. Landau, T. Vidick, arXiv:1602.08828 [quant-ph], 2016.  ITCS 2017.   QIP 2017. Communications in Mathematical Physics November 2017, Volume 356, Issue 1, pp 65

  5. The duality gap for two-team zero-sum games with L. Schulman, ITCS 2017.

  6. A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians with Z. Landau, T. Vidick, arXiv:1307.5143 [quant-ph], 2013.  ITCS 2014.  Nature Physics 11, 566-569 (2015).

  7. Local tests of global entanglement and a counterexample to the generalized area law with D. Aharonov, A. Harrow, Z. Landau, D. Nagaj, M. Szegedy, FOCS 2014.

  8. Algorithms, Games, and Evolution with E. Chastain, A. Livnat, C. Papadimitriou, PNAS vol. 111, no. 29, 10620-10623, 2014.

  9. How ``Quantum" is the D-Wave Machine? with S. Shin, Smith, J. Smolin, arXiv:1401.7087 [quant-ph], 2014.

  10. Fully device independent quantum key distribution with T. Vidick, ITCS 2014.  Phys. Rev. Lett. 113, 140501, 2014.

  11. Classical command of quantum systems with B. Reichardt, F. Unger, ITCS 2013.  Nature 496, 456 - 460 (25 April 2013).

  12. An area law and sub-exponential algorithm for 1D systems with I. Arad, A. Kitaev, Z. Landau, arXiv:1301.1162 [quant-ph], 2012.

  13. Is quantum mechanics falsifiable? A computational perspective on the foundations of quantum mechanics with D. Aharonov, Philosophy of Science anthology "Computability: Godel, Turing, Church, and beyond", Editors: Copeland, Posy, Shagrir, MIT press, 2012.

  14. An improved 1D area law for frustration-free systems. with I.Arad, Z.Landau, Phys. Rev. B 85, 195145 (2012).

  15. Certifiable Quantum Dice: or, true random number generation secure against quantum adversaries. with T. Vidick, Proceedings of the ACM Symposium on the Theory of Computing (2012).

  16. The 1D Area Law and the Complexity of Quantum States: A combinatorial approach. with D.Aharonov, I.Arad, Z.Landau, Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (2011).

  17. The detectability lemma and its applications to Quantum Hamiltonian complexity. with D.Aharonov, I.Arad, Z.Landau, New J. Phys. 13 (2011).
  18. Certifiable Quantum Dice. with T. Vidick, Philosophical Transactions of the Royal Society, A 2012, 370, 3432-3448.

  19. An improved 1D area law for frustration-free systems. with I.Arad, Z.Landau, Phys. Rev. B 85, 195145 (2012).

  20. Certifiable Quantum Dice: or, true random number generation secure against quantum adversaries. with T. Vidick, Proceedings of the ACM Symposium on the Theory of Computing (2012).

  21. The 1D Area Law and the Complexity of Quantum States: A combinatorial approach. with D.Aharonov, I.Arad, Z.Landau, Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (2011).

  22. The detectability lemma and its applications to Quantum Hamiltonian complexity. with D.Aharonov, I.Arad, Z.Landau, New J. Phys. 13 (2011).

  23. The detectability lemma and quantum gap amplification. with D.Aharonov, I.Arad, Z.Landau, Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 417-426 (2009).

  24. Expander Flows, Geometric Embeddings and Graph Partitioning. with S. Arora, S. Rao, Journal of ACM, 56(2), 2009.

  25. Geometry, Flows and Graph Partitioning Algorithms. with S. Arora, S. Rao, Commun. ACM, 51(10):96-105, 2008.

  26. Graph partitioning using single commodity flows. with R. Khandekar, S. Rao, Proceedings of Symposium on the Theory of Computing, 2006.

  27. AdWords and the Generalized Bipartite Matching Problem. with A. Mehta, A. Saberi, V. Vazirani, Proceedings of Symposium on the Foundations of Computer Science, 2005. Journal of ACM, 54(5), 2007.
    SIAM News Article by Sara Robinson pdf

  28. Expander Flows, Geometric Embeddings and Graph Partitioning. with S. Arora, S. Rao, Proceedings of Symposium on the Theory of Computing, 2004.

  29. Quantum Mechanical Algorithms for the Non-Abelian Hidden Subgroup Problem. with M. Grigni, L. Schulman, M. Vazirani, Proceedings of Symposium on the Theory of Computing, 2001; Combinatorica, Volume 24, Number 1, pp 137-154, January 2004.

  30. Limits on Quantum Adiabatic Optimization. with W. van Dam, manuscript.

  31. Dense Quantum Coding and Quantum Finite Automata. with A. Ambainis, A. Nayak, A. Ta-Shma, Proceedings of Symposium on the Theory of Computing, 1999; Journal of the ACM, Volume 49, Issue 4, 2002.

  32. How Powerful is Adiabatic Quantum Computation. with W. van Dam, M. Mosca, Proceedings of Symposium on the Foundations of Computer Science, 2001.

  33. Quantum Walks on Graphs. with D. Aharonov, A. Ambainis, J. Kempe, Proceedings of Symposium on the Theory of Computing, 1999.

  34. Computing with Highly Mixed States. with A. Ambainis, L. Schulman, Proceedings of Symposium on the Theory of Computing, 2000. Journal of the ACM Volume 53, Issue 3 (May 2006), Pages: 507 - 531.

  35. Quantum Bit Escrow. with D. Aharonov, A. Ta-Shma, A. Yao, Proceedings of Symposium on the Theory of Computing, 2000.

  36. Molecular Scale Heat Engines and Scalable Quantum Computation. with L. Schulman, Proceedings of Symposium on the Theory of Computing, 1999.

  37. The Quantum Communication Complexity of Sampling. with A. Ambainis, L. Schulman, A. Ta-Shma, A. Wigderson, Proceedings of Symposium on the Foundations of Computer Science, 1998. Siam J. Comput., Vol. 32, No. 6, pp. 1570-1585, 2003.

  38. On the Power of Quantum Computation. Philosophical Transactions of the Royal Society London A (1998) 356, 1759-1768.

  39. Go With the Winners Algorithms. with D. Aldous, Proceedings of Symposium on the Foundations of Computer Science, 1994.

  40. On syntactic versus computational views of approximability. with S. Khanna, R. Motwani, M. Sudan, Proceedings of Symposium on the Foundations of Computer Science, 1994. SIAM Journal on Computing, 28(1): 164-191, February 1999.

  41. Simple and Efficient Leader Election in the Full Information Model. with R. Ostrowsky, S. Rajagopalan, Proceedings of Symposium on the Theory of Computing, 1994.

  42. Simulating Quadratic Dynamical Systems is PSPACE-hard. with S. Arora, Y. Rabani, Proceedings of Symposium on the Theory of Computing, 1994.

  43. Quantum Complexity Theory. with E. Bernstein, Proceedings of Symposium on the Theory of Computing, 1993. Special issue on Quantum Computation of the Siam Journal of Computing, Oct. 1997.

  44. Strengths and Weaknesses of Quantum Computation. with C. Bennett, E. Bernstein, G. Brassard, Special issue on Quantum Computation of the Siam Journal of Computing, Oct. 1997.

  45. A Mildly Exponential Algorithm for Approximating the Permanent. with M. Jerrum, Proceedings of Symposium on the Foundations of Computer Science, 1992. invited paper, special issue of Algorithmica 16 (1996), 392-401.

  46. Choosing a Reliable Hypothesis. with W. Evans, S. Rajagopalan, Proceedings of the Symposium on Computational Learning Theory}, 1993.

  47. A Markovian Extension of Valiant's Learning Model. with D. Aldous, Proceedings of Symposium on the Foundations of Computer Science, 1990. Information and Computation, Vol. 117, No. 2, pp~181-186, 1995.

  48. Relativizing versus Nonrelativizing Techniques: the Role of Local Checkability. with S. Arora, R. Impagliazzo; early draft.

  49. An Optimal Online Bipartite Matching Algorithm. with R. Karp, V. Vazirani, Proceedings of Symposium on the Theory of Computing, 1990.

  50. Matching is as Easy as Matrix Inversion. with K. Mulmuley, V. Vazirani, Proceedings of Symposium on the Theory of Computing, 1987. Combinatorica, Vol. 7, No. 1, 1987.

  51. Efficiency Considerations in Using Semi-Random Sources. Proceedings of Symposium on the Theory of Computing, 1987.

  52. Random Polynomial Time is Equal to Semi-Random Polynomial Time. with V. Vazirani, Proceedings of Symposium on the Foundations of Computer Science, 1985.

  53. Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Semi-Random Sources. Proceedings of Symposium on the Theory of Computing, 1985. Combinatorica, Vol. 7, No. 4, 1987.

  54. Generating Quasi-Random Sequences from Semi-Random Sources. with M. Santha, Proceedings of Symposium on the Foundations of Computer Science, 1984, Journal Comput. Sys. Sci., Vol. 33, No. 1, 1986.

  55. Efficient and Secure Pseudo-Random Number Generation. with V. Vazirani, Proceedings of Symposium on the Foundations of Computer Science, 1984.

  56. Trapdoor Pseudo-Random Number Generators, with Applications to Protocol Design. with V. Vazirani, Proceedings of Symposium on the Foundations of Computer Science, 1983.

Selected Courses










Current Ph.D. Students

    Jonah Sherman

    Guoming Wang

    Anupam Prakash

    Urmila Mahadev

    Seung Woo Shin

Former Ph.D. Students

    1989 Milena Mihail (Associate Professor, Georgia Tech)

    1991 David Zuckerman (Professor, U.T. Austin)

    1992 Madhu Sudan (Professor, Harvard)

    1994 Sridhar Rajagopalan (research scientist at IBM)

    1994 Sanjeev Arora (Professor, Princeton University)

    1997 Ethan Bernstein (Research scientist, Microsoft Corporation)

    1999 Ashwin Nayak (Professor, Waterloo University and Perimeter Institute)

    2001 Andris Ambainis (Professor, University of Latvia)

    2002 Lisa Hales (Orinda Park Pool, Swim Team Director)

    2004 Lawrence Ip (Researcher, Google)

    2004 Scott Aaronson (Professor, MIT)

    2004 Jordan Kerenidis (Professor, University of Paris)

    2006 Ben Reichardt (Professor, University of Southern California)

    2009 Alexandra Kolla (Asst. Professor, University of Illinois, Urbana-Champaign)

    2011 Daniel Preda

    2011 Thomas Vidick (Professor, Caltech).