Physics – Quantum Physics
Scientific paper
2010-02-15
Lecture Notes in Computer Science 5906 (2009), 10-19
Physics
Quantum Physics
12 pages; Theory of Quantum Computation, Communication, and Cryptography: Fourth Workshop, TQC 2009
Scientific paper
10.1007/978-3-642-10698-9
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.
Dam Wim van
Yuan Qingqing
No associations
LandOfFree
Quantum Online Memory Checking does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum Online Memory Checking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Online Memory Checking will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-597761