Quantum discrepancy: a non-commutative version of combinatorial discrepancy

DOI10.37236/7587MaRDI QIDQ2185209zbMATH OpenOpenAlexFDO

Authors Kasra Alishahi, Mohaddeseh Rajaee, Ali Rajaei

Publication date 4 June 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1711.08809

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

low-discrepancy coloringquantum coloring

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: In this paper, we introduce a notion of quantum discrepancy, a non-commutative version of combinatorial discrepancy which is defined for projection systems, i.e. finite sets of orthogonal projections, as non-commutative counterparts of set systems. We show that besides its natural algebraic formulation, quantum discrepancy, when restricted to set systems, has a probabilistic interpretation in terms of determinantal processes. Determinantal processes are a family of point processes with a rich algebraic structure. A common feature of this family is the local repulsive behavior of points. Alishahi and Zamani (2015) exploit this repelling property to construct low-discrepancy point configurations on the sphere. We give an upper bound for quantum discrepancy in terms of $N$, the dimension of the space, and $M$, the size of the projection system, which is tight in a wide range of parameters $N$ and $M$. Then we investigate the relation of these two kinds of discrepancies, i.e. combinatorial and quantum, when restricted to set systems, and bound them in terms of each other.

Recommendations

• Tighter bounds for the discrepancy of boxes and polytopes
• On the discrepancy of combinatorial rectangles
• scientific article; zbMATH DE number 1241851
• Discrepancy of set-systems and matrices
• The determinant bound for discrepancy is almost tight

Cites work

• scientific article; zbMATH DE number 1465044 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 6026126 (Why is no real title available?)
• A panorama of discrepancy theory
• An introduction to random matrices
• Constructive Discrepancy Minimization for Convex Sets
• Discrepancy in arithmetic progressions
• Geometric discrepancy. An illustrated guide
• Remark concerning integer sequences
• Six Standard Deviations Suffice
• The Generic Chaining
• The Kadison-Singer problem in discrepancy theory.
• The spherical ensemble and uniform distribution of points on the sphere
• Trace inequalities and quantum entropy: an introductory course
• Zeros of Gaussian analytic functions and determinantal point processes

This page was built for publication: Quantum discrepancy: a non-commutative version of combinatorial discrepancy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2185209)