Умеш Вазирани - Umesh Vazirani

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

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

биография

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

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

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

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

Вместе с Беннеттом, Бернстайном и Брассардом он показал, что квантовые компьютеры не могут решать задачи поиска в черном ящике быстрее, чем по количеству элементов для поиска. Этот результат показывает, что Поиск Гровера алгоритм оптимален. Это также показывает, что квантовые компьютеры не могут решить НП-полный проблемы за полиномиальное время с использованием только сертификатора.[5][6]

Награды и отличия

В 2005 году и Вазирани, и его брат Виджай Вазирани были введены в должность члена Ассоциация вычислительной техники, Умеш за "вклад в теоретическая информатика и квантовые вычисления "[7] и его брата Виджая за его работу над аппроксимационные алгоритмы.[8] Вазирани был награжден Премия Фулкерсона за 2012 год за работу над улучшением отношения аппроксимации для разделителей графов и смежных задач (совместно с Сатиш Рао и Санджив Арора ). В 2018 году он был избран в Национальная Академия Наук.

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

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

Рекомендации

  1. ^ Алгоритмы: Дасгупта, Пападимитриу, Вазирани
  2. ^ Вазирани, Умеш Виркумар (1986-01-01). Случайность, противники и вычисления. Калифорнийский университет в Беркли.
  3. ^ Умеш Виркумар Вазирани на Проект "Математическая генеалогия".
  4. ^ Бернштейн и Вазирани 1993.
  5. ^ Беннетт, Чарльз Х .; Бернштейн, Итан; Брассар, Жиль; Вазирани, Умеш (октябрь 1997 г.). «Сильные и слабые стороны квантовых вычислений». SIAM Журнал по вычислениям. 26 (5): 1510–1523. Дои:10.1137 / s0097539796300933. ISSN  0097-5397.
  6. ^ Ааронсон, Скотт. «Лекция 23, четверг, 13 апреля: BBBV, Приложения Гровера» (PDF). Получено 17 ноября, 2020.
  7. ^ Награда стипендиатов ACM: Умеш Вазирани.
  8. ^ Награда стипендиатов ACM: Виджай Вазирани.

внешняя ссылка