Шор, Питер

Питер Шор (; род. 14 августа 1959, Нью-Йорк, США) — американский учёный. Автор работ в области геометрии, теории вероятностей, комбинаторики, теории алгоритмов и квантовой информатики. Наиболее известен своими основополагающими результатами в теории квантовых вычислений.

В 1994 году он разработал эффективный полиномиальный алгоритм разложения больших чисел на множители для квантового компьютера. (Полиномиальный алгоритм разложения больших чисел на множители на классическом компьютере до сих пор не обнаружен и, по мнению многих исследователей, это экспоненциально трудная задача.) В 1995 году показал, что квантовые вычисления возможно проводить и при наличии не очень сильной декогеренции (необратимого воздействия внешней среды), если при этом использовать квантовую алгоритмическую коррекцию ошибок. В математике П. Шором с соавторами была доказана теорема о полярном круге.

Лауреат премии Неванлинны (1998), премии Гёделя (1999), стипендии Мак-Артура (1999) и множества других престижных научных наград.

Биография 
В 1977 занял третье место на математической олимпиаде США, после чего в составе американской сборной участвовал в международной математической олимпиале в Югославии и завоевал там серебряную медаль.

В 1981 году закончил обучение в Калтехе и получил степень бакалавра математики. Продолжил обучение в аспирантуре Массачусетского технологического института, где ему в 1985 году была присвоено звание доктора философии по прикладной математике (близкий аналог — звание кандидата наук в России). Научным руководителем кандидатской работы Питера Шора был Том Лейтон. После защиты провёл один год в университете Беркли в качестве постдока. В 1986 году он присоединился к AT&T Bell Laboratories в Мюррей-Хилл, штат Нью-Джерси, а в 1997 году перешел в лабораторию AT&T в Florham Park, штат Нью-Джерси. В течение нескольких лет он его основной сферой интересов являлись алгоритмы для обычных компьютеров, а также одновременно с ними он изучал теорию вероятностей и комбинаторику. В 1994 году после размышлений о проблемах он сделал свое открытие в области квантовых компьютеров (Алгоритм Шора). С тех пор он проводит большую часть своего времени, занимаясь исследованиями в области квантовых вычислений и квантовой теории информации.

В 2004 году перешёл из компании на преподавательскую работу на кафедру математики Массачусетского технологического института, где работает и поныне. Примерно с того же времени он входит в состав Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института (CSAIL) и Центра теоретической физики.

В 2007 году ему была вручена награда за выдающиеся заслуги от Калифорнийского технического института (Caltech). Также он является членом Национальной академии наук США.

Сыграл себя в сериале «Новая звезда» (англ. «Nova» 1974 — …)

Личная жизнь 
Шор состоит в браке с женой Дженнифер. У них есть две дочери, старшую зовут Валерия.

Научная деятельность 
Профессор Шор известен своими работами по квантовым вычислениям, в частности, разработкой квантового алгоритма, теперь известного как алгоритм Шора, более быстрого, чем любой из известных современных алгоритмов, работающих на классическом цифровом компьютере. Таким образом, он сделал физическое развитие квантовых компьютеров более осуществимым и реальным. Шор продемонстрировал, что ошибки в вычислениях не обязательно ведут к серьёзным нарушениям в работе квантового компьютера — он провел демонстрацию того, что квантовые корректирующие коды могли быть использованы для построения квантового компьютера из немного шумных компонентов. Таким образом Питер Шор сломал широко используемую криптосистему Ривеста-Шамира-Адельмана, использовавшуюся ранее.

В 2002 году был удостоен Международной премии короля Фейсала в области науки (неоф. Арабской нобелевской премии). Помимо неё, профессор Шор был удостоен премии имени Рольфа Неванлинны от Международного конгресса математиков в 1998 году, премии имени Диксона в области науки в том же 1998 году, международной премии в области квантовых коммуникаций и премии Геделя за лучшую работу в области теоретической информатики в 1999 году. В том же 1999 году он был удостоен стипендии MacArthur (прозвище «Genius Fellowship»), которая ежегодно присуждается Фондом Джона Д. и Кэтрин Т. Макартуров гражданам США и жителям любого возраста и области исследований, «которые проявляют исключительные заслуги и обещание продолжения и расширения творческой работы», и Международную премию квантовой связи 1998 года.

Шор является 25-м получателем этого приза от университета Карнеги — Меллоуна. Разработки Шора относятся к квантовому компьютеру, который может значительно превзойти по скорости цифровые компьютеры и научиться решать проблемы, которые трудно решаемы для самых современных параллельных машин. Однако возможности такого устройства не были известны достаточно до 1994 года, когда Шор открыл алгоритм квантования больших чисел или целых чисел в простые числа. Его прорыв вызвал волну исследований среди физиков и ученых в области компьютерных наук, которые теперь помогают вывести квантовые компьютеры из области теории в стадию прототипа. Сложность факторизации длинных номеров с использованием обычных компьютеров лежит в основе некоторых широко используемых методов шифрования информации в Интернете. По этой причине квантовый компьютер может, по крайней мере, потенциально поставить под угрозу безопасность электронных денег и подписей в Интернете. Однако до устройства, которое могло бы на самом деле реализовать алгоритм Шора для больших чисел, ещё много лет, потому что нужно преодолеть многочисленные технические трудности. Поэтому, охранные организации следят за развитием событий в этой области и серьёзной озабоченности пока нет.

Питер Шор — активный участник и пользователь Stack Exchange, у него три золотых «значка» (один из которых за хороший ответ) и сто девяносто два серебряных и бронзовых «значка».

