Draft:Quantum random access code

Quantum random access codes (QRACs) are a quantum information theoretic primitive used to encode a string of classical bits into a quantum state of smaller dimension, such that any single bit of the original string can be retrieved with a certain probability of success. QRACs are a form of quantum data compression that exploit the properties of quantum superposition and measurement to outperform their classical counterparts, known as random access codes (RACs).

QRACs are fundamental in the study of quantum communication complexity, quantum entanglement, and the foundations of quantum mechanics, particularly in the context of contextuality and Bell inequalities.

Definition

A $(n,m,p)$-QRAC is a protocol in which $n$ classical bits, denoted by $x=x_{1}x_{2}\dots x_{n}\in \{0,1\}^{n}$, are encoded into a quantum state $\rho _{x}$ of $m$ qubits. The goal is to retrieve any bit $x_{i}$ (where $i\in \{1,\dots ,n\}$) chosen by a receiver, with a success probability of at least $p$.

Formally, the protocol consists of two maps:

1. Encoding: A map ${\mathcal {E}}:\{0,1\}^{n}\to {\mathcal {D}}({\mathcal {H}}_{2^{m}})$ that assigns a density matrix $\rho _{x}$ to every input string $x$.
2. Decoding: A set of Positive Operator-Valued Measures (POVMs) $\{M_{i}\}_{i=1}^{n}$. Each $M_{i}=\{E_{i}^{0},E_{i}^{1}\}$ is a two-outcome measurement designed to guess the value of the $i$-th bit.

The probability of correctly guessing the $i$-th bit of $x$ is given by:

$P({\text{guess }}x_{i}{\text{ correctly}})={\text{Tr}}(E_{i}^{x_{i}}\rho _{x})\geq p$

For the code to be non-trivial, the probability $p$ must be strictly greater than $1/2$.

Comparison with Classical RACs

A classical random access code (RAC) is defined similarly, but the encoding maps the $n$ bits into $m$ classical bits. A fundamental result in information theory, derived from Holevo's theorem, states that for a classical $(n,m,p)$-RAC to exist with $p>1/2$, we must have $m\geq n(1-H(p))$, where $H(p)$ is the binary entropy function. Effectively, to recover any bit with high probability, the encoded size must be close to the original size.

However, QRACs can compress information below this classical bound. For example, it is possible to encode 2 bits into 1 qubit with a success probability of $p\approx 0.85$, and 3 bits into 1 qubit with $p\approx 0.79$. This demonstrates a quantum advantage in terms of encoding efficiency.

Nayak's Bound

Despite this advantage, quantum mechanics does not allow for infinite compression. Ashwin Nayak proved a strict lower bound for QRACs, known as Nayak's bound. For an $(n,m,p)$-QRAC, the number of qubits $m$ must satisfy:

$m\geq n(1-H(p))$

This inequality is formally identical to the classical bound, but since quantum states exist in a continuous Hilbert space rather than a discrete set, specific constructions like the 2-to-1 and 3-to-1 codes are realizable in the quantum case where they are impossible classically for the same length $m$.

Examples

2-to-1 QRAC

The $(2,1,p)$-QRAC encodes $n=2$ classical bits ($x_{1},x_{2}$) into $m=1$ qubit. The optimal strategy yields a success probability of $p={\frac {1}{2}}+{\frac {1}{2{\sqrt {2}}}}\approx 0.854$.

The encoding maps the four possible strings $00,01,10,11$ to four qubit states located on the equator of the Bloch sphere:

• $00\to |+\rangle$
• $01\to |+i\rangle$
• $10\to |-\rangle$
• $11\to |-i\rangle$

To recover $x_{1}$, one measures in the X-basis (Pauli-X). To recover $x_{2}$, one measures in the Y-basis (Pauli-Y).

3-to-1 QRAC

The $(3,1,p)$-QRAC encodes $n=3$ bits into $m=1$ qubit. The encoding states correspond to the vertices of a cube inscribed in the Bloch sphere. The optimal success probability is $p={\frac {1}{2}}+{\frac {1}{2{\sqrt {3}}}}\approx 0.789$. This is the maximum number of bits that can be encoded into a single qubit such that every bit can be recovered with probability strictly greater than $1/2$.

Entanglement-Assisted QRACs

The concept can be extended to scenarios where the sender and receiver share entanglement. In an Entanglement-Assisted Random Access Code (EARAC), the parties share a maximally entangled state. The sender performs a measurement on their half of the entangled state based on the input string $x$ and sends the classical outcome (or a quantum system) to the receiver. This setup allows for "superdense coding" variants of RACs, achieving higher success probabilities or compression rates than unentangled QRACs.

Applications

Quantum Finite Automata

QRACs were originally developed to prove lower bounds on the size of Quantum Finite Automata (QFA). If a QFA recognizes a language with high probability, its states effectively encode the history of the input string. Nayak's bound on QRACs translates to a lower bound on the number of states required for the automaton.

Foundations of Quantum Mechanics

QRACs are closely related to the study of contextuality. The inability to simultaneously retrieve all encoded bits reflects the uncertainty principle and the disturbance caused by measurement. The success probabilities of QRACs appear as bounds in various Bell inequalities and non-contextuality inequalities. For instance, the success probability of the 2-to-1 QRAC is related to the Tsirelson bound of the CHSH inequality.

Network Coding

In quantum network coding, QRACs provide a primitive for compressing information sent over bottleneck channels in a quantum network. They help in optimizing the throughput of quantum information transfer.

See also

• Quantum information theory
• Holevo's theorem
• Superdense coding
• Quantum finite automaton
• Bell's theorem