Backend
Controlled-Memory Identification with Shared Generators: Dimension--Horizon Tradeoffs and Quantum--Classical Separation
arXiv math.IT0 views
arXiv:2610.21797v1 Announce Type: cross 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.
Source:https://arxiv.org/abs/2610.21797PreviousDecoding Failure Biases IBLT Count Measurements: A Gaussian-Selection Law at the Peeling ThresholdNextOn Minimum Divergence for Distribution Reconstruction
Related posts
Convert YAML to JSON in the Browser (and JSON to YAML) Without Uploading the File
0dev.to
Vercel agent-desktop: computer use for coding agents through the accessibility tree
0dev.to
WARN Act and Job Search — How to Use the 60-Day Notice Period to Find Your Next Job
0dev.to
Node.js SMS Verification Code: Generating and Sending One-Time Passwords via API Integration
0dev.to
Introducing Takeout Mender – A Free Tool to Recover Metadata from Google Takeout
0dev.to
DeepSeek's Open-Source "Super-Agent" Codes Without Being Asked
0dev.to GitHub