Работы Шора, по разработке квантового компьютера, ставят под угрозу современную криптографию, в частности, алгоритм RSA, представляющий собой криптосистему с открытым ключом, в основе которого лежит факторизация произведения двух больших простых чисел. Это приводит к развитию постквантовой криптографии — криптографии, которая будет актуальной после изобретения квантового компьютера, например подпись Меркла, основанная на хеш-таблицах, криптосистемы исправления ошибок (например, McEliece) и шифрование с секретным ключом (например, AES).

Доклад о структуре унитальных отображений и асимптотическая квантовая гипотеза Биркгофа 
Ценность данного доклада в том, что он поднимает множество будущих вопросов, решением которых занимается профессор. Профессор задается вопросом, обобщается ли теорема Биркгофа на квантовые каналы. Одна из теорем Биркгофа утверждает, что всякая бистохастическая матрица есть выпуклая комбинация матриц перестановок. Некоммутативным аналогом стохастического отображения является квантовый канал, то есть вполне положительное отображение эрмитовых матриц, сохраняющее след. Аналогом бистохастических матриц являются унитальные каналы, сохраняющие единичную матрицу. Естественным некоммутативным обобщением теоремы Биркгофа было бы утверждение, что всякий унитальный канал есть выпуклая комбинация унитарных отображений, что, однако, неверно. Более слабым утверждением является асимптотическая квантовая гипотеза Биркгофа об аппроксимации унитарными отображениями n-й тензорной степени канала при n стремящемся к бесконечности. Профессор Шор показывает, что такая гипотеза также неверна и предлагает классификацию унитальных каналов, связанную с этой гипотезой.

Исследования квантовой обратной теоремы Шеннона 
Данная работа является одной из ключевых в деятельности профессора, так как она развивает его исходное исследование и позволяет его доработать. Работа касается квантовой теории информации и пытается проанализировать, сколько информации можно передать по квантовому каналу. В отличие от классического случая, для которого по формуле Шеннона существует только одно значение емкости канала, в квантовом случае оно зависит от того, является ли передаваемая информация классической или квантовой, и какие вспомогательные ресурсы доступны.

Двойственная по отношению к обычной проблеме кодирования с шумовым каналом проблема, где шумовой (классический или квантовый) канал используется для симуляции бесшумного канала, для обратных теорем Шеннона касается использования бесшумных каналов для симуляции шумовых каналов и, в более общем смысле, использования одного шумового канала для симуляции работы другого канала (шумового или бесшумного). Для каналов с ненулевой пропускной способностью такое моделирование всегда возможно, но для того, чтобы оно было эффективным, обычно требуются вспомогательные ресурсы надлежащего вида и количества. В классическом случае общая случайность между отправителем и получателем является достаточным вспомогательным ресурсом, независимо от природы источника, но в квантовом случае необходимые вспомогательные ресурсы для эффективного моделирования зависят как от моделируемого канала, так и от источника и входов в него.

Для тензорных источников энергии (квантовое обобщение классических источников без памяти) достаточно запутывания в форме стандартных эбитов (максимально запутанных пар кубитов), но для общих источников, которые могут произвольно коррелироваться или запутываться на входах канала, дополнительные ресурсы, такие как состояния запутывания или утечки, как правило, являются неизбежными. Объединяя существующие и новые результаты, мы устанавливаем количество коммуникационных и вспомогательных ресурсов, необходимых как в классическом, так и в квантовом случаях, компромиссы между ними и потерю эффективности моделирования в случаях, когда вспомогательные ресурсы отсутствуют или недостаточны. В частности, мы находим новое простое выражение для стоимости прямой связи для имитации когерентной обратной связи квантовых каналов (то есть симуляции, в которой отправитель сохраняет то, что могло бы попасть в окружающую среду при обычном моделировании) на источниках питания, не являющихся источниками питания при наличии неограниченных эбитов, когда другого вспомогательного ресурса нет. Результаты, касающиеся тензорных источников энергии, показывают сильное взаимодействие с теоремой о мощности, связанной с запутанностью.

Примечания

Литература 
 Structure of Unital Maps and the Asymptotic Quantum Birkhoff Conjecture (article)
 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (article)
 Quantum Interactive Proofs with Short Messages (article)
 The Power of Unentanglement (article)
 Superadditivity in Trade-Off Capacities of Quantum Channels (article)
 Quantum and superquantum enhancements to two-sender, two-receiver channels (article)
 polylog-LDPC Capacity Achieving Codes for the Quantum Erasure Channel (article)
 The Quantum Reverse Shannon Theorem and Resource Tradeoffs for Simulating Quantum Channels — IEEE Journals & Magazine

Ссылки 
 
 Identifying Talent: American Mathematics Competitions, Focus, Vol. 24, Issue 3 (March 2004).
 Shor — Computer Scientist, Fusion Newsletter, Vol. 2, Issue 4 (winter 2002/2003).
 DBLP: Peter W. Shor.
 Quantum Computing Expert Peter Shor Receives Carnegie Mellon’s 1998 Dickson Prize in Science.
 Peter W. Shor — MacArthur Foundation
 Peter Shor National Academy of Science

Учёные в области информатики США
Математики США
Математики XX века
Математики XXI века
Члены Национальной академии наук США
Выпускники Школы наук Массачусетского технологического института
Выпускники Калифорнийского технологического института
Преподаватели Центра теоретической физики Массачусетского технологического института
Преподаватели Массачусетского технологического института
Лауреаты премии Гёделя
Стипендиаты Мак-Артура
Лауреаты премии Диксона
Награждённые медалью Дирака
Удостоенные BBVA Foundation Frontiers of Knowledge Award