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

Hiroshi Yano; Kosuke Ito; Naoki Yamamoto; Ruho Kondo; Yota Maeda; Yuki Sato

arxiv: 2604.21274 · v2 · pith:GRNOVVE6new · submitted 2026-04-23 · 🪐 quant-ph · cs.IT· math.IT

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

Ruho Kondo , Yuki Sato , Hiroshi Yano , Yota Maeda , Kosuke Ito , Naoki Yamamoto This is my paper

Pith reviewed 2026-05-21 00:00 UTC · model grok-4.3

classification 🪐 quant-ph cs.ITmath.IT

keywords random access codesquantum random access codesclassical-quantum separationgeometric characterizationbinary linear codesworst-case optimalityaverage-case optimality

0 comments

The pith

For the (2^k-1, k) family, an explicit quantum random access code exceeds the optimal classical worst-case success probability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper introduces a geometric characterization of optimal classical random access codes that map an L-bit string to a k-bit message. The average-case version reduces to choosing 2^k representative strings from {0,1}^L, while the worst-case version reduces to placing 2^k points in the unit hypercube [0,1]^L to minimize a distance-like objective. With this reduction in hand, the authors prove that a classical construction based on binary linear codes is worst-case optimal for the family where L equals 2^k minus one. They then exhibit an explicit quantum version whose worst-case success probability is strictly higher, establishing a separation. The same framework also yields average-optimal classical codes for the (L, L-1) family and quantum codes that meet a previously conjectured performance bound.

Core claim

The paper shows that worst-case optimality for classical (L,k)-RACs is equivalent to selecting 2^k points in [0,1]^L that minimize a distance-like objective. For the parameter family (2^k-1, k), this characterization proves the optimality of a classical construction derived from binary linear codes, while an explicit quantum random access code achieves a strictly higher worst-case success probability and thereby establishes a classical-quantum gap. For the family (L, L-1), the same viewpoint identifies an average-optimal classical construction and recovers explicit quantum constructions that attain a conjectured upper bound.

What carries the argument

Geometric reduction of the worst-case RAC problem to selecting 2^k points in [0,1]^L that minimize a distance-like objective.

If this is right

Several (L,k) families now possess provably optimal classical RAC constructions realized by standard binary linear codes.
The (2^k-1, k) family has a classical worst-case optimum that is strictly exceeded by the given explicit QRAC.
The (L, L-1) family admits a classical construction optimal under the average success criterion.
Explicit (L, L-1) QRACs are recovered that attain the value of a previously conjectured tight upper bound.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same geometric lens may be used to search for classical-quantum gaps in other parameter regimes or for approximate versions of the RAC task.
The reduction to a distance-minimization problem in the hypercube suggests possible links to classical coding theory questions about covering radii or constant-weight codes.
For concrete small values of k the separation can be checked by exhaustive search over the classical side, providing a direct test of the claimed gap.

Load-bearing premise

The average-case and worst-case success probabilities of random access codes are exactly captured by the stated geometric selections of representatives and points.

What would settle it

Direct numerical computation, for any small fixed k such as k=2, of the worst-case success probability achieved by the paper's explicit QRAC versus the minimum value of the distance-like objective over all choices of 2^k points in [0,1]^L.

Figures

Figures reproduced from arXiv: 2604.21274 by Hiroshi Yano, Kosuke Ito, Naoki Yamamoto, Ruho Kondo, Yota Maeda, Yuki Sato.

**Figure 1.** Figure 1: Decoding success probability of RACs and QRACs for L ≤ 7 and k = 3. Conjectural upper bound of QRAC (Eq. (4)) is included. References [1] Wiesner, S. Conjugate coding. ACM Sigact News, 15 (1):78–88, 1983. doi: 10.1145/1008908.1008920. [2] Ambainis, A., Nayak, A., Ta-Shma, A. and Vazirani, U. Dense quantum coding and a lower bound for 1- way quantum automata. In Proceedings of the thirtyfirst annual ACM sy… view at source ↗

