Quantum Random Access Coding (QRAC)

Overview

A quantum random access code, or QRAC, stores several classical bits in a smaller number of qubits so that any one chosen bit can be recovered with probability better than one half. You cannot recover all the bits, because measuring a quantum state destroys it, but you get to choose which single bit to read, and a clever choice of encoding and measurement makes each individual bit recoverable with good probability.

The simplest example stores two bits in a single qubit and recovers either bit with probability about 85 percent. It is one of the cleanest demonstrations that quantum states carry information in a different way from classical bits, and it is a standard tool in quantum communication complexity, in tests of quantum behavior with limited resources, and in some quantum optimization methods.

The problem it solves

Can you encode multiple classical bits into fewer qubits while still being able to decode any single bit with high probability?

History and background

The idea builds on Stephen Wiesner's conjugate coding from around 1970, which was published in 1983. Ambainis, Nayak, Ta-Shma, and Vazirani introduced quantum random access codes in a 1999 STOC paper on dense quantum coding and a lower bound for one-way quantum automata, with a longer journal version in 2002. They gave the two-bits-in-one-qubit code and proved that you cannot compress more than a limited amount: Nayak showed in 1999 that to encode n bits so that each is recoverable with probability p, you need at least a number of qubits proportional to n times one minus the binary entropy of p.

Later work studied codes with more bits per qubit and with shared randomness, including Hayashi, Iwama, Nishimura, Raymond, and Yamashita in 2006 and 2007, who studied random access coding more fully, and Tavakoli, Hameedi, Marques, and Bourennane in 2015, who extended them to d-level systems. Pawłowski and Żukowski showed in 2010 that shared entanglement improves the codes, and the codes became a tool for semi-device-independent tests of quantum behavior. In 2021 and later, Fuller, Hadfield, and coauthors used QRACs to encode three binary variables per qubit in a quantum relaxation approach to optimization, called quantum random access optimization.

How it works

Uses quantum superposition to encode n bits into log(n) + O(1) qubits. To decode bit i, apply a specific measurement basis corresponding to position i. With optimal encoding, recovers any bit with probability exceeding 1/2 by a constant.

A qubit state can be pictured as a point on a sphere, the Bloch sphere. Measuring along one axis, say the z axis, gives a yes-or-no answer determined by whether the point is in the upper or lower hemisphere. Measuring along the x axis gives a different yes-or-no answer, determined by the left or right hemisphere.

To store two bits, choose one of four points on the sphere, placed on the equator of the x-z plane at 45 degrees between the axes, so that each of the four combinations of two bits corresponds to a different corner. If you later measure along z, the answer matches the first bit with probability cosine squared of 22.5 degrees, about 85.4 percent. If you measure along x, it matches the second bit with the same probability.

The loss from 100 percent is the price for packing two bits into one qubit. A third axis allows three bits, using the eight corners of a cube inscribed in the sphere, and each bit is recoverable with probability about 78.9 percent. Beyond that, the success probability drops quickly toward one half, which is consistent with the general bounds.

Step by step

1. Choose the number of bits n and the number of qubits m, and a target success probability p.
2. For each possible input string, define a quantum state of the m qubits. For the two-bit code, the four states are the points on the Bloch sphere equator at 45 degrees from the x and z axes.
3. For each bit position i, define a measurement. In the two-bit code, measuring along z recovers the first bit and along x recovers the second.
4. To encode, the sender prepares the state corresponding to the input string and sends the qubit.
5. The receiver learns which bit is requested, and performs the matching measurement.
6. The measurement result is the recovered bit, which is correct with the success probability of the code, 85.4 percent in the two-bit case.

A worked example

Let the two bits be 1 and 0, and encode them as the Bloch vector pointing at plus 45 degrees in the x-z plane, with the sign for the first bit set by z and the second by x. A request for the first bit leads to a measurement along z, giving the correct value with probability cosine squared of 22.5 degrees, which is about 0.854. A request for the second bit leads to a measurement along x, with the same probability.

For three bits, the encoded Bloch vector points along one of the eight cube-diagonal directions with signs set by the three bits. Measuring along the x, y, or z axis recovers the corresponding bit with probability one half plus one half over the square root of 3, which is about 0.789.

Complexity and resources

What hardware it needs

• A single-qubit or few-qubit device capable of preparing states along several Bloch sphere directions and measuring along different axes.
• Photons, ions, and superconducting qubits have all been used in demonstrations.
• For quantum optimization uses, a gate-based device with qubits encoding three variables each.

Applications

• Quantum communication complexity, to show tasks where quantum messages beat classical messages of the same size.
• Semi-device-independent tests of quantum behavior and dimension witnesses, which require little trust in the devices.
• Quantum random access optimization, which encodes binary optimization variables more compactly in qubits for near-term devices.
• Teaching the nature of quantum measurement and the limits of information storage in quantum states.

Limitations and caveats

• Only one bit can be read, because the measurement destroys the state, so the code is not a way to compress data for storage.
• The success probability falls as more bits are packed into one qubit.
• The Holevo and Nayak bounds prevent exponential compression of classical data.
• For optimization, the compact encoding introduces errors that must be handled by rounding.

Common misconceptions

• A QRAC does not store n bits in about log n qubits. Nayak's bound requires a number of qubits proportional to n for any fixed success probability above one half.
• It does not let you read all the bits. You choose one in advance of the measurement.
• It does not violate the Holevo bound. The bound limits how much information can be extracted jointly, not the choice of one bit.

How it compares

• Classical random access codes can store no more than one bit per bit with high probability, while quantum codes pack more bits at reduced success probability.
• Superdense coding sends two classical bits with one qubit using shared entanglement, a different resource tradeoff.
• Quantum fingerprinting compresses information for equality testing, using logarithmically many qubits, which is a different task.

Real-world impact

Demonstrates fundamental quantum advantage in communication complexity — more relevant to quantum information theory than near-term applications, but underpins quantum fingerprinting and quantum communication protocols.

Why it matters

QRACs are the simplest setting in which the limits and strengths of quantum information are visible at once. They show that quantum states can encode more than one accessible bit per qubit but not more than the Holevo bound, and they supply a clean test for quantum versus classical resources in communication.

They have also found use in modern quantum optimization methods, which use the compact encoding to represent more variables on a given number of qubits.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Teleportation Protocol
• Related algorithm: SWAP Test
• Related algorithm: BB84 Quantum Key Distribution
• Related algorithm: Quantum Approximate Optimization Algorithm (QAOA)

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database