Search papers, labs, and topics across Lattice.
This paper analyzes the limitations of using the quantum cut-and-choose technique alone for verifiable delegated quantum computation. It demonstrates that protocols relying solely on cut-and-choose cannot simultaneously achieve security and efficiency. The findings imply that additional, potentially costly, techniques are necessary for practical verifiable quantum computation.
Quantum cut-and-choose alone can't deliver both security and efficiency in delegated quantum computation, dashing hopes for near-term verifiable outsourcing.
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.