**Figure 2.** Figure 2: Achievable (conjecturally maximum) success probability of (L, L − 1)-RACs and (L, L − 1)-QRACs. Note that the maximum average success probability and the maximum worst case success probability are the same for (L, L − 1)-QRAC. For clarity, markers are shown only for L ≤ 10. [7] Sharma, M., Jin, Y., Lau, H.C. and Raymond, R. Quantum relaxation for solving multiple knapsack problems. In 2024 IEEE Internation… view at source ↗

read the original abstract

A random access code (RAC) encodes an $L$-bit string into a $k$-bit message, where $L>k$, such that any requested bit can be decoded with high probability; a quantum RAC (QRAC) replaces the message with $k$ qubits. This paper provides a geometric characterization of optimal classical $(L,k)$-RACs under both average and worst-case success criteria. We show that the average problem reduces to selecting $2^k$ representatives in $\{0,1\}^L$, whereas the worst-case problem reduces to selecting $2^k$ points in $[0,1]^L$ that minimize a distance-like objective. This framework establishes optimality for several parameter families $(L,k)$, with optimal constructions in many cases realized by standard infinite families of binary linear codes. For the parameter family $(2^k-1,k)$, we prove the worst-case optimality of a classical construction and present an explicit QRAC whose worst-case success probability is strictly higher than the classical optimum, thereby establishing a classical--quantum separation for this family. For the parameter family $(L,L-1)$, the framework identifies a classical RAC construction that is optimal under the average criterion and, assuming a stated conjecture, also optimal under the worst-case criterion. As a by-product, the same geometric viewpoint recovers explicit $(L,L-1)$-QRACs similar to existing constructions that attain the value of an upper bound conjectured in prior work to be tight.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives a geometric reduction that yields explicit optimal classical RACs for several families plus a concrete quantum advantage for the (2^k-1, k) case.

read the letter

The main takeaway is that this work supplies explicit classical constructions that hit optimality for multiple (L,k) families and proves a strict quantum-classical gap for the infinite family where L equals 2 to the k minus 1. They reduce the average-case problem to picking 2^k representatives inside the hypercube and the worst-case problem to minimizing a distance-like objective over 2^k points in the unit cube. Standard binary linear codes then serve as optimal constructions in many cases, which is a practical result. For the highlighted family they establish the classical optimum and give an explicit QRAC whose worst-case success probability is higher, which is the clearest new separation here. The same geometric lens also recovers explicit QRACs for the (L, L-1) family that reach a previously conjectured bound. This organizes scattered results and hands the community concrete benchmarks rather than just existence proofs. The soft spot is the conjecture required to claim worst-case optimality for the (L, L-1) family; that part remains conditional. The reduction to the continuous minimization also needs the full proof to confirm it is tight with actual deterministic encodings, since a strictly lower continuous value would leave a gap in the classical optimality claim. This is for quantum information researchers who work on random access codes and communication tasks. Readers who want explicit constructions and a verified separation will get direct use from the examples and the gap result. It deserves a serious referee to check the derivations and the conjecture. I would send it to peer review.

Referee Report

2 major / 3 minor

Summary. The manuscript develops a geometric characterization of classical (L,k)-random access codes under both average-case and worst-case success criteria. The average-case problem reduces to selecting 2^k representatives in {0,1}^L; the worst-case problem reduces to selecting 2^k points in [0,1]^L that minimize a distance-like objective. This framework is applied to prove worst-case optimality of classical constructions (realized by binary linear codes) for the family (2^k-1,k), to exhibit an explicit QRAC whose worst-case success probability strictly exceeds the classical optimum (establishing a separation), and to identify optimal classical constructions for (L,L-1) under the average criterion (and under the worst-case criterion assuming a stated conjecture). The same viewpoint recovers explicit (L,L-1)-QRACs attaining a previously conjectured upper bound.

Significance. If the central claims hold, the geometric reduction supplies a clean, unified method for proving optimality of RAC constructions and for certifying classical-quantum separations. The explicit separation for the infinite family (2^k-1,k) and the recovery of QRAC constructions matching a prior upper-bound conjecture are concrete advances. The connection to standard families of binary linear codes for optimal classical RACs is a further strength.

major comments (2)

