Exponential Information Compression with Quantum Contextual Redundancy

We propose a protocol to store exponential amounts of classical information in the measurement statistics of a set of eigenstates of many-body Pauli observables. Fewer samples are required for bit retrieval if entanglement is allowed in the encoding, which is achieved by exploiting spontaneously-occurring redundancies in measurement contexts. This is applicable to store large quantities of data when only small portions of information need to be consulted at a time, e.g. decision trees. The present protocol showcases enhancement over classical methods using the same number of resources starting at 16 qubits and would outperform current HPC storage capacity starting at 38 qubits. To illustrate the power of this compression protocol, sets of states of ∼100 qubits are sufficient to store a brute-force solution for chess.