Foundations of Classical and Quantum Verifiable Computing

Recent years have seen a vast surge in the volume and sensitivity of data being generated and collected, e.g., in genetic sequencing, distributed storage services, and graphs of social networks. The ubiquity and sheer size of modern datasets raise an urgent need to develop new techniques and methodologies for scalable computation.

At the same time, the rise of blockchain technology, which underlies deployed distributed systems such as Bitcoin and Ethereum, provides ample motivation for developing decentralised protocols that could go beyond challenging centralised financial control and profoundly impact society by providing a foundation for real-world distributed systems that can be used for public benefit.

A critical paradigm for meeting the challenges imposed by both of the desiderata above is that of verifiable computing. Here, the goal is to allow verification of computation performed by a strong third party (e.g., the cloud or a quantum computer) in a scalable, secure, and privacy-preserving way. Moreover, with the advent of quantum computing on the horizon, it is imperative that the verification would also be post-quantum secure.

This proposal is focused on pushing the boundaries of classical and quantum verifiable computing and its real-world applications to delegation of computation to the cloud and blockchain technology. The proposed approach is inherently interdisciplinary, traversing computer science, mathematics, and quantum physics. The project involves strong national and international collaboration both in academia and industry.

Its primary objective is to resolve long-standing open problems in the field, make an industrial impact by revolutionising how we delegate computation, and significantly increase the UK's capability of meeting the societal needs of preserving privacy and decentralising society in an upcoming quantum world.