К 90-летию Физического института им. П.Н. Лебедева РАН (ФИАН)
Вычислимое и невычислимое в квантовом мире: утверждения и гипотезы
А.К. Федорова,б,в,
Е.О. Киктенкоб,в,
Н.Н. Колачевскийа,б аФизический институт им. П.Н. Лебедева РАН, Ленинский проспект 53, Москва, 119991, Российская Федерация бМеждународный центр квантовой оптики и квантовых технологий (Российский квантовый центр), ул. Новая 100, Сколково, Московская обл., 143025, Российская Федерация вНациональный исследовательский технологический университет «МИСиС», Ленинский просп. 4, Москва, 119049, Российская Федерация
Значительные успехи в разработке вычислительных устройств, использующих квантовые
эффекты, и демонстрация решения с их помощью различных задач стимулировали новую
волну интереса к вопросу о природе "квантового вычислительного преимущества" (quantum
computational advantage). Хотя различные попытки количественно оценить и охарактеризовать
природу квантового вычислительного преимущества предпринимались и раньше, в широком
контексте этот вопрос остается открытым. В самом деле, не существует универсального подхода, помогающего определить круг задач, решение которых квантовые компьютеры способны
ускорить, теоретически и на практике. В настоящей работе мы рассмотрим подход к этому вопросу, основанный на концепции сложности и достижимости квантовых состояний. С одной
стороны, класс квантовых состояний, представляющий интерес для квантовых вычислений,
должен быть сложным, то есть не поддающимся моделированию с помощью классических
компьютеров с менее, чем экспоненциальными ресурсами. С другой стороны, такие квантовые
состояния должны быть достижимы на практическом квантовом компьютере. Это означает,
что унитарная операция, соответствующая преобразованию квантовых состояний от исходного
к желаемому, может быть декомпозирована в не более чем полиномиальную по числу кубитов
последовательность одно- и двухкубитных вентилей. Формулируя ряд утверждений и гипотез,
мы рассматриваем вопрос об описании класса задач, который может быть ускорен с помощью
квантового компьютера.
Ключевые слова: квантовые вычисления, квантовая сложность, квантовые алгоритмы DOI:10.3367/UFNr.2024.07.039721 Цитата: Федоров А К, Киктенко Е О, Колачевский Н Н "Вычислимое и невычислимое в квантовом мире: утверждения и гипотезы" УФН, принята к публикации
Поступила: 17 мая 2024, доработана: 19 июля 2024, одобрена в печать: 19 июля 2024