Джон Уотроус (ученый-компьютерщик) - John Watrous (computer scientist)

Джон Харрисон Уотроус
Портрет профессора Джона Уотроуса, сделанный в Дэвис-центре Университета Ватерлоо в январе 2019 года.
Альма-матерУниверситет Висконсина-Мэдисона
Государственный университет Нью-Йорка в Стоуни-Брук
Научная карьера
ПоляИнформатика, Квантовые вычисления
УчрежденияУниверситет Калгари
Университет Ватерлоо
Институт квантовых вычислений
Институт теоретической физики Периметр
ДокторантЭрик Бах

Джон Харрисон Уотроус профессор Информатика на Школа компьютерных наук Дэвида Р. Черитона на Университет Ватерлоо, член Институт квантовых вычислений, аффилированный член Институт теоретической физики Периметр и член Канадский институт перспективных исследований.[1][2] Он был преподавателем факультета компьютерных наук в Университет Калгари с 2002 по 2006 год, где он провел Кафедра исследований Канады в квантовые вычисления.[1]

Он редактор журнала Теория вычислений[3] и бывший редактор журнала Квантовая информация и вычисления.[4] Его исследовательские интересы включают: квантовая информация и квантовые вычисления. Он хорошо известен своей работой над квантовые интерактивные доказательства, а квантовый аналог знаменитого результата IP равно PSPACE, QIP равно PSPACE.[5][6][7] Этому предшествовала серия результатов, показывающих, что QIP может быть ограничен до 3 сообщений,[8] QIP содержится в EXP,[9] а версия QIP с двумя сообщениями находится в PSPACE.[10] Он также опубликовал важные статьи по квантовые конечные автоматы[11] и квантовые клеточные автоматы.[12] С Скотт Ааронсон, он показал, что некоторые формы путешествие во времени может сделать квантовые и классические вычисления эквивалент: вместе авторы показали, что квантовые эффекты не дают преимуществ для вычислений, если компьютеры могут отправлять информацию в прошлое посредством определенного типа замкнутая времениподобная кривая предложенный физиком Дэвид Дойч.[13]

Он получил свой Кандидат наук. в 1998 г. на Университет Висконсина-Мэдисона под присмотром Эрик Бах.[14][15]

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

  1. ^ а б Джон Уотроус на Канадский институт перспективных исследований интернет сайт.
  2. ^ Джон Уотроус В архиве 2011-07-06 в Wayback Machine на сайте QuantumWorks.
  3. ^ Список редакторов Theory of Computing.
  4. ^ Список редакторов Quantum Information & Computing.
  5. ^ Лэнс Фортноу (2009-07-29). "QIP = PSPACE". Вычислительная сложность. Получено 2009-12-30.
  6. ^ Дэйв Бэкон (28 июля 2009 г.). "OMG QIP = PSPACE!". Квантовый понтифик. Архивировано из оригинал на 2010-01-05. Получено 2009-12-30.
  7. ^ Рахул Джайн; Чжэнфэн Цзи; Сарвагья Упадхьяй; Джон Уотроус (2009). «QIP = PSPACE». arXiv:0907.4737 [Quant-ph ].
  8. ^ Уотроус, Джон (2003). «У PSPACE есть квантовые интерактивные системы доказательства с постоянным циклом». Теор. Comput. Наука. Эссекс, Великобритания: Elsevier Science Publishers Ltd. 292 (3): 575–588. Дои:10.1016 / S0304-3975 (01) 00375-9. ISSN  0304-3975.
  9. ^ Китаев, Алексей; Уотроус, Джон (2000). «Распараллеливание, усиление и экспоненциальное моделирование во времени квантовых интерактивных систем доказательства». STOC '00: Материалы тридцать второго ежегодного симпозиума ACM по теории вычислений. ACM. С. 608–617. ISBN  978-1-58113-184-0.
  10. ^ Рахул Джайн; Сарвагья Упадхьяй; Джон Уотроус (2009). «Квантовые интерактивные доказательства с двумя сообщениями находятся в PSPACE». arXiv:0905.1300 [cs.CC ].
  11. ^ Kondacs, A .; Уотроус, Дж. (1997). «О мощности квантовых конечных автоматов». Материалы 38-го ежегодного симпозиума по основам информатики. С. 66–75.
  12. ^ Уотроус, Джон (1995). «Об одномерных квантовых клеточных автоматах». Proc. 36-й ежегодный симпозиум по основам компьютерных наук (Милуоки, Висконсин, 1995 г.). Лос-Аламитос, Калифорния: IEEE Comput. Soc. Нажмите. С. 528–537. Дои:10.1109 / SFCS.1995.492583. ISBN  0-8186-7183-1. МИСТЕР  1619103..
  13. ^ Лиза Зыга (20.11.2008). «Как путешествия во времени могут повлиять на квантовые вычисления». PhysOrg. Получено 2009-12-30.
  14. ^ Джон Уотроус на Проект "Математическая генеалогия".
  15. ^ Джон Уотроус на Институт квантовых вычислений каталог.