  We propose a protocol to encode classical bits in the measurement statistics
of a set of parity observables, leveraging quantum contextual relations for a
random access code task. The intrinsic information redundancy of quantum
contexts allows for a posterior decoding protocol that requires few samples
when encoding the information in a set of highly entangled states, which can be
generated by a discretely-parametrized quantum circuit. Applications of this
protocol include algorithms involving storage of large amounts of data but
requiring only partial retrieval of the information, as is the case of decision
trees. This classical-to-quantum encoding is a compression protocol for more
than $18$ qubits and shows quantum advantage over state-of-the-art information
storage capacity for more than $44$ qubits. In particular, systems above $100$
qubits would be sufficient to encode a brute force solution for games of
chess-like complexity.
