Ученые нашли задачу, которую квантовые компьютеры не могут решить за разумное время

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

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

Сложность квантовых фаз

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

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

Нерешаемая задача

Ученые создали математический сценарий, где квантовый компьютер получает информацию о квантовом состоянии объекта и должен определить его фазу. Оказалось, что вычислительное время растет экспоненциально с увеличением длины корреляции (ξ) и становится суперполиномиальным при ξ = ω(log n).

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

Последствия открытия

Ранее в этом году Шустер и коллеги опубликовали работу о случайности и квантовых компьютерах, где намекали на фундаментальные ограничения в познании физических свойств.

Это исследование показывает, что некоторые свойства Вселенной могут иметь принципиальные ограничения, препятствующие их полному пониманию. Ученые продолжат изучать, какие физические свойства делают распознавание фаз практически выполнимым, несмотря на теоретическую сложность.

Источник: Thomas Schuster et al, Hardness of recognizing phases of matter, arXiv (2025). DOI: 10.48550/arxiv.2510.08503