Umesh Vazirani

Umesh Virkumar Vazirani is an

Vazirani received a BS from MIT in 1981[2] and received his Ph.D. in 1986 from UC Berkeley under the supervision of Manuel Blum.^[3]

He is the brother of University of California, Irvine professor Vijay Vazirani.

Research

Vazirani is one of the founders of the field of quantum computing. His 1993 paper with his student Ethan Bernstein on quantum complexity theory^[4] defined a model of quantum Turing machines which was amenable to complexity based analysis. This paper also gave an algorithm for the quantum Fourier transform, which was then used by Peter Shor within a year in his celebrated quantum algorithm for factoring integers.

With Charles Bennett, Ethan Bernstein, and Gilles Brassard, he showed that quantum computers cannot solve black-box search problems faster than ${\displaystyle O({\sqrt {N}})}$ in the number of elements to be searched. This result shows that the Grover search algorithm is optimal. It also shows that quantum computers cannot solve NP-complete problems in polynomial time using only the certifier.^{[5][6][dubious – discuss]}

Awards and honors

In 2005, both Vazirani and his brother

• Mulmuley, Ketan; Vazirani, Umesh V.; Vazirani, Vijay V. (1987), "Matching is as easy as matrix inversion", Combinatorica, 7 (1): 105–113,
  S2CID 47370049
  . A preliminary version of this paper was also published in STOC '87.
• Bernstein, Ethan; Vazirani, Umesh (1993), "Quantum complexity theory",
  S2CID 676378
  .
• Kearns, Michael J.; Vazirani, Umesh V. (1994), An Introduction to Computational Learning Theory, MIT Press,
  ISBN 9780262111935
  .
• S2CID 13403194
  .