Issues

 / 

2024

 / 

September

  

On the 90th anniversary of the Lebedev Physics Institute of the Russian Academy of Sciences (LPI). Physics of our days


Computable and noncomputable in the quantum domain: statements and conjectures

  a, b, c,   b, c, §  a, c
a Lebedev Physical Institute, Russian Academy of Sciences, Leninsky prosp. 53, Moscow, 119991, Russian Federation
b National University of Science and Technology "MISIS", Leninskii prosp. 4, Moscow, 119049, Russian Federation
c International Center for Quantum Optics and Quantum Technologies (the Russian Quantum Center), Skolkovo Innovation Center, Bolshoi Boulevard, Building 30, Block 1, 3rd floor, sectors G3, G7, Moscow, Moscow Region, 121205, Russian Federation

Significant advances in the development of computing devices based on quantum effects and the demonstration of their use to solve various problems have rekindled interest in the nature of the "quantum computational advantage." Although various attempts to quantify and characterize the nature of the quantum computational advantage have previously been made, this question largely remains open. Indeed, there is no universal approach that allows determining the scope of problems whose solution can be accelerated by quantum computers, in theory of in practice. In this paper, we consider an approach to this question based on the concept of complexity and reachability of quantum states. On the one hand, the class of quantum states that are of interest for quantum computing must be complex, i.e., not amenable to simulation by classical computers with less than exponential resources. On the other hand, such quantum states must be reachable on a practically feasible quantum computer. This means that the unitary operation that transforms the initial quantum state into the desired one must be decomposable into a sequence of one- and two-qubit gates of a length that is at most polynomial in the number of qubits. By formulating several statements and conjectures, we discuss the question of describing a class of problems whose solution can be accelerated by a quantum computer.

Fulltext pdf (775 KB)
Fulltext is also available at DOI: 10.3367/UFNe.2024.07.039721
Keywords: quantum computing, quantum complexity, quantum algorithms
PACS: 03.67.Ac, 03.67.Lx, 42.50.Dv (all)
DOI: 10.3367/UFNe.2024.07.039721
URL: https://ufn.ru/en/articles/2024/9/f/
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)
BibTexBibNote ® (generic)BibNote ® (RIS)MedlineRefWorks

Received: 17th, May 2024, revised: 19th, July 2024, 19th, July 2024

Оригинал: Федоров А К, Киктенко Е О, Колачевский Н Н «Вычислимое и невычислимое в квантовом мире: утверждения и гипотезы» УФН 194 960–966 (2024); DOI: 10.3367/UFNr.2024.07.039721

References (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. Poplavskii R P Sov. Phys. Usp. 18 222 (1975); Poplavskii R P Usp. Fiz. Nauk 115 465 (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. Fedorov A K, Kiktenko E O, Khabarova K Yu, Kolachevsky N N Phys. Usp. 66 1095 (2023); Fedorov A K, Kiktenko E O, Khabarova K Yu, Kolachevsky N N Usp. Fiz. Nauk 193 1162 (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:arXiv:2401.08187
  19. Manin Yu I Vychislimoe I Nevychislimoe (Computable And Non-computable) (Moscow: Sovetskoe Radio, 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. Belyaev A A, Voronzov V G, Demidov N A, Khabarova K Yu, Kolachevsky N N Phys. Usp. 66 1026 (2023); Belyaev A A, Voronzov V G, Demidov N A, Khabarova K Yu, Kolachevsky N N Usp. Fiz. Nauk 193 1091 (2023)
  23. Khabarova K Yu, Zalivako I V, Kolachevsky N N Phys. Usp. 65 1217 (2022); Khabarova K Yu, Zalivako I V, Kolachevsky N N Usp. Fiz. Nauk 192 1305 (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. Comput.-Aided Design Integr. Circuits Syst. 42 3301 (2023)
  41. Gross D J. Math. Phys. 47 122107 (2006)
  42. Trushechkin A S, Kiktenko E O, Kronberg D A, Fedorov A K Phys. Usp. 64 88 (2021); Trushechkin A S, Kiktenko E O, Kronberg D A, Fedorov A K Usp. Fiz. Nauk 191 93 (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 Uspekhi Fizicheskikh Nauk
Email: ufn@ufn.ru Editorial office contacts About the journal Terms and conditions