University of Warwick
Computer Science

Many common situations demand quick decisions about an extended object or large amount of information, of which we can only observe or analyse a small portion. We announce that a pot of rice is sufficiently cooked by tasting a few grains sampled from its depth and breadth. Similarly, we conclude a bag of thousands of coins contains only 10p coins after pulling out just a few dozens of them to check.

Mathematical abstractions of questions of this nature are called property testing problems, and the protocols for solving them property testing algorithms. Both examples above exhibit two key features: tolerance to a small margin of error -- we don't mind small portions of the rice being overcooked or undercooked; and the prized trait of locality -- by analysing miniscule fractions of the whole input object, we can quickly make a decision within the limits of tolerance.

The states of systems of microscopic particles have complex descriptions, growing exponentially with the number of particles: every additional particle can double this complexity, and the number of variables required to describe states of a tiny 127-'qubit' quantum computer, the largest to date, is 43-digits long in decimal form! Such quantum states possess strange properties like entanglement, a special kind of correlation not seen in non-quantum objects.

My research programme will characterise novel property testing algorithms that run on quantum computers, taking computational advantage of exotic features of quantum mechanics. I will focus on questions about probability distributions and quantum states, building on my recent breakthrough in constructing the first quantum algorithm for estimating the entropy of quantum states with a resource cost smaller than the states' dimension (accepted to QIP-2022, the premier conference on quantum computing).

I will (1) develop fast quantum algorithms for problems including testing whether a state is highly entangled or far from being so, delivering practical impact in the ongoing race towards large-scale quantum computers; and (2) simultaneously counterbalance this optimism by proving 'lower bounds' on the theoretical limits of the power of quantum computing for property testing, contributing to advances in applied maths and computational complexity theory.