Bienvenue dans la terra incognita, le grand fossé quantique–classique

Vous joindrez-vous à notre quête mondiale pour cartographier les falaises du grand inconnu ? L’humanité doit compléter la carte entre nos théories classique et quantique du calcul. Dans ce territoire, une modification apparemment minime d’un modèle physique pourrait transformer entièrement ce qu’il est capable d’accomplir. Quels modèles de calcul se trouvent entre ces falaises—et quelle structure minimale les rend programmables ? L’industrie quantique doit le savoir.

Lorsque je suis entré dans le domaine, le paysage computationnel était souvent présenté comme ayant une seule frontière nette : les systèmes simulables efficacement de manière classique d’un côté et les ordinateurs quantiques universels de l’autre. [Fig. 1] Quelle est la différence structurelle ?

Une carte où les états fondamentaux de l’hamiltonien d’Ising se trouvent dans une région classique verte et les états fondamentaux de l’hamiltonien ZX dans une région quantique orange Caltech, séparés par une seule frontière turquoise courbe en pointillés. — **Figure 1.** Ma vision du monde a révélé le problème que je voulais comprendre. J’avais développé, d’un côté, la logique de spins à l’état fondamental—une logique d’espaces engendrés d’états fondamentaux qui incorpore des circuits de commutation dans des hamiltoniens d’Ising [13, 14]. De l’autre, j’avais démontré que l’hamiltonien ZX, qui diffère de la logique de spins par l’ajout d’un terme XX, permet le calcul quantique universel [1]. Je me suis tourné vers les mathématiques des réseaux de tenseurs pour comprendre la différence entre ces deux structures. J’ai apporté ces idées à Oxford et rédigé une thèse qui étendait la logique de spins à l’état fondamental d’un espace engendré à une somme sur des vecteurs de base, retrouvant la même structure compositionnelle sous la forme de réseaux de tenseurs booléens [4, 21]. Dans ce cadre, l’ajout de scalaires à cette structure permettait d’atteindre les états quantiques généraux.

Mais l’intractabilité classique est, de toute évidence, différente de l’universalité quantique. Il semble que de nombreux systèmes quantiques ne puissent pas être simulés efficacement de manière classique, sans pour autant être programmables comme des ordinateurs quantiques universels.

La différence pourrait être un nouveau type de programmabilité : la capacité de composer des interactions, des contraintes et des transformations afin qu’un système physique exécute un calcul choisi. Les gadgets d’état fondamental offrent une manière de programmer les modèles physiques [13] ; les réseaux de tenseurs transforment la même logique sous-jacente en un langage compositionnel [4].

Ces résultats, parmi d’autres, m’ont amené à voir deux frontières : celle où prend fin la simulation classique efficace et celle où commence le calcul quantique universel. Entre elles s’étend une vaste terra incognita—un fossé quantique–classique composé de systèmes dont la puissance de calcul demeure seulement en partie comprise. [Fig. 2] Il s’agit d’un immense territoire encore inexploré du savoir humain.

Une carte conceptuelle de la Terra Incognita couvrant les régions Classique, Quantique–Classique et Quantique. Des fils relient la logique de spins à la non-linéarité booléenne, les contractions de réseaux de tenseurs pour #SAT à la non-linéarité booléenne, les entropies spectrales aux marches quantiques chirales, les deux résultats QAOA et le contrôle universel du QAOA à l’échantillonnage de circuits réglables. Un fil se termine librement pour indiquer que les liens sont conceptuels et incomplets. — **Figure 2.** **L’image est conceptuelle, tout comme les liens représentés.** Ma vision du monde a changé. Je distingue maintenant deux frontières—celle où prend fin la simulation classique efficace et celle où commence le calcul quantique universel. Mes travaux cartographient ces frontières et l’étrange territoire qui les sépare. Une voie suit la structure compositionnelle commune aux réseaux de tenseurs booléens et à la logique de spins à l’état fondamental [4, 13, 14]. Une autre adapte des techniques quantiques à la mécanique stochastique au moyen d’opérateurs de Dirichlet qui sont des générateurs valides de dynamiques classiques et quantiques [18]. Les marches quantiques chirales étendent cette famille en attribuant des phases aux boucles, ce qui produit une dynamique asymétrique dans le temps [17]. Ce ne sont là que quelques exemples : mes modèles habitent souvent les domaines classique et quantique, avec des paramètres qui permettent d’interpoler entre les deux.

