Research Interests

Research Interests


Hamiltonian Complexity

Hamiltonians are the fundamental object of study in quantum mechanics; they give the energy, time-evolution and all other physical properties of a quantum system. Hamiltonian complexity seeks to understand the properties Hamiltonians from an information theory and computer science perspective. We ask whether many-body systems have metastable states? Can their ground state energies be efficiently computed, even with a quantum computer? Can we say anything about the phase transitions of a Hamiltonian? We can even show there are systems which have ‘undecidable’ properties – there is no algorithmic way of determining them. Hamiltonian complexity also plays a central role in adiabatic quantum computing, particularly in determining what Hamiltonians are “complex enough” for universal computation.
Undecidability of the Spectral Gap
Toby Cubitt, David Perez-Garcia, Michael M. Wolf.
Nature 528, 207-211 (2015)
Size-Driven Quantum Phase Transitions
Johannes Bausch, Toby S. Cubitt, Angelo Lucia, David Perez-Garcia, Michael M. Wolf.
The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
Johannes Bausch, Toby Cubitt, Maris Ozols.


Entanglement is a fundamental feature of quantum physics, and is a useful ingredient in quantum technologies such as quantum cryptography and metrology. Due in part to these applications, and because entanglement is considered to be a distinguishing quality of non-classical behaviour, a rich mathematical theory of entanglement has been developed in recent years which attempts to understand how entanglement in a physical system can be detected and quantified. We investigate the mathematical structure of entangled states and develop techniques to characterise their non-classical properties.
Combinatorial entanglement
J. Lockhart, S. Severini.
Entanglement properties of quantum grid states
J. Lockhart, O Gühne, S. Severini.

Discrete mathematical structures in quantum theory

Finite relational structures and homomorphisms between them are pervasive notions in logic, computer science and combinatorics. Many relevant questions in finite model theory, constraint satisfaction and graph theory can be phrased in terms of (existence or number of) homomorphisms between finite structures. Developing a quantum theory about these fundamental structures can serve to delineate the scope of quantum advantage and understand the use of quantum resources in an abstract setting. We follow the tradition of using category theory to combine concepts across disciplines that are not yet related, with the hope of provide sensible definitions at a formal level and then use them to single out fundamental aspects along with potential new applications.
For every quantum walk there is a (classical) lifted Markov chain with the same mixing time
Danial Dervovic.
Quantum and non-signalling graph isomorphisms
Albert Atserias, Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, Antonios Varvitsiotis.
The Quantum Monad on Relational Structures
Samson Abramsky, Rui Soares Barbosa, Nadish de Silva, Octavio Zapata.

Quantum Shannon Theory

The advent of quantum theory offers new and interesting ways of transmitting, extracting and utilising information. Quantum Shannon theory aims to understand both the theoretical limits of these processes, such as what is the maximum rate of transmission using a quantum channel? How efficiently can quantum information be compressed without error? How much information can we learn from a single quantum measurement? Broadly speaking, it is a generalisation of classical information theory.
Bounds on entanglement assisted source-channel coding via the Lovasz theta number and its variants
Toby Cubitt, Laura Mancinska, David Roberson, Simone Severini, Dan Stahlke, Andreas Winter.
On zero-error communication via quantum channels in the presence of noiseless feedback
Runyao Duan, Simone Severini, Andreas Winter.
IEEE Trans. Inf. Theory, vol. 62, no. 9, pp. 5260-5277 (2016)
Superactivation of the Asymptotic Zero-Error Classical Capacity of a Quantum Channel
Toby S. Cubitt, Jianxin Chen, Aram W. Harrow.
IEEE Trans. Inf. Th., vol. 57, no. 12, pp. 8114-8126, (2011)
Quantum Conditional Mutual Information, Reconstructed States, and State Redistribution
Fernando G.S.L. Brandao, Aram W. Harrow, Jonathan Oppenheim, Sergii Strelchuk.
Phys. Rev. Lett. 115, 050501 (2015)

Review Articles in Quantum Computation and Machine Learning

Readers who seek a detailed introduction can refer to our recent review articles:
Quantum machine learning: a classical perspective
Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, Leonard Wossnig.
Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers
Alejandro Perdomo-Ortiz, Marcello Benedetti, John Realpe-Gómez, Rupak Biswas.
Quantum linear systems algorithms: a primer
Danial Dervovic, Mark Herbster, Peter Mountney, Simone Severini, Naïri Usher, Leonard Wossnig.