[Geometric characterization section] The section presenting the geometric characterization of the worst-case problem: the claimed exact equivalence between the max-min success probability over deterministic classical encodings and the continuous minimization of the distance-like objective over [0,1]^L must be shown to be tight; if the relaxation admits values unattainable by any function of the input bits, the optimality proof for the classical construction on (2^k-1,k) and the resulting separation would not be established.
[(L,L-1) optimality subsection] The subsection on the (L,L-1) family: worst-case optimality is asserted only under a stated conjecture; the manuscript should either prove the conjecture, supply supporting numerical evidence for small L, or clearly delineate which results remain conditional.

minor comments (3)

[Geometric characterization section] Clarify the precise definition of the distance-like objective (including any normalization) and verify that the decoder that achieves the minimum is explicitly constructible from the chosen points.
[QRAC construction for (2^k-1,k)] In the explicit QRAC construction for (2^k-1,k), state the worst-case success probability achieved and compare it numerically to the classical optimum for at least one small k (e.g., k=2 or 3).
[Related work and (L,L-1) QRAC] Ensure all references to prior RAC and QRAC literature are complete; the recovery of the (L,L-1)-QRAC should cite the original conjecture it matches.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and constructive comments. We address each major comment below and will update the manuscript to strengthen the presentation.

read point-by-point responses

Referee: [Geometric characterization section] The section presenting the geometric characterization of the worst-case problem: the claimed exact equivalence between the max-min success probability over deterministic classical encodings and the continuous minimization of the distance-like objective over [0,1]^L must be shown to be tight; if the relaxation admits values unattainable by any function of the input bits, the optimality proof for the classical construction on (2^k-1,k) and the resulting separation would not be established.

Authors: We thank the referee for highlighting the need to rigorously establish tightness. The geometric reduction in the manuscript interprets the worst-case objective as a continuous optimization over points in [0,1]^L, where each coordinate is the marginal probability of a 1 in that position under a (possibly randomized) encoding. Because the objective is a convex combination of success probabilities and the feasible set is the convex hull of the deterministic 0-1 encodings, the minimum is attained at a vertex. We will add an explicit lemma in the revised Section 3 proving that any interior point can be replaced by a convex combination of deterministic encodings without increasing the objective value, confirming that the continuous minimum equals the discrete maximum-minimum success probability. This closes the gap and validates both the optimality claim for (2^k-1,k) and the separation. revision: yes
Referee: [(L,L-1) optimality subsection] The subsection on the (L,L-1) family: worst-case optimality is asserted only under a stated conjecture; the manuscript should either prove the conjecture, supply supporting numerical evidence for small L, or clearly delineate which results remain conditional.

Authors: We agree that the worst-case optimality statement for the (L,L-1) family is conditional on the conjecture. In the revision we will (i) explicitly mark all claims that depend on the conjecture, (ii) add a short paragraph delineating the conditional results, and (iii) include numerical verification for L=3 to L=7 obtained by exhaustive enumeration of small encodings, showing that the conjectured construction matches the computed optimum in every checked case. While we do not prove the conjecture here, the added evidence and clearer delineation address the referee's concern without overstating the result. revision: yes

Circularity Check

0 steps flagged

No significant circularity; geometric reductions and code constructions are independent

full rationale

The paper derives its optimality claims from explicit geometric reductions of the average-case RAC to selecting 2^k representatives in {0,1}^L and the worst-case to minimizing a distance-like objective over 2^k points in [0,1]^L, then invokes standard infinite families of binary linear codes for constructions. The classical-quantum separation for (2^k-1,k) follows from proving the classical optimum via this framework and exhibiting an explicit QRAC exceeding it. No step reduces by definition to its inputs, no fitted parameters are relabeled as predictions, and no load-bearing premise rests solely on self-citation; the framework is self-contained against external coding-theory benchmarks. The stated conjecture for (L,L-1) is noted but does not collapse the central derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the validity of the stated geometric reductions from RAC success probabilities to point-selection problems in the hypercube and unit cube; these reductions are presented as equivalences but their justification is not visible in the abstract.

axioms (1)

domain assumption The average-case and worst-case success probabilities of an (L,k)-RAC are exactly captured by the minimum-distance objectives over representatives in {0,1}^L and [0,1]^L respectively.
This equivalence is invoked to reduce the optimality question to a geometric selection problem.

