Verifying BQP Computations on Noisy Devices with Minimal Overhead

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.

Popular Summary

Recent advances in quantum computing suggest that most machines will be accessed remotely and computations will be delegated to service providers. In such a setting, the confidentiality of the data and the code, as well as the integrity of the computation cannot be guaranteed a priori. Schemes for blind and verified computations have been proposed in the past, but are far from being practical as they induce large overheads. We report the first verification scheme where each round can tolerate a constant amount of noise without compromising security.

In previous schemes, the overheads are due to fault-tolerant encoding used for boosting their attack detection capability. For limited resource devices, requiring high security would be impractical as no more qubits would be left for the computation itself. We removed this burden for all BQP computations by devising a new amplification scheme for attack detection. It is based on the repetition of several rounds of computation interleaved by testing rounds aimed at guaranteeing that the service provider is behaving honestly. The advantage of this scheme is twofold. First, exponential information-theoretic security is obtained with the only overhead being a polynomial number of repetitions. This means that all available qubits can be devoted to computation. Second, the scheme is robust in the sense that it can cope with noise and return the correct result with probability exponentially close to 1 as long as the probability to fail a single test run is less than $25\mathrm{\%}$.

We believe this scheme will be a motivation for hardware providers to integrate verifiability as a capability of their future quantum architecture as well as a feature that will be demanded by end users to protect their intellectual property.

Figure 1

An example of rounds of the proposed protocol. Graphs in gray denote computation rounds, while graphs containing red nodes (traps) and green nodes (dummies) are test rounds. Each qubit is always included in one type of test round. The server remains completely oblivious to the differences between the rounds, which are solely known to the client.

Figure 2

The four cases needed to determine a closed-form upper bound for the probability of failure. First, we determine the probability for the number of affected computation rounds. If it is low enough [$Z<d(2p-1)/(2p-2)$], there is no need to abort. If it is high [$Z\ge d(2p-1)/(2p-2)$], we find a bound on the probability that the number of failed test rounds $Y$ is below or above $w$.