Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNoncontextual coloring of orthogonality hypergraphs
94
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We discuss chromatic constructions on orthogonality hypergraphs which are classical set representable or have a faithful orthogonal representation. The latter ones have a quantum mechanical realization in terms of intertwined contexts or maximal observables. Structure reconstruction of these hypergraphs from their table of two-valued states is possible for a class of hypergraphs, namely perfectly separable hypergraphs. Some examples from exempt categories that either cannot be reconstructed by two-valued states or whose set of two-valued states does not yield a coloring are presented.
rate research
Read More
Contextuality is a fundamental feature of quantum theory and is necessary for quantum computation and communication. Serious steps have therefore been taken towards a formal framework for contextuality as an operational resource. However, the most important component for a resource theory - a concrete, explicit form for the free operations of contextuality - was still missing. Here we provide such a component by introducing noncontextual wirings: a physically-motivated class of contextuality-free operations with a friendly parametrization. We characterize them completely for the general case of black-box measurement devices with arbitrarily many inputs and outputs. As applications, we show that the relative entropy of contextuality is a contextuality monotone and that maximally contextual boxes that serve as contextuality bits exist for a broad class of scenarios. Our results complete a unified resource-theoretic framework for contextuality and Bell nonlocality.
Quantum measurements are noncontextual, with outcomes independent of which other commuting observables are measured at the same time, when consistently analyzed using principles of Hilbert space quantum mechanics rather than classical hidden variables.
We study in this paper the structure of solutions in the random hypergraph coloring problem and the phase transitions they undergo when the density of constraints is varied. Hypergraph coloring is a constraint satisfaction problem where each constraint includes $K$ variables that must be assigned one out of $q$ colors in such a way that there are no monochromatic constraints, i.e. there are at least two distinct colors in the set of variables belonging to every constraint. This problem generalizes naturally coloring of random graphs ($K=2$) and bicoloring of random hypergraphs ($q=2$), both of which were extensively studied in past works. The study of random hypergraph coloring gives us access to a case where both the size $q$ of the domain of the variables and the arity $K$ of the constraints can be varied at will. Our work provides explicit values and predictions for a number of phase transitions that were discovered in other constraint satisfaction problems but never evaluated before in hypergraph coloring. Among other cases we revisit the hypergraph bicoloring problem ($q=2$) where we find that for $K=3$ and $K=4$ the colorability threshold is not given by the one-step-replica-symmetry-breaking analysis as the latter is unstable towards more levels of replica symmetry breaking. We also unveil and discuss the coexistence of two different 1RSB solutions in the case of $q=2$, $K ge 4$. Finally we present asymptotic expansions for the density of constraints at which various phase transitions occur, in the limit where $q$ and/or $K$ diverge.
Motivated by the ErdH{o}s-Faber-Lov{a}sz (EFL) conjecture for hypergraphs, we consider the list edge coloring of linear hypergraphs. We show that if the hyper-edge sizes are bounded between $i$ and $C_{i,epsilon} sqrt{n}$ inclusive, then there is a list edge coloring using $(1 + epsilon) frac{n}{i - 1}$ colors. The dependence on $n$ in the upper bound is optimal (up to the value of $C_{i,epsilon}$).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
