Foundations of classical and quantum verifiable computing

Lead Research Organisation: University of Warwick
Department Name: Computer Science

Abstract

Recent years have seen a vast surge in the volume and sensitivity of data that are being generated and collected, e.g., in genetic sequencing, distributed storage services, and graphs of social networks. The ubiquity and sheer size of modern data sets 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 key paradigm for meeting the challenges imposed by both of the aforementioned desiderata is that of verifiable computing. Here, the goal is to allow verification of computation that is performed by a third-party, 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, as well as to blockchain technology. Its primary objective is to develop a wide arsenal of tools that would open new possibilities for meeting the challenges imposed by big data and the need for decentralised peer-to-peer systems.

The proposed approach is inherently interdisciplinary, involving fundamental concepts in cryptography, complexity theory, randomised algorithms, and quantum information, as well as relying on techniques from coding theory, combinatorics, and abstract algebra.

Planned Impact

In recent years verifiable computing, the core of this research proposal, found a myriad of applications underlying the technical foundations of real-world technologies, including delegation of computation to the cloud, and decentralised systems such as blockchain technology and cryptocurrencies. Indeed, verifiable computing is a key ingredient in the future growth and evolution of blockchains and cloud computing, as advances in proof protocols can enhance the auditability and accountability of decentralised and outsourced computation, while obtaining key properties such as user privacy, post-quantum security, increased transaction throughput, off-chain computation, and transparent privacy.

The proposal outlines active engagement and close interaction with UK industry to obtain consistent feedback and disseminate ideas that would lead to an impact on UK society and industry. This would be facilitated via collaboration with the Warwick Manufacturing Group (WMG), which provides innovative solutions to industry, through research and knowledge transfer in engineering, manufacturing, and technology, as well as by Warwick's strong ties with the Alan Turing Institute, which would provide me with access to the top UK resources in data science, as well as a wide variety of opportunities to extend the impact of my work on UK industry. In addition, I propose to collaborate with the highly accomplished cryptocurrency company Zcash and the influential blockchain startup StarkWare Industries, towards establishing a practically-relevant theory.

The impact of developing the powerful methodologies of verifiable computing that are outlined in this proposal could go well beyond challenging centralised financial control (as decentralised systems such as Bitcoin, Zcash, and Ethereum have done in the last few years), and benefit UK society in many ways. More specifically, the purposed research aims to provide a foundation for real-world cloud computing and decentralised systems that can be used for public benefits such as preserving privacy, publicly-shared immutable ledgers for medical needs, decentralised validation of academic qualifications, and more.
 
Title Local algorithm analysis 
Description Developed a new methodology for construction and analysing the performance of local algorithms. 
Type Of Material Improvements to research infrastructure 
Year Produced 2020 
Provided To Others? Yes  
Impact The new methodology led to several breakthrough papers and new algorithms. 
 
Description Birkbeck 
Organisation Birkbeck, University of London
Country United Kingdom 
Sector Academic/University 
PI Contribution Conducted research in algorithms and coding theory.
Collaborator Contribution Participated in all stages of the research.
Impact Two papers, published at the best international conference in algorithms. Resolving several long-standing open problems in coding theory and algorithm, including a major, 16-years old open problem in local decoding algorithms.
Start Year 2020
 
Description CNRS 
Organisation Sorbonne University
Country France 
Sector Academic/University 
PI Contribution Led a research team in a collaboration culminating in paper that appeared in QIP 2021, the top international conference in quantum information.
Collaborator Contribution Participation in all stages of the research.
Impact Research collaboration aimed at exploring the potential of quantum machine learning. We identified a key bottleneck towards obtaining quantum speedups for machine learning and laid out a plan for overcoming it.
Start Year 2020
 
Description Georgetown 
Organisation Georgetown University
Country United States 
Sector Academic/University 
PI Contribution Participated in all steps of the research.
Collaborator Contribution Participated in all steps of the research.
Impact We obtained a new methodology for boosting knowledge. The work was accepted to STOC, the top conference on the foundations of computer science.
Start Year 2021
 
Description IBM T. J. Watson Research Center 
Organisation IBM
Department IBM T. J. Watson Research Center, Yorktown Heights
Country United States 
Sector Private 
PI Contribution Led a research team in a collaboration culminating in paper that appeared in QIP 2021, the top international conference in quantum information.
Collaborator Contribution Participation in all stages of the research.
Impact Research collaboration aimed at exploring the potential of quantum machine learning. We identified a key bottleneck towards obtaining quantum speedups for machine learning and laid out a plan for overcoming it.
Start Year 2020
 
Description Microsoft Quantum 
Organisation Microsoft Research
Country Global 
Sector Private 
PI Contribution Led a research team in a collaboration culminating in paper that appeared in QIP 2021, the top international conference in quantum information.
Collaborator Contribution Participation in all stages of the research
Impact Research collaboration aimed at exploring the potential of quantum machine learning. We identified a key bottleneck towards obtaining quantum speedups for machine learning and laid out a plan for overcoming it.
Start Year 2020
 
Description Oxford 
Organisation University of Oxford
Country United Kingdom 
Sector Academic/University 
PI Contribution Led a research team in a collaboration culminating in the paper that appeared in TQC 2021, one of the top international conference in quantum information.
Collaborator Contribution Participated in all steps of the research
Impact We devised a new method of delegating quantum computation in a scalable way, and we resolved a long-standing textbook open problem.
Start Year 2021
 
Description UC Berkeley 
Organisation University of California, Berkeley
Country United States 
Sector Academic/University 
PI Contribution We resolved the key open problem of showing hypercontractivity on high dimensional expanders.
Collaborator Contribution Participation in all stages of the research
Impact The work was accepted to STOC, the top conference in theoretical computer science.
Start Year 2021
 
Description Global talent campaign 
Form Of Engagement Activity A press release, press conference or response to a media enquiry/interview
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Interviewed for a campaign aimed at attracting global talent to the UK.
Year(s) Of Engagement Activity 2022
 
Description Quanta Magazine 
Form Of Engagement Activity A press release, press conference or response to a media enquiry/interview
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Interviewed for a highly popular international magazine on science.
Year(s) Of Engagement Activity 2022
 
Description STEM Challenges campaign 
Form Of Engagement Activity A magazine, newsletter or online publication
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Undergraduate students
Results and Impact A campaign aimed to attract young people to research in STEM subjects.
Year(s) Of Engagement Activity 2022