Quantum Random Access Codes with Shared Randomness

1.1 Random access codes

• A random access code compresses a message while allowing recovery of any requested input bit; the paper focuses on encoding n bits into one bit or one qubit.Success probability must exceed one half, since guessing achieves one half.Source: §1.1 · p. 3
• The introduction distinguishes classical and quantum recovery: measuring a qubit can disturb its state, so recovering one bit need not permit recovery of the rest.It also notes applications of QRACs in communication complexity, network coding, locally decodable codes, and quantum state learning.Source: §1.1 · p. 3, §1.2 · p. 3

1.2 History and applications

• Shared randomness lets the parties coordinate their strategy, and the paper reports QRACs with p > 1/2 for every n ≥ 1.The paper also outlines classical shared-randomness codes, quantum upper bounds, and constructions for selected small n.Source: §1.2 · p. 4, §1.3 · p. 4

1.3 Outline of results

• The paper’s roadmap covers classical codes with shared randomness, quantum codes and upper bounds, then numerical and symmetric constructions for small n.It also identifies a concluding summary, open problems, and possible generalizations.Source: §1.3 · p. 4

2.1 Types of classical encoding-decoding strategies

• A pure classical strategy is a deterministic encoding and decoding scheme, while mixed strategies randomize locally and shared-randomness strategies are distributions over pure strategies.The section also gives an example in which Alice and Bob use shared randomness to choose a bit position and Bob uses a private random bit when another position is requested.Source: §2.1 · pp. 4–5
• Deterministic independent encoding and decoding have worst-case success probability 0, while guessing provides a baseline of 1/2.The section presents cooperation through a shared random string as an alternative strategy setting.Source: §2.1 · pp. 4–5

2.2 Yao’s principle

• Yao’s principle lets the authors analyze worst-case randomized performance through deterministic strategies under an input distribution; for RACs, uniform inputs are the hardest distribution.Shared input randomization makes a pure strategy’s uniform-average success equal to a strategy’s worst-case success.Source: §2.2 · pp. 5–6

2.3.1 Optimal strategy

• The optimal pure classical n 7→1 RAC uses majority encoding and identity decoding, and shared randomization converts it into an optimal strategy with shared randomness.The majority encoder outputs 0 when the input Hamming weight is below n/2 and 1 otherwise.Source: §2.2 · p. 7, §2.3.1 · p. 8

2.3.2 Asymptotic bounds

• As n increases, the optimal pure classical code’s success probability approaches 1/2; odd- and even-n upper and lower bounds are also presented.The passage identifies 1/2 as the success probability achievable by guessing.Source: Figure 1 · p. 9, §2.3.2 · p. 10

3.1 Visualizing a qubit

• Two visualizations are introduced for qubit random access codes: the Bloch sphere and a unit disk representation.The unit disk approach is presented as a representation not known to have appeared elsewhere.Source: §3.1 · p. 10, §3.1.2 · p. 12

3.1.1 Bloch sphere representation

• Each pure qubit state corresponds one-to-one with a point on the unit sphere in R3, with θ and ϕ serving as its parameters.The states |0⟩ and |1⟩ are the poles, where ϕ does not affect the physical state.Source: §3.1.1 · p. 10
• An orthogonal qubit measurement uses two antipodal Bloch vectors, and outcome probabilities can be interpreted through projections onto their axis.For the projection described, p0 = d1/2, where d1 is the distance from the projection to |ψ1⟩.Source: §3.1.1 · pp. 11–12

3.1.2 Unit disk representation

• The unit disk represents each pure state with one complex number β; its boundary points all represent |1⟩, and gluing that boundary recovers the Bloch sphere.The representation also encodes finite state sets as polynomials whose roots are the corresponding β values.Source: §3.1.2 · p. 12
• The Hadamard transformation reshapes the disk’s constant-θ and constant-ϕ curves, mapping the origin to |+⟩ and the boundary to |−⟩.The origin maps to the right pole, while the unit circle maps to the left pole in the transformed disk.Source: §3.1.2 · p. 13
• Finite sets of qubit states can be encoded as polynomials with those states’ complex representatives as roots.For the polyhedral-state examples discussed later, the scalar can be chosen so the polynomial has integer coefficients.Source: §3.1.2 · p. 13

