Verifying BQP Computations on Noisy Devices with Minimal Overhead

Abstract

With the development of delegated quantum computation, clients will want to ensure confidentiality of their data and algorithms and the integrity of their computations. While protocols for blind and verifiable quantum computation exist, they suffer from high overheads and from oversensitivity: when running on noisy devices, imperfections trigger the same detection mechanisms as malicious attacks, resulting in perpetually aborted computations. We introduce the first blind and verifiable protocol for delegating bounded-error quantum polynomial (BQP) computations to a powerful server, with repetition as the only overhead. It is composable and statistically secure with exponentially low bounds and can tolerate a constant amount of global noise.