# Efficient diagonalisation of low-rank observables

Let $$n$$ be the number of qubits we're using, and let $$\mathrm H=\sum_{i=1}^T\alpha_i\mathrm U_i|0\rangle\langle0|\mathrm U_i^\dagger$$ be an $$n$$-qubit hermitian observable where $$T=O(\mathrm{poly}(n))$$, $$\alpha_i\in\mathbb R\!\setminus\!\{0\}$$ and $$\mathrm U_i$$ a unitary that can be implemented as a circuit of size $$O(\mathrm{poly}(n))$$.

For my purposes, I would like to express $$\mathrm H$$ as an observable consisting of only a single term, without any ancillary qubits; thus, the most general desired form is $$\mathrm H=\mathrm W\mathrm D\mathrm W^\dagger$$ with $$\mathrm W$$ an $$n$$-qubit unitary and $$\mathrm D$$ a $$2^n\times2^n$$ real diagonal matrix.

Question: is there a construction of $$\mathrm W$$ and $$\mathrm D$$ that can be computed in time $$O(\mathrm{poly}(n))$$, possibly exploiting that $$\mathrm H$$ is of low rank (namely polynomial in $$n$$)? Clearly, $$\mathrm W$$ and $$\mathrm D$$ can be brute forced by diagonalising $$\mathrm H$$, but from what I have found even the fastest diagonalisation algorithms still run in time proportional to the dimensionality of $$\mathrm H$$, which is exponential.

Of course, if you know of any papers related to this question, sharing would be highly appreciated. Thanks!

There are a few things you can say quite easily. Let $$|\psi_i\rangle=U_i|0\rangle.$$ Now, let $$|\phi\rangle$$ be a state that is orthogonal to all of these states. Then $$H|\phi\rangle=0.$$ This is most of your job done given that the Hilbert space is of dimension $$2^n$$, and your space spanned by the $$|\psi_i\rangle$$ is no more than size poly($$n$$).
So, now, I'd probably construct a matrix $$H'=\sum_{i,j}|i\rangle\langle j| \langle\psi_i|H|\psi_j\rangle,$$ which only has polynomial size. I don't know how easily you can construct this - it might depend on exactly what you're assuming you know but, frankly, if you cannot compute these values, there's not a whole lot you will be able to do classically! If you can diagonalise $$H'$$ (which should be fine), you can diagonalise $$H$$.