Welcome to the terra incognita, the grand quantum–classical divide

Will you join our global quest to chart the cliffs of the great unknown? Humanity needs to complete the map between our classical and quantum theories of computation. In this territory, a seemingly small change in a physical model might entirely transform what it is capable of. What computational models lie between these cliffs—and what minimal structure makes them programmable? The quantum industry needs to know.

When I entered the field, the computational landscape was often presented as having one clean boundary: efficiently simulated classical systems on one side and universal quantum computers on the other. [Fig. 1] What’s the structural difference?

An expectation map with Ising-Hamiltonian ground states in a green Classical region and ZX-Hamiltonian ground states in a Caltech orange Quantum region, separated by one gently curving turquoise dashed boundary.
Figure 1. My worldview exposed the problem I wanted to understand. I had developed ground-state spin logic—a logic of ground-state spans that embeds switching circuits into Ising Hamiltonians—on one side [13, 14]. On the other, I had proven that the ZX Hamiltonian, which differs from spin logic by the addition of an XX term, enables universal quantum computation [1]. I turned to the mathematics of tensor networks to understand the difference between these two structures. I took these ideas to Oxford and wrote a thesis that extended ground-state spin logic from a span to a sum over basis vectors, recovering the same compositional structure as spin logic in the form of Boolean tensor networks [4, 21]. General quantum states could be reached in that setting by including scalars with this structure.

But classical intractability, by all accounts, is different from quantum universality. It appears that many quantum systems cannot be efficiently simulated classically, yet they are not programmable as universal quantum computers.

The difference may be programmability: the ability to compose interactions, constraints, and transformations so that a physical system performs a chosen computation. Ground-state gadgets provide one way to program physical models [13]; tensor networks turn the same underlying logic into a compositional language [4].

These and other results caused me to see two boundaries: where efficient classical simulation ends, and where universal quantum computation begins. Between them lies a broad terra incognita—a quantum–classical divide of systems whose computational power remains only partly understood. [Fig. 2] This is a great uncharted terrain of human knowledge.

A conceptual Terra Incognita map across Classical, Quantum–Classical, and Quantum regions. Threads connect ground-state spin logic with Boolean non-linearity; tensor-network contractions for #SAT with Boolean non-linearity; spectral entropies with chiral quantum walks; the two QAOA results; and universal QAOA control with tunable circuit sampling. One wire ends freely to show that the connections are conceptual and incomplete.
Figure 2. The image is conceptual, and so are the connections. My worldview has changed. I now see two distinct edges—where efficient classical simulation ends and where universal quantum computation begins. My work charts these edges and the strange territory between them. One path follows the shared compositional structure of Boolean tensor networks and ground-state spin logic [4, 13, 14]. Another adapts quantum techniques to stochastic mechanics through Dirichlet operators that are valid generators of both classical and quantum dynamics [18]. Chiral quantum walks extend this family by assigning phases to loops, producing time-asymmetric dynamics [17]. These are only a few examples: my models often inhabit both classical and quantum realms, with parameters that interpolate between them.

Following these boundaries led me from physical models to tensor-network languages, then to statistical models and large-system behavior. Along the way, my work contributed to quantum complex networks and quantum machine learning.

Parts of this program are synthesized in the Nature Perspective Quantum Machine Learning [10], and in the reviews Tensor Networks in a Nutshell [11] and Complex Networks from Classical to Quantum [12].

Three ideas to take away

  1. The territory between efficient classical simulability and quantum computational universality remains only partly mapped. [2, 7, 8, 9, 23, 51, 52]
  2. Physical ground states can encode logic and universal computation. [50, 1, 13, 14] Programming ground states uses classical and quantum gadgets. [50, 13, 15, 51, 56]
  3. Ground-state spin logic and Boolean tensor-network states share the same compositional structure. [4]

Dig deeper

For the technical structure, research table, and bibliography, see my Research Program.

For biographies, downloadable photographs, and media inquiries, see the Media Kit.

Sources and paper links

Parts of this work are synthesized in the Nature Perspective Quantum Machine Learning [10], and in the reviews Tensor Networks in a Nutshell [11] and Complex Networks from Classical to Quantum [12].

[1]Realizable Hamiltonians for universal adiabatic quantum computers J. Biamonte and 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). APS Editors’ Suggestion; Letter. DOI: 10.1103/PhysRevA.103.L030401.

[3]Simulation of electronic structure Hamiltonians using quantum computers J. Whitfield, J. Biamonte, and A. Aspuru-Guzik Molecular Physics 109, 735 (2011). DOI: 10.1080/00268976.2011.552441. — A Molecular Physics Young Author Prize was awarded to James D. Whitfield for this paper in the 2011 prize cycle; the award was announced in 2012.

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

[5]Tensor network contractions for #SAT J. Biamonte, J. Morton, and 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, and 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, and 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, and J. Biamonte Physical Review A 104, L010401 (2021), Letter. DOI: 10.1103/PhysRevA.104.L010401.

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

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

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

[12]Complex networks from classical to quantum J. Biamonte, M. Faccin, and 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, and 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, and S. Kais Physical Review A 91, 012315 (2015). DOI: 10.1103/PhysRevA.91.012315.

[16]Categorical quantum circuits V. Bergholm and 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, and J. Biamonte Scientific Reports 3, 2361 (2013). DOI: 10.1038/srep02361.

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

[19]Spectral entropies as information-theoretic tools for complex network comparison M. De Domenico and 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, and 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 Doctor of Science higher doctorate, Moscow Institute of Physics and Technology (2022). DOI: 10.48550/arXiv.2009.10088.

[22]On barren plateaus and cost function locality in variational quantum algorithms A. V. Uvarov and 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, and 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, and 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, and 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, and 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, and 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 and 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 and A. Kissinger Cambridge University Press (2017). DOI: 10.1017/9781316219317.

[32]Quantum annealing in the transverse Ising model T. Kadowaki and 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, and 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, and 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, and 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 and 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, and 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 and R. Albert Science 286, 509–512 (1999). DOI: 10.1126/science.286.5439.509.

[40]Bose–Einstein condensation in complex networks G. Bianconi and 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, and M. Lewenstein Nature Physics 3, 256–259 (2007). DOI: 10.1038/nphys549.

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

[43]Quantum computation and decision trees E. Farhi and 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 Oxford Computing Laboratory seminar, 1 June 2007. Oxford Advanced Seminar on Informatic Structures archive.

[46]Interacting quantum observables: Categorical algebra and diagrammatics B. Coecke and 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, and 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, and 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, and 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, and 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 and 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 and B. M. Terhal Quantum Information & Computation 8(10), 900–924 (2008). DOI: 10.48550/arXiv.quant-ph/0504050.