$n$-qubit states with maximum entanglement across all bipartitions: A graph state approach

We discuss the construction of $n$-qubit pure states with maximum bipartite entanglement across all possible choices of $k$ vs $n-k$ bi-partitioning, which implies that the Von Neumann entropy of every $k$-qubit reduced density matrix corresponding to this state should be $k \ln 2 $. Such states have been referred to as $k$-uniform, $k$-MM states. We show that a subset of the 'graph states' satisfy this condition, hence providing a recipe for constructing $k$-uniform states. Finding recipes for construction of $k$-uniform states using graph states is useful since every graph state can be constructed starting from a product state using only controlled-$Z$ gates. Though, a priori it is not clear how to construct a graph which corresponds to an arbitrary $k$-uniform state, but in particular, we show that graphs with no isolated vertices are $1$-uniform. Graphs organized as a circular linear chain corresponds to the case of $2$-uniform state, where we show that the minimum number of qubits required to host such a state is $n=5$. $3$-uniform states can be constructed by forming bi-layer graphs with $n/2$ qubits ($n=2\mathbb{Z}$) in each layer, such that each layer forms a fully connected graph while inter-layer connections are such that the vertices in one layer has a one to one connectivity to the other layer. $4$-uniform states can be formed by taking 2D lattice graphs( also referred elsewhere as a 2D cluster Ising state ) with periodic boundary conditions along both dimensions and both dimensions having at least $5$ vertices.