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.
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.
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.
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.
Review Articles in Quantum Computation and Machine Learning
Readers who seek a detailed introduction can refer to our recent review articles:
- UCL Gatsby Computational Neuroscience Unit
- Centre for for Computational Statistics and Machine Learning
- UCL Intelligent Systems group
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.
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.
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.
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.
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.
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.
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.
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.
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.