Quantum discrepancy: a non-commutative version of combinatorial discrepancy

DOI10.37236/7587zbMATH Open1441.05218arXiv1711.08809OpenAlexW3024526543MaRDI QIDQ2185209FDOQ2185209

Authors: Kasra Alishahi, Mohaddeseh Rajaee, Ali Rajaei 

Publication date: 4 June 2020

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

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.

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

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

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

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)

Cites Work

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

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)