In 1948, engineer Claude Shannon laid the foundations of information theory. The Nyquist–Shannon theorem gave the first answer: to avoid losing a signal, you need at least twice as many measurements as the fastest feature in the signal. In 2006, the method of compressed sensing relaxed this requirement. If a signal consists of only a few significant frequencies, you can reduce the number of measurements. However, the classical approach still carries a logarithmic penalty tied to the size of the original data — the price for the algorithm not knowing in advance where those frequencies hide.
The authors of the new work propose quantum compressed sensing. Instead of many separate measurements, they prepare a single quantum probe (say, an atom or a photon) and encode the entire high-dimensional signal into its state. Then they run the probe through a specially tailored evolution. This evolution itself, without any extra attempts, finds exactly where the significant frequencies are hidden in the signal. It's like tuning a radio that doesn't sweep the dial across the whole band but instantly jumps to the occupied stations.
In classical compressed sensing, after measurements you have to solve a hard recovery problem — something like assembling a puzzle from a few pieces. In the quantum version, recovery degenerates into a simple linear estimate: the probe after evolution directly points to the sought frequencies. Experiments with signals in both time and frequency domains confirmed this. The number of measurements grows strictly proportionally to the number of significant frequencies and is completely independent of the total signal size.
This approach opens the door to sensors that spend minimal resources on what matters most — whether it's capturing a fast process, medical scanning, or communication over a noisy channel. It's not just an acceleration; it's a game changer: measure exactly as much as needed, and not a bit more.
In classical compressed sensing, the logarithmic penalty log(N/K) arises because the algorithm doesn't know in advance which frequencies are significant and must search through possibilities. A quantum probe does this search all at once, thanks to superposition — the ability of a quantum particle to exist in many states simultaneously.
In Greg Egan's novel "Permutation City," digitized personalities compress themselves into quantum states to exist in limited memory — quantum compressed sensing embodies a similar idea for physical signals.