Classical Verification of Quantum Learning Advantages with Noises
This work addresses the challenge of reliable classical verification for quantum learning with noisy devices, which is incremental but crucial for practical applications with current quantum hardware.
The paper tackles the problem of verifying quantum learning advantages in the presence of noise, proposing an error rectification algorithm that restores noise-free results from quantum Fourier sampling with constant-level noises, enabling efficient agnostic parity learning on noisy quantum devices with logarithmic sample scaling.
Classical verification of quantum learning allows classical clients to reliably leverage quantum computing advantages by interacting with untrusted quantum servers. Yet, current quantum devices available in practice suffers from a variety of noises and whether existed classical verification protocols carry over to noisy scenarios remains unclear. Here, we propose an efficient classical error rectification algorithm to reconstruct the noise-free results given by the quantum Fourier sampling circuit with practical constant-level noises. In particular, we prove that the error rectification algorithm can restore the heavy Fourier coefficients by using a small number of noisy samples that scales logarithmically with the problem size. We apply this algorithm to the agnostic parity learning task with uniform input marginal and prove that this task can be accomplished in an efficient way on noisy quantum devices with our algorithm. In addition, we prove that a classical client with access to the random example oracle can verify the agnostic parity learning results from the noisy quantum prover in an efficient way, under the condition that the Fourier coefficients are sparse. Our results demonstrate the feasibility of classical verification of quantum learning advantages with noises, which provide a valuable guide for both theoretical studies and practical applications with current noisy intermediate scale quantum devices.