Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.29073

On the Origin of Beyond-Classical Advantage in the Parity-Permutation Problem

Jayashree Karmakar, Biswadeep Chatterjee, Rafiuddin Gazi, Ananya Chakraborty, Snehasish Roy Chowdhury, Manik Banik, Tamal Guha, Sahil Gopalkrishna Naik, Kunika Agarwal

quant-phSubmitted Jul 31, 2026• Announced Aug 3, 2026• 0 citations
arXivHTMLPDF

Abstract

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 $\big\lceil \sqrt{n}\big\rceil$ 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.

Comments
10 pages, 2 figures

Related papers

Quantum Advantage in Identifying the Parity of Permutations with Certainty

A. Diebra, S. Llorens, D. González-Lociga +4 more

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.

arXiv:2508.04310•Physical Review Letters•Nov 17, 2025•0 citations

Contextual advantage implies limited distinguishability in any physical theory

Roberto D. Baldijão, Felipe A. Barretto, Jarosław K. Korbicz

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.

quant-pharXiv:2607.26145•Jul 30, 2026•0 citations

Experimental Quantum-Inspired Advantage in Permutation Parity Identification using Spatial Modes of Light

Chen Teitelbaum, Shani Izhak, Ady Arie

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.

•Oct 29, 2026•0 citations

Experimental Quantum-Inspired Advantage in Permutation Parity Identification using Spatial Modes of Light

Chen Teitelbaum, Shani Izhak, Ady Arie

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.

•Oct 29, 2026•0 citations

Universal entangleability of non-classical theories

Guillaume Aubrun, Ludovico Lami, Carlos Palazuelos

Inspired by its fundamental importance in quantum mechanics, we define and study the notion of entanglement for abstract physical theories, investigating its profound connection with the concept of superposition. We adopt the formalism of general probabilistic theories (GPTs), encompassing all physical models whose predictive power obeys minimal requirements. Examples include classical theories, which do not exhibit superposition and whose state space has the shape of a simplex, quantum mechanics, as well as more exotic models such as Popescu-Rohrlich boxes. We call two GPTs entangleable if their composite admits either entangled states or entangled measurements, and conjecture that any two non-classical theories are in fact entangleable. We present substantial evidence towards this conjecture by proving it (1) for the simplest case of 3-dimensional theories; (2) when the local state spaces are discrete, which covers foundationally relevant cases; (3) when one of the local theories is quantum mechanics. Furthermore, (4) we envision the existence of a quantitative relation between local non-classicality and global entangleability, explicitly describing it in the geometrically natural case where the local state spaces are centrally symmetric.

arXiv:1910.04745•Oct 10, 2019•4 citations

Role of fine-grained uncertainty in determining the limit of preparation contextuality

Gautam Sharma, Sk Sazim, Shiladitya Mal

The optimal success probability of a communication game sets fundamental limitations on an operational theory. The quantum advantage of a parity oblivious random access code (PORAC), a communication game, over classical resources reveals the preparation contextuality of quantum theory [R. W. Spekkens et al., Phys. Rev. Lett. 102, 010401 (2009)]. The optimal quantum advantage in the $N$-dit PORAC game for finite dimensions is an open problem. Here, we show that the degree of uncertainty allowed in an operational theory determines the amount of preparation contextuality. We connect the upper bound of the fine-grained uncertainty relation to the success probability of a PORAC game played with the quantum resource. Subsequently, we find the optimal success probability for a 2-dit PORAC game using mutually unbiased bases for the decoding strategy. Finally, we also derive an upper bound on the quantum advantage for the $N$-dit PORAC game.

arXiv:1905.09695•Physical Review A•Sep 28, 2021•8 citations
We investigate the task of identifying the parity (odd vs even) of an unknown permutation applied to nnn particles. Classically, using fewer than nnn 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⌉\big\lceil \sqrt{n}\big\rceil⌈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.
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.
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.
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.
Inspired by its fundamental importance in quantum mechanics, we define and study the notion of entanglement for abstract physical theories, investigating its profound connection with the concept of superposition. We adopt the formalism of general probabilistic theories (GPTs), encompassing all physical models whose predictive power obeys minimal requirements. Examples include classical theories, which do not exhibit superposition and whose state space has the shape of a simplex, quantum mechanics, as well as more exotic models such as Popescu-Rohrlich boxes. We call two GPTs entangleable if their composite admits either entangled states or entangled measurements, and conjecture that any two non-classical theories are in fact entangleable. We present substantial evidence towards this conjecture by proving it (1) for the simplest case of 3-dimensional theories; (2) when the local state spaces are discrete, which covers foundationally relevant cases; (3) when one of the local theories is quantum mechanics. Furthermore, (4) we envision the existence of a quantitative relation between local non-classicality and global entangleability, explicitly describing it in the geometrically natural case where the local state spaces are centrally symmetric.
The optimal success probability of a communication game sets fundamental limitations on an operational theory. The quantum advantage of a parity oblivious random access code (PORAC), a communication game, over classical resources reveals the preparation contextuality of quantum theory [R. W. Spekkens et al., Phys. Rev. Lett. 102, 010401 (2009)]. The optimal quantum advantage in the NNN-dit PORAC game for finite dimensions is an open problem. Here, we show that the degree of uncertainty allowed in an operational theory determines the amount of preparation contextuality. We connect the upper bound of the fine-grained uncertainty relation to the success probability of a PORAC game played with the quantum resource. Subsequently, we find the optimal success probability for a 2-dit PORAC game using mutually unbiased bases for the decoding strategy. Finally, we also derive an upper bound on the quantum advantage for the NNN-dit PORAC game.