pith-pipeline@v0.9.0 · 5809 in / 1325 out tokens · 62935 ms · 2026-05-21T00:00:41.149988+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 5: maximum average decoding success probability = 1 - min_{S subset {0,1}^L, |S|=2^k} d→_Cham({0,1}^L, S; dH/L)
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 9: worst-case optimality via min directed Hausdorff distance over conv(S) subset [0,1]^L with d∞

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · 2 internal anchors

[1]

Conjugate coding

Wiesner, S. Conjugate coding. ACM Sigact News, 15 (1):78–88, 1983. doi: 10.1145/1008908.1008920

work page doi:10.1145/1008908.1008920 1983
[2]

and Vazirani, U

Ambainis, A., Nayak, A., Ta-Shma, A. and Vazirani, U. Dense quantum coding and a lower bound for 1- way quantum automata. In Proceedings of the thirty- first annual ACM symposium on Theory of computing, pages 376–383, 1999. doi: 10.1145/301250.301347

work page doi:10.1145/301250.301347 1999
[3]

Fuller, B. et al. Approximate solutions of combinatorial problems via quantum relaxations. IEEE Transactions on Quantum Engineering, 5:1–15, 2024. doi: 10.1109/ TQE.2024.3421294

work page arXiv 2024
[4]

Almudever, and Sebastian Feld

Teramoto, K., Raymond, R. and Imai, H. The role of entanglement in quantum-relaxation based opti- mization algorithms. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 1, pages 543–553. IEEE, 2023. doi: 10.1109/QCE57702.2023.00068

work page doi:10.1109/qce57702.2023.00068 2023
[5]

Tamura, K. et al. Noise robustness of quantum relaxation for combinatorial optimization. IEEE Trans- actions on Quantum Engineering, 5:1–9, 2024. doi: 10.1109/TQE.2024.3439135

work page doi:10.1109/tqe.2024.3439135 2024
[6]

and Yamamoto, N

Kondo, R., Sato, Y., Raymond, R. and Yamamoto, N. Recursive quantum relaxation for combinatorial optimization problems. Quantum, 9:1594, 2025. doi: 10.22331/q-2025-01-15-1594. 13 101 102 103 Length of Original Bits L 0.5 0.6 0.7 0.8 0.9 1.0Maximum Success probability QRAC RAC (average) RAC (worst) Fig. 2. Achievable (conjecturally maximum) success probabi...

work page doi:10.22331/q-2025-01-15-1594 2025
[7]

Dubey, Christian Ufrecht, Maniraman Periyasamy, Axel Plinge, Christopher Mutschler & Daniel D

Sharma, M., Jin, Y., Lau, H.C. and Raymond, R. Quantum relaxation for solving multiple knapsack problems. In 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), vol- ume 1, pages 692–698. IEEE, 2024. doi: 10.1109/ QCE60285.2024.00086

work page arXiv 2024
[8]

and Pistoia, M

He, Z., Raymond, R., Shaydulin, R. and Pistoia, M. Non-variational quantum random access optimization with alternating operator ansatz. Scientific Reports, 15(1):29191, 2025. doi: 10.1038/s41598-025-13543-w

work page doi:10.1038/s41598-025-13543-w 2025
[9]

and Yamashiro, Y

Matsuyama, H. and Yamashiro, Y. Sampling-based quantum optimization algorithm with quantum relax- ation. In 2025 IEEE International Conference on Quan- tum Computing and Engineering (QCE), volume 01, pages 2323–2333, 2025. doi: 10.1109/QCE65121.2025. 00253

work page doi:10.1109/qce65121.2025 2025
[10]

and Ya- mashita, S

Iwama, K., Nishimura, H., Raymond, R. and Ya- mashita, S. Unbounded-error one-way classical and quantum communication complexity. In International Colloquium on Automata, Languages, and Program- ming, pages 110–121. Springer, 2007. doi: 10.1007/ 978-3-540-73420-8_12

work page 2007
[11]

Optimal lower bounds for quantum au- tomata and random access codes

Nayak, A. Optimal lower bounds for quantum au- tomata and random access codes. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 369–376. IEEE, 1999. doi: 10.1109/SFFCS.1999.814608

