We establish a sharp quantum advantage in determining the parity (even-odd) of an unknown permutation applied to any number n≥3 of particles. Classically, this is impossible with fewer than n labels, being that the success is limited to random guessing. Quantum mechanics does it with certainty with as few as ⌈sqrt[n] ⌉ distinguishable states per particle, thanks to entanglement. Below this threshold, not even quantum mechanics helps: both classical and quantum success are limited to random guessing. For small n, we provide explicit expressions for states that ensure perfect parity identification. We also assess the minimum entanglement these states need to carry, finding it to be close to maximal, and even maximal in some cases. The task requires no oracles or contrived setups and provides a simple, rigorous example of genuine quantum advantage.
We establish a sharp quantum advantage in determining the parity (even-odd) of an unknown permutation applied to any number n≥3 of particles. Classically, this is impossible with fewer than n labels, being that the success is limited to random guessing. Quantum mechanics does it with certainty with as few as ⌈sqrt[n] ⌉ distinguishable states per particle, thanks to entanglement. Below this threshold, not even quantum mechanics helps: both classical and quantum success are limited to random guessing. For small n, we provide explicit expressions for states that ensure perfect parity identification. We also assess the minimum entanglement these states need to carry, finding it to be close to maximal, and even maximal in some cases. The task requires no oracles or contrived setups and provides a simple, rigorous example of genuine quantum advantage.
We investigate the task of identifying the parity (odd vs even) of an unknown permutation applied to n particles. Classically, using fewer than n distinct labels per particle limits the success probability to random guessing, whereas quantum mechanics, exploiting entanglement in both preparation and measurement, accomplishes the task perfectly with as few as ⌈n⌉ levels per particle [\href{https://doi.org/10.1103/yhyv-xnwq}{PRL {\bf 135}, 260603 (2025)}]. We show that even without entangled preparation, quantum theory still offers a probabilistic advantage over classical strategies. Moreover, such product preparations yield perfect success in locally quantum theories, where elementary systems are quantum but their composition follows the minimal tensor product structure of generalized probabilistic theories (GPTs). We further identify GPT models that accomplish the task with certainty without requiring entanglement either at the preparation stage or at the measurement stage. Our central result establishes that the linear dimension of the elementary systems, rather than entanglement, is the fundamental resource governing the existence of probabilistic advantage in the permutation parity problem. In particular, below the required dimension threshold, no amount of entanglement can improve upon the random-guessing limit.
A permutation of n particles is either even or odd according to the parity of the number of pairwise swaps required to realize it. Classically, deterministic identification of this parity requires n distinct local labels, one for each particle. A recently proposed quantum protocol [A. Diebra et al., Phys. Rev. Lett. 135, 260603 (2025)] reduces this requirement to a local dimension dmin = ⌈√n⌉ by exploiting multipartite entanglement, while retaining deterministic parity identification after a single application of the permutation. Here, we experimentally realize the minimal nontrivial case, n = 3 and d = 2, by mapping the parity-sensitive state structure onto a coherent superposition of Hermite–Gaussian spatial modes. A programmable multi-plane light converter implements all six elements of the permutation group S3, and a single projection measurement separates the even and odd permutation classes with a visibility of V ≃ 0.78. Our experiment reproduces, with structured classical light, the operational mechanism underlying this multipartite quantum-advantage protocol and establishes programmable spatial-mode processing as a versatile platform for exploring quantum protocols based on symmetry, interference, and reduced dimensional resources.
A permutation of n particles is either even or odd according to the parity of the number of pairwise swaps required to realize it. Classically, deterministic identification of this parity requires n distinct local labels, one for each particle. A recently proposed quantum protocol [A. Diebra et al., Phys. Rev. Lett. 135, 260603 (2025)] reduces this requirement to a local dimension dmin = ⌈√n⌉ by exploiting multipartite entanglement, while retaining deterministic parity identification after a single application of the permutation. Here, we experimentally realize the minimal nontrivial case, n = 3 and d = 2, by mapping the parity-sensitive state structure onto a coherent superposition of Hermite–Gaussian spatial modes. A programmable multi-plane light converter implements all six elements of the permutation group S3, and a single projection measurement separates the even and odd permutation classes with a visibility of V ≃ 0.78. Our experiment reproduces, with structured classical light, the operational mechanism underlying this multipartite quantum-advantage protocol and establishes programmable spatial-mode processing as a versatile platform for exploring quantum protocols based on symmetry, interference, and reduced dimensional resources.
The quantum permutation algorithm provides computational speed-up over classical algorithms for determining the parity of a given cyclic permutation. For its n-qubit implementations, the number of required quantum gates scales quadratically with n due to the quantum Fourier transforms included. We show here for the n-qubit case that the algorithm can be simplified so that it requires only O(n) quantum gates, which theoretically reduces the complexity of the implementation. To test our results experimentally, we utilize IBM's 5-qubit quantum processor to realize the algorithm by using the original and simplified recipes for the 2-qubit case. It turns out that the latter results in a significantly higher success probability which allows us to verify the algorithm more precisely than the previous experimental realizations. We also verify the algorithm for the first time for the 3-qubit case with a considerable success probability by taking the advantage of our simplified scheme.
A central question in quantum information is whether a given set of states can provide an advantage in some information-processing task. We establish a universal connection between two such questions: how well a set of states can be discriminated, and whether it can power tasks whose advantage stems from generalized contextuality. Working in the framework of generalized probabilistic theories (GPTs), which includes quantum and classical systems as special cases, we show that any set of states able to provide a nonclassical advantage in a contextuality-powered task must obey nontrivial upper bounds on the success probability of every state discrimination task using the full set. Contextual advantage therefore implies limited distinguishability, exposing a trade-off between two basic operational resources. Importantly, this is more than a statement about the idealized limit: perfect distinguishability is not needed to preclude contextuality. Our thresholds lie strictly below unity, so any set whose discrimination performance exceeds them while still imperfectly distinguishable is already guaranteed to admit a noncontextual explanation. The bounds follow from a simple geometric property, linear dependence of the state set, take a closed analytical form, and depend only on the prior of the task and the convex geometry of the states. As an illustration, we apply them to generalized parity-oblivious multiplexing, where sufficiently high success in the task implies that at least one sub-ensemble of the codebook cannot power any contextual advantage.
The most general examples of quantum learning advantages involve data labeled by cryptographic or intrinsically quantum functions, where classical learners are limited by the infeasibility of evaluating the labeling functions using polynomial-sized classical circuits. While broad in scope, such results reveal little about advantages arising from the learning process itself. In cryptographic settings, further insight is possible via random-generatability - the ability to classically generate labeled data - enabling hardness proofs for identification tasks, where the goal is to identify the labeling function from a dataset, even when evaluation is classically intractable. These tasks are particularly relevant in quantum contexts, including Hamiltonian learning and identifying physically meaningful order parameters. However, for quantum functions, random-generatability is conjectured not to hold, leaving no known identification advantages in genuinely quantum regimes. In this work, we give the first proofs of quantum identification learning advantages under standard complexity assumptions. We confirm that quantum-hard functions are not random-generatable unless BQP is contained in the second level of the polynomial hierarchy, ruling out cryptographic-style data generation strategies. We then introduce a new approach: we show that verifiable identification - solving the identification task for valid datasets while rejecting invalid ones - is classically hard for quantum labeling functions unless BQP is in the polynomial hierarchy. Finally, we show that, for a broad class of tasks, solving the identification problem implies verifiable identification in the polynomial hierarchy. This yields our main result: a natural class of quantum identification tasks solvable by quantum learners but hard for classical learners unless BQP is in the polynomial hierarchy.