Я думаю, что есть много интересных ответов на ваш вопрос, но я хотел бы указать на то, что лично я считаю самым завораживающим следствием квантовой теории для криптографии.
Одним из самых захватывающих квантовых явлений, у которого нет классического аналога, не является клонирование . По сути это означает, что если у вас недостаточно информации о каком-либо квантовом состоянии, вы не сможете подготовить больше его копий. Это можно рассматривать (неофициально) как подтверждение принципа неопределенности: если бы вы могли подготовить две совершенные копии системы, о которой вы ничего не знаете, то ничто не мешает вам измерить каждую копию на другой основе, получив таким образом знания о двух взаимно несмещенных свойства (например, если вы могли бы идеально скопировать электрон, то вы могли бы измерить его импульс в одном экземпляре и его положение в другом).
Нет клонирования, как правило, огромная боль. Например, рассмотрим, например, алгоритм Миллера-Рабина для тестирования простоты . Это рандомизированный алгоритм, который означает, что каждый раз, когда вы его запускаете, он играет немного по-другому. Учитывая простое число, этот алгоритм всегда скажет вам, что это простое число. Учитывая составное число, оно все еще скажет вам, что оно простое. Однако можно доказать, что это происходит с вероятностью, меньшей чем1 / 2, Это подразумевает, что если вы запустите алгоритмN раз на составном числе вероятность того, что он скажет вам, что это простое каждый раз, самое большее 1 / 2N, Этот процесс называется усилением , и основное предположение состоит в том, что мы всегда можем повторить алгоритм. Хотя это классически тривиально, это предположение обычно не выполняется в квантовой сфере, поскольку состояние входа может быть измерено и, следовательно, необратимо разрушено. Marriot и Watrous показали, что алгоритмы BQP все еще могут быть усилены таким образом, но способ сделать это весьма нетривиален.
Как и следовало ожидать, сейчас наступает этап «лимоны к лимонаду». Потому что, если клонирование состояний невозможно, можем ли мы использовать это в наших интересах, скажем, для создания вещей, которые мы не хотим, чтобы люди делали копии, таких как деньги?
Удивительно, но эта идея предшествует большей части квантовых вычислений и информации. Еще в 1968 году Стив Виснер предложил применить клонирование для реализации денег, которые физически невозможно подделать. Что еще более удивительно, его конструкция чрезвычайно проста и требует только умения применять местные ворота Адамара (и, следовательно, деньги кодируются в полностью отделимое состояние). К сожалению, как гласит история, кажется, что Виснер не смог опубликовать свой прорыв в течение более десяти лет.
Приложения без клонирования с тех пор значительно расширились, и продолжаются исследования очень естественных дополнительных проблем, таких как публичные квантовые деньги (в схеме Виснера, только тот, кто создал деньги, может проверить это. Это заслуживает вопроса: способен ли он заработать деньги, которые каждый может проверить, но никто не может их подделать) ( см. также ), квантовая защита от копирования , неклонируемое шифрование , одноразовые токены подписии т. д. Это все захватывающие примитивы, которые классически невозможны, но могут быть возможны при использовании квантовых вычислений (при некоторых мягких вычислительных предположениях). Современное состояние техники заключается в том, что почти все такие конструкции либо основаны на сильных (или просто нерегулярных) предположениях, либо на существовании какого-то нереального оракула. Но имейте в виду, что эти вопросы являются относительно новыми, и исследования с их участием очень активны!