work page doi:10.1109/sffcs.1999.814608 1999
[12]

and Storgaard, S.A

Mančinska, L. and Storgaard, S.A. The geometry of bloch space in the context of quantum random access codes. Quantum Information Processing, 21(4):143,

work page
[13]

doi: 10.1007/s11128-022-03470-4

work page doi:10.1007/s11128-022-03470-4
[14]

and Tavakoli, A

Farkas, M., Miklin, N. and Tavakoli, A. Sim- ple and general bounds on quantum random access codes. Quantum, 9:1643, 2025. doi: 10.22331/ q-2025-02-25-1643

work page 2025
[15]

and Rai, A

Ambainis, A., Kravchenko, D., Sazim, S., Bae, J. and Rai, A. Quantum advantages in (n, d) 7! 1 random access codes. New Journal of Physics, 26(12):123023,

work page
[16]

doi: 10.1088/1367-2630/ad9bdf

work page doi:10.1088/1367-2630/ad9bdf
[17]

and Bouren- nane, M

Tavakoli, A., Hameedi, A., Marques, B. and Bouren- nane, M. Quantum random access codes using single d- level systems. Physical review letters, 114(17):170502,

work page
[18]

doi: 10.1103/PhysRevLett.114.170502

work page doi:10.1103/physrevlett.114.170502
[19]

and Raymond, R

Imamichi, T. and Raymond, R. Constructions of quantum random access codes. In Proceedings of the Asian Quantum Information Symposium (AQIS),

work page
[20]

URL https://research.ibm.com/publications/ constructions-of-quantum-random-access-codes

work page
[21]

and Imai, H

Teramoto, K., Raymond, R., Wakakuwa, E. and Imai, H. Quantum-relaxation based optimization algorithms: theoretical extensions. arXiv preprint arXiv:2302.09481, 2023. doi: 10.48550/arXiv.2302. 09481

work page internal anchor Pith review doi:10.48550/arxiv.2302 2023
[22]

Improved classical and quantum random access codes

Liabøtrø, O. Improved classical and quantum random access codes. Physical Review A, 95(5):052315, 2017. doi: 10.1103/PhysRevA.95.052315

work page doi:10.1103/physreva.95.052315 2017
[23]

Analytical construction of (n, n 1) quan- tum random access codes saturating the conjectured bound

Suzuki, T. Analytical construction of (n, n 1) quan- tum random access codes saturating the conjectured bound. arXiv preprint arXiv:2601.19190, 2026. doi: https://doi.org/10.48550/arXiv.2601.19190

work page doi:10.48550/arxiv.2601.19190 2026
[24]

and Wolf, H.C

Barrow, H.G., Tenenbaum, J.M., Bolles, R.C. and Wolf, H.C. Parametric correspondence and chamfer matching: Two new techniques for image matching. In Proceedings of the 5th International Joint Conference on Artificial Intelligence (IJCAI), pages 659–663, 1977. doi: 10.5555/1622943.1622971

work page doi:10.5555/1622943.1622971 1977
[25]

and Jain, A.K

Dubuisson, M.P. and Jain, A.K. A modified haus- dorff distance for object matching. In Proceedings of 12th international conference on pattern recogni- tion, volume 1, pages 566–568. IEEE, 1994. doi: 10.1109/ICPR.1994.576361

work page doi:10.1109/icpr.1994.576361 1994
[26]

Quantum Random Access Codes with Shared Randomness

Ambainis, A., Leung, D., Mancinska, L. and Ozols, M. Quantum random access codes with shared ran- domness. arXiv preprint arXiv:0810.2937, 2008. doi: 10.48550/arXiv.0810.2937

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.0810.2937 2008
[27]

Grundzüge der Mengenlehre

Hausdorff, F. Grundzüge der Mengenlehre. Göschens Lehrbücherei/Gruppe I: Reine und Angewandte Math- ematik Series. Von Veit, 1914. ISBN 9783110989854. 14 doi: 10.1007/BF01999507

work page doi:10.1007/bf01999507 1914
[28]

Gurobi Optimizer Refer- ence Manual, 2026

