Значительные успехи в разработке вычислительных устройств, использующих квантовые эффекты, и демонстрация решения с их помощью различных задач стимулировали новую волну интереса к вопросу о природе "квантового вычислительного преимущества" (quantum computational advantage). Хотя различные попытки количественно оценить и охарактеризовать природу квантового вычислительного преимущества предпринимались и раньше, в широком контексте данный вопрос остаётся открытым. В самом деле, не существует универсального подхода, помогающего определить круг задач, решение которых квантовые компьютеры способны ускорить, теоретически и на практике. В настоящей работе мы рассмотрим подход к этому вопросу, основанный на концепции сложности и достижимости квантовых состояний. С одной стороны, класс квантовых состояний, представляющий интерес для квантовых вычислений, должен быть сложным, т.е. не поддающимся моделированию с помощью классических компьютеров с менее чем экспоненциальными ресурсами. С другой стороны, такие квантовые состояния должны быть достижимы на практическом квантовом компьютере. Последнее означает, что унитарная операция, соответствующая преобразованию квантовых состояний от исходного к желаемому, может быть декомпозирована в не более чем полиномиальную по числу кубитов последовательность одно- и двухкубитных вентилей. Формулируя ряд утверждений и гипотез, мы рассматриваем вопрос об описании класса задач, решение которых может быть ускорено с помощью квантового компьютера.

%0 Journal Article
%T Computable and noncomputable in the quantum domain: statements and conjectures
%A A. K. Fedorov
%A E. O. Kiktenko
%A N. N. Kolachevsky
%I Uspekhi Fizicheskikh Nauk
%D 2024
%J Usp. Fiz. Nauk
%V 194
%N 9
%P 960-966
%U https://ufn.ru/ru/articles/2024/9/e/
%U https://doi.org/10.3367/UFNr.2024.07.039721