Suivre ces frontières m’a conduit des modèles physiques aux langages de réseaux de tenseurs, puis aux modèles statistiques et au comportement des grands systèmes. Au passage, mes travaux ont contribué aux réseaux complexes quantiques et à l’apprentissage automatique quantique.

Des parties de ce programme sont synthétisées dans la Perspective de Nature Quantum Machine Learning [10], ainsi que dans les articles de synthèse Tensor Networks in a Nutshell [11] et Complex Networks from Classical to Quantum [12].

Trois idées à retenir

Le territoire entre la simulabilité classique efficace et l’universalité du calcul quantique ne demeure que partiellement cartographié. [2, 7, 8, 9, 23, 51, 52]
Les états fondamentaux physiques peuvent encoder la logique et le calcul universel. [50, 1, 13, 14] La programmation des états fondamentaux utilise des gadgets classiques et quantiques. [50, 13, 15, 51, 56]
La logique de spins à l’état fondamental et les états de réseaux de tenseurs booléens partagent la même structure compositionnelle. [4]

Pour approfondir

Pour consulter la structure technique, le tableau de recherche et la bibliographie, voir mon Programme de recherche.

Pour les biographies, les photographies téléchargeables et les demandes des médias, consultez le Dossier média.

Sources et liens vers les articles

[1]Realizable Hamiltonians for universal adiabatic quantum computers J. Biamonte et P. Love Physical Review A 78, 012352 (2008). DOI : 10.1103/PhysRevA.78.012352.

[2]Universal variational quantum computation J. Biamonte Physical Review A 103, L030401 (2021), lettre. DOI : 10.1103/PhysRevA.103.L030401.

[3]Simulation of electronic structure Hamiltonians using quantum computers J. Whitfield, J. Biamonte et A. Aspuru-Guzik Molecular Physics 109, 735 (2011). DOI : 10.1080/00268976.2011.552441.

[4]Categorical tensor network states J. Biamonte, S. Clark et D. Jaksch AIP Advances 1, 042172 (2011). DOI : 10.1063/1.3672009.

[5]Tensor network contractions for #SAT J. Biamonte, J. Morton et J. Turner Journal of Statistical Physics 160, 1389–1404 (2015). DOI : 10.1007/s10955-015-1276-z.

[6]Tensor networks and graphical calculus for open quantum systems C. J. Wood, J. D. Biamonte et D. G. Cory Quantum Information & Computation 15, 759–811 (2015). DOI : 10.26421/QIC15.9-10-3.

[7]Reachability deficits in quantum approximate optimization V. Akshay, H. Philathong, M. Morales et J. Biamonte Physical Review Letters 124, 090504 (2020). DOI : 10.1103/PhysRevLett.124.090504.

[8]Parameter concentrations in quantum approximate optimization V. Akshay, D. Rabinovich, E. Campos et J. Biamonte Physical Review A 104, L010401 (2021), lettre. DOI : 10.1103/PhysRevA.104.L010401.

[9]Training saturation in layerwise quantum approximate optimisation E. Campos, D. Rabinovich, V. Akshay et J. Biamonte Physical Review A 104, L030401 (2021), lettre. DOI : 10.1103/PhysRevA.104.L030401.

[10]Quantum machine learning J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe et S. Lloyd Nature 549, 195–202 (2017). DOI : 10.1038/nature23474.

[11]Tensor Networks in a Nutshell J. Biamonte et V. Bergholm arXiv:1708.00006 (2017). DOI : 10.48550/arXiv.1708.00006.

[12]Complex networks from classical to quantum J. Biamonte, M. Faccin et M. De Domenico Communications Physics 2, 53 (2019). DOI : 10.1038/s42005-019-0152-6.

[13]Nonperturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins J. Biamonte Physical Review A 77, 052331 (2008). DOI : 10.1103/PhysRevA.77.052331.

[14]Ground-state spin logic J. Whitfield, M. Faccin et J. Biamonte Europhysics Letters 99, 57004 (2012). DOI : 10.1209/0295-5075/99/57004.

