RSS-ленты
РусскийEnglish
Выпуск 11, 2024
Том год страница
Выпуски Авторы PACS Подписчикам Для авторов

Выпуски

 / 

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
2-s2.0-85208396821
2024PhyU...67..906F
Цитата: Федоров А К, Киктенко Е О, Колачевский Н Н "Вычислимое и невычислимое в квантовом мире: утверждения и гипотезы" УФН 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 conjectures” Phys. Usp. 67 906–911 (2024); DOI: 10.3367/UFNe.2024.07.039721

Список литературы (45) ↓

  1. Moore G E Electronics 38 (8) 114 (1965); reprinted, Moore G E IEEE Solid-State Circuits Soc. Newslett. 11 (3) 33 (1965)
  2. Rivest R L, Shamir A, Adleman L Commun. ACM 21 (2) 120 (1978)
  3. Waldrop M M Nature 530 144 (2016)
  4. Fedorov A K, Gisin N, Beloussov S M, Lvovsky A I arXiv:2203.17181
  5. Brassard G, Chuang I, Lloyd S, Monroe C Proc. Natl. Acad. Sci. USA 95 11032 (1998)
  6. Shor P Proc. 35th Annual Symp. on Foundations of Computer Science, 20-22 November 1994, Santa Fe, NM, USA (Piscataway, NJ: IEEE, 1994) p. 124-134
  7. Lloyd S Science 273 1073 (1996)
  8. Feynman R P Int. J. Theor. Phys. 21 467 (1982)
  9. Feynman R P Found. Phys. 16 507 (1986)
  10. Поплавский Р П УФН 115 465 (1975); Poplavskii R P Sov. Phys. Usp. 18 222 (1975)
  11. Preskill J "Quantum computing and the entanglement frontier" arXiv:1203.5813
  12. Ladd T D, Jelezko F, Laflamme R, Nakamura Y, Monroe C, O'Brien J L Nature 464 45 (2010)
  13. 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
  14. Nielsen M A, Chuang I L Quantum Computation and Quantum Information (Cambridge: Cambridge Univ. Press, 2000)
  15. Aaronson S, Gottesman D Phys. Rev. A 70 052328 (2004)
  16. Федоров А К, Киктенко Е О, Хабарова К Ю, Колачевский Н Н УФН 193 1162 (2023); Fedorov A K, Kiktenko E O, Khabarova K Yu, Kolachevsky N N Phys. Usp. 66 1095 (2023)
  17. Raussendorf R, Briegel H J Phys. Rev. Lett. 86 5188 (2001)
  18. Ermakov I, Lychkovskiy O, Byrnes T "Unified framework for efficiently computable quantum circuits" arXiv:2401.08187
  19. Манин Ю И Вычислимое и невычислимое (М.: Советское радио, 1980)
  20. Wang Y et al "Fault-tolerant one-bit addition with the smallest interesting colour code" arXiv:2309.09893; Wang Y et al Sci. Adv. 10 eado9024 (2024)
  21. 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)
  22. Беляев А А, Воронцов В Г, Демидов Н А, Хабарова К Ю, Колачевский Н Н УФН 193 1091 (2023); Belyaev A A, Voronzov V G, Demidov N A, Khabarova K Yu, Kolachevsky N N Phys. Usp. 66 1026 (2023)
  23. Хабарова К Ю, Заливако И В, Колачевский Н Н УФН 192 1305 (2022); Khabarova K Yu, Zalivako I V, Kolachevsky N N Phys. Usp. 65 1217 (2022)
  24. 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. A 107 052612 (2023)
  25. 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)
  26. 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
  27. 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. A 109 032619 (2024)
  28. Aharonov D, van Dam W, Kempe J, Landau Z, Lloyd S, Regev O SIAM J. Comput. 37 166 (2007)
  29. Orús R Nat. Rev. Phys. 1 538 (2019)
  30. Deng D-L, Li X, Das Sarma S Phys. Rev. X 7 021021 (2017)
  31. Sharir O, Shashua A, Carleo G Phys. Rev. B 106 205136 (2022)
  32. Kurmapu M K, Tiunova V V, Tiunov E S, Ringbauer M, Maier C, Blatt R, Monz T, Fedorov A K, Lvovsky A I PRX Quantum 4 040345 (2023)
  33. Patel K N, Markov I L, Hayes J P quant-ph/0302002
  34. Bravyi S, Maslov D IEEE Trans. Inform. Theory 67 4546 (2021)
  35. Hastings M B Phys. Rev. B 73 085115 (2006)
  36. Vatan F, Williams C Phys. Rev. A 69 032315 (2004)
  37. Arute F et al Nature 574 505 (2019)
  38. Wu Y et al Phys. Rev. Lett. 127 180501 (2021)
  39. 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
  40. Sun X, Tian G, Yang S, Yuan P, Zhang S IEEE Trans. Computer-Aided Design Integr. Circuits Syst. 42 3301 (2023)
  41. Gross D J. Math. Phys. 47 122107 (2006)
  42. Трушечкин А С, Киктенко Е О, Кронберг Д А, Федоров А К УФН 191 93 (2021); Trushechkin A S, Kiktenko E O, Kronberg D A, Fedorov A K Phys. Usp. 64 88 (2021)
  43. Pokharel B, Lidar D A Phys. Rev. Lett. 130 210602 (2023)
  44. Ghosh S, Deshpande A, Hangleiter D, Gorshkov A V, Fefferman B Phys. Rev. Lett. 131 030601 (2023)
  45. 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
© Успехи физических наук, 1918–2024
Электронная почта: ufn@ufn.ru Телефоны и адреса редакции О журнале Пользовательское соглашение