Умеш Вазирани

Умеш Вазирани
Национальность	Индийско-американский
Альма-матер	Массачусетский технологический институт , Калифорнийский университет в Беркли
Известный	Алгоритм Бернштейна-Вазирани
Родственники	Виджай Вазирани (брат)
Награды	Премия Фулкерсона (2012)
Научная карьера
Поля	Квантовые вычисления , Вычислительная сложность
Учреждения	Калифорнийский университет, Беркли
Диссертация	Случайность, противники и вычисления   (1986)
Докторантура	Мануэль Блюм
Докторанты	Скотт Ааронсон Андрис Амбайнис Санджив Арора Пол Кристиано Урмила Махадев Мадху Судан Дэвид Цукерман
Веб-сайт	www .cs .Беркли .edu /~министр /

Умеш Виркумар Вазирани — индийско-американский академик, профессор электротехники и информатики имени Роджера А. Штрауха в Калифорнийском университете в Беркли и директор Центра квантовых вычислений Беркли. Его исследовательские интересы лежат в первую очередь в области квантовых вычислений . Он также является соавтором учебника по алгоритмам.

Биография

Вазирани получил степень бакалавра наук в Массачусетском технологическом институте в 1981 году. и получил докторскую степень. в 1986 году из Калифорнийского университета в Беркли под руководством Мануэля Блюма .

Он брат Калифорнийского университета в Ирвайне профессора Виджая Вазирани .

Исследования

Вазирани — один из основателей области квантовых вычислений. Его статья 1993 года со своим учеником Итаном Бернштейном по квантовой теории сложности. определил модель квантовых машин Тьюринга , которая поддавалась анализу на основе сложности. В этой статье также был дан алгоритм квантового преобразования Фурье использовался Питером Шором , который затем в течение года в его знаменитом квантовом алгоритме факторизации целых чисел .

Вместе с Чарльзом Беннеттом , Итаном Бернстайном и Жилем Брассаром он показал, что квантовые компьютеры не могут решать задачи поиска в «черном ящике» быстрее, чем $O({\sqrt {N}})$ по количеству элементов, подлежащих поиску. Этот результат показывает, что алгоритм поиска Гровера является оптимальным. Это также показывает, что квантовые компьютеры не могут решать NP-полные задачи за полиномиальное время, используя только сертификатор.

Награды и почести

В 2005 году Вазирани и его брат Виджай Вазирани были удостоены звания членов Ассоциации вычислительной техники Умеша за «вклад в теоретическую информатику и квантовые вычисления ». и Виджаю за его работу над алгоритмами аппроксимации . Вазирани был удостоен премии Фулкерсона за 2012 год за работу по улучшению коэффициента аппроксимации разделителей графов и смежных проблем (совместно с Сатишем Рао и Сандживом Аророй ). В 2018 году он был избран членом Национальной академии наук .

Избранные публикации

• Малмули, Кетан; Вазирани, Умеш В.; Вазирани, Виджей В. (1987), «Сопоставление так же просто, как инверсия матрицы», Combinatorica , 7 (1): 105–113, CiteSeerX   10.1.1.70.2247 , doi : 10.1007/BF02579206 , MR   0905157 , S2CID   47370049 . Предварительная версия этой статьи была также опубликована в журнале STOC '87.
• Бернштейн, Итан; Вазирани, Умеш (1993), «Квантовая теория сложности», Труды двадцать пятого ежегодного симпозиума ACM по теории вычислений (STOC '93) , стр. 11–20, CiteSeerX   10.1.1.655.1186 , doi : 10.1145/167088.167097 , ISBN  978-0897915915 , S2CID   676378 .
• Кернс, Майкл Дж.; Вазирани, Умеш В. (1994), Введение в теорию вычислительного обучения , MIT Press, ISBN  9780262111935 .
• Беннетт, Чарльз Х .; Бернштейн, Итан; Брассар, Жиль ; Вазирани, Умеш (1997), «Сильные и слабые стороны квантовых вычислений», SIAM Journal on Computing , 26 (5): 1510–1523, arXiv : quant-ph/9701001 , Bibcode : 1997quant.ph..1001B , doi : 10.1137 /S0097539796300933 , MR   1471991 , S2CID   13403194 .

Внешние ссылки

• Умеш Вазирани в Калифорнийском университете в Беркли