Uspekhi Fizicheskikh Nauk
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



UFN:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Uspekhi Fizicheskikh Nauk, 2024, Volume 194, Number 9, Pages 960–966
DOI: https://doi.org/10.3367/UFNr.2024.07.039721
(Mi ufn15908)
 

ON THE 90TH ANNIVERSARY OF THE P.N. LEBEDEV PHYSICAL INSTITUTE (LPI)
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. K. Fedorovabc , E. O. Kiktenkobc, N. N. Kolachevskyab

a Lebedev Physical Institute, Russian Academy of Sciences, Moscow
b Russian Quantum Center, Innovation Center Skolkovo, Moscow
c National University of Science and Technology MISIS, Moscow
References:
Abstract: 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.
Funding agency Grant number
Program of Strategic Academic Leadership Prioritet-2030 K1-2022-027
This work was supported by the Priority 2030 program at the National University of Science and Technology MISiS (project K1-2022-027).
Received: May 17, 2024
Revised: July 19, 2024
Accepted: July 19, 2024
English version:
Physics–Uspekhi, 2024, Volume 67, Issue 9, Pages 906–911
DOI: https://doi.org/10.3367/UFNe.2024.07.039721
Bibliographic databases:
Document Type: Article
PACS: 03.67.Ac, 03.67.Lx, 42.50.Dv
Language: Russian
Citation: A. K. Fedorov, E. O. Kiktenko, N. N. Kolachevsky, “Computable and noncomputable in the quantum domain: statements and conjectures”, UFN, 194:9 (2024), 960–966; Phys. Usp., 67:9 (2024), 906–911
Citation in format AMSBIB
\Bibitem{FedKikKol24}
\by A.~K.~Fedorov, E.~O.~Kiktenko, N.~N.~Kolachevsky
\paper Computable and noncomputable in the quantum domain: statements and conjectures
\jour UFN
\yr 2024
\vol 194
\issue 9
\pages 960--966
\mathnet{http://mi.mathnet.ru/ufn15908}
\crossref{https://doi.org/10.3367/UFNr.2024.07.039721}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2024PhyU...67..906F}
\transl
\jour Phys. Usp.
\yr 2024
\vol 67
\issue 9
\pages 906--911
\crossref{https://doi.org/10.3367/UFNe.2024.07.039721}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=001343554500004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85208396821}
Linking options:
  • https://www.mathnet.ru/eng/ufn15908
  • https://www.mathnet.ru/eng/ufn/v194/i9/p960
    Related publications
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Успехи физических наук Physics-Uspekhi
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024