Alexandru Gheorghiu: Proofs of Quantumness


Chalmers University


Vinod Vaikuntanathan
Abstract: Recent demonstrations of quantum computational advantage by groups at Google and USTC have highlighted the impressive capabilities of near-term quantum computers. However, these experiments come at the cost of requiring exponential time to check the results. Is it possible to certify quantum advantage efficiently (i.e. in polynomial time)? The answer is yes, using protocols known as proofs of quantumness. In this talk, I will survey this area, discussing the various ways in which proofs of quantumness can be constructed, the types of assumptions they rely on and the resources required to implement them. Time permitting, I'll also discuss a number of interesting open questions.