Quantum discrepancy: a non-commutative version of combinatorial discrepancy

Kasra Alishahi ; Mohaddeseh Rajaee ; Ali Rajaei

The electronic journal of combinatorics, Tome 27 (2020) no. 2

Résumé

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.

Détail

DOI : 10.37236/7587

Classification : 05D10, 05D40, 11K38
Mots-clés : low-discrepancy coloring, quantum coloring