What follows is a nice problem that was recently posed by Mario Krenn. Progress on this problem may lead to new insights in quantum physics (see this, this, this, and this for details). In addition, Mario has announced two cash prizes to encourage work in this direction. (!)
Consider a weighted and edge-colored bipartite graph consisting of
- disjoint vertex sets and ,
- an edge set ,
- an edge coloring , and
- a complex vertex weighting .
This graph provides a combinatorial abstraction of a quantum mechanical system. Specifically, denotes a set of photon sources, is the set of optical output paths, is the set of all possible photons, gives the mode number of photon , and the complex weights allow one to model quantum interference between the photon sources. Consider the following experiment: Place a detector at each , and let each randomly produce either correlated photons or no photons. We are interested in the event that all detectors simultaneously detect exactly one photon. The mode numbers of these photons can be viewed as a vertex coloring , and this coloring reveals some information about which sources produced which photons. Specifically, we say is -consistent if
- the neighborhoods form a partition of , and
- for every and every , it holds that .
In quantum optics, we cannot directly access the mode numbers of the photons, and in fact, we obtain a superposition of various possibilities. This superposition forms something called a Greenberger–Horne–Zeilinger (GHZ) state if satisfies an additional monochromatic property, defined below. Let denote the set of all -consistent , and define the weight of a coloring of to be
By convention, implies . We say is monochromatic if the weight of every coloring of takes the form
Here, denotes the image of the map . In words, is monochromatic if indicates whether gives every member of the same color in the palette . If is monochromatic, then the corresponding quantum mechanical system produces GHZ states, and the dimensionality of the state space is the size of the color palette .
In practice, one is interested in producing high-dimensional states with a given number particles, and the most practical of photon sources creates only two photons. For these reasons, we are particularly interested in the supremum of over all monochromatic such that and for every . Let denote this supremum. Notice that the constraint on implies that is monochromatic only if is even. For such , Mario poses the following conjecture:
Excitingly, there are two prizes associated with this conjecture. First, there’s a 3000-Euro prize for its resolution (i.e., for either a proof or a disproof). In addition, there’s a 1000-Euro best-paper award offered for the best results obtained in this vein (to be judged by Mario). See this page for more details.
To explain the source of Krenn’s Conjecture, we point out that “half” of the conjecture is known to be true; that is, the inequality holds, while the inequality is open for every with . We obtain this lower bound on by restricting our attention to for which
- for every and , and
- for every .
This restriction is convenient, since we can capture using the edge-colored multigraph with vertex set , edge set , assignment defined by , and edge coloring defined by for every . For such , the corresponding is monochromatic if and only if the following hold simultaneously:
- for every color , there exists a unique perfect matching of such that , and
- for every perfect matching of , it holds that is a singleton set.
This reduces our problem to finding multigraphs whose perfect matchings are all disjoint, since one may color edges in the th perfect matching with , and then color any remaining edges with . Let denote the supremum of for which there exists a multigraph on vertices with a total of perfect matchings, all of which are disjoint. Then the above discussion gives
Notice we can already conclude for every by taking to be a -factor. In the special case where , one may draw arbitrarily many edges between the two vertices to obtain , i.e., . It remains to consider with . In this case, the multigraph we seek can be taken to be a simple graph without loss of generality (i.e., multiple edges are not helpful here), and so in this language, Ilya Bogdanov proved that equals the right-hand side of Krenn’s Conjecture. The case corresponds to the -factorization of , while the remaining cases correspond to the -factorization of :
In order to determine whether this lower bound is sharp, one must consider more general choices of . In particular, do non-unit weights on allow for a larger color palette? Interestingly, Mario has an example of with , , , and for every . However, this graph is only monochromatic in the limit as , so this does not quite prove that is at least .