Random Access Codes: Explicit Constructions, Optimality, and Classical-Quantum Gaps

• URL: http://arxiv.org/abs/2604.21274v1
• Date: Thu, 23 Apr 2026 04:36:05 GMT
• Title: Random Access Codes: Explicit Constructions, Optimality, and Classical-Quantum Gaps
• Abstract summary: 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.
• Score: 1.3033126970138174
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A random access code (RAC) encodes an $L$-bit string into a $k$-bit $(L>k)$ message from which any designated source bit can be recovered with high probability. Its quantum counterpart, a quantum random access code (QRAC), replaces the $k$-bit message with $k$ qubits. While upper bounds on the decoding success probability have long been studied in both classical and quantum settings, explicit constructions of optimal codes are known only in special cases, even for classical RACs. In this paper, we develop a constructive framework for classical $(L,k)$-RACs under both average- and worst-case criteria. We show that optimal code design reduces to selecting $2^k$ points in $\{0,1\}^L$ and $[0,1]^L$ for the average- and worst-case criteria, respectively, so as to minimize a distance-like objective. This characterization yields explicit constructions for general $(L,k)$. For $k=L-1$, we further obtain closed-form optimal encoders and decoders for both criteria, and show that the resulting classical $(L,L-1)$-RACs attain the corresponding proved upper bounds. We also show that these optimal classical codes induce $(L,L-1)$-QRACs that attain a conjectured upper bound on the decoding success probability. Numerical optimization suggests little difference between RACs and QRACs in the average-case setting, but a potentially large classical-quantum gap in the worst-case nonasymptotic regime.

Related papers

• Classical codes violate the conjectured square-root bound for quantum random access codes [2.199781594442351]
  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.
  arXiv  Detail & Related papers  (2026-07-17T04:31:15Z)
• Optimal Quantum $(r,δ)$-Locally Repairable Codes via Classical Ones [52.3857155901121]
  Local repairable codes (LRCs) play a crucial role in mitigating data loss in large-scale distributed and cloud storage systems.<n>This paper establishes a unified decomposition theorem for general optimal $(r,delta)$-LRCs.<n>We construct three infinite families of optimal quantum $(r,delta)$-LRCs with flexible parameters.
  arXiv  Detail & Related papers  (2025-07-24T08:21:20Z)
• Quantum One-Time Memories from Stateless Hardware, Random Access Codes, and Simple Nonconvex Optimization [0.0]
  We present a construction of one-time memories (OTMs) using classical-accessible stateless hardware.<n>Unlike the aforementioned approach, our approach leverages quantum random access codes (QRACs) to encode two classical bits.<n>We prove soundness against a number of classical queries to the hardware.
  arXiv  Detail & Related papers  (2025-01-07T22:29:33Z)
• Entanglement-assisted Quantum Error Correcting Code Saturating The Classical Singleton Bound [44.154181086513574]
  We introduce a construction for entanglement-assisted quantum error-correcting codes (EAQECCs) that saturates the classical Singleton bound with less shared entanglement than any known method for code rates below $ frackn = frac13 $. We demonstrate that any classical $[n,k,d]_q$ code can be transformed into an EAQECC with parameters $[n,k,d;2k]]_q$ using $2k$ pre-shared maximally entangled pairs.
  arXiv  Detail & Related papers  (2024-10-05T11:56:15Z)
• Transfer Q Star: Principled Decoding for LLM Alignment [105.89114186982972]
  Transfer $Q*$ estimates the optimal value function for a target reward $r$ through a baseline model. Our approach significantly reduces the sub-optimality gap observed in prior SoTA methods.
  arXiv  Detail & Related papers  (2024-05-30T21:36:12Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• 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)
• Biased Random Access Codes [0.0]
  A random access code (RAC) is a communication task in which the sender encodes a random message into a shorter one to be decoded by the receiver. We present algorithms that allow a numerical evaluation of the optimal performance over both classical and quantum strategies.
  arXiv  Detail & Related papers  (2023-02-16T18:53:25Z)
• 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)
• Quantum Random Access Codes for Boolean Functions [0.05076419064097732]
  We study and give protocols for $f$-random access codes with classical ($f$-RAC) and quantum ($f$-QRAC) encoding. The success probability of our protocols is characterized by the emphnoise stability of the Boolean function $f$.
  arXiv  Detail & Related papers  (2020-11-12T17:48:37Z)

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.