Science: Физики нашли задачу, неподвластную даже квантовым компьютерам

Физики из Калифорнийского технологического института, Гарварда и подразделения Google Quantum AI доказали, что существует класс задач, неподвластных даже самым мощным квантовым компьютерам.

Работа опубликована в журнале Science Advances и посвящена вычислительной сложности анализа экзотических квантовых фаз материи, пишет Science Advances.

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

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