Выпуски

 / 

2024

 / 

Сентябрь

  

К 90-летию Физического института им. П.Н. Лебедева РАН (ФИАН). Физика наших дней


Вычислимое и невычислимое в квантовом мире: утверждения и гипотезы

  а, б, в,   б, в, §  а, б
а Физический институт им. П.Н. Лебедева РАН, Ленинский проспект 53, Москва, 119991, Российская Федерация
б Международный центр квантовой оптики и квантовых технологий (Российский квантовый центр), Территория Инновационного Центра "Сколково", Большой бульвар д. 30, стр. 1, 3 этаж, секторы G3, G7, Москва, Московская обл., 121205, Российская Федерация
в Национальный исследовательский технологический университет «МИСиС», Ленинский просп. 4, Москва, 119049, Российская Федерация

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

Текст pdf (306 Кб)
English fulltext is available at DOI: 10.3367/UFNe.2024.07.039721
Ключевые слова: квантовые вычисления, квантовая сложность, квантовые алгоритмы
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/
001343554500004
Цитата: Федоров А К, Киктенко Е О, Колачевский Н Н "Вычислимое и невычислимое в квантовом мире: утверждения и гипотезы" УФН 194 960–966 (2024)
BibTexBibNote ® (generic)BibNote ® (RIS)MedlineRefWorks

Поступила: 17 мая 2024, доработана: 19 июля 2024, 19 июля 2024

English citation: Fedorov A K, Kiktenko E O, Kolachevsky N N “Computable and noncomputable in the quantum domain: statements and conjecturesPhys. Usp. 67 906–911 (2024); DOI: 10.3367/UFNe.2024.07.039721

© Успехи физических наук, 1918–2024
Электронная почта: ufn@ufn.ru Телефоны и адреса редакции О журнале Пользовательское соглашение