Quelle structure minimale permet le calcul quantique ?

Je construis et j’analyse des modèles de calcul situés entre la simulation classique efficace et le calcul quantique universel. J’examine comment les interactions, les règles de composition et la structure statistique des familles d’instances déterminent ce que ces modèles peuvent calculer.

Concepts et cadres sélectionnés. Les concepts et cadres présentés dans mes publications individuelles et collaboratives comprennent la logique de spins à l’état fondamental (13, 14) ; les états catégoriques de réseaux de tenseurs, notamment une preuve constructive que la famille de tenseurs AND/COPY/scalaire est expressivement complète : des états arbitraires de n qubits peuvent être construits directement dans le langage des réseaux de tenseurs, sans recourir à un ensemble universel de portes quantiques comme intermédiaire (4) ; les marches quantiques chirales en temps continu obtenues par brisure de la symétrie d’inversion du temps (17) ; les mesures d’entropie spectrale pour comparer les réseaux complexes (19) ; les déficits d’accessibilité dans le QAOA (7) ; et la saturation de l’entraînement dans le QAOA couche par couche (9).

Résultats sélectionnés. Les publications citées établissent la QMA-complétude de deux familles restreintes d’hamiltoniens 2-locaux contenant des termes X/Z 1-locaux et des couplages XX/ZZ ou ZX/XZ 2-locaux (1) ; des constructions de gadgets perturbatifs utilisées pour établir des modèles restreints XX/ZZ et ZX/XZ et pour simuler des couplages YY effectifs au moyen d’interactions de type XX/ZZ (1, 15) ; des analyses de complexité en portes et de ressources pour la simulation quantique d’hamiltoniens de structure électronique (3) ; des représentations par réseaux de tenseurs d’invariants polynomiaux sous transformations unitaires locales, les états de produits matriciels constituant un exemple principal (25) ; la contraction en temps polynomial de problèmes de comptage dont les expressions en réseaux de tenseurs contiennent O(log n) tenseurs COPY avec un fan-out borné polynomialement (5) ; un calcul graphique reliant les représentations de Liouville, de Choi, par matrice de processus, de Kraus et système–environnement des applications complètement positives (6) ; des conditions précises d’universalité pour une classe de constructions QAOA unidimensionnelles, avec des extensions à des hamiltoniens de coût spécifiés sur des graphes et des hypergraphes (23) ; et deux constructions de fonctions objectif établissant l’universalité computationnelle du calcul quantique variationnel (2).

J’ai également cosigné des études expérimentales sur la chimie quantique photonique en 2010 (54), les marches quantiques chirales en 2016 (47) et l’apprentissage adversarial quantique avec des qubits supraconducteurs en 2022 (55). Mes publications comprennent aussi des travaux sur les réseaux complexes quantiques (19, 12) et l’apprentissage automatique quantique (10, 55).

Le Programme de recherche est organisé selon Modèles de calcul → Langages de programmation → Propriétés émergentes. Le tableau ci-dessous suit cette progression de gauche à droite.

