К 90-летию Физического института им. П.Н. Лебедева РАН (ФИАН). Физика наших дней
Вычислимое и невычислимое в квантовом мире: утверждения и гипотезы
А.К. Федоров†а,б,в,
Е.О. Киктенко‡б,в,
Н.Н. Колачевский§а,б аФизический институт им. П.Н. Лебедева РАН, Ленинский проспект 53, Москва, 119991, Российская Федерация бМеждународный центр квантовой оптики и квантовых технологий (Российский квантовый центр), ул. Новая 100, Сколково, Московская обл., 143025, Российская Федерация вНациональный исследовательский технологический университет «МИСиС», Ленинский просп. 4, Москва, 119049, Российская Федерация
Значительные успехи в разработке вычислительных устройств, использующих квантовые эффекты, и демонстрация решения с их помощью различных задач стимулировали новую волну интереса к вопросу о природе "квантового вычислительного преимущества" (quantum computational advantage). Хотя различные попытки количественно оценить и охарактеризовать природу квантового вычислительного преимущества предпринимались и раньше, в широком контексте данный вопрос остаётся открытым. В самом деле, не существует универсального подхода, помогающего определить круг задач, решение которых квантовые компьютеры способны
ускорить, теоретически и на практике. В настоящей работе мы рассмотрим подход к этому вопросу, основанный на концепции сложности и достижимости квантовых состояний. С одной стороны, класс квантовых состояний, представляющий интерес для квантовых вычислений, должен быть сложным, т.е. не поддающимся моделированию с помощью классических компьютеров с менее чем экспоненциальными ресурсами. С другой стороны, такие квантовые состояния должны быть достижимы на практическом квантовом компьютере. Последнее означает, что унитарная операция, соответствующая преобразованию квантовых состояний от исходного
к желаемому, может быть декомпозирована в не более чем полиномиальную по числу кубитов последовательность одно- и двухкубитных вентилей. Формулируя ряд утверждений и гипотез, мы рассматриваем вопрос об описании класса задач, решение которых может быть ускорено с помощью квантового компьютера.
Ключевые слова: квантовые вычисления, квантовая сложность, квантовые алгоритмы PACS:03.67.Ac, 03.67.Lx, 42.50.Dv (все) DOI:10.3367/UFNr.2024.07.039721 URL: https://ufn.ru/ru/articles/2024/9/e/ Цитата: Федоров А К, Киктенко Е О, Колачевский Н Н "Вычислимое и невычислимое в квантовом мире: утверждения и гипотезы" УФН194 960–966 (2024)
Preskill J "Quantum computing and the entanglement frontier" arXiv:1203.5813
Ladd T D, Jelezko F, Laflamme R, Nakamura Y, Monroe C, O'Brien J L Nature464 45 (2010)
Gottesman D "The Heisenberg representation of quantum computers" quant-ph/9807006; Gottesman D Group 22: Proc. of the 12th Intern. Colloquium on Group Theoretical Methods in Physics (Eds S P Corney, R Delbourgo, P D Jarvis) (Cambridge, MA: Intern. Press, 1999) p. 32
Nielsen M A, Chuang I L Quantum Computation and Quantum Information (Cambridge: Cambridge Univ. Press, 2000)
Fedorov A K, Akimov A V, Biamonte J D, Kavokin A V, Khalili F Ya, Kiktenko E O, Kolachevsky N N, Kurochkin Y V, Lvovsky A I, Rubtsov A N, Shlyapnikov G V, Straupe S S, Ustinov A V, Zheltikov A M Quantum Sci. Technol.4 040501 (2019)
Беляев А А, Воронцов В Г, Демидов Н А, Хабарова К Ю, Колачевский Н Н УФН193 1091 (2023); Belyaev A A, Voronzov V G, Demidov N A, Khabarova K Yu, Kolachevsky N N Phys. Usp.66 1026 (2023)
Aksenov M A, Zalivako I V, Semerikov I A, Borisenko A S, Semenin N V, Sidorov P L, Fedorov A K, Khabarova K Yu, Kolachevsky N N Phys. Rev.A107 052612 (2023)
Zalivako I V, Borisenko A S, Semerikov I A, Korolkov A E, Sidorov P L, Galstyan K P, Semenin; N V, Smirnov V N, Aksenov M D, Fedorov A K, Khabarova K Yu, Kolachevsky N N Front. Quantum Sci. Technol.2 1228208 (2023)
Zalivako I V, Nikolaeva A S, Borisenko A S, Korolkov A E, Sidorov P L, Galstyan K P, Semenin N V, Smirnov V N, Aksenov M A, Makushin K M, Kiktenko E O, Fedorov A K, Semerikov I A, Khabarova K Yu, Kolachevsky N N "Towards multiqudit quantum processor based on a 171Yb+ ion string: Realizing basic quantum algorithms" arXiv:2402.03121
Kazmina A S, Zalivako I V, Borisenko A S, Nemkov N A, Nikolaeva A S, Simakov I A, Kuznetsova A V, Egorova E Yu, Galstyan K P, Semenin N V, Korolkov A E, Moskalenko I N, Abramov N N, Besedin I S, Kalacheva D A, Lubsanov V B, Bolgar A N, Kiktenko E O, Khabarova K Yu, Galda A, Semerikov I A, Kolachevsky N N, Maleeva N, Fedorov A K Phys. Rev.A109 032619 (2024)
Aharonov D, Gao X, Landau Z, Liu Y, Vazirani U STOC 2023. Proc. of the 55th Annual ACM Symp. on Theory of Computing (Eds B Saha, R A Servedio) (New York: Association for Computing Machinery, 2023) p. 945-957
Трушечкин А С, Киктенко Е О, Кронберг Д А, Федоров А К УФН191 93 (2021); Trushechkin A S, Kiktenko E O, Kronberg D A, Fedorov A K Phys. Usp.64 88 (2021)
Sotnikov O M, Iakovlev I A, Kiktenko E O, Fedorov A K, Mazurenko V V "Achieving the volume-law entropy regime with random-sign Dicke states" arXiv:2404.15050