3.2 Types of quantum encoding-decoding strategies

• A quantum strategy with shared randomness is a probability distribution over pure quantum strategies, and its worst-case success can be bounded through average success over pure strategies.The section also defines pure strategies by an encoding function and a measurement for each bit to be recovered.Source: §3.2 · pp. 13–14
• Quantum strategies with shared randomness cannot simulate certain classical strategies, including fixed-output strategies, but the paper says this ability gives no advantage.The authors describe these as the most powerful quantum encoding-decoding strategies when local and shared classical randomness are allowed.Source: §3.2 · p. 14

3.3 Known quantum RACs

• The section contrasts the known 2→1 and 3→1 quantum codes with classical 2→1 codes, whose worst-case success cannot exceed 1/2 in the mixed setting.It also notes that a quantum 4→1 scheme cannot exist.Source: §3.3 · p. 14

3.3.1 The 2 7→1 QRAC

• For 2→1 QRACs, the encoding uses two mutually orthogonal pairs of antipodal Bloch vectors, with measurement bases along the x and y axes.The four regions cut out by the measurement planes each encode one string; optimal states are as far from both planes as possible.Source: §3.3.1 · p. 14
• The 2→1 QRAC has the same success probability for every input string and requested bit.Its encoding uses the four vertices of a square inscribed in the xy-plane, with measurements along the x and y axes.Source: §3.3.1 · pp. 14–15

3.3.2 The 3 7→1 QRAC

• For 3→1 QRACs, three orthogonal measurement planes divide the sphere into eight regions, with one string encoded in each region.The optimal encoding states are the eight vertices of a cube inscribed in the Bloch sphere.Source: §3.3.2 · p. 15
• The 3→1 QRAC has the same success probability in all cases, using cube-vertex encoding states and three orthogonal measurement directions.The measurement directions are the three pairs of antipodal vertices of an octahedron.Source: §3.3.2 · p. 15

3.3.3 Impossibility of the 4 7→1 QRAC

• Four great circles divide the Bloch sphere into at most 14 regions, fewer than the 16 needed to encode four strings separately, so a 4→1 QRAC cannot achieve success above 1/2.The bound follows by projecting three circles to three plane lines, which make at most seven regions; each corresponds to two opposite sphere regions.Source: §3.3.3 · pp. 15–16, Figure 7 · p. 16, Figure 8 · p. 16

• For fixed measurements, maximizing the success probability reduces to choosing the measurement directions, because the optimal encoding is already determined by them.The encoding vectors align with the corresponding summed measurement vectors when those are nonzero.Source: §3.4 · p. 17
• When all bits use the same measurement, majority encoding makes the resulting QRAC as good as the optimal classical RAC.Source: §3.4 · p. 17
• The claim that using the same measurement for every bit is the worst decoding strategy remains a conjecture.The authors state that they have not proved it.Source: §3.4 · p. 17
• A broader conjecture states that every measurement choice admits an encoding at least as good as the optimal classical RAC.Source: §3.4 · p. 17

3.5 Relation to a random walk in R3

• With optimal encoding, success probability is expressed through the average distance traveled by a random walk taking step vi or −vi with equal probability.Source: §3.5 · p. 18

3.6 Upper bound

• For any n, the QRAC success probability is at most 1/2 + 1/(2√n), and the known 2→1 and 3→1 codes attain this bound.Source: §3.6 · p. 19
• The upper-bound intuition contrasts n mutually orthogonal directions in R^n with the three-dimensional Bloch-vector setting, which cannot provide more than three mutually orthogonal directions.Source: §3.6 · p. 19

