Let $H$ be a Hermitian matrix of dimension $2^k$ - i.e. on a system with $k$ qubits. Let $H$ be invariant under permutations of qubits. I would like to express $H$ in the following form:
$$H=\sum_{\alpha} c_{\alpha} H_{\alpha}^{\otimes k},$$
where $H_{\alpha}$ are Hermitian matrices of dimension $2$.
My question is: given that $H$ is permutation-invariant - is such a form always possible? If yes, can we a) find an upper bound on the number of terms we need in the sum and b) construct an algorithm that returns the $H_{\alpha}$ in poly-time with either the minimum number of terms or some approximately minimal number of terms?
A specific example I would like to solve is if $H$ is a rank-1 projector onto some permutation-invariant $k$-qubit state $|\Psi\rangle$, say the GHZ state $\frac{1}{\sqrt{2}}(|00\ldots0\rangle + |11\ldots1\rangle)$.
Example 1: Let $H=I_1Z_2+Z_1I_2$. Then $H=\frac{1}{2}(I_1+Z_1)(I_2+Z_2)-\frac{1}{2}(I_1-Z_1)(I_2-Z_2)$, so we only need two terms.
Example 2: Let $H=|\Psi\rangle\langle\Psi|$, where $|\Psi\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$. Then $H=II+XX-YY+ZZ$, so there are four terms, but can we do this in less than four terms?
Steps taken:
- Eq. 11b of this paper shows that H is in the span of $|\phi\rangle\langle\phi|^{\otimes}n$. However it is still unclear if there is a construction with a finite number of terms.
2: Eq. 7 and Definition 17 of this paper shows that $H$ can be written as a linear combinations of ``orbits'' of Pauli strings, which in our case are defined by $S_k (P) = \sum_{\pi \in S_k} \pi(P)$. Then the problem can be reduced to express any orbit of $P$ in the desired form.
