Given a stabilizer state, check if all k qubit subsets are maximally mixed

Question

Problem

I’m checking if all k-qubit subsets of a n-qubit stabilizer state are maximally mixed.

Approach that works, but is slow

The following approach works. But it's numerically painful, so I'm looking stim tricks or some lin alg result that may help me.

1. List the stabilizer states generators in their binary symplectic representation.
2. Pick n-k qubits to trace out. Remove the columns corresponding to those n-k qubits.
3. Calculate the rank of the remaining matrix. From the rank the entanglement entropy follows. Check if the EE is maximized.
4. Repeat for all choices of n-k qubits.

This works, but scales as O(n choose k) O(n^3). Here's my simple stim code:

tab = stim.TableauSimulator()
## (Add gates here)
tableau = tab.current_inverse_tableau()**-1
==============================================================================
Get binary symplectic rep. of the generators (i.e. tableau's z_output)
==============================================================================
gens = np.array([tableau.z_output(m) for m in range(len(tableau))])
N = len(gens)
BSR = np.zeros((N, 2*N), dtype=int)
BSR[:, :N] = (gens == 1) | (gens == 2) # Fill first N columns with 1 if gens = 1 or 2 (i.e. X part)
BSR[:, N:] = (gens == 2) | (gens == 3) # Fill next N columns with 1 if gens = 2 or 3 (i.e. Z part)
==============================================================================
Find smallest rank for all possible k
==============================================================================
ranks = []
comb_array = np.array(list(combinations(range(N), k)))
for columns_to_keep in comb_array:
    RM = BSR[:, np.concatenate([columns_to_keep, N + columns_to_keep])].astype(int)
    ranks.append(np.linalg.matrix_rank(RM))
rank = min(ranks)

I was thinking there might be a more clever way to use stim to get the answer.

---

Stated as a purely lin alg problem

I have an n by 2n binary matrix. For example:

[[1 0 1 0 1 0 1 0 0 0 0 0 0 0]
 [0 1 1 0 0 1 1 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 1 1 0 0 0 0]
 [0 0 0 1 1 1 1 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 1 1 0 0]
 [0 0 0 0 0 0 0 0 1 0 1 0 1 0]
 [0 0 0 0 0 0 0 1 1 0 1 0 0 1]]

I pick a number between 0 and n, which I call k. I find the combination of 2k columns of the matrix which have the minimum rank. In this case it be, for k =3:

[[1 0 1 0 0 0]
 [0 1 1 0 0 0]
 [0 0 0 1 1 1]
 [0 0 0 0 0 0]
 [0 0 0 1 0 0]
 [0 0 0 0 1 0]
 [0 0 0 1 1 0]]

My only restriction is that if I choose column j I need to also include column j + n.

Answer 1

This is not a fully formed solution, but is how I would get started...

Every stabilizer state is locally equivalent to a graph state, which has the special property that the $n\times 2n$ matrix can be written as $$ \begin{bmatrix} 1 & A \end{bmatrix} $$ where $1$ is the $n\times n$ identity matrix. The diagonals of $A$ are empty, and this defines the adjacency matrix of some $n$ vertex graph. (You can achieve this through a combination of performing row reduction on your matrix, swapping columns between the two blocks using Hadamard gates, and possibly applying $\sqrt{Y}$.)

Consider a subset of $k$ vertices on the graph. I can group these together on the adjacency matrix so that their connections are specified by $A_k$: $$ A=\begin{bmatrix} A_k & B^T \\ B & A_{\bar k} \end{bmatrix}. $$ I claim that that subset will be maximally mixed if $B$ has maximal rank modulo 2 (i.e. rank $k$). To see this, note that the maximally mixed nature of a subset is unchanged by performing unitaries on the partition. Hence, we can perform controlled-phases along the edges of $A_K$ and $A_{\bar k}$, which removes those edges. So it's equivalence to $$ A'=\begin{bmatrix} 0 & B^T \\ B & 0 \end{bmatrix}. $$ This graph state can be written as $$ |\psi\rangle=\sum_{x\in\{0,1\}^k}|x\rangle Z_{Bx}|+\rangle^{\otimes (n-k)} $$ where $B_y$ uses a binary vector $y$ to specify which qubits to apply $Z$ to. Let's trace out the other system. $$ \rho=\sum_{x,y\in\{0,1\}^k}|x\rangle\langle y|\langle +|^{\otimes (n-k)}Z_{B(x\oplus y)}|+\rangle^{\otimes (n-k)}. $$ The inner product is 1 only if $B(x\oplus y)=0$. This clearly happens in $x=y$, so we get all the diagonal elements. If $B$ has rank $k$ (modulo 2), there are no vectors $z$ such that $Bz\equiv 0\text{ mod }2$, so there are no diagonal elements, and we have a maximally mixed state. If $B$ has a smaller rank, there exists a $z$, and hence the density matrix has off-diagonal elements. It is not maximally mixed. This is something called the cut-rank of the graph, limited to a partition size of $k$. You want to know if the cut-rank is $k$. (Interesting note: the cut-rank is preserved by local complementation.) The rank-width of $A$ may also be relevant, but I'm unsure.

A necessary condition is that every vertex must have degree at least $k$. If not, select a vertex that has degree less than $k$. Select a subset of vertices that includes all its neighbours as well. This subset is no more than $k$ vertices (qubits). But at least one vertex has no edges outside the set. In other words, at least one row of $B$ is the all zeros row, and $B$ does not have maximal rank. So, this gives a very quick first check. One still has to check the ranks of all possible $B$ matrices carefully. (I don't know if there's something more clever that one can do at this point.)

Computationally, one improvement that you could make is to work through every possible binary string of length $n$ and weight $w\leq k$. Compute $|\bar x\cdot(Ax)|\leq k-w$, which means evaluate $Ax$, and perform an element-wise multiplication with the complement of $x$ and count the remaining 1s. If the number of remaining 1s is less than (or equal to) $k-w$, then there exists a subset of $k$ places defined by $x+\bar x\cdot(Ax)$ (which is weight $k$ or less) such that the $B$ is not maximal rank, because there's an all 0s output. This probably scales marginally better than what you had.