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:2508.04310 · Physical Review Letters

Quantum Advantage in Identifying the Parity of Permutations with Certainty

A. Diebra, S. Llorens, D. González-Lociga, A. Rico, John Calsamiglia, M. Hillery, E. Bagán

Published Nov 17, 2025• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.1103/yhyv-xnwq

Related papers

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

Jayashree Karmakar, Biswadeep Chatterjee, Rafiuddin Gazi +6 more

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.

quant-pharXiv:2607.29073•Aug 3, 2026•0 citations

Optimization and experimental realization of the quantum permutation algorithm

İ. Yalçınkaya, Z. Gedik

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.

arXiv:1708.07900•Physical Review A•Dec 29, 2017•30 citations

Fine-tuning a quantum witness

Ian S. Osborne

Quantum Mechanics Quantum entanglement produces correlations between particles that cannot be described classically, and it is a resource sought out in many applications to leverage the quantum advantage over classical operation. However, determining whether particles are entangled is a complex process that can require a set of measurements (the witness) to establish the extent of the correlations between them. Shanhandeh et al. describe a protocol that should simplify the job of the witness somewhat. Using already known information about the systems, they demonstrate that entangled and unentangled states can be distinguished using fewer measurements. Extendable to larger systems, the simplified but enhanced witness should prove useful in quantum devices for which verifying entanglement is required. Phys. Rev. Lett. 118 , 110502 (2017).

Science•Apr 6, 2017•0 citations

Entanglement-induced provable and robust quantum learning advantages

Haimeng Zhao, Dong-Ling Deng

Quantum computing holds unparalleled potentials to enhance machine learning. However, a demonstration of quantum learning advantage has not been achieved so far. We make a step forward by rigorously establishing a noise-robust, unconditional quantum learning advantage in expressivity, inference speed, and training efficiency, compared to commonly-used classical models. Our proof is information-theoretic and pinpoints the origin of this advantage: entanglement can be used to reduce the communication required by non-local tasks. In particular, we design a task that can be solved with certainty by quantum models with a constant number of parameters using entanglement, whereas commonly-used classical models must scale linearly to achieve a larger-than-exponentially-small accuracy. We show that the quantum model is trainable with constant resources and robust against constant noise. Through numerical and trapped-ion experiments on IonQ Aria, we demonstrate the desired advantage. Our results provide valuable guidance for demonstrating quantum learning advantages with current noisy intermediate-scale devices.

arXiv:2410.03094•npj Quantum Information•Jul 29, 2025•16 citations

Quantum computing: beyond the limits of conventional computation†

Marius Nagy, Selim G. Akl

The quantum model of computation not only offers entirely new ways to manipulate information, but also allows information processing tasks to be formulated in unconventional, genuine quantum mechanical terms. We show that the task of distinguishing among entangled quantum states combines entanglement and non-determinism in a way that makes the quantum solution impossible to simulate on any classical machine (even one equipped with the same measurement capabilities as the quantum computational device). A new class of information processing tasks is thus uncovered whose members are readily carried out by a quantum computer, yet are impossible to perform on any classical machine (whether deterministic or probabilistic). In the broad, unconventional context created by quantum mechanics, the computational power of a quantum computer is therefore strictly greater than that of a classical computer.

International Journal of Parallel Emergent and Distributed Systems•Mar 30, 2007•23 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
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 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.
The quantum permutation algorithm provides computational speed-up over classical algorithms for determining the parity of a given cyclic permutation. For its nnn-qubit implementations, the number of required quantum gates scales quadratically with nnn due to the quantum Fourier transforms included. We show here for the nnn-qubit case that the algorithm can be simplified so that it requires only O(n)O(n)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.
Quantum Mechanics Quantum entanglement produces correlations between particles that cannot be described classically, and it is a resource sought out in many applications to leverage the quantum advantage over classical operation. However, determining whether particles are entangled is a complex process that can require a set of measurements (the witness) to establish the extent of the correlations between them. Shanhandeh et al. describe a protocol that should simplify the job of the witness somewhat. Using already known information about the systems, they demonstrate that entangled and unentangled states can be distinguished using fewer measurements. Extendable to larger systems, the simplified but enhanced witness should prove useful in quantum devices for which verifying entanglement is required. Phys. Rev. Lett. 118 , 110502 (2017).
Quantum computing holds unparalleled potentials to enhance machine learning. However, a demonstration of quantum learning advantage has not been achieved so far. We make a step forward by rigorously establishing a noise-robust, unconditional quantum learning advantage in expressivity, inference speed, and training efficiency, compared to commonly-used classical models. Our proof is information-theoretic and pinpoints the origin of this advantage: entanglement can be used to reduce the communication required by non-local tasks. In particular, we design a task that can be solved with certainty by quantum models with a constant number of parameters using entanglement, whereas commonly-used classical models must scale linearly to achieve a larger-than-exponentially-small accuracy. We show that the quantum model is trainable with constant resources and robust against constant noise. Through numerical and trapped-ion experiments on IonQ Aria, we demonstrate the desired advantage. Our results provide valuable guidance for demonstrating quantum learning advantages with current noisy intermediate-scale devices.
The quantum model of computation not only offers entirely new ways to manipulate information, but also allows information processing tasks to be formulated in unconventional, genuine quantum mechanical terms. We show that the task of distinguishing among entangled quantum states combines entanglement and non-determinism in a way that makes the quantum solution impossible to simulate on any classical machine (even one equipped with the same measurement capabilities as the quantum computational device). A new class of information processing tasks is thus uncovered whose members are readily carried out by a quantum computer, yet are impossible to perform on any classical machine (whether deterministic or probabilistic). In the broad, unconventional context created by quantum mechanics, the computational power of a quantum computer is therefore strictly greater than that of a classical computer.
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.