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.