The Foliage Partition: An Easy-to-Compute LC-Invariant for Graph States

This paper introduces the foliage partition, an easy-to-compute LC-invariant for graph states, of computational complexity <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mn>3</mml:mn></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> in the number of qubits. Inspired by the foliage of a graph, our invariant has a natural graphical representation in terms of leaves, axils, and twins. It captures both, the connection structure of a graph and the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>2</mml:mn></mml:math>-body marginal properties of the associated graph state. We relate the foliage partition to the size of LC-orbits and use it to bound the number of LC-automorphisms of graphs. We also show the invariance of the foliage partition when generalized to weighted graphs and qudit graph states.