В свежей, полезной статье про «маркетинг» квантовых компьютеров (и хайп вокруг них) упомянута публикация профессора Дьяконова, где рассматривается интересный аргумент против возможности квантовых вычислений на кубитах, а именно — аргумент «недостижимого количества состояний»:

«Таким образом, число непрерывных переменных, описывающих состояние компьютера в каждый данный момент должно оцениваться числом, по меньшей мере, 2^1000 (~10^300), которое много, много больше числа частиц во Вселенной (их, всего лишь, порядка 10^80)!»

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

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

Эти (комплексные) вероятности, чтобы ими манипулировать, вкладываются в огромное пространство состояний системы, например, той самой «недостижимой» «размерности ». И в этом пространстве, по установленным уравнениям преобразований, отдельные конфигурации интерферируют: вероятности сокращаются, приводя к полезному результату. Именно идея использовать мощность пространства квантовых состояний для аналоговых вычислений и лежит в основе концепции квантовых вычислений. Например, именно так её сформулировал, одним из первых, советский математик Юрий Иванович Манин в книжке «Вычислимое и невычислимое» (это ещё 1980 год, издательство «Советское радио»).

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

Не так давно профессор Бернштейн опубликовал интересную статью с критическим разбором некоторых аргументов о том, что квантовые компьютеры не будут работать. (Бернштейн — djb — весьма известный специалист в области математических основ криптографии, наверняка знаком читателям «Хабра»; вполне вероятно, что ваш браузер при загрузке этой веб‑страницы использовал для обмена ключами TLS криптосистему X25519, которая работает на кривой, разработанной и впервые реализованной Бернштейном.) В статье Бернштейна разбираются типовые возражения, относящиеся к самой возможности квантовых вычислений. Естественно, там рассматривается и аргумент про большое количество состояний/переменных. Бернштейн логично отмечает, что само по себе большое количество возможных состояний не является препятствием, как минимум, для классических вычислений. Это подтверждено практикой. А именно — всякий современный ноутбук может сгенерировать псевдослучайное число разрядностью в тысячу бит так, чтобы вероятности получения разных значений различались. Для этого не требуется загрузить в память все значений — распределение вероятности вполне успешно задают математические преобразования, вводимые на 1000 битов, но без необходимости прямого указания всех возможных значений. Цитата (перевод с английского):

«Я не утверждаю, что вычисление на кубитах это то же самое, что и вычисление на случайных битах. Если посмотреть детально, то можно увидеть, что квантовое вычисление позволяет провести дополнительный полезный трюк, задав схемы интерференции между положительными и отрицательными переменными. Однако аргумент, говорящий, что „квантовые вычисления невозможны, так как там настолько много переменных“, не может быть верным, поскольку этот же аргумент говорит, что ваш ноутбук невозможен».

Действительно, если нужно управлять тысячей битов, то необязательно реализовывать такое управление через «гиперпамять» из ячеек. Другими словами, если рассматривать чисто арифметическую аргументацию про , на практике, то не важно, кубит там или не кубит: сгенерировать 1000-битное значение, соответствующее определённым параметрам, можно побитно, без экспоненциального роста вычислительных затрат. Да, экспоненциальный рост возник бы, если бы потребовалось перебрать все варианты, взвесить их и выбрать нужное значение, но распределение‑то можно реализовать и без такого перебора.

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

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

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

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