Source-linked AI summary
Device-Independent Verifiable Blind Quantum Computation
Michal Hajdušek, Carlos A. Pérez-Delgado, Joseph F. Fitzsimons
TL;DR
The paper addresses the prohibitive overhead of device-independent verification for quantum computations. It combines device-independent remote state preparation with verified blind quantum computation and Bell-state self-testing, achieving resource scaling of O(m^4 lnm).
Problem
Existing device-independent verification schemes for arbitrary quantum computations require resources scaling as extremely high-degree polynomials in the number of gates.
Source: Conclusion · pp. 8–9Method
The protocol replaces direct quantum state distribution with device-independent remote state preparation, then performs authenticated blind computation using self-testing and trap-based verification.
Source: Results · pp. 2, 7Results
Resources scale as O(m^4 lnm), while the protocol remains device-independent and uses a verified blind-computation phase after state preparation.
Source: Results · pp. 7–8, Conclusion · p. 9Takeaways & Limitations
Combining individual EPR-pair self-testing with authenticated computation substantially reduces the overhead of device-independent verification relative to prior schemes.
Source: Conclusion · pp. 8–9The protocol assumes measurement events can respect spacelike separation and that the verifier's device can measure individual qubits in arbitrary bases.
Source: Results · p. 2
Abstract
from arXiv · showhide
As progress on experimental quantum processors continues to advance, the problem of verifying the correct operation of such devices is becoming a pressing concern. The recent discovery of protocols for verifying computation performed by entangled but non-communicating quantum processors holds the promise of certifying the correctness of arbitrary quantum computations in a fully device-independent manner. Unfortunately, all known schemes have prohibitive overhead, with resources scaling as extremely high degree polynomials in the number of gates constituting the computation. Here we present a novel approach based on a combination of verified blind quantum computation and Bell state self-testing. This approach has dramatically reduced overhead, with resources scaling as only $O(m^4\ln m)$ in the number of gates.
Results
The results develop a device-independent blind quantum-computation protocol by replacing the initial state-distribution phase with device-independent remote state preparation while retaining classical execution and verification. Combining self-testing with multi-trap verification, the protocol certifies an approximately ideal hidden input and bounds acceptance of incorrect outputs with O(m^4 lnm) Bell pairs per measurement setting.
- The protocol replaces Protocol 6’s initial state distribution with self-testing-based remote preparation, leaving the classical execution and verification phase unchanged.Security therefore depends on preparing the initial classical-quantum correlation with sufficiently high fidelity.Source: Results · pp. 2–3
- Alice randomly interweaves self-testing and remote-preparation trials, preventing Bob from knowing which received qubits certify correlations and which generate computation inputs.The procedure assumes spatially separated, non-communicating quantum provers and sufficiently rapid sequential EPR-pair transmission.Source: Results · p. 2
- The self-testing analysis extends Bell-pair certification to complex measurements, using a local isometry whose phase-kickback component extracts the desired state and complex-phase information.The approach builds on Mayers and Yao and McKague et al., without requiring a trusted measurement device.Source: Results · pp. 3–5
- Alice’s measurement outcome remotely prepares Bob’s computation, trap, or dummy qubit while hiding the chosen state, because she does not announce her random angle or outcome.Tracing out Alice’s system leaves Bob’s reduced state maximally mixed.Source: Results · p. 3
- Unless Alice aborts, Bob holds ideal corresponding qubit states within ˜ε, with probability at least p, where ˜ε = O(χ^1/4).Theorem 1 derives this from χ-close measured correlations and a local isometry extracting the desired state.Source: Results · p. 4
- δ = exp(−(˜n+m)ε^2/8) bounds the confidence analysis, obtained with Azuma-Hoeffding rather than an independence-dependent Chernoff bound.This martingale-based treatment supports device-independent estimation over self-testing and remote-preparation pairs.Source: Results · p. 5
- Input-state infidelity from dishonest behavior contributes an additive error to the probability that verification accepts an incorrect outcome.The analysis relates the tested shared state’s distance to fidelity of Bob’s input and then bounds incorrect acceptance through the verification channel.Source: Results · pp. 6–7
- The protocol first tests Alice’s device and produces a separable input state on Bob’s computer, then performs verifiable blind computation with classical input and output.Correctness follows from the corresponding unmodified blind-verification protocol, while self-testing makes the construction device-independent.Source: Results · p. 7
- Multi-trap verification achieves constant verifiability by placing traps in a constant-fraction tape of cylindrical brickwork-state rows.The increased trap probability yields the constant acceptance guarantee, while dummy qubits isolate traps from the brickwork computation.Source: Results · p. 7
- Corollary 1 states that Protocol 2 is (1−p∆+2p√m˜ε)-verifiable, concerning the probability that an incorrect outcome is accepted at the end of verification.Here p is Alice’s confidence that Bob possesses an m-qubit input state close to the ideal one, with p ≥(1−δ)3m(1−2δ)11m.Source: Results · p. 7
- O(m^4 lnm) Bell pairs per measurement setting suffice for verifying remote state preparation of an m-qubit input.The scaling follows from requiring ε˜ = O(m^-1/2), Theorem 1’s ε˜ = O(ε^1/4), and ε = O(m^-2).Source: Results · pp. 7–8
Conclusion
The scheme improves resource efficiency for device-independent verification by combining remote state preparation with authenticated computation and avoiding the extreme overhead of earlier approaches. Its resource overhead scales as O(m^4 lnm), while a related independent approach scales as n^c for c > 2048.
- Splitting verification into device-independent remote state preparation followed by authenticated computation improves on schemes that self-test an entire graph state or perform extensive tomography.The comparison schemes require overheads with leading terms of at least n^22 and n^8192, respectively.Source: Conclusion · p. 8
- A related independent protocol uses CHSH rigidity rather than Bell-pair self-testing and has overhead scaling as n^c for a constant c > 2048.Source: Conclusion · p. 9
- O(m^4 lnm) resources are required, a drastic efficiency improvement over other device-independent verification methods.Source: Conclusion · p. 9