paper

Quantum Online Memory Checking

arXiv:1002.2970 · doi:10.1007/978-3-642-10698-9

Abstract

The problem of memory checking considers storing files on an unreliable public server whose memory can be modified by a malicious party. The main task is to design an online memory checker with the capability to verify that the information on the server has not been corrupted. To store n bits of public information, the memory checker has s private reliable bits for verification purpose; while to retrieve each bit of public information the checker communicates t bits with the public memory. Earlier work showed that, for classical memory checkers, the lower bound s*t \in Omega(n) holds. In this article we study quantum memory checkers that have s private qubits and that are allowed to quantum query the public memory using t qubits. We prove an exponential improvement over the classical setting by showing the existence of a quantum checker that, using quantum fingerprints, requires only s \in O(log n) qubits of local memory and t \in O(polylog n) qubits of communication with the public memory.

12 pages; Theory of Quantum Computation, Communication, and Cryptography: Fourth Workshop, TQC 2009

Cited by in corpus (28)