Умеш Виркумар Вазирани — индийско-американский учёный, профессор электротехники и компьютерных наук имени Роджера А. Штрауха в Калифорнийском университете в Беркли и директор Центра квантовых вычислений в Беркли. Его исследовательские интересы в основном лежат в области квантовых вычислений . Он также является соавтором учебника по алгоритмам. [1]
Вазирани получил степень бакалавра в Массачусетском технологическом институте в 1981 году [2] и степень доктора философии в 1986 году в Калифорнийском университете в Беркли под руководством Мануэля Блума . [3]
Он является братом профессора Калифорнийского университета в Ирвайне Виджая Вазирани .
Вазирани является одним из основателей области квантовых вычислений. Его статья 1993 года с его студентом Итаном Бернстайном по квантовой теории сложности [4] определила модель квантовых машин Тьюринга , которая поддавалась анализу на основе сложности. В этой статье также был дан алгоритм для квантового преобразования Фурье , который затем был использован Питером Шором в течение года в его знаменитом квантовом алгоритме для факторизации целых чисел .
С Чарльзом Беннетом , Итаном Бернстайном и Жилем Брассаром он показал, что квантовые компьютеры не могут решать задачи поиска черного ящика быстрее, чем за количество элементов, которые нужно найти. Этот результат показывает, что алгоритм поиска Гровера является оптимальным. Он также показывает, что квантовые компьютеры не могут решать NP-полные задачи за полиномиальное время, используя только сертификатор. [5] [6] [ dubious – discussion ]
В 2005 году Вазирани и его брат Виджай Вазирани были избраны членами Ассоциации вычислительной техники , Умеш за «вклад в теоретическую информатику и квантовые вычисления » [7] , а Виджай за работу над алгоритмами аппроксимации [8] . Вазирани был удостоен премии Фулкерсона за 2012 год за работу по улучшению коэффициента аппроксимации для разделителей графов и связанных с ними проблем (совместно с Сатишем Рао и Сандживом Аророй ). В 2018 году он был избран в Национальную академию наук .
