July 11, 2026
A binary \((n,m)\) quantum random access code (QRAC) compresses an \(n\)-bit classical string into an \(m\)-qubit quantum state, from which a decoder attempts to recover a randomly selected target bit. Of particular interest is the optimal average probability of success, \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\), which is numerically conjectured to satisfy the bound \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\leq \frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}}\). Recent constructions of \((n,n-1)\) QRACs by Suzuki and \((n,n-2)\) QRACs by Akibue et al. meet this bound exactly, raising the question of their strict optimality. In this work, we settle this question by proving the conjectured upper bound for \(m\in\{n-1,n-2\}\), thereby precisely determining \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-1}\) and \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-2}\). The proof utilizes a translation recently studied by Lin and de Wolf from local to global reconstruction via pretty good measurement, along with dimensional and positive-semidefinite constraints on an induced channel.
Introduction.– The fundamental limits of data compression are a central theme in quantum information theory. Though Holevo’s theorem [1] shows that a system of \(m\) qubits cannot be used to retrieve more than \(m\) bits of classical information, this global limitation does not fully capture how reliably individual bits of a classical string can be accessed when \(n\) bits are compressed into \(m\) qubits. Quantum random access codes (QRACs), introduced by Ambainis et al. [2], formalize this tradeoff between compressibility and retrievability. In an \((n,m)\) binary QRAC, a classical string \(x\in\{0,1\}^n\) is encoded into an \(m\)-qubit state \(\rho_x\), from which a decoder attempts to recover a randomly selected target bit as reliably as possible. To avoid degenerate cases we assume throughout that \(0<m<n\). A key performance metric is the optimal average probability of success, \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\).
Quantum Random Access Codes (QRACs) serve as a fundamental primitive in quantum information processing, bridging quantum technologies and theoretical computer science. As analytical tools, they provide rigorous frameworks for proving lower bounds in one-way quantum communication complexity [3], [4] and constructions and analysis of quantum network coding [5]. They also offer powerful techniques for bounding classical primitives in theoretical computer science, including locally decodable codes [6] and private information retrieval [7]. Operationally, QRACs underlie a range of modern quantum information tasks, including the certification of uncharacterized devices via dimension witnesses [8], semi-device-independent cryptography [9]–[11], high-dimensional communication [12], and self-testing [13].
Due to the fundamental significance of QRACs, a precise characterization of \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\) is highly desirable. While much progress has been made in the literature through various bounds and QRAC constructions [2], [13]–[22], exact characterizations of \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\) are currently known only in a handful of cases, namely \((n,m)=(2,1), (3,1)\) which follow from [2], [15], and \((n,m)=(3,2),(4,2),(6,2)\) which follow from [16], [17]. For each of these cases, \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\) has the form, \[\begin{align} P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}&= \frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}},\\ \forall (n,m)&\in\{(2,1),(3,1),(3,2),(4,2),(6,2)\}.\notag \end{align}\] Remarkably, the same form also appears in a numerically conjectured general upper bound noted in [20], [21]: \[P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m} \stackrel{?}{\le} \frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}}. \label{eq:conjbound}\tag{1}\] It is known that the bound 1 holds if \(m\in\{1,2\}\), because the bound \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\leq \frac{1}{2}+\frac{1}{2}\sqrt{\frac{2^{m-1}}{n}}\) is established in [17], and for \(m\in\{1,2\}\) we have \(2^{m-1}=m\).
The conjectured bound 1 is especially intriguing for \(m\in\{n-1,n-2\}\), because for these settings there exist QRAC constructions that achieve it. Specifically the \((n,n-1)\) QRACs constructed by Suzuki in [20], and the \((n,n-2)\) QRACs constructed by Akibue et al. in [21], achieve average success probability \(\frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}}\) for \(m=n-1\) and \(m=n-2\), respectively. Thus, if the conjectured bound 1 can be proved for \(m\in\{n-1,n-2\}\), then it would prove the optimality of both constructions, and thus determine the precise values of \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-1}\) and \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-2}\). Indeed, a proof of 1 for \(m\in\{n-1,n-2\}\) is the main contribution of this work.
Our converse utilizes a translation from local to global reconstruction via pretty good measurement (PGM), that is studied in [19]. The full-string PGM [23], [24] produces an entire candidate string \(Y^{\mathfrak{C},\tiny PGM}\) for the uniform string \(X\) encoded by a QRAC \(\mathfrak{C}\). Lin and de Wolf in [19] show that reducing the outcome of the global PGM to the \(i^{th}\) bit by summing over the possible outcomes for other bits, induces exactly the one-bit PGM for the \(i^{th}\) bit.
Building on this foundation, we find upper and lower bounds on the expected Hamming distance \(\Delta^{\mathfrak{C},\tiny PGM}:=\mathbb{E}[d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM})]\). For the upper bound, if a given QRAC \(\mathfrak{C}\) has average success probability \(P^{\mathfrak{C}}\), then by averaging over one-bit PGMs we show that \(\Delta^{\mathfrak{C},\tiny PGM} \leq \frac{n}{2}\left(1-\left(2P^{\mathfrak{C}}-1\right)^2\right)\). For the lower bound, based on the full-string PGM we show that when \(m\in\{n-1,n-2\}\), then \(\Delta^{\mathfrak{C},\tiny PGM}\geq \frac{n-m}{2}\). Combining these bounds produces the desired proof of 1 with \(m\in\{n-1,n-2\}\) for the QRAC \(\mathfrak{C}\). Since the bound holds for any \((n,m)\) QRAC \(\mathfrak{C}\) with \(m\in\{n-1,n-2\}\), it also holds for the optimal average success probability.
QRAC Model.– Let \([n]=\{1,\ldots,n\}\). A binary \((n,m)\) QRAC \(\mathfrak{C}\) is specified as a tuple \((\{\rho_x^{\mathfrak{C}}\}_{x\in\{0,1\}^n}, \{M^{\mathfrak{C}}_{0|i},M^{\mathfrak{C}}_{1|i}\}_{i\in[n]})\) where \(\{\rho^{\mathfrak{C}}_x\}_{x\in\{0,1\}^n}\) is an ensemble of quantum states on a Hilbert space of dimension at most \(2^m\), and \(\{M^{\mathfrak{C}}_{0|i},M^{\mathfrak{C}}_{1|i}\}\) is a binary decoding POVM for the \(i^{th}\) bit. The encoder obtains a uniformly random binary string \(X\in\{0,1\}^n\) and maps any realization \(X=x=x_1x_2\cdots x_n\) to the corresponding quantum state \(\rho_x^{\mathfrak{C}}\). The decoder is given the encoded quantum state, along with an independently generated uniformly random index \(\mathcal{I}\in[n]\). Given \(\rho^{\mathfrak{C}}_x\) and the realization \(\mathcal{I}=i\), the decoder produces \(Y_i^{\mathfrak{C}}\) as the measurement outcome of the POVM \(\{M^{\mathfrak{C}}_{0|i},M^{\mathfrak{C}}_{1|i}\}\) applied to \(\rho^{\mathfrak{C}}_x\). Define the coordinate-wise success probability of \(\mathfrak{C}\) as \[\begin{align} p_i^{\mathfrak{C}}&:=\mathbb{P}(Y_i^{\mathfrak{C}}=X_i\mid \mathcal{I}=i)\notag\\ &= \frac{1}{2^n}\sum_{x\in\{0,1\}^n}\mathbb{P}(Y_i^{\mathfrak{C}}=X_i\mid X=x, \mathcal{I}=i)\notag\\ &=\frac{1}{2^n}\sum_{x\in\{0,1\}^n}\mathop{\mathrm{Tr}}\!\left(\rho^{\mathfrak{C}}_x M^{\mathfrak{C}}_{x_i|i}\right),\label{eq:coordinate-success}\\ \intertext{and the average success probability (ASP) of \mathfrak{C} as} P^{\mathfrak{C}}&:=\frac{1}{n}\sum_{i=1}^n p^{\mathfrak{C}}_i. \end{align}\tag{2}\] Define the coordinate-wise success probability of \(\mathfrak{C}\), optimized over all POVMs for the \(i^{th}\) bit decoding, as \[\begin{align} p_i^{\mathfrak{C}*}&:= \max_{\tiny POVM:\{M_{0|i},M_{1|i}\}}\frac{1}{2^n}\sum_{x\in\{0,1\}^n}\mathop{\mathrm{Tr}}\!\left(\rho^{\mathfrak{C}}_x M_{x_i|i}\right)\label{eq:POVMopt} \end{align}\tag{3}\] The optimal ASP for the entire class of \((n,m)\) QRACs, \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\) is defined as in [20], \[\begin{align} &P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m} :=\max_{\mathfrak{C}}P^{\mathfrak{C}}\\ &= \max_{\{\rho_x\},\{M_{b|i}\}} \frac{1}{n2^n} \sum_{x\in\{0,1\}^n} \sum_{i=1}^n \mathop{\mathrm{Tr}}\!\left(\rho_x M_{x_i|i}\right). \label{eq:opt-avg-success} \end{align}\tag{4}\] Full PGM and the Full PGM Channel.– The full-string PGM is defined from the average state \[\begin{align} \bar\rho^{\mathfrak{C}}:=2^{-n}\sum_{x\in\{0,1\}^n}\rho^{\mathfrak{C}}_x \label{eq:average-state} \end{align}\tag{5}\] as in [19] with uniform \(X\) as follows. \[Q_y^{\mathfrak{C}}=2^{-n}(\bar\rho^{\mathfrak{C}})^{-1/2}\rho^{\mathfrak{C}}_y(\bar\rho^{\mathfrak{C}})^{-1/2}, \qquad y\in\{0,1\}^n, \label{eq:pgm-def}\tag{6}\] where inverse powers are taken on \(\mathop{\mathrm{supp}}(\bar\rho^{\mathfrak{C}})\) and are zero on the orthogonal complement. Then \(\sum_y Q^{\mathfrak{C}}_y=\Pi_{\mathop{\mathrm{supp}}(\bar\rho^{\mathfrak{C}})}\) is the orthogonal projection matrix onto \(\mathop{\mathrm{supp}}(\bar\rho^{\mathfrak{C}})\), and \(\{Q^{\mathfrak{C}}_y\}_y\) is a POVM on \(\mathop{\mathrm{supp}}(\bar\rho^{\mathfrak{C}})\); if desired as a POVM on the whole ambient Hilbert space, it may be completed arbitrarily on \(\mathop{\mathrm{supp}}(\bar\rho^{\mathfrak{C}})^\perp\). This completion does not affect the probabilities below, because all code states are supported on \(\mathop{\mathrm{supp}}(\bar\rho^{\mathfrak{C}})\). Let \(Y^{\mathfrak{C},\tiny PGM}\in\{0,1\}^n\) denote the PGM output when the input is \(X\in\{0,1\}^n\).
For \(x,y\in\{0,1\}^n\), write \[d_{\mathrm H}(x,y)=\bigl|\{i\in[n]:x_i\ne y_i\}\bigr|\] for their Hamming distance. For the random pair \((X,Y^{\mathfrak{C},\tiny PGM})\), define \[\begin{align} \Delta^{\mathfrak{C},\tiny PGM}:=\mathbb{E}[d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM})]. \end{align}\]
The full PGM induces a classical channel \(T_{xy}^{\mathfrak{C},\tiny PGM}\) with input \(x\in\{0,1\}^n\), output \(y\in\{0,1\}^n\), and the transition probabilities, \[T_{xy}^{\mathfrak{C},\tiny PGM}=\mathbb{P}[Y^{\mathfrak{C},\tiny PGM}=y\mid X=x]=\mathop{\mathrm{Tr}}(\rho^{\mathfrak{C}}_xQ^{\mathfrak{C}}_y). \label{eq:T-def}\tag{7}\]
Useful Lemmas.– We start with three useful lemmas. The first lemma produces an upper bound on the expected Hamming distance, \(\Delta^{\mathfrak{C},\tiny PGM}\), between \(X\) and the full PGM output \(Y\).
Lemma 1. For the full-string PGM output \(Y^{\mathfrak{C},\tiny PGM}\), \[\begin{align} \Delta^{\mathfrak{C},\tiny PGM} \leq\frac{n}{2}\left(1-(2P^{\mathfrak{C}}-1)^2\right). \label{eq:Deltaup} \end{align}\qquad{(1)}\]
Proof. From Lin and de Wolf [19], let us recall that reducing the outcome of the global PGM to the \(i^{th}\) bit by summing over the possible outcomes for other bits, induces exactly the one-bit PGM for the \(i^{th}\) bit. Thus, the \(i^{th}\) coordinate of the full-string PGM output \(Y^{\mathfrak{C},\tiny PGM}\), namely \(Y_i^{\mathfrak{C},\tiny PGM}\), represents the output of a one-bit PGM for the \(i^{th}\) bit from the binary marginal ensemble \(\{(1/2,\sigma^{\mathfrak{C}}_{i,0}),(1/2,\sigma^{\mathfrak{C}}_{i,1})\}\), where \[\begin{align} \sigma^{\mathfrak{C}}_{i,b}:=\frac{1}{2^{n-1}}\sum_{x\in\{0,1\}^n: x_i=b}\rho_x^{\mathfrak{C}},\qquad b\in\{0,1\}. \end{align}\] This allows us to apply Renes’s refined PGM bound [25] for a one-bit PGM to obtain, \[\begin{align} \mathbb{P}[Y_i^{\mathfrak{C},\tiny PGM}=X_i]&\geq (p_i^{\mathfrak{C}*})^2+(1-p_i^{\mathfrak{C}*})^2\label{eq:renes} \end{align}\tag{8}\] The optimized POVM in 3 is at least as good as choosing the better of the POVM prescribed by \(\mathfrak{C}\) and its swapped version, i.e., \[\begin{align} p_i^{\mathfrak{C}*}\geq \max\{p_i^{\mathfrak{C}},1-p_i^{\mathfrak{C}}\}\geq 1/2.\label{eq:swap} \end{align}\tag{9}\] Recognizing that the function \(z^2+(1-z)^2\) is increasing for \(z\geq 1/2\), we combine 8 and 9 to obtain, \[\begin{align} &\mathbb{P}[Y_i^{\mathfrak{C},\tiny PGM}=X_i]\notag\\ &\geq (\max\{p_i^{\mathfrak{C}},1-p_i^{\mathfrak{C}}\})^2+(1-\max\{p_i^{\mathfrak{C}},1-p_i^{\mathfrak{C}}\})^2\\ &= (p_i^{\mathfrak{C}})^2+(1-p_i^{\mathfrak{C}})^2\label{eq:Crenes}\\ \intertext{which is equivalently expressed as} &\mathbb{P}[Y_i^{\mathfrak{C},\tiny PGM}\neq X_i]\leq 2p_i^{\mathfrak{C}}(1-p_i^{\mathfrak{C}}). \end{align}\tag{10}\] Summing over all \(i\in[n]\) yields, \[\begin{align} \Delta^{\mathfrak{C},\tiny PGM}&=\mathbb{E}[d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM})]\notag\\ &=\sum_{i\in[n]}\mathbb{P}[Y_i^{\mathfrak{C},\tiny PGM}\neq X_i]\\ &\leq \sum_{i\in[n]}2p_i^{\mathfrak{C}}(1-p_i^{\mathfrak{C}})\\ &\leq 2nP^{\mathfrak{C}}(1-P^{\mathfrak{C}}).\label{eq:Jensens} \end{align}\tag{11}\] Step 11 follows from an application of Jensen’s inequality, recognizing that \(z(1-z)\) is a concave function of \(z\). Finally, rearranging the bound \(\Delta^{\mathfrak{C},\tiny PGM}\leq 2nP^{\mathfrak{C}}(1-P^{\mathfrak{C}})\) yields the desired bound ?? . ◻
The second lemma establishes that the matrix of transition probabilities for the channel \(T^{\mathfrak{C},\tiny PGM}\) defined in 7 is positive-semidefinite.
Lemma 2. The matrix \(T^{\mathfrak{C},\tiny PGM}\) is positive-semidefinite.
Proof. Define \[\begin{align} A_x^{\mathfrak{C}}:=(\bar\rho^{\mathfrak{C}})^{-1/4}\rho_x^{\mathfrak{C}}(\bar\rho^{\mathfrak{C}})^{-1/4} \end{align}\] and note that the cyclicity of trace implies \[\begin{align} T_{xy}^{\mathfrak{C},\tiny PGM}&=\mathop{\mathrm{Tr}}(\rho^{\mathfrak{C}}_xQ^{\mathfrak{C}}_y)\\ &=\mathop{\mathrm{Tr}}(\rho^{\mathfrak{C}}_x2^{-n}(\bar\rho^{\mathfrak{C}})^{-1/2}\rho^{\mathfrak{C}}_y(\bar\rho^{\mathfrak{C}})^{-1/2})\\ &=2^{-n}\mathop{\mathrm{Tr}}(A_x^{\mathfrak{C}}A_y^{\mathfrak{C}}) \label{eq:T-gram} \end{align}\tag{12}\] Thus, \(T_{xy}^{\mathfrak{C},\tiny PGM}=2^{-n}\mathop{\mathrm{Tr}}(A_x^{\mathfrak{C}}A_y^{\mathfrak{C}})\) is a real symmetric Gram matrix in the Hilbert-Schmidt inner product, which makes it positive semidefinite. ◻
The third lemma bounds the probability that the Hamming distance between \(X\) and the full PGM output is odd, essentially by showing that for any \(n\)-bit random strings \(X\) and \(Y\), if the matrix representation of their joint probability mass function is positive semidefinite, then the Hamming distance between \(X\) and \(Y\) is not more likely to be odd than it is to be even.
Lemma 3. We have the following bound, \[\mathbb{P}[d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM})\text{ is odd}]\le \frac{1}{2}. \label{eq:odd-bound}\qquad{(2)}\]
Proof. Let \(s: \{0,1\}^n \to \{-1, 1\}\) be defined by \(s(x) = (-1)^{|x|}\), where \(|x|\) denotes the Hamming weight of \(x\). Using the fact established in Lemma 2, i.e., \(T^{\mathfrak{C},\tiny PGM}\succeq 0\), we have \[\begin{align} 0 &\le 2^{-n}\sum_{x,y}s(x)T_{xy}^{\mathfrak{C},\tiny PGM}s(y)\\ &=2^{-n}\sum_{x,y}s(x)\mathbb{P}[Y^{\mathfrak{C}, \tiny PGM}=y\mid X=x]s(y)\tag{13}\\ &=\sum_{x,y}s(x)\mathbb{P}[Y^{\mathfrak{C},\tiny PGM}=y, X=x]s(y)\tag{14}\\ &= \mathbb{E}[s(X)s(Y^{\mathfrak{C},\tiny PGM})]\\ &= \mathbb{E}[(-1)^{|X|+|Y^{\mathfrak{C},\tiny PGM}|}]\tag{15}\\ &= \mathbb{E}[(-1)^{d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM})}]\tag{16}\\ &= \mathbb{P}[d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM})\text{ is even}]\notag\\ & -\mathbb{P}[d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM})\text{ is odd}]\\ &=1-2\mathbb{P}[d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM})\text{ is odd}]\tag{17} \end{align}\] Step 13 follows from 7 . Step 14 follows from the uniform distribution on \(X\). Step 16 follows from the fact that \((|x|+|y|)\mod 2\) is equal to \(d_{\mathrm H}(x,y)\mod 2\). Re-arranging 17 yields the desired bound ?? . ◻
Main Result.– Our main result appears in the following theorem.
Theorem 1. For \(m\in\{n-1,n-2\}\), every binary \((n,m)\) QRAC \(\mathfrak{C}\) has average success probability bounded as \[P^{\mathfrak{C}}\le \frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}} . \label{eq:main-converse}\qquad{(3)}\] Consequently Eq. 1 holds for \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\).
Proof. By relabeling the two outcomes of each coordinate POVM if necessary, we may assume without loss of generality that \(p_i^{\mathfrak{C}}\ge 1/2\) for all \(i\). This is because relabeling leaves the encoding ensemble, and hence the full-string PGM channel and \(\Delta^{\mathfrak{C},\tiny PGM}=\mathbb{E}[d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM})]\), unchanged, while it can only increase the ASP.
It will be useful to recall Nayak’s result in [14] which directly implies that \(\mathbb{P}[Y=X]\leq 2^{m-n}\) if \(Y\in\{0,1\}^n\) is obtained by making any measurement (not restricted to PGM) of an \(m\)-qubit encoding of a uniform \(X\in\{0,1\}^n\). In particular, this implies \[\begin{align} \mathbb{P}[Y^{\mathfrak{C},\tiny PGM}=X]\le 2^{m-n}.\label{eq:genbound} \end{align}\tag{18}\]
Case 1: For \(m=n-1\) we have, \[\begin{align} \Delta^{\mathfrak{C},\tiny PGM}&=\sum_{i\in[n]}\mathbb{P}[Y_i^{\mathfrak{C},\tiny PGM}\neq X_i]\\ &\geq \mathbb{P}[Y^{\mathfrak{C},\tiny PGM}\neq X]\\ &\geq 1/2\label{eq:applygenbound} \end{align}\tag{19}\] Step 19 follows by applying 18 with \(m=n-1\).
Case 2: Now consider \(m=n-2\). For compact notation let us define \(q_0:=\mathbb{P}[d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM})=0]\) and \(q_{\rm odd}:=\mathbb{P}[d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM}) is odd]\). \[\begin{align} \Delta^{\mathfrak{C},\tiny PGM}&=\mathbb{E}[d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM})]\\ &\geq \mathbb{P}[d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM}) is odd]\tag{20}\\ &+2\mathbb{P}[d_{\mathrm H}(X,Y^{\mathfrak{C},\tiny PGM}) is non-zero and even]\notag\\ &=q_{\rm odd}+2(1-q_0-q_{\rm odd})\\ &=2 - 2q_0- q_{\rm odd}\\ &\geq 2 - 2(1/4)-(1/2)\tag{21}\\ &=1 \end{align}\] Step 20 uses the fact that odd values of the Hamming distance must be at least one, and non-zero even values of the Hamming distance must be at least \(2\). Step 21 applies the bound \(q_0\leq 1/4\) which follows from 18 for \(m=n-2\), and the bound \(q_{\rm odd}\leq 1/2\) which follows from Lemma 3.
Thus \(\Delta^{\mathfrak{C},\tiny PGM}\ge (n-m)/2\) in both cases. Applying Lemma 1 and substituting this into ?? yields \[\begin{align} \frac{n-m}{2}&\leq \frac{n}{2}\left(1-(2P^{\mathfrak{C}}-1)^2\right)\\ \implies n(2P^{\mathfrak{C}}-1)^2&\leq m . \end{align}\] Since \(P^{\mathfrak{C}}=\frac{1}{n}\sum_{i=1}^n p^{\mathfrak{C}}_i\geq 1/2\) as assumed without loss of generality, for \(m\in\{n-1,n-2\}\) we obtain the desired bound \[\begin{align} P^{\mathfrak{C}}\le \frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}}. \end{align}\] ◻
The exact values of \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\) for \(m\in\{n-1,n-2\}\) now follow as a corollary.
Corollary 1. For \(m\in\{n-1,n-2\}\), \[P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m} =\frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}} . \label{eq:exact-high-rate}\qquad{(4)}\]
Proof. The upper bound follows by Theorem 1. For \(m=n-1\), Suzuki’s \((n,n-1)\) construction achieves the right-hand side [20]. For \(m=n-2\) the \((n,n-2)\) construction of Akibue et al. achieves the right-hand side [21]. ◻
Discussion.– We determined the precise values of the optimal average success probability for the classes of binary \((n,n-1)\) and \((n,n-2)\) QRACs by proving that the numerically conjectured upper bound 1 holds for these settings. While we focus on settings where the dimension \(D\) of the encoded quantum system is a power of \(2\), namely \(D=2^m\) for integer \(m\), it is noteworthy that none of the three lemmas in our proof require \(D\) to be a power of \(2\). Also note that 18 can be stated more generally as \(\mathbb{P}[Y^{\mathfrak{C},\tiny PGM}=X]\le \frac{D}{2^n}\). Following this line of thought, suppose \(n=4\) and \(D=6\), so that \(2=n-2<\log_2(D)=\log_2(6)<n-1=3\). Then in Step 21 we find \(\Delta^{\mathfrak{C},\tiny PGM}\geq 2-2(6/16)-1/2=3/4\). Following the subsequent steps yields the bound \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n=4,D=6}\leq \frac{1}{2}+\frac{1}{2}\sqrt{\frac{5}{8}}\) which is strictly smaller (tighter) than the value \(\frac{1}{2}+\frac{1}{2}\sqrt{\frac{\log_2(6)}{4}}\) obtained by replacing \(n=4, m=\log_2(D)=\log_2(6)\) in the RHS of 1 . Evidently, the direct logarithmic interpolation of the numerically conjectured bound, which is now proved for \(m=\log_2(D)\in\{n-1,n-2\}\), to intermediate values \(\log_2(D)\in(n-2,n-1)\) is not always tight, as we see from the \(n=4, D=6\) example. In general, while the conjectured bound may hold more broadly, its tightness in all cases where \(P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\) is precisely characterized so far, seems a mere coincidence.
Acknowledgements.–The authors acknowledge the use of OpenAI’s ChatGPT (GPT-5.5) as a research assistant during the discovery of the results presented in this work. Through an iterative, human-directed process, the authors formulated the research objectives, hypotheses, and problem constraints, while ChatGPT was used to generate intermediate calculations. All content is independently verified, revised, and approved by the authors, who take full responsibility for the manuscript.