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

• URL: http://arxiv.org/abs/2607.29073v1
• Date: Fri, 31 Jul 2026 06:51:06 GMT
• Title: On the Origin of Beyond-Classical Advantage in the Parity-Permutation Problem
• Abstract summary: We investigate the task of identifying the parity (odd vs even) of an unknown permutation applied to $n$ particles.<n>We show that even without entangled preparation, quantum theory still offers a probabilistic advantage over classical strategies.
• Score: 0.05417521241272644
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Classical simulation of free-fermionic dynamics and quantum chemistry with magic input [0.15554979526414522]
  We show that for a class of paired non-Gaussian fermionic states, quantum simulation primitives can be efficiently approximated to additive error under free-fermionic dynamics.
  arXiv  Detail & Related papers  (2026-04-29T15:42:59Z)
• Probabilistic and approximate universal quantum purification machines [0.0]
  We formalize the task of lifting arbitrary quantum states and channels to purifications and Stinespring dilations.<n>In the probabilistic exact setting, we show that universality is not necessary to rule out such transformations.<n>In the approximate setting, we allow for general machines that are not required, in general, to produce a pure output.
  arXiv  Detail & Related papers  (2026-04-07T18:01:03Z)
• Exponential Advantage from One More Replica in Estimating Nonlinear Properties of Quantum States [16.185988658474635]
  We prove that estimation of $mathrmtr(rhok O)$ for a broad class of observables $O$ is exponentially hard for any protocol restricted to $(k-1)$-replica joint measurements.<n>Results establish, for the first time, an exponential separation between $(k-1)$- and $k$-replica protocols for any integer $k>2$.
  arXiv  Detail & Related papers  (2025-09-28T17:46:43Z)
• Resourcefulness of non-classical continuous-variable quantum gates [0.0]
  In continuous-variable quantum computation, identifying key elements that enable a quantum computational advantage is a long-standing issue.<n>We develop a comprehensive and versatile approach in which the techniques of $(s)$-ordered quasiprobabilities are exploited to identify the contribution of each quantum gate to the potential achievement of quantum computational advantage.
  arXiv  Detail & Related papers  (2024-10-11T20:03:53Z)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem.<n>We show that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions.<n>We show that our assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives.
  arXiv  Detail & Related papers  (2024-10-10T16:10:10Z)
• Learning to Classify Quantum Phases of Matter with a Few Measurements [41.94295877935867]
  We study the identification of quantum phases of matter, at zero temperature, when only part of the phase diagram is known in advance. We show how to use our previous knowledge to construct an observable capable of classifying the phase even in the unknown region. An important application of our findings is the classification of the phases of matter obtained in quantum simulators.
  arXiv  Detail & Related papers  (2024-09-08T18:52:34Z)
• One-Shot Min-Entropy Calculation Of Classical-Quantum States And Its Application To Quantum Cryptography [21.823963925581868]
  We develop a one-shot lower bound calculation technique for the min-entropy of a classical-quantum state.<n>It offers an alternative tight finite-data analysis for the BB84 quantum key distribution scheme.<n>It gives the best finite-key bound known to date for a variant of device independent quantum key distribution protocol.
  arXiv  Detail & Related papers  (2024-06-21T15:11:26Z)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  We study learnability of quantum circuit Born machines (QCBMs) and quantum generative adversarial networks (QGANs) We first analyze the generalization ability of QCBMs and identify their superiorities when the quantum devices can directly access the target distribution. Next, we prove how the generalization error bound of QGANs depends on the employed Ansatz, the number of qudits, and input states.
  arXiv  Detail & Related papers  (2022-05-10T08:05:59Z)
• Quantum dynamics corresponding to chaotic BKL scenario [62.997667081978825]
  Quantization smears the gravitational singularity avoiding its localization in the configuration space. Results suggest that the generic singularity of general relativity can be avoided at quantum level.
  arXiv  Detail & Related papers  (2022-04-24T13:32:45Z)
• Why we should interpret density matrices as moment matrices: the case of (in)distinguishable particles and the emergence of classical reality [69.62715388742298]
  We introduce a formulation of quantum theory (QT) as a general probabilistic theory but expressed via quasi-expectation operators (QEOs) We will show that QT for both distinguishable and indistinguishable particles can be formulated in this way. We will show that finitely exchangeable probabilities for a classical dice are as weird as QT.
  arXiv  Detail & Related papers  (2022-03-08T14:47:39Z)
• Simple upper and lower bounds on the ultimate success probability for discriminating arbitrary finite-dimensional quantum processes [2.538209532048866]
  We present a simple upper bound on the ultimate success probability for discriminating arbitrary quantum processes. In the special case of multi-shot channel discrimination, it can be shown that the ultimate success probability increases by at most a constant factor determined by the given channels. We also present a lower bound based on Bayesian updating, which has a low computational cost.
  arXiv  Detail & Related papers  (2020-12-27T01:14:23Z)
• From a quantum theory to a classical one [117.44028458220427]
  We present and discuss a formal approach for describing the quantum to classical crossover. The method was originally introduced by L. Yaffe in 1982 for tackling large-$N$ quantum field theories.
  arXiv  Detail & Related papers  (2020-04-01T09:16:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.