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!


1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.