Quantum Proofs for Skeptical Verifiers

A verifier-prover — where a “prover” suggests an answer to a question, which is then checked by a “verifier” — is a powerful analytical tool in computer science. As an example, understanding the number of transactions required to answer a computational question in a prover-verifier setting offers insights into the difficulty of that computational problem. Problems that can be solved with few transactions between a quantum prover and classical verifier is said to have complexity “QMA”. Unfortunately, even a modest modification, where the quantum prover is untrusted (its purported answers may sometimes be in error), is not yet fully understood. Understanding the implications of an untrusted quantum prover (e.g. How might one handle QMA problems despite an untrusted quantum prover?) is particularly relevant given the rapid development of noisy intermediate-scale quantum (“NISQ”) machines. This project seeks to develop proof systems robust against an untrusted quantum prover.

Faculty Supervisor:

Anne Broadbent

Student:

Arthur Mehta

Partner:

AgnostiQ Labs

Discipline:

Computer science

Sector:

Professional, scientific and technical services

University:

University of Ottawa