{"id":"arxiv/2607.29073","url":"https://arxiv.org/abs/2607.29073","tags":["quant-ph"],"score":0,"title":"On the Origin of Beyond-Classical Advantage in the Parity-Permutation Problem","domain":"quant-ph","source":"arxiv","authors":["Jayashree Karmakar","Biswadeep Chatterjee","Rafiuddin Gazi","Ananya Chakraborty","Snehasish Roy Chowdhury","Manik Banik","Tamal Guha","Sahil Gopalkrishna Naik","Kunika Agarwal"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-31","reactions":{}}