[15]Hamiltonian gadgets with reduced resource requirements Y. Cao, R. Babbush, J. Biamonte et S. Kais Physical Review A 91, 012315 (2015). DOI : 10.1103/PhysRevA.91.012315.

[16]Categorical quantum circuits V. Bergholm et J. Biamonte Journal of Physics A: Mathematical and Theoretical 44, 245304 (2011). DOI : 10.1088/1751-8113/44/24/245304.

[17]Quantum transport enhancement by time-reversal symmetry breaking Z. Zimboras, M. Faccin, Z. Kadar, J. Whitfield, B. Lanyon et J. Biamonte Scientific Reports 3, 2361 (2013). DOI : 10.1038/srep02361.

[18]Quantum Techniques in Stochastic Mechanics J. C. Baez et J. Biamonte World Scientific (2017). DOI : 10.1142/10623.

[19]Spectral entropies as information-theoretic tools for complex network comparison M. De Domenico et J. Biamonte Physical Review X 6, 041062 (2016). DOI : 10.1103/PhysRevX.6.041062.

[20]Abrupt transitions in variational quantum circuit training E. Campos, A. Nasrallah et J. Biamonte Physical Review A 103, 032607 (2021). DOI : 10.1103/PhysRevA.103.032607.

[21]On the Mathematical Structure of Quantum Models of Computation Based on Hamiltonian Minimisation J. Biamonte Doctorat supérieur en sciences, Institut de physique et de technologie de Moscou (2022). DOI : 10.48550/arXiv.2009.10088.

[22]On barren plateaus and cost function locality in variational quantum algorithms A. V. Uvarov et J. D. Biamonte Journal of Physics A: Mathematical and Theoretical 54, 245301 (2021). DOI : 10.1088/1751-8121/abfac7.

[23]On the universality of the quantum approximate optimization algorithm M. E. S. Morales, J. D. Biamonte et Z. Zimboras Quantum Information Processing 19, 291 (2020). DOI : 10.1007/s11128-020-02748-9.

[24]Algebraically contractible topological tensor network states S. J. Denny, J. D. Biamonte, D. Jaksch et S. R. Clark Journal of Physics A: Mathematical and Theoretical 45, 015309 (2012). DOI : 10.1088/1751-8113/45/1/015309.

[25]Tensor network methods for invariant theory J. Biamonte, V. Bergholm et M. Lanzagorta Journal of Physics A: Mathematical and Theoretical 46, 475301 (2013). DOI : 10.1088/1751-8113/46/47/475301.

[26]Degree distribution in quantum walks on complex networks M. Faccin, T. Johnson, J. Biamonte, S. Kais et P. Migdał Physical Review X 3, 041007 (2013). DOI : 10.1103/PhysRevX.3.041007.

[27]Community detection in quantum complex networks M. Faccin, P. Migdał, T. H. Johnson, V. Bergholm et J. D. Biamonte Physical Review X 4, 041012 (2014). DOI : 10.1103/PhysRevX.4.041012.

[28]Applications of negative dimensional tensors R. Penrose Combinatorial Mathematics and Its Applications, 221–244 (1971).

[29]A categorical semantics of quantum protocols S. Abramsky et B. Coecke Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science (2004). DOI : 10.48550/arXiv.quant-ph/0402130.

[30]A survey of graphical languages for monoidal categories P. Selinger New Structures for Physics, 289–355 (2011). DOI : 10.1007/978-3-642-12821-9_4.

[31]Picturing Quantum Processes B. Coecke et A. Kissinger Cambridge University Press (2017). DOI : 10.1017/9781316219317.

[32]Quantum annealing in the transverse Ising model T. Kadowaki et H. Nishimori Physical Review E 58, 5355–5363 (1998). DOI : 10.1103/PhysRevE.58.5355.

[33]Quantum computation by adiabatic evolution E. Farhi, J. Goldstone, S. Gutmann et M. Sipser arXiv:quant-ph/0001106 (2000). DOI : 10.48550/arXiv.quant-ph/0001106.

[34]Robustness of adiabatic quantum computation A. M. Childs, E. Farhi et J. Preskill Physical Review A 65, 012322 (2001). DOI : 10.1103/PhysRevA.65.012322.

