Квантовые вычисления со времен Демокрита - Скотт Ааронсон

противника, если считать, что задача нахождения кратчайшего вектора трудна для квантовых компьютеров. Стоит отметить, что сами по себе его криптосистемы являются чисто классическими. С другой стороны, даже если бы вам нужна была надежность в отношении классического противника, вам все равно пришлось бы считать, что задача нахождения кратчайшего вектора трудна для квантовых компьютеров, поскольку переход от этой задачи к взлому криптосистемы — это квантовое сведение! Позже, в 2009 г., Крис Пикерт[52] открыл способ «деквантизации» сведения Регева, так что теперь достаточно уверенности в классической трудности задачи нахождения кратчайшего вектора.

Что еще интереснее, Крейг Джентри показал[53] в 2009 г., что, воспользовавшись предполагаемой трудностью определенных задач с решетками, связанных с нахождением кратчайшего вектора, можно строить полностью гомоморфные криптосистемы: то есть криптосистемы с открытым ключом, которые позволяют вам проводить произвольные вычисления с зашифрованными данными вообще без их расшифровки. Почему это важно? Ну, для таких приложений, как «облачные вычисления»: вам может потребоваться, скажем, переложить какие-то длинные вычисления с вашего мобильного устройства на какой-то внешний сервер, но так, чтобы не позволить этому серверу заглянуть в ваши секретные данные. То есть вы должны иметь возможность переслать на сервер зашифрованные входные данные, а сервер должен иметь возможность провести сложные вычисления, за которые вы заплатили, и переслать вам обратно зашифрованные выходные данные, которые вы затем сможете самостоятельно расшифровать (а может быть, даже и проверить); при этом сервер ничего о ваших данных не узнает. И дополнительный бонус: поскольку наши нынешние полностью гомоморфные системы шифрования основаны на задачах, связанных с решетками, то у них с системами Регева есть одна общая черта: никто не знает, как их взломать даже при помощи квантового компьютера. О возможности полностью гомоморфной криптографии впервые заговорили в 1970-е гг., но до самого последнего времени никто не знал, как это организовать. Так что это одно из крупнейших достижений теоретической криптографии за несколько десятков лет.

Но имеет ли все это практическое значение? Традиционно считалось, что нет. Лет десять назад длины ключей и сообщений в системах на основе решетки были хотя формально и полиномиальными, но такими длинными, что сам вопрос казался почти шуткой: объем данных на пути от обычного текста к шифрованному увеличивался иногда в миллионы раз (в зависимости от того, какую степень надежности вы хотели получить). Но с тех пор криптография на решетках постепенно движется в направлении практичности, отчасти, откровенно говоря, потому, что все поняли: можно значительно повысить эффективность, поступившись в небольшой степени требованиями к надежности. Если когда-нибудь масштабируемые квантовые компьютеры, способные взломать RSA, покажутся серьезной и реальной опасностью, я предсказываю, что ответом на это станет переход на новые криптосистемы с открытым ключом, похожие на криптосистемы на решетках. И опять же перспектива создания полностью гомоморфного шифрования может дать дополнительный и совершенно отдельный повод для такого перехода.

А что же криптосистемы на основе эллиптических кривых — еще один важный класс криптосистем с открытым ключом (в отличие от криптосистем на решетках, этот класс сегодня уже используется коммерчески)? К несчастью, криптосистемы на эллиптических кривых легко взламываются квантовыми компьютерами, поскольку задача их взлома может быть выражена как задача поиска абелевой скрытой подгруппы. (Потому что группы эллиптических кривых — это абелевы группы.) С другой стороны, самые известные классические алгоритмы взлома криптосистем на эллиптических кривых, судя по всему, работают медленнее, чем решето числового поля при взломе RSA, — речь идет о степени ~2n против ~

. Не исключено, что этот факт относится к категории фундаментальных, но не исключено также, что причина просто в том, что группы эллиптических кривых не слишком хорошо изучены.

На этом мы завершаем наш краткий обзор классической теории сложности и криптографии; мы готовы говорить о квантовой механике.

9. Квант

Существует два способа преподавать квантовую механику. Первый способ — для многих физиков сегодня он по-прежнему единственный — следует исторической последовательности, в которой совершались открытия и высказывались идеи. Вы начинаете с классической механики и электродинамики и на каждом шагу долго и нудно решаете дифференциальные уравнения. Затем вы узнаете о «парадоксе черного тела», о различных странных экспериментальных данных и о глобальном кризисе в физике, порожденном этими вещами. Далее вы знакомитесь с пестрым лоскутным одеялом всевозможных идей, предложенных физиками с 1900 по 1926 г., когда все искали пути разрешения кризиса. Затем, если вам повезет, после долгих лет прилежных занятий вы наконец приступите к изучению центральной концептуальной идеи: что природа описывается не вероятностями (которые всегда неотрицательны), но числами, получившими название амплитуд, которые могут быть положительными, отрицательными или даже комплексными.

Ну да, очевидно, у физиков есть какие-то свои резоны для преподавания квантовой механики именно по этой методике; она прекрасно работает для определенного типа студентов. Но у «исторического» подхода есть и недостатки, которые в век квантовой информации становятся все более очевидными. К примеру, у меня были ситуации, когда специалисты по квантовой теории поля — люди, потратившие годы на вычисление головоломных интегралов по контуру, — просили меня объяснить им смысл неравенства Белла или других простых концептуальных вещей, таких как алгоритм Гровера. Я же чувствовал себя так, будто Эндрю Уайлс[54] попросил меня объяснить теорему Пифагора.

Непосредственным результатом того, что я определил для себе как алфавитный подход к объяснению квантовой механики, — вплоть до настоящего времени вы можете наблюдать его чуть ли не во всех популярных книгах и статьях, — стало то, что предмет этот приобрел ненужную репутацию запутанного и трудного. Образованные люди заучивали наизусть лозунги: «свет это одновременно волна и частица», «кот ни жив, ни мертв, пока вы на него не посмотрите», «вы можете узнать координату или импульс, но не то и другое одновременно», «одна частица мгновенно узнает спин второй частицы посредством жуткого дальнодействия» и т. п. Но они усваивали также, что не нужно даже пытаться понимать подобные вещи, не вложив в процесс годы упорного труда.

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

Итак, что такое