Umesh Virkumar Vazirani es un académico indio-estadounidense que ocupa la cátedra Roger A. Strauch de Ingeniería Eléctrica y Ciencias de la Computación en la Universidad de California, Berkeley , y es director del Centro de Computación Cuántica de Berkeley. Sus intereses de investigación se centran principalmente en la computación cuántica . También es coautor de un libro de texto sobre algoritmos. [1]
Vazirani recibió una licenciatura del MIT en 1981 [2] y recibió su doctorado en 1986 de la UC Berkeley bajo la supervisión de Manuel Blum . [3]
Es hermano del profesor Vijay Vazirani de la Universidad de California en Irvine .
Vazirani es uno de los fundadores del campo de la computación cuántica. Su artículo de 1993 con su alumno Ethan Bernstein sobre la teoría de la complejidad cuántica [4] definió un modelo de máquinas de Turing cuánticas que era susceptible de análisis basado en la complejidad. Este artículo también proporcionó un algoritmo para la transformada cuántica de Fourier , que luego fue utilizada por Peter Shor un año después en su célebre algoritmo cuántico para factorizar números enteros .
Junto con Charles Bennett , Ethan Bernstein y Gilles Brassard , demostró que las computadoras cuánticas no pueden resolver problemas de búsqueda de caja negra con una velocidad mayor que la cantidad de elementos que se deben buscar. Este resultado demuestra que el algoritmo de búsqueda de Grover es óptimo. También demuestra que las computadoras cuánticas no pueden resolver problemas NP-completos en tiempo polinomial utilizando solo el certificador. [5] [6] [ dudoso – discutir ]
En 2005, tanto Vazirani como su hermano Vijay Vazirani fueron incluidos como miembros de la Association for Computing Machinery , Umesh por "contribuciones a la informática teórica y la computación cuántica " [7] y Vijay por su trabajo en algoritmos de aproximación . [8] Vazirani recibió el Premio Fulkerson en 2012 por su trabajo en la mejora de la relación de aproximación para separadores de gráficos y problemas relacionados (junto con Satish Rao y Sanjeev Arora ). En 2018, fue elegido miembro de la Academia Nacional de Ciencias .