CS Paper Radar

Classical, quantum, and general probabilistic state-discrimination profiles

Mihály Weiner

cs.IT quant-ph ·submitted 2026-09-15 23:30 UTC · v1
theory

Abstract

For a collection of states indexed by $[n]={1,\ldots,n}$, let $F(H)$ denote the optimal unnormalized minimum discrimination error for each nonempty subfamily $H\subseteq[n]$. We call $F$ the discrimination profile and characterize exactly which profiles can arise in a general probabilistic theory (GPT). For fixed $n$, the GPT region $\mathfrak{G}_n$ is a bounded rational polytope, giving a hierarchy $\mathfrak{C}_n\subseteq\mathfrak{Q}_n\subseteq\mathfrak{G}_n$ of classical, quantum, and GPT profiles, analogous to the local--quantum--no-signalling hierarchy in Bell theory. For $n=3$ we determine the classical and GPT polytopes explicitly. Within $\mathfrak{G}_3$, the classical region is characterized by $β:=F(123)-F(12)-F(13)-F(23)\le0$, while the GPT maximum is $1$. For qubit triples, the maximal value is attained by the trine, $β_{\mathrm{tr}}=3\sqrt3/2-2$, and we prove the dimension-independent quantum bound $β_{\mathrm Q}\le2/3$, with a slight further improvement. Hence $0=β_{\mathrm C}<3\sqrt3/2-2\leβ_{\mathrm Q}\le2/3<1=β_{\mathrm{GPT}}$. We conjecture $β_{\mathrm Q}=β_{\mathrm{tr}}$ and prove this for arbitrary pure-state triples, together with further supporting evidence. For arbitrary $n$, every classical facet admitting a GPT violation already admits a quantum violation in dimension at most $3$. A four-state qubit example shows that quantum success profiles need not be submodular, unlike for $n=3$. Finally, we exhibit a four-dimensional quantum triple whose discrete profile is classical for all subfamilies but becomes nonclassical when unequal priors are allowed.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Quantum-Classical Separations for Exact Learning

cs.CC quant-phcs.LG ·2026-09-29 ·Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande
theory similarity 0.59
Abstract

