Source-linked AI summary
Graph Homomorphisms for Quantum Players
Laura Mančinska, David E. Roberson
TL;DR
The paper studies whether quantum players can certify graph homomorphisms, extending the coloring game amid limited general lower bounds for quantum chromatic number. It develops quantum homomorphisms and proves consequences for graph parameters and zero-error capacity, including a Lovász-theta lower bound for quantum chromatic number.
Problem
General lower bounds for quantum chromatic number are scarce, and its computability is unknown.
Source: §1 · p. 2Method
The paper defines a homomorphism game and studies quantum strategies through quantum homomorphisms between graphs.
Source: §1 · p. 2Results
Complement Lovász theta lower bounds quantum chromatic number; quantum independence and clique numbers can separate from classical values, but odd girth does not.
Source: §1 · p. 3Takeaways & Limitations
Quantum homomorphisms relate graph parameters to entanglement-assisted one-shot zero-error capacity and yield graphs where entanglement assistance increases that capacity.
Source: §1 · pp. 2–3Which graph pairs admit a quantum homomorphism without an ordinary one remains unresolved in general.
Source: §7.1 · p. 28
Abstract
from arXiv · showhide
A homomorphism from a graph $X$ to a graph $Y$ is an adjacency preserving mapping $f:V(X) \rightarrow V(Y)$. We consider a nonlocal game in which Alice and Bob are trying to convince a verifier with certainty that a graph $X$ admits a homomorphism to $Y$. This is a generalization of the well-studied graph coloring game. Via systematic study of quantum homomorphisms we prove new results for graph coloring. Most importantly, we show that the Lov\'{a}sz theta number of the complement lower bounds the quantum chromatic number, which itself is not known to be computable. We also show that some of our newly introduced graph parameters, namely quantum independence and clique numbers, can differ from their classical counterparts while others, namely quantum odd girth, cannot. Finally, we show that quantum homomorphisms closely relate to zero-error channel capacity. In particular, we use quantum homomorphisms to construct graphs for which entanglement-assistance increases their one-shot zero-error capacity.
1 Introduction
The paper generalizes quantum coloring games to graph homomorphism games, then uses quantum homomorphisms to study graph parameters and zero-error capacity. Its results include a Lovász-theta lower bound for quantum chromatic number and separations between some classical and quantum parameters.
1 Introduction
- Quantum homomorphisms extend the coloring game by asking players to return target-graph vertices that preserve consistency and adjacency.Classical players win exactly when an ordinary homomorphism exists; quantum players define the generalized relation.Source: §1 · p. 2
- Lovász theta of the complement lower bounds quantum chromatic number, giving a previously unknown efficiently computable lower bound.The paper also shows that the quantum colorings in [AHKS06] are optimal.Source: §1 · pp. 2–3
- Quantum independence and clique numbers can separate from their classical counterparts, whereas quantum odd girth cannot.Quantum independence is also upper bounded by Lovász theta.Source: §1 · p. 3
- Quantum homomorphisms connect to entanglement-assisted one-shot zero-error capacity, which they lower-bound through quantum independence number.The paper constructs graphs where entanglement assistance increases one-shot zero-error capacity.Source: §1 · p. 3
- Projective rank generalizes orthogonal rank and fractional chromatic number, lies between complement Lovász theta and quantum chromatic number, and respects quantum homomorphisms.If X quantum-homomorphically maps to Y, then projective rank of X is at most that of Y.Source: §1 · p. 3
2 Homomorphism Game
The homomorphism game asks two noncommunicating players to return target vertices consistently and preserve adjacency. The paper characterizes classical and quantum strategies, derives structural properties, and relates quantum homomorphisms to ordinary homomorphisms and non-signalling strategies.
2.1 The Classical Strategy
- Classical players win the homomorphism game with certainty if and only if a graph homomorphism from X to Y exists.Shared randomness cannot change this condition because every deterministic strategy used with nonzero probability must win.Source: §2.1 · p. 5
2.2 The Quantum Strategy
- A quantum homomorphism exists exactly when projectors satisfy the game’s consistency and adjacency orthogonality constraints.The projectors can be chosen real; when Y is vertex-transitive, they can also be chosen to have equal rank.Source: §2.2 · p. 6
2.3 Basic Properties of Quantum Homomorphisms
- Quantum homomorphisms are transitive, and a connected source graph mapping quantumly into a disconnected target maps into one component.The construction composes winning strategies for X to Y and Y to Z.Source: §2.3 · p. 7
2.4 Reformulating Quantum Homomorphisms in Terms of Homomorphisms
- X quantum-homomorphically maps to Y exactly when X maps ordinarily to M(Y), a graph built from projective measurements indexed by Y’s vertices.The graph M(Y) may be difficult to analyze and has uncountably many vertices.Source: §2.4 · p. 8
2.5 Non-signalling Strategies
- Arbitrary non-signalling correlations let players play the homomorphism game as well as if they could communicate during it.The paper notes that such correlations need not be physically producible.Source: §2.5 · p. 9
3 Lov´asz ϑ
The paper proves that complement Lovász theta, already preserved by ordinary homomorphisms, is also preserved by quantum homomorphisms. This yields a computable obstruction to a quantum homomorphism when the source’s theta value is larger than the target’s.
3 Lov´asz ϑ
- Complement Lovász theta is efficiently approximable through a semidefinite program and is preserved by ordinary graph homomorphisms.The paper uses a definition in terms of homomorphisms into an infinite graph of unit vectors.Source: §3 · p. 10
- If X quantum-homomorphically maps to Y, then complement Lovász theta of X is at most that of Y.The proof represents vertices of X by real vectors constructed from the projectors witnessing the quantum homomorphism.Source: §3 · pp. 10–11
- If complement Lovász theta of X exceeds that of Y, then X cannot quantum-homomorphically map to Y.The paper notes that no general algorithm is known for deciding whether such a quantum homomorphism exists.Source: §3 · p. 11
4 Quantum Parameters
This section develops consequences of quantum homomorphisms for graph parameters, showing that quantum independence and clique numbers can differ from their classical counterparts while quantum odd girth agrees with classical odd girth, and establishing a Lovász-theta lower bound on quantum chromatic number. It also relates homomorphisms to vertex-transitive targets to homomorphisms into Kneser graphs and gives a Lovász-theta corollary for those targets.
4.1 Quantum Chromatic Number
- The complement Lovász theta number lower-bounds χq(X), improves on the previous ω(X) bound, and is efficiently approximable despite χq(X) being of unknown computability.The improvement follows from ω(X) ≤ θ̄(X), while ω(X) is NP-hard to compute.Source: §4.1 · p. 12
4.2 Quantum Independence and Clique Numbers
- If X quantumly maps to Y but does not map classically, the homomorphic product yields αq(X ⋉ Y) > α(X ⋉ Y), creating quantum advantage with a non-complete target.The construction is inspired by and generalizes Theorem 16 of [MSS13].Source: §4.2 · pp. 13, 15
- For graphs X and Y, X maps to Y quantumly exactly when αq(X ⋉ Y) = |V(X)|, extending the corresponding classical characterization using α.The quantum lemma’s converse relies on the quantum strategy; the analogous non-signalling version does not hold.Source: §4.2 · pp. 13, 15
- For Ω_n □ K_n, quantum independence reaches |V(Ω_n)|, while classical independence is bounded by nα(Ω_n), yielding a large separation for n divisible by 4.The classical bound uses Vizing’s result together with the bound on α(Ω_n) from.Source: §4.2 · p. 15
- The paper bounds the quantum clique number and establishes a quantum clique-coclique bound for vertex-transitive graphs, but a quantum no-homomorphism lemma does not hold in general.The proposed no-homomorphism implication fails for Ω_n when n is a multiple of 4 but not a power of 2.Source: §4.2 · pp. 15–16
4.3 Walks and Quantum Odd Girth
- Quantum homomorphisms preserve walks of every length, implying that quantum odd girth always equals ordinary odd girth.The walk lemma says that if x and x′ are joined by a length-ℓ walk but y and y′ are not, the corresponding projectors are orthogonal.Source: §4.3 · p. 17
- A quantum homomorphism from C_g to X implies C_g → X, so quantum odd girth equals classical odd girth.The proof shows X contains an odd cycle of length g or less; the reverse comparison follows from the definitions.Source: §4.3 · p. 18
4.4 Quantum Homomorphisms to Kneser Graphs
- If X ⋉ Y maps to K_{n:r} with nr = |V(Y)|, then X maps to Y.The classical implication follows by bounding α(X ⋉ Y) by |V(X)| and applying Lemma 4.4.Source: §4.4 · p. 18
- For a subgroup G of Aut(Y) acting transitively on V(Y), homomorphisms from X to Y correspond to homomorphisms from X ⋉ Y to K_{n:r}.Here n = |G| and r = |G|/|V(Y)|; the lemma covers both classical and quantum homomorphisms.Source: §4.4 · pp. 18–19
- For vertex-transitive Y, Corollary 4.16 gives a Lovász-theta bound related to the Kneser-graph construction, but it is weaker than Lemma 4.15.The paper notes that the corollary may be more practical because the theta number is efficient to approximate; it also cites [Rob16] for an equivalence that makes the corollary implied by Corollary 4.9.Source: §4.4 · p. 19
5 Zero-Error Capacity
Section 5 relates quantum homomorphisms to zero-error channel capacity and quantum independence. It uses that connection to construct graphs whose one-shot zero-error capacity increases with entanglement assistance.
5 Zero-Error Capacity
- For a classical channel, one-shot zero-error capacity is the independence number of its confusability graph, while shared entanglement defines the corresponding assisted capacity.Distinct messages must be encoded as mutually unconfusable inputs; such input sets are independent sets in the confusability graph.Source: §5 · pp. 19–20
- A quantum protocol sends each message using a measurement on Alice’s share of an entangled state, then lets Bob decode from his residual state and the channel output.The passage’s condition for successful decoding requires orthogonality of residual states for distinct messages and confusable inputs.Source: §5 · pp. 20–21
5.1 Relation to Quantum Independence Number
- Quantum independence number is related to entanglement-assisted one-shot zero-error capacity, with equality characterized by a strategy using projective measurements and a maximally entangled state.The equality condition is that c∗0(X) can be achieved using projective measurements and the shared state Φ.Source: §5.1 · pp. 21–22
- c0(X ⋉Y) < c∗0(X ⋉Y): when X q→Y but X does not homomorphically map to Y, the construction gives a graph with a strict entanglement-assisted capacity advantage.The passage gives c0(X ⋉Y) = α(X ⋉Y) < |V(X)| = αq(X ⋉Y) ≤ c∗0(X ⋉Y) ≤ |V(X)|.Source: §5.1 · p. 22
5.2 Relation to Quantum Homomorphisms
- Quantum homomorphisms preserve the order of entanglement-assisted one-shot zero-error capacity.The section also describes applying a homomorphism coordinatewise on graph products as part of its asymptotic discussion.Source: §5.2 · pp. 22–23
- The entanglement-assisted Shannon capacity is the asymptotic version of the one-shot assisted capacity, and the paper considers an asymptotic extension of its homomorphism result.The strong product X ⊠Y has vertex set V(X)×V(Y), with distinct vertices adjacent when each coordinate is equal or adjacent.Source: §5.2 · p. 23
6 Projective Rank
Projective rank is a fractional, projector-based graph parameter connected to quantum homomorphisms and several classical graph parameters. It is monotone under quantum homomorphisms, though its computational properties remain uncertain.
6 Projective Rank
- A d/r-projective representation assigns rank-r projectors to vertices, with adjacent vertices receiving orthogonal projectors; projective rank is the infimum of representation values d/r.The infimum is not known always to be attained or rational.Source: §6 · pp. 23–24
- A projective representation of X ⋉ Y with value |V(Y)| implies X q→Y, and the converse holds when Y is vertex transitive.The value is motivated by the fact that X ⋉ Y contains a clique of size |V(Y)|.Source: §6 · pp. 23–24
6.1 Relation to Other Parameters
- Projective rank is at most orthogonal rank, fractional chromatic number, and quantum chromatic number.Rank-one projective representations recover orthogonal representations, while fractional coloring gives a projective representation and quantum coloring bounds projective rank.Source: §6.1 · pp. 24–25
- The theta number of the complement lower bounds projective rank: θ̄(X) ≤ ξf(X).The paper extends the known θ̄ lower bounds for orthogonal rank and fractional chromatic number.Source: §6.1 · p. 25
- For vertex-transitive X, projective rank is at most |V(X)|/αq(X), yielding a quantum-independence upper bound stronger than the cited earlier bound.The construction sums the projectors associated with each vertex to form a projective representation.Source: §6.1 · pp. 25–26
6.2 Relation to Quantum Homomorphisms
- Quantum homomorphisms preserve the order of projective rank: X q→Y implies ξf(X) ≤ ξf(Y).The proof combines the homomorphism projectors with a projective representation of Y; the resulting parameter may be difficult or impossible to compute.Source: §6.2 · pp. 26–27
7 Concluding Remarks
The concluding comparison places classical and quantum graph parameters in a partial order, with examples separating several classical and quantum measures. The paper also identifies unresolved questions about decidability, parameter separations, and whether key bounds are always attained or equal.
7 Concluding Remarks
- The chromatic number can strictly exceed fractional chromatic number, quantum chromatic number, and orthogonal rank; fractional chromatic number is incomparable with both quantum chromatic number and orthogonal rank.The paper also places projective rank strictly below these three parameters.Source: §7 · p. 27
- The complement theta number is at most projective rank and is strictly below it on C5; examples also show strict separation between the asymptotic parameters ¯Θ∗ and ¯Θ.The cited text gives ξf(C5)=5/2.Source: §7 · pp. 27–28
7.1 Open Questions
- It remains open whether quantum-homomorphism existence is decidable; bounding the required projector dimension would make the decision problem decidable.The question remains open even for quantum colorings.Source: §7.1 · p. 28
- Quantum versions of chromatic number and independence or clique number can separate from their classical counterparts, whereas quantum and classical odd girth do not separate.The authors ask which other graph parameters admit such separations.Source: §7.1 · p. 28
- The paper leaves open whether projective rank always attains its infimum or is always rational, and whether quantum independence always equals entanglement-assisted one-shot zero-error capacity.The latter equality would imply attainment using projective measurements on a maximally entangled state.Source: §7.1 · p. 28