A matrix-discrepancy argument proves tight one-way quantum lower bounds for collision finding (Ω(N^{1/4})) and for streaming triangle finding (Ω(√Δ_V)) where Boolean-Hidden-Matching reductions fail.
Positive semidefinite rank
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
Let M be a p-by-q matrix with nonnegative entries. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices $A_i, B_j$ of size $k \times k$ such that $M_{ij} = \text{trace}(A_i B_j)$. The psd rank has many appealing geometric interpretations, including semidefinite representations of polyhedra and information-theoretic applications. In this paper we develop and survey the main mathematical properties of psd rank, including its geometry, relationships with other rank notions, and computational and algorithmic aspects.
fields
quant-ph 2years
2026 2representative citing papers
A hierarchy of representability conditions for 2-RDMs in non-particle-number-conserving quantum systems is obtained from the polar cone of the p-positive cone, unified with conserving cases by adding particle-number variance.
citing papers explorer
-
Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
A matrix-discrepancy argument proves tight one-way quantum lower bounds for collision finding (Ω(N^{1/4})) and for streaming triangle finding (Ω(√Δ_V)) where Boolean-Hidden-Matching reductions fail.
-
Representability for Quantum Theory beyond Particle-Number Conservation
A hierarchy of representability conditions for 2-RDMs in non-particle-number-conserving quantum systems is obtained from the polar cone of the p-positive cone, unified with conserving cases by adding particle-number variance.