Verified delegated quantum computation requires techniques beyond cut-and-choose
This addresses the problem of verifying outsourced quantum computations for clients with limited quantum resources, showing that current approaches are insufficient without costly additions, which is incremental as it builds on existing verification methods.
The paper investigates whether quantum cut-and-choose techniques alone can achieve secure and efficient verifiable delegated quantum computation, finding that protocols relying solely on these methods cannot be both secure and efficient simultaneously.
Delegated quantum computation enables a client with limited quantum capabilities to outsource computations to a more powerful quantum server while preserving correctness and privacy. Verification is crucial in this setting to ensure that the untrusted quantum server performs the computation honestly and returns correct results. A common verification method is the quantum cut-and-choose technique. Inspired by classical verification methods for two-party computation, the client uses the majority of the delegated rounds to test the server's honesty, while keeping the remaining ones for the actual computation. Combining this technique with other methods, such as quantum error correction, could help achieve negligible cheating probabilities for the server; however, such methods can impose significant overheads making implementations unfeasible for the near-term future. In this work, we investigate whether cut-and-choose can yield efficient and secure verifiable quantum computation without additional costly techniques. We find that verifiable delegated quantum computation protocols relying solely on cut-and-choose techniques cannot be secure and efficient at the same time.