Quantum memory enables exponentially larger identification than classical memory
Controlled-Memory Identification with Shared Generators: Dimension--Horizon Tradeoffs and Quantum--Classical Separation
Information Theory
Summary
This paper studies how much information can be reliably identified using a limited memory system controlled by a small set of operations. The authors find that when using quantum memory, the number of identifiable messages grows roughly with the square of the memory's dimension, while classical systems only grow linearly. They also show that this advantage depends on allowing a small error rate in acceptance. This result mathematically quantifies a separation between quantum and classical capabilities in controlled-memory identification tasks.
What this means in practice
- •For quantum communication engineers: Design memory devices that use a small set of quantum operations to encode and identify many messages more efficiently than classical counterparts.
- •For cryptographers: Develop protocols that exploit quantum memory’s larger identification capacity with limited operations to improve authentication or identification schemes.
A theory result. No direct application yet.
Authors
Yixin Zhao
Abstract
We determine the finite-horizon identification limits of a \(d\)-dimensional memory when the control interface is restricted to four shared, time-homogeneous generators. A writer encodes a message by applying a prefix word to a common root state. The verifier then applies a candidate-dependent query word followed by a shared terminal binary test, with each word of length at most \(T\). For fixed error tolerances \(λ_2>0\) and \(λ_1+λ_2<1\), the optimal identification sizes satisfy \(\ln N_{\mathsf Q,4}=Θ_{λ_1,λ_2}(\min\{d^2,T\})\) for arbitrary CPTP generators and \(\ln N_{\mathsf S,4}=Θ_{λ_1,λ_2}(\min\{d,T\})\) for stochastic maps. Four unitary letters and four permutation letters attain these respective bounds, showing that a four-letter reversible alphabet reaches the static code-size orders in optimal quadratic and linear word length. In the fully dimension-limited regime, this yields \(\ln N_{\mathsf Q,4}=Θ(d^2)\) versus \(\ln N_{\mathsf S,4}=Θ(d)\), establishing a quadratic quantum--classical separation in logarithmic code size. Low-overlap Grassmann and agreement-code packings supply the orbit endpoints, while exact inverse query words match each encoded state to its designated test. At the sharp boundary \(λ_2=0\), \(0\leqλ_1<1\), all four model classes satisfy \(\ln N=Θ(\min\{\ln d,T\})\). Thus any fixed positive false-acceptance tolerance activates the metric-packing regime, whereas zero false acceptance imposes an exclusive-witness constraint and yields the logarithmic-dimension boundary.