Gurobi Optimization, LLC. Gurobi Optimizer Refer- ence Manual, 2026. URL https://www.gurobi.com. 15

work page 2026

[1] [1]

Conjugate coding

Wiesner, S. Conjugate coding. ACM Sigact News, 15 (1):78–88, 1983. doi: 10.1145/1008908.1008920

work page doi:10.1145/1008908.1008920 1983

[2] [2]

and Vazirani, U

Ambainis, A., Nayak, A., Ta-Shma, A. and Vazirani, U. Dense quantum coding and a lower bound for 1- way quantum automata. In Proceedings of the thirty- first annual ACM symposium on Theory of computing, pages 376–383, 1999. doi: 10.1145/301250.301347

work page doi:10.1145/301250.301347 1999

[3] [3]

Fuller, B. et al. Approximate solutions of combinatorial problems via quantum relaxations. IEEE Transactions on Quantum Engineering, 5:1–15, 2024. doi: 10.1109/ TQE.2024.3421294

work page arXiv 2024

[4] [4]

Almudever, and Sebastian Feld

Teramoto, K., Raymond, R. and Imai, H. The role of entanglement in quantum-relaxation based opti- mization algorithms. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 1, pages 543–553. IEEE, 2023. doi: 10.1109/QCE57702.2023.00068

work page doi:10.1109/qce57702.2023.00068 2023

[5] [5]

Tamura, K. et al. Noise robustness of quantum relaxation for combinatorial optimization. IEEE Trans- actions on Quantum Engineering, 5:1–9, 2024. doi: 10.1109/TQE.2024.3439135

work page doi:10.1109/tqe.2024.3439135 2024

[6] [6]

and Yamamoto, N

Kondo, R., Sato, Y., Raymond, R. and Yamamoto, N. Recursive quantum relaxation for combinatorial optimization problems. Quantum, 9:1594, 2025. doi: 10.22331/q-2025-01-15-1594. 13 101 102 103 Length of Original Bits L 0.5 0.6 0.7 0.8 0.9 1.0Maximum Success probability QRAC RAC (average) RAC (worst) Fig. 2. Achievable (conjecturally maximum) success probabi...

work page doi:10.22331/q-2025-01-15-1594 2025

[7] [7]

Dubey, Christian Ufrecht, Maniraman Periyasamy, Axel Plinge, Christopher Mutschler & Daniel D

Sharma, M., Jin, Y., Lau, H.C. and Raymond, R. Quantum relaxation for solving multiple knapsack problems. In 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), vol- ume 1, pages 692–698. IEEE, 2024. doi: 10.1109/ QCE60285.2024.00086

work page arXiv 2024

[8] [8]

and Pistoia, M

He, Z., Raymond, R., Shaydulin, R. and Pistoia, M. Non-variational quantum random access optimization with alternating operator ansatz. Scientific Reports, 15(1):29191, 2025. doi: 10.1038/s41598-025-13543-w

work page doi:10.1038/s41598-025-13543-w 2025

[9] [9]

and Yamashiro, Y

Matsuyama, H. and Yamashiro, Y. Sampling-based quantum optimization algorithm with quantum relax- ation. In 2025 IEEE International Conference on Quan- tum Computing and Engineering (QCE), volume 01, pages 2323–2333, 2025. doi: 10.1109/QCE65121.2025. 00253

work page doi:10.1109/qce65121.2025 2025

[10] [10]

and Ya- mashita, S

Iwama, K., Nishimura, H., Raymond, R. and Ya- mashita, S. Unbounded-error one-way classical and quantum communication complexity. In International Colloquium on Automata, Languages, and Program- ming, pages 110–121. Springer, 2007. doi: 10.1007/ 978-3-540-73420-8_12

work page 2007

[11] [11]

Optimal lower bounds for quantum au- tomata and random access codes

Nayak, A. Optimal lower bounds for quantum au- tomata and random access codes. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 369–376. IEEE, 1999. doi: 10.1109/SFFCS.1999.814608

work page doi:10.1109/sffcs.1999.814608 1999

[12] [12]

and Storgaard, S.A

Mančinska, L. and Storgaard, S.A. The geometry of bloch space in the context of quantum random access codes. Quantum Information Processing, 21(4):143,