• Enhanced strategies allow constant decoding functions alongside orthogonal measurements, and shared-randomness strategies are distributions over such strategies.Source: §3.7 · p. 20
• The paper states that enhanced QRACs with shared randomness cover the most general model when classical randomness is allowed.It also states that any classical RAC can be simulated by the corresponding type of quantum RAC.Source: §3.7 · p. 20
• For any n, even the general model has success probability at most 1/2 + 1/(2√n).The bound also holds when mixed encodings and POVM measurements are allowed.Source: §3.6 · p. 19, §3.7 · pp. 20–21
• The known 2→1 and 3→1 QRACs attain the general-model upper bound, while for n = 4 the bound gives p ≤ 3/4.Source: §3.7 · p. 21

3.8.1 Lower bound by random measurements

• Randomly chosen measurement directions yield a lower bound related to the average distance of a random walk taking unit steps in random directions.The asymptotic expression formally applies only for large n; sampling suggests it is below the actual success probability for small n.Source: §3.8.1 · pp. 21–22

3.8.2 Lower bound by orthogonal measurements

• For the orthogonal construction, measurement directions are distributed roughly equally among the three coordinate axes, reducing the walk calculation to a cubic-lattice setting.Source: §3.8.2 · p. 23
• The orthogonal-measurement construction gives a better lower bound than random measurements and requires less shared randomness.Its periodic pattern of length 6 is attributed to equal coordinate-axis step counts and the odd-even behavior of one-dimensional walks.Source: §3.8.2 · p. 23

4 Constructions of QRACs with SR

• The section considers constructions of quantum random access codes with shared randomness for particular n, first describing numerically obtained QRACs, then constructing QRACs with high degree of symmetry, and finally comparing both kinds.Source: §4 · p. 23
• The comparison considers codes using random measurements and orthogonal measurements, with numerical and asymptotic success-probability values for the former.Table 1 describes the comparison and identifies the values it reports, but the supplied passage does not include those values.Source: Table 1 · p. 23
• The coordinate-axis lower bound is better than the asymptotic random-measurement bound except at n = 6.Figure 10 notes a periodic pattern of length 6.Source: Figure 10 · p. 24

4.1 Numerical results

• Numerical success probabilities for the n→1 QRACs with shared randomness are summarized in Table 2 and Figure 11; the authors omit detailed discussion of n = 7, 8, and n ≥ 10.The n = 10 code is symmetric, whereas the n = 11 and 12 codes have almost no discernible symmetry.Source: Table 2 · p. 24, §4.1 · p. 25, Figure 11 · p. 26

4.1.1 The 2 7→1 and 3 7→1 QRACs with SR

• Numerical optimization recovers the optimal 2→1 and 3→1 shared-randomness QRACs, whose encoding points form a square and a cube, respectively.The passage identifies these as the optimal codes discussed earlier but does not provide their success-probability values here.Source: §4.1.1 · p. 25

4.1.2 The 4 7→1 QRAC with SR

• A 4→1 shared-randomness QRAC is constructed by combining 2→1 and 3→1 schemes, using the 3→1 scheme when the last two bits agree and the 2→1 scheme otherwise.The authors state that they do not know whether this code is optimal.Source: §4.1.2 · pp. 25, 27, 28

4.1.3 The 5 7→1 QRAC with SR

• Using input randomization, the method obtains the same success probability for any input, making the reported success probability input-independent rather than specific to one input.Source: §4.1.3 · p. 30

4.1.4 The 6 7→1 QRAC with SR

• The 6→1 construction uses measurement directions at cuboctahedron vertices and encodes strings at vertices of a cube, truncated octahedron, or octahedron; input randomization yields its reported success probability.The 64 strings divide among these three types in counts of 16, 24, and 24.Source: §4.1.4 · pp. 30, 31, 33

4.1.5 The 9 7→1 QRAC with SR

