Measurement Geometry for Quantum Random Access Codes: Beyond Nayak Bound and Toward Optimality

• URL: http://arxiv.org/abs/2606.12700v1
• Date: Wed, 10 Jun 2026 21:41:58 GMT
• Title: Measurement Geometry for Quantum Random Access Codes: Beyond Nayak Bound and Toward Optimality
• Abstract summary: 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.
• Score: 0.13999481573773068
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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. Although the Nayak bound remains the standard general upper bound on the decoding probability, numerical evidence suggests a stronger upper bound in the small-qubit regime. In this work, we formulate the optimal decoding probability in terms of decoding measurements, reformulating QRAC design as a spectral problem for noncommuting measurements. Using this formulation, we give an elementary proof of the Nayak bound by simplifying the Chernoff-bound argument. Moreover, we refine the argument to obtain upper bounds that improve over Nayak's bound in the entire finite-size regime. The equality conditions of our bounds justify defining mutually unbiased projector-valued measurements (MUPVMs), a generalization of mutually unbiased bases. We show that decoding measurement of any two-qubit QRAC attaining the conjectured bound must form MUPVMs. We also show that any MUPVM, assisted by one ancillary qubit, yields a QRAC with optimal N-scaling decoding probability. Finally, we propose a new MUPVM-based construction for the (M+2,M)-QRAC family attaining the conjectured bound.

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)
• One Qubit Can Beat One Bit: Quantum Advantage for Post-Training Quantization [7.09016563801433]
  One-bit post-training quantization represents each weight using only its sign, requiring all deployment contexts to share the same binary weight matrix.<n>We study this shared-sign constraint and introduce Quantum Random Access Quantization (QRAQ)<n>This framework encodes context-dependent signs in a quantum random-access code and retrieves them via context-matched Pauli measurements.
  arXiv  Detail & Related papers  (2026-08-05T14:04:50Z)
• 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)
• Decoded Quantum Interferometry Beyond Hamming: Rank-Metric and Translation Association Schemes [39.146761527401424]
  Decoded Quantum Interferometry (DQI) uses coherent decoding and a quantum Fourier transform to find high-quality solutions of structured optimisation problems.<n>We extend the core DQI mechanism beyond Hamming space to finite geometries with translation symmetry.<n>We find solutions with an effective-rank proxy near min(m,n)-l, and the corresponding expected score can be converted into a constant-probability bound on the residual rank of a sample.
  arXiv  Detail & Related papers  (2026-06-03T13:12:15Z)
• Quantum Hypothesis Testing Lemma for Deterministic Identification over Quantum Channels [49.126395046088014]
  This work shows that the existence of a DI code in the quantum setting follows from a suitable packing in a modified space of output quantum states.<n>This result enables us to tighten the capacity lower bound for DI over quantum channels beyond the simultaneous decoding approach.
  arXiv  Detail & Related papers  (2025-04-29T17:57:36Z)
• Reed-Muller Codes on CQ Channels via a New Correlation Bound for Quantum Observables [7.415361840837667]
  We analyze decoding functions using symmetry and the nested structure of Reed-Muller codes.<n>Our results show that any set of $2o(sqrtlog N)$ bits can be decoded with a high probability when the code rate is less than the Holevo capacity.
  arXiv  Detail & Related papers  (2025-02-06T05:19:24Z)
• QDistRnd: A GAP package for computing the distance of quantum error-correcting codes [0.029541734875307393]
  GAP package QDistRnd implements a probabilistic algorithm for finding the minimum distance of a quantum low-density parity-check code linear over a finite field GF(q)
  arXiv  Detail & Related papers  (2023-08-29T09:17:57Z)
• Gaussian conversion protocol for heralded generation of qunaught states [66.81715281131143]
  bosonic codes map qubit-type quantum information onto the larger bosonic Hilbert space. We convert between two instances of these codes GKP qunaught states and four-foldsymmetric binomial states corresponding to a zero-logical encoded qubit. We obtain GKP qunaught states with a fidelity of over 98% and a probability of approximately 3.14%.
  arXiv  Detail & Related papers  (2023-01-24T14:17:07Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Widening the sharpness modulation region of an entanglement-assisted sequential quantum random access code: Theory, experiment, and application [2.531490578771959]
  We propose an entanglement-assisted sequential QRAC protocol which can enable device-independent tasks. We get more than 27 standard deviations above the classical bound even when both decoders perform approximately projective measurements. Our results may promote a deeper understanding of the relationship among quantum correlation, quantum measurement, and quantum information processing.
  arXiv  Detail & Related papers  (2021-04-30T03:27:28Z)
• Geometry of Banach spaces: a new route towards Position Based Cryptography [65.51757376525798]
  We study Position Based Quantum Cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. We show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol.
  arXiv  Detail & Related papers  (2021-03-30T13:55:11Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)

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.