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.