Controlled-Memory Identification with Shared Generators: Dimension--Horizon Tradeoffs and Quantum--Classical Separation

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 \(\lambda_2>0\) and \(\lambda_1+\lambda_2<1\), the optimal identification sizes satisfy \(\ln N_{\mathsf Q,4}=\Theta_{\lambda_1,\lambda_2}(\min\{d^2,T\})\) for arbitrary CPTP generators and \(\ln N_{\mathsf S,4}=\Theta_{\lambda_1,\lambda_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}=\Theta(d^2)\) versus \(\ln N_{\mathsf S,4}=\Theta(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 \(\lambda_2=0\), \(0\leq\lambda_1<1\), all four model classes satisfy \(\ln N=\Theta(\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.

Quantum Physics (quant-ph); Information Theory (cs.IT)

arXiv:2610.21797 [quant-ph]

(or arXiv:2610.21797v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.21797 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.