Classical codes violate the conjectured square-root bound for quantum random access codes

• URL: http://arxiv.org/abs/2607.15617v1
• Date: Fri, 17 Jul 2026 04:31:15 GMT
• Title: Classical codes violate the conjectured square-root bound for quantum random access codes
• Abstract summary: We find that classical random access codes with private randomness, which form a subclass of this QRAC model, violate the bound.<n>Achievability theorem of Ambainis, Nayak, Ta-Shma, and Vazirani then yields violations for every fixed $pin(1/2,1)$ at sufficiently large input length.
• Score: 2.199781594442351
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider whether every quantum random access code (QRAC) with density-operator encodings and arbitrary decoding measurements obeys the conjectured bound $p\leq(1+\sqrt{m/n})/2$, where $n$ classical bits are encoded into $m$ qubits and $p$ is the worst-case success probability. We find that classical random access codes with private randomness, which form a subclass of this QRAC model, violate the bound. We embed these classical codes as QRACs with diagonal encoding states and commuting decoding measurements, and construct pure-state realizations with identical decoding statistics. The achievability theorem of Ambainis, Nayak, Ta-Shma, and Vazirani then yields violations for every fixed $p\in(1/2,1)$ at sufficiently large input length. The counterexamples span the full open interval between the conjectured and Nayak bounds at each fixed compression rate. A finite-blocklength analysis further yields order-optimal logarithmic qubit scaling for a recovery bias scaling as $\sqrt{\log_2 n/n}$ with a sufficiently large prefactor. These results identify the classical coding rate as the source of the separation and motivate restricted bounds based on quantitative spectral properties of decoding measurements.

Related papers

• Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes [9.855041870231533]
  Belief propagation with quantum messages (BPQM) is a quantum algorithm that decodes classical codes transmitted over classical--quantum channels.<n>We construct a two-stage BPQM decoder for random $q$-ary LDPC codes over symmetric $q$-ary pure-state channels.<n>We prove that its ensemble-average block-error probability vanishes as the blocklength $N$ tends to infinity.
  arXiv  Detail & Related papers  (2026-09-05T03:36:03Z)
• Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry [0.0]
  For general max-k-XORSAT with $k geq 3$, no-time algorithm can do substantially better than random guessing on worst-case instances.<n>We make this connection explicit and extend the hardness to max-E$k$-LINSAT$(q,r)$ with bounded degree $D$ and over arbitrary finite fields.
  arXiv  Detail & Related papers  (2026-06-11T16:59:12Z)
• Measurement Geometry for Quantum Random Access Codes: Beyond Nayak Bound and Toward Optimality [0.13999481573773068]
  Quantum random access codes (QRACs) ask how well N classical bits can be encoded into M qubits while allowing any single bit to be recovered.<n>We formulate the optimal decoding probability in terms of decoding measurements.<n>We show that decoding measurement of any two-qubit QRAC attaining the conjectured bound must form MUPVMs.
  arXiv  Detail & Related papers  (2026-06-10T21:41:58Z)
• Random Access Codes: Explicit Constructions, Optimality, and Classical-Quantum Gaps [1.3033126970138174]
  We develop a constructive framework for classical $(L,k)$-RACs under both average- and worst-case criteria.<n>We show that these optimal codes induce $(L,L-1)$-QRACs that attain a conjectured upper bound on the decoding success probability.
  arXiv  Detail & Related papers  (2026-04-23T04:36:05Z)
• SDP bounds on quantum codes: rational certificates [1.7188280334580195]
  A fundamental problem in quantum coding theory is to determine the maximum size of quantum codes of given block length and distance.<n>Recent work introduced bounds based on semidefinite programming, strengthening the well-known quantum linear programming bounds.<n>We provide rational infeasibility certificates for a range of quantum codes.
  arXiv  Detail & Related papers  (2026-03-20T12:33:38Z)
• Deterministic identification over channels with finite output: a dimensional perspective on superlinear rates [49.126395046088014]
  We consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets.<n>Our main findings are that the maximum length of messages thus identifiable scales superlinearly as $R,nlog n$ with the block length $n$.<n>We show that it is sufficient to ensure pairwise reliable distinguishability of the output distributions to construct a DI code.
  arXiv  Detail & Related papers  (2024-02-14T11:59:30Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete. We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes. Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
  arXiv  Detail & Related papers  (2021-08-10T15:00:20Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• Describing quantum metrology with erasure errors using weight distributions of classical codes [9.391375268580806]
  We consider using quantum probe states with a structure that corresponds to classical $[n,k,d]$ binary block codes of minimum distance. We obtain bounds on the ultimate precision that these probe states can give for estimating the unknown magnitude of a classical field.
  arXiv  Detail & Related papers  (2020-07-06T16:22:40Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.