В 1994 году, по словам профессора Питера Шора, доктора философии 1985 года, внутренние семинары в AT&T Bell Labs были очень оживленными. Аудитория физиков была активной и любознательной, часто забрасывала спикеров вопросами на протяжении всего выступления. Шор, работавший в то время в Bell Labs, помнит несколько случаев, когда оратор не мог пройти дальше третьего слайда, пытаясь ответить на краткую цепочку вопросов до истечения времени.
В том же году, когда настала очередь Шора представить алгоритм, который он недавно разработал, физики уделили пристальное внимание всему выступлению Шора, а затем и кое-чему.
«Мой прошел довольно хорошо, — сказал он вчера аудитории Массачусетского технологического института.
В том выступлении на семинаре 1994 года Шор представил доказательство, показывающее, как квантовая система может применяться для решения конкретной задачи быстрее, чем классический компьютер. Эта проблема, известная как проблема дискретного логарифмирования, была известна как неразрешимая классическими средствами. Таким образом, в то время дискретные логарифмы использовались в качестве основы для нескольких систем безопасности.
Работа Шора была первой, которая показала, что квантовый компьютер может решить реальную практическую проблему. Его выступление произвело фурор на семинаре, и новости распространились, а затем смешались. Через четыре дня после его первоначального выступления физики по всей стране предположили, что Шор решил родственную, хотя и гораздо более сложную проблему: разложение простых чисел — задачу нахождения двух простых множителей очень большого числа. Хотя в некоторых системах безопасности используются дискретные логарифмы, большинство современных схем шифрования основаны на простой факторизации и предположении, что их невозможно взломать.
«Это было похоже на детскую игру в «телефон», когда распространялся слух, что я разобрался с факторингом, — говорит Шор. «И за четыре дня после [the talk]Я имел!”
Доработав исходную задачу, Шор нашел похожее квантовое решение для простой факторизации. Его решение, известное сегодня как алгоритм Шора, показало, как квантовый компьютер может факторизовать очень большие числа. Квантовые вычисления, которые когда-то считались мысленным экспериментом, внезапно обрели в алгоритме Шора руководство по эксплуатации для очень реального и потенциально разрушительного применения. Его работа одновременно положила начало нескольким новым направлениям исследований в области квантовых вычислений, информатики и криптографии.
Остальное — история, основные моменты которой Шор рассказал стоящей аудитории в Хантингтон-холле Массачусетского технологического института, комната 10-250. Шор, профессор прикладной математики им. Морса в Массачусетском технологическом институте, выступил в качестве лауреата Премии Джеймса Р. Киллиана-младшего за достижения в области факультета в этом году, что является высшей наградой, которую преподаватели Института могут вручить одному из своих членов каждый учебный год.
Представляя доклад Шора, Лили Цай, заведующая кафедрой, процитировала цитату из награды:
«Все без исключения преподаватели, которые номинировали его, отметили его дальновидность, гениальность и техническое мастерство, а также похвалили его за блестящую работу», — сказала Цай. «Работа профессора Шора демонстрирует, что квантовые компьютеры могут открыть новые направления человеческой мысли и деятельности».
Квантовая история
Во время часовой лекции Шор рассказал аудитории краткую историю квантовых вычислений, приправив выступление личными воспоминаниями о своей роли. История, по его словам, началась в 1930-х годах с открытия квантовой механики — физического поведения материи в мельчайших субатомных масштабах — и вскоре возник вопрос: почему квантовая механика была такой странной?
Физики столкнулись с новым описанием физического мира, столь отличным от «классической» ньютоновской механики, которую понимали на протяжении столетий. Шор говорит, что физик Эрвин Шредингер попытался «проиллюстрировать абсурдность» новой теории своим теперь уже известным мысленным экспериментом с котом в коробке: как он может воплощать оба состояния — мертвое и живое? Упражнение бросило вызов идее суперпозиции, ключевому свойству квантовой механики, которое предсказывает, что квантовый бит, такой как атом, должен одновременно удерживать более одного состояния.
Еще более страшным было предсказание запутанности, согласно которому два атома могут быть неразрывно связаны. Любое изменение в одном должно затем повлиять на другое, независимо от расстояния, разделяющего их.
«Никто не думал об использовании этой странности для хранения информации до Визнера», — сказал Шор.
Визнером был Стивен Визнер, который в конце 1960-х был аспирантом Колумбийского университета, которому позже приписывают формулировку некоторых основных принципов квантовой теории информации. Ключевым вкладом Визнера была статья, которая изначально была отвергнута. Он предложил способ создания «квантовых денег» или валюты, устойчивой к подделке, используя странное свойство, согласно которому квантовые состояния не могут быть полностью продублированы — предсказание, известное как теорема «не-клонирования».
Как вспоминает Шор, Визнер записал свою идею на пишущей машинке, отослал ее на рассмотрение своим коллегам и получил категорический отказ. Так продолжалось до тех пор, пока другой физик, Чарльз Беннетт, не нашел статью, «вытащил ее из ящика стола и опубликовал», укрепив роль Визнера в истории квантовых вычислений. Беннетт пошел еще дальше, поняв, что основная идея квантовых денег может быть применена для разработки схемы распределения квантовых ключей, в которой безопасность части информации, такой как закрытый ключ, передаваемый между сторонами, защищена еще одним странным квантовым свойством. .
Беннет разработал эту идею вместе с Жилем Брассаром в 1984 году. Алгоритм BB84 был первым протоколом для криптосистемы, полностью основанной на странных явлениях квантовой физики. Где-то в 1980-х Беннетт пришел в Bell Labs, чтобы представить BB84. Шор впервые услышал о квантовых вычислениях, и это его зацепило.
Первоначально Шор пытался найти ответ на вопрос, который Беннетт задал аудитории: как можно математически доказать, что протокол действительно безопасен? Проблема, однако, была слишком острой, и Шор отказался от вопроса, но не от темы. Он последовал за усилиями своих коллег в растущей области квантовой информатики и в конце концов остановился на статье физика Дэниела Саймона, который предложил нечто действительно странное: система квантовых вычислительных битов может решать конкретную задачу экспоненциально быстрее, чем классический компьютер. .
Сама проблема, как ее поставил Саймон, была эзотерической, и его статья, как и статья Визнера, была первоначально отвергнута. Но Шор что-то увидел в ее структуре, а именно то, что проблема связана с гораздо более конкретными проблемами дискретного логарифмирования и факторизации. Он работал с отправной точки Саймона, чтобы увидеть, может ли квантовая система решать дискретные логарифмы быстрее, чем классическая система. Его первые попытки закончились ничьей. Квантовый алгоритм решал задачу так же быстро, как и его классический аналог. Но были намеки на то, что можно было бы сделать лучше.
«Есть еще надежда попробовать», — вспоминает Шор.
Когда ему это удалось, он представил свой алгоритм квантового дискретного логарифмического алгоритма на симпозиуме 1994 года в Bell Labs. За четыре дня, прошедшие после выступления, ему удалось также разработать одноименный алгоритм простой факторизации.
Прием был ошеломляющим, но также и скептическим, поскольку физики предполагали, что практический квантовый компьютер мгновенно рухнет при малейшем намеке на шум, что приведет к каскаду ошибок в его вычислении факторинга.
«Меня беспокоит эта проблема, — сказал Шор.
Итак, он снова приступил к работе, ища способ исправить ошибки в квантовой системе, не нарушая состояния вычислительных квантовых битов. Он нашел ответ с помощью конкатенации, которая в широком смысле относится к серии взаимосвязанных событий. В своем случае Шор нашел способ связать кубиты и сохранить информацию об одном логическом или вычислительном кубите среди девяти сильно запутанных физических кубитов. Таким образом, любая ошибка в логическом кубите может быть измерена и исправлена в физических кубитах без необходимости измерения (и, следовательно, уничтожения) кубита, участвующего в реальных вычислениях.
Новый алгоритм Шора был первым квантовым кодом исправления ошибок, который доказал, что квантовый компьютер может быть устойчивым к ошибкам, и, следовательно, вполне реальная возможность.
«Мир квантовой механики — это не мир вашей интуиции, — сказал Шор в заключение своего выступления. «Квантовая механика — это то, каков мир на самом деле».
Квантовое будущее
После своего выступления Шор ответил на несколько вопросов из аудитории, в том числе на вопрос, который сегодня приводит к огромным усилиям в области квантовой информатики: когда мы увидим настоящий, практичный квантовый компьютер?
По оценке Шора, если учесть большое число, для квантовой системы потребуется не менее 1000 кубитов. Чтобы учесть очень большие числа, лежащие в основе современного Интернета и систем безопасности, потребуются миллионы кубитов.
«На это уйдет много лет, — сказал Шор. «Возможно, мы никогда не создадим квантовый компьютер… но если у кого-то появится отличная идея, возможно, мы сможем увидеть его через 10 лет».
В то же время он отметил, что по мере того, как работа в области квантовых вычислений в последние годы резко расширялась, то же самое происходило с постквантовой криптографией и усилиями по разработке альтернативных криптографических систем, защищенных от взлома кода на основе квантовых вычислений. Шор сравнивает эти усилия с борьбой, приведшей к «2000 году», и перспективой цифровой катастрофы на рубеже прошлого века.
«Наверное, стоило начать несколько лет назад, — сказал Шор. «Если вы будете ждать до последней минуты, когда станет ясно, что квантовые компьютеры будут построены, вы, вероятно, опоздаете».
Шор получил докторскую степень в Массачусетском технологическом институте в 1985 году, а затем защитил докторскую диссертацию в Исследовательском институте математических наук в Беркли, Калифорния. Затем он провел несколько лет в AT&T Bell Labs, а затем в AT&T Shannon Labs, прежде чем вернуться в Массачусетский технологический институт в качестве штатного преподавателя в 2003 году.
Вклад Шора был отмечен многочисленными наградами, последней из которых стала Премия за прорыв в фундаментальной физике 2023 года, которую он разделил с Беннеттом, Брассардом и физиком Дэвидом Дойчем. Его другие награды включают стипендию Макартура, премию Неванлинны (ныне медаль IMU Abacus), медаль Дирака, международную премию короля Фейсала в области науки и премию BBVA Foundation Frontiers of Knowledge. Шор является членом Национальной академии наук и Американской академии искусств и наук. Он также является членом Американского математического общества и Ассоциации вычислительной техники.