[35]Density matrix formulation for quantum renormalization groups S. R. White Physical Review Letters 69, 2863–2866 (1992). DOI : 10.1103/PhysRevLett.69.2863.

[36]Finitely correlated states on quantum spin chains M. Fannes, B. Nachtergaele et R. F. Werner Communications in Mathematical Physics 144, 443–490 (1992). DOI : 10.1007/BF02099178.

[37]Renormalization algorithms for quantum many-body systems in two and higher dimensions F. Verstraete et J. I. Cirac arXiv:cond-mat/0407066 (2004). DOI : 10.48550/arXiv.cond-mat/0407066.

[38]Matrix product states and projected entangled pair states: Concepts, symmetries, theorems J. I. Cirac, D. Pérez-García, N. Schuch et F. Verstraete Reviews of Modern Physics 93, 045003 (2021). DOI : 10.1103/RevModPhys.93.045003.

[39]Emergence of scaling in random networks A.-L. Barabási et R. Albert Science 286, 509–512 (1999). DOI : 10.1126/science.286.5439.509.

[40]Bose–Einstein condensation in complex networks G. Bianconi et A.-L. Barabási Physical Review Letters 86, 5632–5635 (2001). DOI : 10.1103/PhysRevLett.86.5632.

[41]Entanglement percolation in quantum networks A. Acín, J. I. Cirac et M. Lewenstein Nature Physics 3, 256–259 (2007). DOI : 10.1038/nphys549.

[42]Quantum random networks S. Perseguers, M. Lewenstein, A. Acín et J. I. Cirac Nature Physics 6, 539–543 (2010). DOI : 10.1038/nphys1665.

[43]Quantum computation and decision trees E. Farhi et S. Gutmann Physical Review A 58, 915–928 (1998). DOI : 10.1103/PhysRevA.58.915.

[44]A simple proof that Toffoli and Hadamard are quantum universal D. Aharonov arXiv:quant-ph/0301040 (2003). DOI : 10.48550/arXiv.quant-ph/0301040.

[45]Some Models of Quantum Computation J. Biamonte Séminaire de l’Oxford Computing Laboratory, 1^er juin 2007. Archives de l’Oxford Advanced Seminar on Informatic Structures.

[46]Interacting quantum observables: Categorical algebra and diagrammatics B. Coecke et R. Duncan New Journal of Physics 13, 043016 (2011). DOI : 10.1088/1367-2630/13/4/043016.

[47]Chiral quantum walks D. Lu, J. D. Biamonte, J. Li, H. Li, T. H. Johnson, V. Bergholm, M. Faccin, Z. Zimborás, R. Laflamme, J. Baugh et S. Lloyd Physical Review A 93, 042302 (2016). DOI : 10.1103/PhysRevA.93.042302.

[48]On the computational complexity of Ising spin glass models F. Barahona Journal of Physics A: Mathematical and General 15, 3241–3253 (1982). DOI : 10.1088/0305-4470/15/10/028.

[49]Quantum Mechanical Computers R. P. Feynman Optics News 11(2), 11–20 (1985). DOI : 10.1364/ON.11.2.000011.

[50]Classical and Quantum Computation A. Yu. Kitaev, A. H. Shen et M. N. Vyalyi Graduate Studies in Mathematics 47, American Mathematical Society (2002). DOI : 10.1090/gsm/047.

[51]The Complexity of the Local Hamiltonian Problem J. Kempe, A. Kitaev et O. Regev SIAM Journal on Computing 35, 1070–1097 (2006). DOI : 10.1137/S0097539704445226.

[52]Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd et O. Regev SIAM Journal on Computing 37, 166–194 (2007). DOI : 10.1137/S0097539705447323.

[53]Effective Hamiltonian Models of the Cross-Resonance Gate E. Magesan et J. M. Gambetta Physical Review A 101, 052308 (2020). DOI : 10.1103/PhysRevA.101.052308.

[56]The complexity of quantum spin systems on a two-dimensional square lattice R. Oliveira et B. M. Terhal Quantum Information & Computation 8(10), 900–924 (2008). DOI : 10.48550/arXiv.quant-ph/0504050.