Квантовый компьютер находит факторы


Алгоритм квантового разложения Шора был впервые запущен на твердотельном устройстве и успешно разложил составное число. Это начало революции квантовых вычислений?

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

Квантовый компьютер, с другой стороны, обещает учесть число любого размера за одну операцию, и, если таковой удастся построить, будущее PKI выглядит мрачным, и нам придется найти методы шифрования, которые были бы безопасны от квантовой атаки .

До недавнего времени идея факторизации с использованием квантового компьютера была всего лишь идеей. На самом деле создание квантового компьютера – сложная задача из-за необходимости поддерживать запутанное состояние между квантовыми битами – кубитами. Эта задача усложняется по мере увеличения количества кубитов.

Теперь команде из UCSB удалось построить и эксплуатировать квантовую схему, состоящую из четырех сверхпроводящих фазовых кубитов. Сложность управления этими квантовыми элементами потребовала создания системы управления, обеспечивающей точную работу и значительную степень автоматизации. Этот прототип облегчит масштабирование до более крупных и сложных схем. Тем не менее, есть еще несколько ученых-информатиков, которые считают, что полезный квантовый компьютер невозможно построить, потому что существует некий глубокий закон природы, который усложняет задачу, чем больше кубитов вы пытаетесь использовать.

В этом случае конструкция создает запутанные биты быстрее, чем раньше, и команда подтвердила, что запутанность происходит с помощью квантовой томографии. В заключительной части эксперимента был реализован алгоритм факторизации Шора с использованием 15 в качестве факторизуемого значения. В 150 000 прогонов расчета чип давал правильный результат в 48% случаев. Поскольку алгоритм Шора должен давать правильный ответ только в 50% случаев, это хороший результат.

Конечно, факторинг 15 – это не то, что угрожает PKI и криптографии в целом, но факторинг больших чисел – это просто вопрос увеличения количества кубитов, и этот подход действительно кажется масштабируемым твердотельным подходом.


Добавить комментарий