Optimal Average Success Probabilities of Binary $(n,n-1)$ and $(n,n-2)$ Quantum Random Access Codes via a Proof of the Corresponding Conjectured Bound

• URL: http://arxiv.org/abs/2607.10414v1
• Date: Sat, 11 Jul 2026 17:44:29 GMT
• Title: Optimal Average Success Probabilities of Binary $(n,n-1)$ and $(n,n-2)$ Quantum Random Access Codes via a Proof of the Corresponding Conjectured Bound
• Abstract summary: We prove the conjectured upper bound for $minn-1,n-2$, thereby precisely determining $PQ,mathrmavg,mathrmopt_n,n-1$ and $PQ,mathrmavg,mathrmopt_n,n-2$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• A Simple Algorithm for Best Separable State [5.5559749120901385]
  We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states.<n>In classical terms, the goal is to maximize $langle(x otimes y), M (x otimes y)rangle$ over unit vectors $x,y$ where $0 preceq M preceq I$.
  arXiv  Detail & Related papers  (2026-08-10T19:04:15Z)
• Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding [26.296743455346604]
  Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM)<n>We study the $T$ count of sparse QROM, in which only $s$ of the $2n$ addresses store nonzero data.<n>Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+$T$ circuits.
  arXiv  Detail & Related papers  (2026-07-30T14:18:29Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
  arXiv  Detail & Related papers  (2026-07-08T17:49:40Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Sandwich test for Quantum Phase Estimation [0.0]
  Quantum Phase Estimation (QPE) has potential for a scientific revolution through numerous practical applications.<n>Many QPE algorithms use the Hadamard test to estimate $langle psi|Uk|psirangle$ for a large integer $k$.<n>We present a new algorithm, the SANDWICH test to address this bottleneck.
  arXiv  Detail & Related papers  (2025-07-31T16:45:07Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Sharp Noisy Binary Search with Monotonic Probabilities [5.563988395126509]
  We revisit the noisy binary search model of Karp and Kleinberg. We produce an algorithm that succeeds with probability $1-delta$ from [ frac1C_tau, varepsilon cdot left(lg n + O(log2/3 n log 1/3 frac1delta + log frac1delta) right.
  arXiv  Detail & Related papers  (2023-11-01T20:45:13Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• The geometry of Bloch space in the context of quantum random access codes [0.0]
  We study the communication protocol known as a Quantum Random Access Code (QRAC) We prove that for any $(n,m,p)$-QRAC with shared randomness the parameter $p$ is upper bounded by $ tfrac12+tfrac12sqrttfrac2m-1n$.
  arXiv  Detail & Related papers  (2021-06-01T00:15:33Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
  For a quantum circuit $C$ on $n$ qubits and a sample $z in 0,1n$, the benchmark involves computing $|langle z|C|0n rangle|2$. We show that for any $varepsilon ge frac1mathrmpoly(n)$, outputting a sample $z$ is the optimal 1-query for $|langle z|C|0nrangle|2$ on average.
  arXiv  Detail & Related papers  (2020-08-20T01:04:32Z)

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.