A QRAC encodes $n$ bits in $m$ qubits so that one of the bits can be retrieved. Let $p>0.5$ be the success probability of the receiver correctly obtaining any one of the $n$ bits of their choice by performing the appropriate measurement.

Nayak's bound states that such an $(n, m, p)$-QRAC must satisfy $m \geq (1−H(p))n$, where H(·) is the entropy function. So for any constant $p$, the "compression ratio" ($m/n$) that can be obtained is at least $(1-H(p))$. That is we can only get a constant (in $n$) factor space savings.

This paper introduces a Quantum Random Access code that claims (in section 7) to be able to store $\approx 0.5\cdot 3^u$ bits in $C u^2 1.5^u$ qubits where $C$ is a constant $\approx 243$, where the success probability is 0.999.

I'm confused how this doesn't violate Nayak's bound since the space savings is not a constant factor, yet the success probability is constant.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.