We study exact learning with membership queries for concept classes $\mathcal C\subseteq\{0,1\}^N$, focusing on the relationships among their deterministic, randomized, and quantum query complexities, denoted $\mathsf{D}(\mathcal C)$, $\mathsf{R}(\mathcal C)$, and $\mathsf{Q}(\mathcal C)$, respectively. The two canonical quantum speedups in this model are witnessed by Grover search and Bernstein-Vazirani, leading to the longstanding conjecture $$ \mathsf{R}(\mathcal C)=O(\mathsf{Q}(\mathcal C)^2+\mathsf{Q}(\mathcal C)\log N). $$ We first refute this conjecture by constructing concept classes $\mathcal C$ and $\mathcal C'$ satisfying \[ \mathsf{R}(\mathcal C)=Ω\!\left(\frac{\mathsf{Q}(\mathcal C)^3\log N}{\log \mathsf{Q}(\mathcal C)}\right) \qquad\text{and}\qquad \mathsf{D}(\mathcal C')=Ω(\mathsf{Q}(\mathcal C')^3\log N). \] The first bound matches the upper bound of Arunachalam et al.~[Quantum'21] up to constant factors, while the second matches the upper bound of Servedio and Gortler~[SICOMP'04]. In particular, this shows that the saving in the randomized upper bound of Arunachalam et al. fundamentally relies on randomness. Apart from characterizing the optimal relationship between classical and quantum query complexity, our results are the first to show that quantum speedups for learning can go beyond the Grover and Bernstein-Vazirani paradigms.

0.49

Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes

cs.IT quant-ph ·2026-09-05 ·Avijit Mandal, Christophe Piveteau, Joseph M. Renes, Henry D. Pfister
highly cited similarity 0.59
Abstract

Belief propagation with quantum messages (BPQM) is a quantum algorithm that decodes classical codes transmitted over classical--quantum channels. It realizes optimal decoding on tree factor graphs over pure-state classical-quantum channels. However, this tree-based analysis does not ensure vanishing block-error probability for LDPC Tanner graphs with cycles. In this work, we construct a two-stage BPQM decoder for random $q$-ary LDPC codes over symmetric $q$-ary pure-state channels, where $q$ is prime, and prove that its ensemble-average block-error probability vanishes as the blocklength $N$ tends to infinity. For regular ensembles with $d_v\geq3$, fidelity bounds yield double-exponential decay of the average symbol-error probability throughout the BPQM success region. We apply depth-$\ell$ BPQM to coordinates with tree neighbourhoods and treat the remaining coordinates as erasures. With a suitable $\ell=Θ(\log\log N)$, a noncommutative union bound controls the BPQM decoding errors, while the minimum-distance property guarantees erasure recovery. We also extend the analysis to finite-support irregular ensembles. These results are relevant to quantum algorithms based on Regev's reduction, where coherent decoding uncomputes a codeword register. Decoded quantum interferometry (DQI) uses a closely related Fourier-based framework that reduces sparse max-LINSAT optimization problems to LDPC decoding problems on pure-state channels. Our results justify the use of BPQM in the decoding step of DQI and of coding-theoretic algorithms based on Regev's reduction whenever the code is drawn from one of the random LDPC ensembles analyzed here and the induced memoryless symmetric pure-state channel lies in the BPQM success region. Curiously, our numerical results indicate that DQI+BPQM achieves a satisfaction ratio that closely matches that of simulated annealing.

0.41

Exponential Quantum Advantage in Numbers-on-Forehead Communication

cs.CC quant-ph ·2026-09-30 ·Haoyu Wang, Pei Wu, Guangxu Yang
publishedtheory similarity 0.57
Abstract · 27 pages. Minor editorial revisions

We give the first exponential quantum advantage in the general interactive three-party Numbers-on-Forehead (NOF) model for a decision problem. Previous separations hold only for restricted protocols like one-way communication for a relation. We construct an explicit partial Boolean function, the Interleaved Unitary Product problem, that requires only $O(\log n)$ NOF quantum communication but $\widetildeΩ(n^{1/32})$ randomized communication. This function builds on the two-party unitary product problem of Arunachalam, Girish, and Lifshitz (TQC 2024). The main technical obstacle is that discrepancy, the standard lower-bound method for NOF, also lower-bounds quantum communication. We instead develop a regularity-based argument for randomized NOF lower bounds, building on the approach of Kelley, Lovett, and Meka and adapting the regularity decomposition of Abboud, Fischer, Kelley, Lovett, and Meka (STOC 2024) to cylinder intersections. Combined with matrix-product estimates of Arunachalam, Girish, and Lifshitz, this yields our randomized lower bound.

0.58

On the signaling dimension of the cross-polytope

cs.IT math-ph ·2026-10-05 ·Tamás Bencze, Péter E. Frenkel
theory similarity 0.56
Abstract · 8 pages. New result, Theorem 2.4. added. Minor errors corrected

In the general probabilistic model of information theory, the signaling dimension of a given communication protocol (or, equivalently, of its state space) is the smallest possible complexity of a classical communication protocol capable of perfectly simulating the given one in terms of input-output correlations. The signaling dimensions of three-, four-, and five-dimensional cross-polytopes have been known to be 3. We give logarithmic lower and upper bounds for the signaling dimensions of higher dimensional cross-polytopes, pinning down the value up to an additive gap of 2. The lower bound shows that the signaling dimension goes to infinity, in contrast to the case of balls and hypercubes.

0.29

Complexity Barriers to State Preparation in Quantum Approximate Optimization

cs.CC quant-ph ·2026-09-25 ·Stuart Hadfield
theory similarity 0.55
Abstract

For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \emph{any uniformly efficient quantum or hybrid procedure recovering a fixed positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For $d\in\{2,3\}$ variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor $1/d^2$. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard $n$-qubit families with relative quantum relaxation excess $Θ(1/n)$, while the maximally mixed state has energy approximation ratio $1-Θ(1/n)$, zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.

0.39

A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding

cs.IT quant-phmath.OC ·2026-09-09 ·Hoang Ta, Hoang Anh Tran
similarity 0.55
Abstract

Computing the optimal success probability for transmitting classical messages through a single use of a quantum channel is NP-hard, even for two messages. An existing semidefinite programming hierarchy based on symmetric extensions provides convergent upper bounds with an a priori error estimate that decays as the inverse square root of the extension level. In this work, we construct a Hermitian sum-of-squares hierarchy for an arbitrary number of messages and prove quadratic convergence in its level. The error bound is proportional to the advantage over random guessing. Our approach combines state-discrimination duality with positive polynomial kernels on products of spheres to construct feasible polynomial dual certificates. For binary messages, the resulting bounds give a multiplicative approximation from above of the trace-norm contraction coefficient.

0.28

Subadditivity and the failure of strong subadditivity in the Nichols--Wootters family of entropies

cs.IT quant-phmath-ph ·2026-11-11 ·Lin Zhang, Wenlin Zhang, Haobo Ma
theory similarity 0.55
Abstract · 110 pages

We prove subadditivity for the Nichols--Wootters family of entropies interpolating between the von Neumann entropy and the subentropy, with all spectra evaluated in one common ambient dimension. Beyond the von Neumann entropy, equality holds exactly when at least one marginal is pure. This settles the subadditivity conjecture concerning subentropy. Every member except the von Neumann entropy fails strong subadditivity, already on a maximally entangled two-qubit state tensored with a mixed qubit. Its strong-subadditivity defect takes both signs on quantum Markov states. For a pure bipartite state tensored with an ancillary state, we identify the defect with a separately concave product gap and determine its exact maximum under rank constraints. For arbitrary bipartite states, we obtain an explicit lower bound in the marginal purities. For two-qubit states, we determine the optimal coefficient multiplying the product of the smaller marginal eigenvalues in every common ambient dimension, including the subentropy coefficient $1/3$. A positive representation by Haar averages of compressed matrix entropies gives the pinching inequality underlying these results and also yields entropy-gain bounds for unital quantum channels.As an application, each entropy equals the classical communication capacity retained after a specified isotropic partial projective measurement, at a prescribed average input state, even when entangled block encodings are allowed.

0.20

High quantum local differential privacy breaks entanglement

cs.CR quant-phcs.IT ·2026-09-11 ·Sujeet Bhalerao, Theshani Nuradha, Felix Leditzky
theory similarity 0.55
Abstract · 25 pages

Differential privacy provides a mathematical framework for guaranteeing privacy for sensitive data. In quantum information processing, the interaction of privacy constraints with quantum resources such as entanglement remains a question of interest. Given that the utility of many protocols, and often the presence of a quantum advantage, relies on quantum resources such as entanglement, it is crucial to understand when a privacy requirement for a quantum channel is compatible with the channel's ability to preserve entanglement. We study this question for quantum local differential privacy (QLDP). Our main result shows that every $\varepsilon$-QLDP channel with a $d$-dimensional input is entanglement-breaking whenever $\varepsilon\leq\log\frac{d}{d-1}$. We also prove an approximate version for $(\varepsilon,δ)$-QLDP, where channels in the same high-privacy regime are close in diamond norm to an entanglement-breaking channel. We further prove a composition result for a collection of private quantum channels having entangled inputs and global measurements in the high-privacy regime. Finally, we apply our results to private quantum learning theory. We prove that any learning protocol using arbitrary quantum memory on copies of the output of an entanglement-breaking channel can be simulated by a protocol that measures the corresponding unprocessed input copies one at a time while storing only classical information. Combining this result with our high-privacy entanglement-breaking theorem, we show that under sufficiently private local noise, a learning protocol with quantum memory for purity testing and bipartite product testing is subject to the sample complexity lower bounds for protocols with single-copy measurements on the noiseless tasks. We also obtain stronger sample complexity lower bounds when a single highly private channel acts on the entire multipartite input.

0.52