For any questions or inquiries related to our research in this area, please contact Andrea Rocchetto or Leonard Wossnig.
For machine learning activities at UCL, see the following links:

Learning Theory

Learning theory aims to place the problem of learning from data on a solid mathematical foundation. Typical questions that one asks in this setting are: how much data is required to learn a given function? What computational resources are required to perform a learning task? Through the study of formal models of learning we seek to understand whether quantum resources can be exploited to perform a learning task more efficiently. Known results indicate that depending on the type of learning model considered, it is possible to have a better generalisation error (i.e. we can learn with fewer examples) or we can learn functions that would otherwise be hard for classical learners. The framework of learning theory can also be applied to the study of quantum systems. In this case, our research focuses on investigating the relationship between quantum states that can be efficiently learned and the class of circuits that can be efficiently classically simulated.
Learning DNFs under product distributions via μ-biased quantum Fourier sampling
Varun Kanade, Andrea Rocchetto, Simone Severini.
Experimental learning of quantum states
Andrea Rocchetto, Scott Aaronson, Simone Severini, Gonzalo Carvacho, Davide Poderini, Iris Agresti, Marco Bentivegna, Fabio Sciarrino.
Stabiliser states are efficiently PAC-learnable
Andrea Rocchetto.

Quantum Linear Algebra and Machine Learning

In quantum linear algebra we seek out algorithms that allow us to speed up fundamental tasks like solving systems of linear equations. These are important since many machine learning algorithms rely on such tasks as subroutines. Thus, coming up with genuine ways to improve classical linear algebra methods or developing quantum methods for these tasks is an important part of QML. The practicality of these algorithms remains an open question, due to the underlying assumptions.
A quantum linear system algorithm for dense matrices
Leonard Wossnig, Zhikuan Zhao, Anupam Prakash.
Quantum gradient descent and Newton’s method for constrained polynomial optimization
Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione, Seth Lloyd.

Quantum Sampling

Recently, there has been increasing interest in the potential that quantum computing technologies have for speeding up sampling. This goes beyond the original focus of the quantum annealing computational paradigm, which was solving discrete optimization problems. The focus of our research is the development of hybrid quantum-classical algorithms capable of enhancing and tackling large industrial-scale machine learning data sets.
A generative modeling approach for benchmarking and training shallow quantum circuits
Marcello Benedetti, Delfina Garcia-Pintos, Yunseong Nam, Alejandro Perdomo-Ortiz.
Quantum-assisted Helmholtz machines: A quantum-classical deep learning framework for industrial datasets in near-term devices
Marcello Benedetti, John Realpe-Gómez, Alejandro Perdomo-Ortiz.
Quantum-assisted learning of graphical models with arbitrary pairwise
Marcello Benedetti, John Realpe-Gómez, Rupak Biswas, Alejandro Perdomo-Ortiz.
Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
Marcello Benedetti, John Realpe-Gómez, Rupak Biswas, Alejandro Perdomo-Ortiz.
Phys. Rev. A 94, 022308 (2016)

Learning for Quantum Hardware

Classical machine learning techniques can be used to help the physical design of quantum hardware for quantum information processing. Indeed, quantum physics is notoriously difficult to understand using our classical intuition, and this limits our ability to engineer physical quantum devices. A possible application is the design of Hamiltonian computers, where machine learning tools are used to reduce the resource overhead for obtaining quantum gates with minimal control. This work is partially conducted by Sougato Bose‘s group.
Learning hard quantum distributions with variational autoencoders
Andrea Rocchetto, Edward Grant, Sergii Strelchuk, Giuseppe Carleo, Simone Severini.
Quantum gate learning in engineered qubit networks: Toffoli gate with always-on interactions
Leonardo Banchi, Nicola Pancotti, Sougato Bose.
npj Quantum Information 2: 16019 (2016)
Supervised quantum gate “teaching” for quantum hardware design
Leonardo Banchi, Nicola Pancotti, Sougato Bose.