• The 9→1 code combines three 3→1 QRACs, with encoding points formed by projecting a 4×4×4 cubic lattice onto the Bloch-ball surface.The lattice consists of vertices of eight equal cubes, one in each octant.Source: §4.1.5 · p. 33
• The three polyhedron-associated string types use a cube (8 vertices, 28 strings per vertex), a deformed truncated cube (24, 3), and a deformed small rhombicuboctahedron (24, 9).Each string type is encoded into vertices of its corresponding polyhedron.Source: §4.1.5 · pp. 33–34, Figure 22 · p. 35
• The coefficients β for the corresponding qubit states are roots of (36β^8 + 24β^4 + 1)^28(1444β^8 + 760β^4 + 81)^3(484β^8 + 440β^4 + 1)^9.Source: §4.1.5 · p. 34
• Input randomization is used to obtain a success probability.Source: §4.1.5 · p. 34

4.2 Symmetric constructions

• The section asks whether numerical codes for n ≥ 4 are optimal and whether their quality is connected to symmetry; it concludes symmetric codes are not necessarily optimal.The authors also speculate that properties beyond symmetry could help construct good QRACs.Source: §4.2 · p. 35

4.2.1 Symmetric great circle arrangements

• The authors use “symmetric codes” descriptively: their empirical approach does not require a formal symmetry criterion, and each proposed criterion fails for at least one example.The criteria include rotational equivalence of great circles and regular or uniform spherical pieces.Source: §4.2.1 · p. 36, Triangular symmetry groups · p. 36
• Most numerical codes exhibit equal-triangle tilings, while two triangular symmetry groups absent from those codes are used to construct symmetric 9→1 and 15→1 QRACs.The authors also select four marked polyhedra whose great-circle arrangements do not appear in numerical codes for further constructions.Source: Triangular symmetry groups · pp. 37–38, Table 5 · p. 37, Table 6 · p. 38

4.2.2 Symmetric 4 7→1 QRAC with SR

• The symmetric 4→1 QRAC has lower success probability than the numerically obtained 4→1 code, despite its higher symmetry.Its four measurement planes partition the Bloch sphere into 14 parts, and the corresponding great-circle grid is a cuboctahedron projection.Source: §4.2.2 · pp. 39, 41, Figure 26 · p. 39

4.2.3 Symmetric 6 7→1 QRAC with SR

• The symmetric 6→1 construction uses six measurement directions from antipodal vertex pairs and encodes strings at icosahedron or dodecahedron vertices.The union of those polyhedra is called a pentakis dodecahedron.Source: §4.2.3 · p. 41, Figure 28 · p. 41

4.2.4 Symmetric 9 7→1 QRAC with SR

• The symmetric 9→1 code combines the coordinate-axis measurements of a 3→1 code with the six measurements used for a 6→1 code.Its great circles come from the normalized disdyakis dodecahedron arrangement.Source: §4.2.4 · pp. 41–42, Figure 29 · p. 42

4.2.5 Symmetric 15 7→1 QRAC with SR

• The symmetric 15→1 code uses 15 antipodal measurement-direction pairs from vertices of the icosidodecahedron.Its great circles correspond to the normalized disdyakis triacontahedron arrangement.Source: §4.2.5 · p. 42, Figure 30 · p. 42

4.3 Discussion

• None of the discussed symmetric codes is optimal, although their success probabilities do not differ much from numerical codes.The symmetric 3→1 code is optimal, while the 6→1 code may also be optimal because the authors did not improve it.Source: §4.3 · pp. 42–43
• For qubits, vectors from different MUBs are orthogonal, and the x-, y-, and z-axis measurements form three such bases.Numerical 2→1, 3→1, 4→1, and 9→1 codes use MUBs throughout; three of the five bases in the numerical 5→1 code are also MUBs.Source: §4.3 · p. 43
• The symmetric 4→1 construction uses a SIC-POVM whose four Bloch vectors form a tetrahedron.The comparison describes the numerical code as less symmetric and notes that two of its measurement directions coincide.Source: §4.3 · p. 43
• The numerical 4→1 QRAC has higher success probability than the symmetric SIC-POVM-based code.The numerical code uses MUBs; the symmetric code appears to leave two of its 16 strings without influence on success probability.Source: §4.3 · pp. 43–44
• Measurement-vector orthogonality seems more important than symmetry for code performance.Comparisons of 9→1 and 15→1 codes likewise motivate roughly n/3 measurements along each coordinate axis as a construction heuristic.Source: §4.3 · p. 44