work page

[13] [13]

doi: 10.1007/s11128-022-03470-4

work page doi:10.1007/s11128-022-03470-4

[14] [14]

and Tavakoli, A

Farkas, M., Miklin, N. and Tavakoli, A. Sim- ple and general bounds on quantum random access codes. Quantum, 9:1643, 2025. doi: 10.22331/ q-2025-02-25-1643

work page 2025

[15] [15]

and Rai, A

Ambainis, A., Kravchenko, D., Sazim, S., Bae, J. and Rai, A. Quantum advantages in (n, d) 7! 1 random access codes. New Journal of Physics, 26(12):123023,

work page

[16] [16]

doi: 10.1088/1367-2630/ad9bdf

work page doi:10.1088/1367-2630/ad9bdf

[17] [17]

and Bouren- nane, M

Tavakoli, A., Hameedi, A., Marques, B. and Bouren- nane, M. Quantum random access codes using single d- level systems. Physical review letters, 114(17):170502,

work page

[18] [18]

doi: 10.1103/PhysRevLett.114.170502

work page doi:10.1103/physrevlett.114.170502

[19] [19]

and Raymond, R

Imamichi, T. and Raymond, R. Constructions of quantum random access codes. In Proceedings of the Asian Quantum Information Symposium (AQIS),

work page

[20] [20]

URL https://research.ibm.com/publications/ constructions-of-quantum-random-access-codes

work page

[21] [21]

and Imai, H

Teramoto, K., Raymond, R., Wakakuwa, E. and Imai, H. Quantum-relaxation based optimization algorithms: theoretical extensions. arXiv preprint arXiv:2302.09481, 2023. doi: 10.48550/arXiv.2302. 09481

work page internal anchor Pith review doi:10.48550/arxiv.2302 2023

[22] [22]

Improved classical and quantum random access codes

Liabøtrø, O. Improved classical and quantum random access codes. Physical Review A, 95(5):052315, 2017. doi: 10.1103/PhysRevA.95.052315

work page doi:10.1103/physreva.95.052315 2017

[23] [23]

Analytical construction of (n, n 1) quan- tum random access codes saturating the conjectured bound

Suzuki, T. Analytical construction of (n, n 1) quan- tum random access codes saturating the conjectured bound. arXiv preprint arXiv:2601.19190, 2026. doi: https://doi.org/10.48550/arXiv.2601.19190

work page doi:10.48550/arxiv.2601.19190 2026

[24] [24]

and Wolf, H.C

Barrow, H.G., Tenenbaum, J.M., Bolles, R.C. and Wolf, H.C. Parametric correspondence and chamfer matching: Two new techniques for image matching. In Proceedings of the 5th International Joint Conference on Artificial Intelligence (IJCAI), pages 659–663, 1977. doi: 10.5555/1622943.1622971

work page doi:10.5555/1622943.1622971 1977

[25] [25]

and Jain, A.K

Dubuisson, M.P. and Jain, A.K. A modified haus- dorff distance for object matching. In Proceedings of 12th international conference on pattern recogni- tion, volume 1, pages 566–568. IEEE, 1994. doi: 10.1109/ICPR.1994.576361

work page doi:10.1109/icpr.1994.576361 1994

[26] [26]

Quantum Random Access Codes with Shared Randomness

Ambainis, A., Leung, D., Mancinska, L. and Ozols, M. Quantum random access codes with shared ran- domness. arXiv preprint arXiv:0810.2937, 2008. doi: 10.48550/arXiv.0810.2937

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.0810.2937 2008

[27] [27]

Grundzüge der Mengenlehre

Hausdorff, F. Grundzüge der Mengenlehre. Göschens Lehrbücherei/Gruppe I: Reine und Angewandte Math- ematik Series. Von Veit, 1914. ISBN 9783110989854. 14 doi: 10.1007/BF01999507

work page doi:10.1007/bf01999507 1914

[28] [28]

Gurobi Optimizer Refer- ence Manual, 2026

Gurobi Optimization, LLC. Gurobi Optimizer Refer- ence Manual, 2026. URL https://www.gurobi.com. 15

work page 2026