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.