5.1 Summary

• Alice's optimal classical n→1 RAC with shared randomness XORs the input with shared random bits, sends the majority, and lets Bob XOR the received bit with the requested shared bit.The paper gives the code's asymptotic success probability in equation (27).Source: §5.1 · p. 44
• The optimal quantum RAC with shared randomness is bounded above and below, and the paper compares classical and quantum success probabilities in Figure 31.The cited passages do not provide the inequalities' values.Source: §5.1 · p. 44, Figure 31 · p. 45

5.2 Open problems for n 7→1 QRACs

• Orthogonal-measurement QRACs outperform random-measurement lower bounds, but the authors lack an asymptotic expression for the orthogonal-measurement bound.The open problems also ask for proofs of optimality and uniqueness of numerical codes for n≥4, and for a proof of the Homer conjecture comparing quantum and classical RACs with shared randomness.Source: §5.2 · p. 44
• Figure 31 compares optimal classical RACs, numerical QRACs, and quantum upper and lower bounds.Figure 32 focuses on the gaps between the quantum upper bound, numerical codes, and two lower bounds.Source: Figure 31 · p. 45, Figure 32 · p. 46

5.3 Possible generalizations

• For d>2, MUB-based QRACs have been explored, but the qubit encoding rule may yield a non-positive-semidefinite matrix and thus an invalid density matrix.A sufficiently short generalized Bloch vector gives a valid mixed state; better choices depend on the incompletely characterized shape of the valid-state region.Source: §5.3 · p. 47
• The authors suggest extending their upper bound using generalized Bloch vectors and considering shared entanglement, higher-dimensional systems, or recovering multiple bits.For qudits, basis states correspond to simplex vertices, while orthogonal Bloch-vector directions connect to measurements in mutually unbiased bases.Source: §5.3 · pp. 45, 47

A Combinatorial interpretation of sums

• The appendix interprets the sums in equations (22) and (23) as counts of subsets with a marked element.Counting by choosing the subset first or the marked element first yields the same totals.Source: A Combinatorial interpretation of sums · pp. 47–48
• For even n, complement pairing matches every subset larger than half the remaining elements to a smaller subset, so each class contains half of all subsets.The passage specifies the count as 2^(2m−2) when n=2m.Source: A Combinatorial interpretation of sums · p. 48
• For odd n, subsets of the balanced size map to themselves, while larger and smaller subsets pair by complementation.The two counting approaches then give the same results for both odd and even n.Source: A Combinatorial interpretation of sums · p. 48

B POVMs versus orthogonal measurements

• For an n→1 QRAC, the relevant POVM has two outcomes and can be specified by E0 and E1=I−E0.The text diagonalizes E0 in a basis and constrains its eigenvalues through positive semidefiniteness.Source: B POVMs versus orthogonal measurements · p. 48
• The direct simulation measures in an orthogonal basis and probabilistically post-processes the outcome, but that process is not itself a probabilistic combination of enhanced orthogonal measurements.The construction instead uses the state-independent lower bounds on the two output probabilities to assign mixture weights.Source: B POVMs versus orthogonal measurements · p. 49
• Any two-outcome qubit POVM can be simulated by a probabilistic combination of enhanced orthogonal measurements with identical outcome probabilities.At least one of the two mixed-output weights c01 and c10 is zero.Source: B POVMs versus orthogonal measurements · p. 50
• The limiting cases recover random guessing, a projective measurement, or a constant output, depending on a and b.For a=b=1/2 the process is random guessing; a=1,b=0 gives a projective measurement, and a=b=1 gives constant output 0.Source: B POVMs versus orthogonal measurements · p. 50