[Перевод] Классические компьютеры перенимают квантовые идеи

4cdc27a31b012e23ce957eeac043f859.jpg
Кремниевый чип с тремя кубитами, созданный исследователями IBM, надеющимися когда-нибудь сконструировать такие чипы с тысячами кубитов

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

«Идут бурные дебаты по поводу того, будут ли квантовые компьютеры вообще когда-либо созданы,- говорит Крис Пейкерт [Chris Peikert], специалист по криптографии и информатике их Технологического института Джорджии. — Но это один вопрос, а второй — могут ли квантовые техники или алгоритмы помочь вам решать задачи новыми способами».
В последнее время квантовые идеи помогли исследователям доказать безопасность многообещающих технологий шифрования под названием «криптография на решётках», чьё применение может помочь скрыть чувствительные данные пользователей, такие, как их ДНК, даже от компаний, обрабатывающих эти данные. Доказательство через квантовые подсчёты также привело к формуле минимальной длины кодов исправления ошибок, оберегающих данные от повреждений.

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

«Если бы это случилось один раз, это было бы совпадением. Но существует так много вариантов, в которых 'квантовое' мышление приводит к получению доказательства»,- говорит Одед Регев [Oded Regev], специалист по информатике из Нью-йоркского университета.

300f9e4199ebcb93eacf9ecf3e3497ed.jpg
Для шифрования данных можно использовать многомерные решётки, доказательство чего было получено при помощи квантовых вычислений

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

В более общем случае квантовые идеи — это мощные инструменты для решения классических вычислительных задач. «Существует несколько классических задач, не имеющих ничего общего с квантовым миром, но лучше всего анализировать их, обобщив до квантового уровня, доказав что-либо при помощи теории квантовой информации, и затем масштабировав обратно до классического уровня»,- говорит Рональд де Вульф, теоретик в области информатики в нидерландском Центре математики и информатики.

По сегодняшним прикидкам, не более 5% учёных, работающих в области теоретической информатики, изучают квантовые вычисления. Но исследователи говорят, что последние успехи «квантового мышления» привели к росту количества теоретиков, стремящихся подучить физику. «Эти удивительные ответвления от квантовых вычислений на самом деле заставили учёных, пользующихся классическими методами информатики, заняться изучением квантовых вычислений»,- говорит Скотт Ааронсон [Scott Aaronson], теоретик в области информатики в Массачусетском технологическом институте.

Цель квантовых вычислений — использовать странное поведение частиц на квантовых масштабах для проведения вычислений, кажущихся невозможными для обычных компьютеров. Обычный компьютер хранит биты информации в транзисторах, которые на манер переключателей могут находиться в одном из двух состояний, обозначающих 1 или 0. Квантовый компьютер хранит кубиты информации в субатомных частицах, электронах или фотонах, которые могут существовать в состояниях 1, 0, или в суперпозиции их обоих, а также могут запутываться друг с другом, в результате чего состояние одного кубита предопределяет состояние другого.

3e6ac7860cb86efa2df0d0d918db1913.jpg
Чип от IBM с тремя кубитами

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

Проблема лишь в том, что никто пока не смог создать квантовый компьютер, в котором количество кубитов превышало бы количество пальцев на руках. Крис Лиракис [Chris Lirakis], физик из группы сверхпроводимых квантовых расчётов в IBM Research, объясняет, что для удержания системы запутанных кубитов от коллапса её нужно изолировать и охладить почти до абсолютного нуля. В то же время, кубиты нужно разнести примерно на сантиметр друг от друга, чтобы операции с одним из них не влияли на остальные. Эти ограничения делают системы из тысячи кубитов слишком большими для того, чтобы разместить их в холодильниках, способных поддерживать нужную температуру.

«Нужно решить очень много весьма серьёзных инженерных задач, чтобы сделать эту систему масштабируемой,- говорит Лиракис. — Все проблемы играют в перетягивание каната».

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

С увеличением популярности квантовых технологий можно ожидать решения всё большего количества классических задач. «Именно эти результаты убедили меня, что даже если бы во вселенной не было квантовых механизмов, специалисты по информатике, в конце концов, изобрели бы их для решения задач».

© Geektimes