imported>WikiHarold: Replace raw Quantum Collection backlink with B backlink template

2026-05-08T19:08:27Z

Replace raw Quantum Collection backlink with B backlink template

← Older revision	Revision as of 19:08, 8 May 2026
(No difference)

imported>WikiHarold: Replace raw Quantum Collection backlink with B backlink template

2026-05-08T19:08:27Z

Replace raw Quantum Collection backlink with B backlink template

New page

{{Short description|Encoding an n-bit string in m qubits}}
{{Quantum book backlink|Quantum information and computing}}

'''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).<ref name="Ambainis2002">{{cite book |last1=Ambainis |first1=A. |last2=Nayak |first2=A. |last3=Ta-Shma |first3=A. |last4=Vazirani |first4=U. |chapter=Dense quantum coding and a lower bound for 1-way quantum automata |title=Proceedings of the thirty-first annual ACM symposium on Theory of Computing |year=1999 |pages=376–383 |doi=10.1145/301250.301347 |arxiv=quant-ph/9804043 |isbn=1-58113-067-8 }}</ref>

QRACs are fundamental in the study of quantum communication complexity, [[Quantum entanglement|quantum entanglement]], and the foundations of quantum mechanics, particularly in the context of contextuality and Bell inequalities.<ref name="Galvao2002">{{cite journal |last1=Galvão |first1=E. F. |title=Foundations of quantum theory and quantum information applications |journal=PhD Thesis, Oxford University |year=2002 |arxiv=quant-ph/0212124 |bibcode=2002quant.ph.12124G }}</ref>
<div style="float:right; border:1px solid #e0d890; background:#fff8cc; padding:6px; margin:0 0 1em 1em; width:420px;">
[[File:Quantum_random_access_code_yellow.png|400px]]
<div style="font-size:90%;">Quantum random access code protocol. Alice encodes an <i>n</i>-bit string into <i>m</i> qubits, with <i>m</i> < <i>n</i>. Bob chooses an index <i>i</i> and performs a measurement to guess the requested bit <i>x</i><sub>i</sub>.</div>
</div>
== Definition ==

A <math>(n, m, p)</math>-QRAC is a protocol in which <math>n</math> classical bits, denoted by <math>x = x_1 x_2 \dots x_n \in \{0, 1\}^n</math>, are encoded into a quantum state <math>\rho_x</math> of <math>m</math> qubits. The goal is to retrieve any bit <math>x_i</math> (where <math>i \in \{1, \dots, n\}</math>) chosen by a receiver, with a success probability of at least <math>p</math>.<ref name="Ambainis2002"/>

Formally, the protocol consists of two maps:
# '''Encoding''': A map <math>\mathcal{E}: \{0, 1\}^n \to \mathcal{D}(\mathcal{H}_{2^m})</math> that assigns a density matrix <math>\rho_x</math> to every input string <math>x</math>.
# '''Decoding''': A set of [[POVM|Positive Operator-Valued Measures]] (POVMs) <math>\{M_i\}_{i=1}^n</math>. Each <math>M_i = \{E_i^0, E_i^1\}</math> is a two-outcome measurement designed to guess the value of the <math>i</math>-th bit.

The probability of correctly guessing the <math>i</math>-th bit of <math>x</math> is given by:
:<math>P(\text{guess } x_i \text{ correctly}) = \text{Tr}(E_i^{x_i} \rho_x) \ge p</math>

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

== Comparison with Classical RACs ==
A classical random access code (RAC) is defined similarly, but the encoding maps the <math>n</math> bits into <math>m</math> ''classical'' bits. A fundamental result in information theory, derived from [[Holevo's theorem]], states that for a classical or quantum <math>(n, m, p)</math>-RAC to exist with <math>p > 1/2</math>, we must have <math>m \ge n(1 - H(p))</math>, where <math>H(p)</math> is the [[Binary entropy function|binary entropy function]]. Effectively, to recover ''any'' bit with high probability, the encoded size must be close to the original size.<ref name="Nayak1999">{{cite book |last1=Nayak |first1=A. |chapter=Optimal lower bounds for quantum automata and random access codes |title=40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) |year=1999 |pages=369–376 |doi=10.1109/SFFCS.1999.814608 |arxiv=quant-ph/9904093 |isbn=0-7695-0409-4 }}</ref>

Although quantum and classical RACs share the same aforementioned bound, QRACs can compress information more efficiently than classical ones. For example, it is possible to encode 2 bits into 1 qubit with a success probability of <math>p \approx 0.85</math>, and 3 bits into 1 qubit with <math>p \approx 0.79</math>. This demonstrates a quantum advantage in terms of encoding efficiency.<ref name="Ambainis2002"/>

=== 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 <math>(n, m, p)</math>-QRAC, the number of qubits <math>m</math> must satisfy:
:<math>m \ge n(1 - H(p))</math>
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 <math>m</math>. However, the number of <math>n</math> classical bits that can be encoded with <math>m</math> qubits is at most <math>4^{m}-1</math> even when <math>p</math> is infinitely close to <math>1/2</math>.<ref name="Nayak1999"/><ref name="Hayashi2006" /><ref>{{Cite journal |last=Iwama |first=Kazuo |last2=Nishimura |first2=Harumichi |last3=Raymond |first3=Rudy |last4=Yamashita |first4=Shigeru |date=2007 |editor-last=Arge |editor-first=Lars |editor2-last=Cachin |editor2-first=Christian |editor3-last=Jurdziński |editor3-first=Tomasz |editor4-last=Tarlecki |editor4-first=Andrzej |title=Unbounded-Error One-Way Classical and Quantum Communication Complexity |url=https://link.springer.com/chapter/10.1007/978-3-540-73420-8_12?error=cookies_not_supported&code=2e698b6e-4033-42ef-90f9-dded9e106dcf |journal=Automata, Languages and Programming |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=110–121 |doi=10.1007/978-3-540-73420-8_12 |isbn=978-3-540-73420-8|arxiv=0706.3265 }}</ref>

== Examples ==

=== 2-to-1 QRAC ===
The <math>(2, 1, p)</math>-QRAC encodes <math>n=2</math> classical bits (<math>x_1, x_2</math>) into <math>m=1</math> qubit. The optimal strategy yields a success probability of <math>p = \frac{1}{2} + \frac{1}{2\sqrt{2}} \approx 0.854</math>.<ref name="Hayashi2006">{{Cite book |last1=Hayashi |first1=Masahito |last2=Iwama |first2=Kazuo |last3=Nishimura |first3=Harumichi |last4=Raymond |first4=Rudy |last5=Yamashita |first5=Shigeru |date=2007 |editor-last=Thomas |editor-first=Wolfgang |chapter=Quantum Network Coding |series=Lecture Notes in Computer Science |volume=4393 |editor2-last=Weil |editor2-first=Pascal |title=Stacs 2007 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=610–621 |doi=10.1007/978-3-540-70918-3_52 |arxiv=quant-ph/0601088 |isbn=978-3-540-70918-3}}</ref>

The encoding maps the four possible strings <math>00, 01, 10, 11</math> to four qubit states located on the equator of the [[Physics:Bloch sphere|Bloch sphere]]:
* <math>00 \to |+\rangle</math>
* <math>01 \to |+i\rangle</math>
* <math>10 \to |-\rangle</math>
* <math>11 \to |-i\rangle</math>
To recover <math>x_1</math>, one measures in the X-basis (Pauli-X). To recover <math>x_2</math>, one measures in the Y-basis (Pauli-Y).

=== 3-to-1 QRAC ===
The <math>(3, 1, p)</math>-QRAC encodes <math>n=3</math> bits into <math>m=1</math> qubit. The encoding states correspond to the vertices of a cube inscribed in the Bloch sphere. The optimal success probability is <math>p = \frac{1}{2} + \frac{1}{2\sqrt{3}} \approx 0.789</math>. 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 <math>1/2</math>.<ref name="Ambainis2002"/><ref>{{Cite journal |last=Hayashi |first=M |last2=Iwama |first2=K |last3=Nishimura |first3=H |last4=Raymond |first4=R |last5=Yamashita |first5=S |date=2006-08-04 |title=(4,1)-Quantum random access coding does not exist—one qubit is not enough to recover one of four bits |url=https://iopscience.iop.org/article/10.1088/1367-2630/8/8/129 |journal=New Journal of Physics |volume=8 |issue=8 |pages=129–129 |doi=10.1088/1367-2630/8/8/129 |issn=1367-2630|arxiv=quant-ph/0604061 }}</ref>

== Entanglement-Assisted QRACs ==
The concept can be extended to scenarios where the sender and receiver share [[Quantum entanglement|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 <math>x</math> 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.<ref name="Pawlowski2010">{{cite journal |last1=Pawłowski |first1=M. |last2=Żukowski |first2=M. |title=Entanglement-assisted random access codes |journal=Physical Review A |volume=81 |issue=4 |article-number=042326 |year=2010 |doi=10.1103/PhysRevA.81.042326 |arxiv=0912.3524 |bibcode=2010PhRvA..81d2326P }}</ref>

== Applications ==

=== Quantum Finite Automata ===
QRACs were originally developed to prove lower bounds on the size of [[Quantum finite automaton|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.<ref name="Ambainis2002"/>

=== 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.<ref name="Tavakoli2015">{{cite journal |last1=Tavakoli |first1=A. |last2=Hameedi |first2=A. |last3=Marques |first3=B. |last4=Bourennane |first4=M. |title=Quantum random access codes using single d-level systems |journal=Physical Review Letters |volume=114 |issue=17 |article-number=170502 |year=2015 |doi=10.1103/PhysRevLett.114.170502 |pmid=25978213 |arxiv=1411.6669 |bibcode=2015PhRvL.114q0502T }}</ref>

=== 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.<ref name="Hayashi2006"/>

=See also=
{{#invoke:PhysicsQC|tocHeadingAndList|Physics:Quantum basics/See also}}

=References=
{{reflist|3}}

{{Author|Harold Foppele}}

{{Sourceattribution|Random access code|1}}

Physics:Quantum random access code - Revision history

imported>WikiHarold: Replace raw Quantum Collection backlink with B backlink template

imported>WikiHarold: Replace raw Quantum Collection backlink with B backlink template