Covering a Graph with Minimal Local Sets

Abstract

Local sets, a graph structure invariant under local complementation, have been originally introduced in the context of quantum computing for the study of quantum entanglement within the so-called graph state formalism. A local set in a graph is made of a non-empty set of vertices together with its odd neighborhood. We show that any graph can be covered by minimal local sets, i.e. that every vertex is contained in at least one local set that is minimal by inclusion. More precisely, we introduce an algorithm for finding a minimal local set cover in polynomial time. This result is proved by exploring the link between local sets and cut-rank. We prove some additional results on minimal local sets: we give tight bounds on their size, and we show that there can be exponentially many of them in a graph. Finally, we provide an extension of our definitions and our main result to $q$-multigraphs, the graphical counterpart of quantum qudit graph states.

Update: Fixed a minor mistake in Proposition 2 (an "if and only if" has been replaced by an "if")

References in corpus (22)

• Graph States for Quantum Secret Sharing
• Multipartite entanglement, quantum-error-correcting codes, and entangling power of quantum evolutions
• Graphical description of the action of local Clifford transformations on graph states
• Interacting Quantum Observables: Categorical Algebra and Diagrammatics
• Absolute Maximal Entanglement and Quantum Secret Sharing
• Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
• Maximally multipartite entangled states
• Absolutely Maximally Entangled states, combinatorial designs and multi-unitary matrices
• Genuinely multipartite entangled states and orthogonal arrays
• Absolutely maximally entangled states of seven qubits do not exist
• Entanglement and quantum combinatorial designs
• Bounds on absolutely maximally entangled states from shadow inequalities, and the quantum MacWilliams identity
• Exploring pure quantum states with maximally mixed reductions
• Local unitary versus local Clifford equivalence of stabilizer states
• Pivoting makes the ZX-calculus complete for real stabilizers
• Rank-width: Algorithmic and structural results
• Local unitary versus local Clifford equivalence of stabilizer and graph states
• Constructions of k-uniform and absolutely maximally entangled states beyond maximum distance codes
• Which graph states are useful for quantum information processing?
• Limitations of nearest-neighbour quantum networks
• $k$-uniform mixed states
• On the Minimum Degree up to Local Complementation: Bounds and Complexity