Testing quantum systems in the high-complexity regime.

From carefully crafted quantum algorithms to information-theoretic security in cryptography, a quantum computer can achieve impressive feats with no classical analogue. Can their correct realization be verified? When the power of the device greatly surpasses that of the user, computationally as well as cryptographically, what means of control remain available to the user?

Recent lines of work in quantum cryptography and complexity develop approaches to this question based on the notion of an interactive proof. Generally speaking an interactive proof models any interaction whereby a powerful device aims to convince a restricted user of the validity of an agree-upon statement -- such as that the machine generates perfect random numbers or executes a specific quantum algorithm.

Two models have emerged in which large-scale verification has been shown possible: either by placing reasonable computational assumptions on the quantum device, or by requiring that it consists of isolated components across which Bell tests can be performed.

In the talk I will discuss recent results on the verification power of interactive proof systems between a quantum device and a classical user, focusing on the certification of quantum randomness from a single device (arXiv:1804.00640) and the verification of arbitrarily complex computations using two devices (arXiv:2001.04383).