Contextuality describes systems whose behaviour precludes any explanation in terms of a classical notion of reality wherein all properties can be ascribed values simultaneously. The primary examples of such systems arise within quantum mechanics. Contextuality subsumes nonlocality as a special case. It is significant not just for the theoretical foundations of quantum theory but also as a potential resource for achieving advantage in a variety of information-theoretic tasks, e.g. computation. Here, we study contextuality both abstractly, by considering high-level, theory-independent mathematical frameworks, and concretely, as resources in particular tasks. This work lies at the intersection of many fields including mathematical logic, quantum physics, programming languages, and quantum computation.
Logical paradoxes in quantum computation
Nadish de Silva.
Minimum quantum resources for strong non-locality
Samson Abramsky, Rui Soares Barbosa, Giovanni Carù, Nadish de Silva, Kohei Kishida, Shane Mansfield.

Spectral Graph Theory

Spectral graph theory aims to study structural properties of graphs in relationship to algebraic properties of matrices associated to those graphs. Such algebraic properties are known to give information about diameter, independence number, and even planarity. We investigated connections between eigenspaces and graph homomorphisms, an area with almost no previous results. We were able to use the well-behaved algebraic properties of strongly regular graphs (SRGs) to show that any homomorphism between a pair of cospectral SRGs must be a coloring. This settled a conjecture of Cameron and Kazanidis.
Homomorphisms of Strongly Regular Graphs
David E. Roberson
Note on von Neumann and Rényi entropies of a Graph
Michael Dairyko, Leslie Hogben, Jephian C.-H. Lin, Joshua Lockhart, David Roberson, Simone Severini, Michael Young.

Quantum and Classical Clocks: Fundamental Differences and Limitations

Throughout millennia, humans have been developing more and more accurate clocks, with every development aiding new technologies. Today, the most advanced and accurate clocks are atomic clocks and the next generation of clocks promise more advanced telecommunications and GPS. However, what are the fundamental limitations to this progress? Will we hit a fundamental limit which is unsurpassable? Recently we have been examining these questions with tools from quantum information theory. More specifically, uncovering the fundamental limitations of quantum and classical clocks as a function of available dimension and energy and understanding the limitations imposed by thermodynamics.
Autonomous quantum machines and finite sized clocks
Mischa P. Woods, Ralph Silva, Jonathan Oppenheim
Autonomous quantum clocks: does thermodynamics limit our ability to measure time?
Paul Erker, Mark T. Mitchison, Ralph Silva, Mischa P. Woods, Nicolas Brunner, Marcus Huber.
Phys. Rev. X 7, 031022 (2017)

Theory of quantum computation and simulation

Theoretical computer science is devoted to the study of computation as a mathematical concept. In particular, computational complexity theory attempts to understand the tasks that can be performed efficiently by a computing device with access to a particular resource, e.g., a certain amount of compute time, a memory of a particular size, the ability to generate randomness. A computer with the ability to prepare and manipulate quantum states is of course in the scope of this field, and so these classical techniques can be brought to bear on the analysis of such a device. Members of the group have conducted research in quantum interactive proof systems, quantum simulation, and randomness generation. In addition, computer science techniques can be applied to physics, for instance in the study of thermodynamics.
Quantum State Isomorphism
Joshua Lockhart, Carlos E. González Guillén
Universal Quantum Hamiltonians
Toby Cubitt, Ashley Montanaro, Stephen Piddock
Local random quantum circuits are approximate polynomial-designs
Fernando G. S. L. Brandao, Aram W. Harrow, Michal Horodecki.
Commun. Math. Phys. (2016) vol. 346, no. 2, pp. 397-434
The second laws of quantum thermodynamics
Fernando G.S.L. Brandao, Michał Horodecki, Nelly Huei Ying Ng, Jonathan Oppenheim, Stephanie Wehner.
PNAS 112, 3275 (2015)

Noisy Quantum Systems

Noise acts on physical systems and thus corrupts the information and computation to be performed. In the case of quantum systems, the sensitivity to noise is a major obstacle towards the realisation of a scalable universal quantum computer. Fault tolerance requires for large error correction codes to be constructed, which in turn require an enormous number of physical qubits to deter and track errors throughout every step of the computation. Such a device is currently believed to be at least a decade away. However, given the current existence of small noisy quantum devices, an immediate interesting question is to find useful computational tasks, whereby utilising these noisy quantum systems outperform their classical counterparts. For instance, these could be used for simulating complex quantum systems or to further our understanding of how noise acting on physical systems impacts on the computation to be performed.
Noise in One-Dimensional Measurement-Based Quantum Computing
Naïri Usher, Dan E. Browne