dorsal/arxiv
View SchemaOptimal lower bounds for quantum automata and random access codes
| Authors | Ashwin Nayak |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9904093 |
| URL | https://arxiv.org/abs/quant-ph/9904093 |
Abstract
Consider the finite regular language L_n = {w0 : w \in {0,1}^*, |w| \le n}. It was shown by Ambainis, Nayak, Ta-Shma and Vazirani that while this language is accepted by a deterministic finite automaton of size O(n), any one-way quantum finite automaton (QFA) for it has size 2^{Omega(n/log n)}. This was based on the fact that the evolution of a QFA is required to be reversible. When arbitrary intermediate measurements are allowed, this intuition breaks down. Nonetheless, we show a 2^{Omega(n)} lower bound for such QFA for L_n, thus also improving the previous bound. The improved bound is obtained by simple entropy arguments based on Holevo's theorem. This method also allows us to obtain an asymptotically optimal (1-H(p))n bound for the dense quantum codes (random access codes) introduced by Ambainis et al. We then turn to Holevo's theorem, and show that in typical situations, it may be replaced by a tighter and more transparent in-probability bound.
{
"annotation_id": "c1c87666-9e84-4474-9edf-e389c023e0cf",
"date_created": "2026-03-02T18:02:48.352000Z",
"date_modified": "2026-03-02T18:02:48.352000Z",
"file_hash": "8c4d584584a9a258d702c61e3e4cf64cc3689d1f4749a877f12d028bed04f593",
"private": false,
"record": {
"abstract": "Consider the finite regular language L_n = {w0 : w \\in {0,1}^*, |w| \\le n}.\nIt was shown by Ambainis, Nayak, Ta-Shma and Vazirani that while this language\nis accepted by a deterministic finite automaton of size O(n), any one-way\nquantum finite automaton (QFA) for it has size 2^{Omega(n/log n)}. This was\nbased on the fact that the evolution of a QFA is required to be reversible.\nWhen arbitrary intermediate measurements are allowed, this intuition breaks\ndown. Nonetheless, we show a 2^{Omega(n)} lower bound for such QFA for L_n,\nthus also improving the previous bound. The improved bound is obtained by\nsimple entropy arguments based on Holevo\u0027s theorem. This method also allows us\nto obtain an asymptotically optimal (1-H(p))n bound for the dense quantum codes\n(random access codes) introduced by Ambainis et al. We then turn to Holevo\u0027s\ntheorem, and show that in typical situations, it may be replaced by a tighter\nand more transparent in-probability bound.",
"arxiv_id": "quant-ph/9904093",
"authors": [
"Ashwin Nayak"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Optimal lower bounds for quantum automata and random access codes",
"url": "https://arxiv.org/abs/quant-ph/9904093"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "5a4b9068-e721-475b-861f-86d66ef5939e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}