Modèles de calcul	Langage de programmation	Propriétés émergentes
Les hamiltoniens d’Ising réalisent des espaces engendrés par des prédicats booléens en tant qu’espaces fondamentaux exacts [13,14,21], tandis que la minimisation de l’énergie induit un treillis distributif d’espaces de solutions physiquement synthétisables.	L’algèbre de la minimisation incorpore des portes logiques composables et synthétise exactement des espaces fondamentaux prescrits de chaînes de bits, fournissant une solution algébrique au problème inverse de l’état fondamental d’Ising [13,14,21]	Les statistiques de modèles révèlent des déficits d’accessibilité du QAOA dans les problèmes SAT aléatoires ordonnés par densité. Elles montrent que l’échec de l’entraînement peut provenir de l’espace des états accessibles plutôt que de l’optimiseur et anticipent le déplacement du domaine vers des explications structurelles de l’entraînabilité variationnelle, notamment des prédictions analytiques de la concentration des paramètres et de la saturation de l’entraînement [7-9]
Les modèles d’états fondamentaux à hamiltoniens ZX sont QMA-complets et universels pour les modèles énergétiques du calcul quantique [1]. Ce résultat a fait de la complexité hamiltonienne un outil prédictif pour la conception matérielle, en déterminant les coupleurs à deux corps non commutatifs et à signe variable nécessaires pour passer du recuit d’Ising transverse au calcul quantique universel par état fondamental [1]. Dix-huit ans après sa publication, l’article a été présenté comme un Citation Classic en 2026 [1].	Les états d’histoire de Feynman–Kitaev à amplitudes réelles encodent le calcul quantique universel [1] Des gadgets perturbatifs permettent l’interopérabilité ZZ/XX ↔ ZX [1] ; un gadget du quatrième ordre synthétise YY à partir de ZZ/XX après annulation complète du troisième ordre [15] ; ensemble, ces constructions donnent accès à toute chaîne de Pauli réelle [1,15]	L’accès à toute chaîne de Pauli réelle intègre les hamiltoniens de structure électronique au cadre universel de basse énergie [1,15] Par ailleurs, les estimations de ressources dans le modèle à portes ont établi des bornes explicites de complexité pour les calculs d’énergie moléculaire [3]
Un calcul AND/COPY/scalaire a été introduit afin de factoriser constructivement des états quantiques arbitraires en réseaux de tenseurs définis algébriquement [4]. Prolongeant la logique des états fondamentaux d’Ising [13], ce travail a intégré les méthodes des réseaux de tenseurs au modèle catégorique de la théorie quantique au moyen d’un langage compositionnel qui englobe les circuits quantiques [4,16]. La forme normale algébrique BCJ fournit une preuve constructive que les tenseurs AND/COPY/scalaire forment un ensemble générateur universel pour les états quantiques arbitraires.	Une factorisation algébrique directe d’états quantiques arbitraires en réseaux de tenseurs a été introduite : la construction BCJ démontre que l’ensemble générateur AND/COPY/scalaire est expressivement complet [4] Les réécritures graphiques rendent interopérables les représentations canoniques des systèmes quantiques ouverts, permettant de passer systématiquement d’une description mathématique à l’autre [6]	L’algèbre tensorielle, et non la seule géométrie, détermine la contractibilité : les réécritures de bialgèbre et de Hopf rendent exactement contractables les réseaux de tenseurs de théories de jauge sur réseau pour les groupes abéliens finis, tandis que le coût de contraction de #SAT n’est exponentiel qu’en fonction du nombre de tenseurs COPY [5,24] Les diagrammes tensoriels fermés engendrent des invariants complets sous transformations unitaires locales pour les états de produits de matrices, notamment les entropies de Rényi [25]
Un cadre opératoriel commun pour les réseaux complexes quantiques a été construit, reliant le transport en liaison forte, la mécanique stochastique et la cinétique d’action de masse, et clarifiant leurs mathématiques communes ainsi que leurs différences physiques [12,18] ; les distributions quantiques des degrés et la détection de communautés transforment la structure du réseau en observables dépendant de l’état [26,27]	La brisure de la symétrie d’inversion du temps transforme les phases de boucle en langage de contrôle du transport directionnel, définissant ainsi les marches quantiques chirales [17]. Le formalisme de création-annihilation et des états cohérents fournit de nouvelles démonstrations de théorèmes majeurs sur les réseaux de réactions et identifie les formes de Dirichlet comme une frontière stochastique-quantique [18]	L’entropie spectrale transforme la diffusion laplacienne en outils de théorie de l’information pour comparer, regrouper et inférer les réseaux [19] ; ce programme de cinq articles est aujourd’hui reconnu comme ayant contribué à établir les réseaux complexes quantiques en tant que domaine cohérent [12,17,19,26,27]
Il a été démontré que l’échantillonnage par circuits quantiques paramétrés est computationnellement universel, faisant passer les architectures de circuits variationnels du statut d’ansätze heuristiques à celui de modèle formel du calcul quantique. L’article a été retenu dans l’Editors’ Selection [2]	Les impulsions alternées du QAOA forment elles-mêmes un langage universel de contrôle quantique, capable d’approximer des opérateurs unitaires arbitraires sous des conditions explicites d’interaction et de symétrie [23] Une loi d’aire combinatoire pour les circuits quantiques fait de la connectivité matérielle et de la profondeur des circuits des limites structurelles de l’expressivité à faible profondeur [2]	Les bornes sur la variance du gradient identifient la largeur du cône causal des termes de Pauli comme un contrôle structurel des plateaux stériles, reliant l’entraînabilité à la localité de la fonction de coût et à la structure de l’ansatz [22] L’apprentissage de portes à k corps présente un seuil abrupt en profondeur : une seule couche supplémentaire peut faire passer le circuit d’un régime impossible à apprendre à un apprentissage parfait [20]

Certaines 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].

Références

[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.

[54]Towards quantum chemistry on a quantum computer B. P. Lanyon, J. D. Whitfield, G. G. Gillett, M. E. Goggin, M. P. Almeida, I. Kassal, J. D. Biamonte, M. Mohseni, B. J. Powell, M. Barbieri, A. Aspuru-Guzik et A. G. White Nature Chemistry 2, 106–111 (2010). DOI : 10.1038/nchem.483.

[55]Experimental quantum adversarial learning with programmable superconducting qubits W. Ren, W. Li, S. Xu, K. Wang, W. Jiang, F. Jin, X. Zhu, J. Chen, Z. Song, P. Zhang, H. Dong, X. Zhang, J. Deng, Y. Gao, C. Zhang, Y. Wu, B. Zhang, Q. Guo, H. Li, Z. Wang, J. Biamonte, C. Song, D.-L. Deng et H. Wang Nature Computational Science 2, 711–717 (2022). DOI : 10.1038/s43588-022-00351-9.