Imagine all the different ways you can rearrange a list of labelled items. If you know only a tiny fraction of the labels describing the elements of the list, it’s easy to assume you have almost no information about the order of the list as a whole under permutations. After all, if you shuffle a large deck of cards and then hide most of the labels on the cards, how could anyone possibly tell what permutations you made?
Recent theoretical work by physicists at Universitat Autonoma de Barcelona (UAB), Spain, and Hunter College of the City University of New York (CUNY), US, reveals that this intuition can fail in surprising ways, hinting at deep links between information, symmetry and computation. Specifically, the UAB-CUNY team found that quantum mechanics plays a key role in preserving parity – a global property of a permutation – even when most local information is erased.
An impressive parity identification
Imagine a clever magician named Alice. She hands you a stack of n coloured disks in a known order and leaves the room while you shuffle them. When she returns, she asks: “Can I tell how you permuted the disks?”
If every disk has its own unique label, the answer is obviously “yes”. But if Alice removes some of the labels, she can pose a subtler challenge: “Can I at least tell whether your shuffle swapped the positions of the cards an even or odd number of times?”
Classically, the answer is “no”. With fewer labels than disks, some labels must be repeated. Swapping two disks with the same label leaves the observed configuration unchanged, yet flips the parity of the underlying permutation. As a result, determining parity with certainty requires one unique label per disk. Anything less, and the information is fundamentally lost.
Quantum mechanics changes this conclusion. In their paper, which is published in Physical Review Letters, UAB’s Arnau Diebra and colleagues showed that as long as there are at least √n labels, far fewer than the total number of disks, one can still determine the parity of any permutation applied to the system when the game follows the rules of quantum mechanics. The problem remains the same; the only difference is that we are now preparing our initial state as a quantum state. In other words, even when most of the detailed information about individual elements is erased, a global feature of the transformation survives and exploiting quantum features makes it possible to extract it with carefully chosen information. This is not sleight of hand: it is a genuine mathematical insight into how much information certain global properties retain under massive data reduction.
Quantum advantage
In the field of quantum science, it’s common to ask whether quantum systems can outperform classical ones at specific tasks, a phenomenon known as quantum advantage. Here, “advantage” does not necessarily mean doing everything faster, but rather the ability to solve carefully chosen problems using fewer resources such as time, memory or information. Notable examples include quantum algorithms that factor large numbers more efficiently than any known classical method, and quantum communication protocols that achieve tasks that would be impossible with classical correlations alone.
The parity-identification problem fits naturally into this landscape. Parity is a global property, insensitive to most local details. In this respect, it resembles many other quantities studied in quantum physics, from topological invariants to entanglement measures.
What makes quantum advantage possible in this problem is entanglement – and lots of it. A compound quantum system is said to be entangled when its subsystems are correlated in a nonclassical way. A simple example might be a pair of qubits (quantum bits) for which measuring the state of one qubit gives you information about the state of the other in a way that cannot be reproduced by any classical correlation. In their work, the UAB-CUNY physicists used a geometric measure of entanglement: the “distance” between the state of the system and a state in which all subsystems are separable (that is, not entangled). If this distance is too short, the protocol fails entirely.
The crucial point is that entanglement allows information about the permutation to be stored in genuinely nonlocal correlations among particles (the “cards” in the deck), rather than in properties of each particle/card individually. In effect, the “memory” needed to identify the parity is written into the joint quantum state. No single particle carries the answer, but the system as a whole does. This is precisely what classical systems cannot replicate: once local labels are lost, there is nowhere left for the information to hide.
Can one do better than √n ?
The fact that the threshold for quantum advantage scales with √n is one of the most intriguing aspects of the work. At present, the reason for this remains an open question. While Diebra and colleagues emphasize that the scaling is provably optimal within quantum mechanics, they acknowledge that a more intuitive or fundamental explanation is still missing. Finding such an explanation could illuminate broader principles governing how quantum systems compress and protect global information.
While the parity-identification problem has no immediate known applications, understanding how properties can be inferred from limited information is also crucial when dealing with realistic quantum devices, where noise, decoherence and imperfect measurements severely restrict what information can be accessed. Results like this therefore suggest that some computational or informational tasks may remain feasible even when our view of the system is drastically incomplete.
Entangled light leads to quantum advantage
Speaking more broadly, the conceptual implications of proving new examples quantum advantage are clear: even for extremely simple inference tasks, quantum strategies can outperform classical ones in unexpected and qualitative ways. The result therefore provides a clean testing ground for deeper questions about quantum resources, symmetry and information compression. Which specific features of entanglement are responsible for the advantage? Can similar thresholds be found for other groups or more complex symmetries? And does the square-root scaling reflect a universal principle?
For now, the work serves as a reminder that – even decades into the development of quantum information theory – basic questions about how information is stored, hidden, and revealed in quantum systems can still produce genuine surprises.
