# How many eigenstates are accessible in polynomial time?

A result of Hamiltonian complexity theory by Poulin et al. shows that only a small fraction of the volume of Hilbert space can be reached in polynomial time for any physical system or quantum computer. Notably, their main result addresses the difficulty of reaching arbitrary states in Hilbert space from some fiducial state.

I am interested in understanding how Poulin et al's result applies if one restricts themselves to only eigenstates. I'd like to understand how many of those eigenstates are accessible in polynomial time to a gate-based quantum computer. So, how many eigenstates of a Hamiltonian, and under what conditions, are reachable when from a fiducial product state (as one usually starts with in a quantum computer)?

Since it is known that finding the ground states of many Hamiltonians is QMA-complete, you cannot reach all eigenstates of a Hamiltonian except under rare instances. But, I wonder if can you reach any of the eigenstates, and how does the number of those reachable eigenstates scale with the qubit number etc.?

If your Hamiltonian $$\mathcal H$$ is non-degenerate, local (or sparse), and acts on $$m$$ qubits, and you can efficiently prepare your fiducial state $$|\psi\rangle$$ say as the all-$$0$$'s product state $$|000\cdots 0\rangle$$ on $$m$$ qubits, then you can certainly prepare at least one eigenstate, and perhaps up to a (polynomial in $$m$$)-number of eigenstates, with the Quantum Phase Estimation algorithm.

In detail, you can:

1. Simulate controlled versions of the Hamiltonian $$U=\exp(-i\mathcal H t)$$ acting initially on a lower register prepared in initial state by using an upper register of $$n=O(\log_2 m)$$ control ancillas;
2. Perform an inverse Quantum Fourier Transform on these $$m$$ ancillas in the upper register;
3. Measure the the upper register, which, by the axioms of quantum mechanics and up to some error associated with the Hamiltonian simulation and with the number of ancilla, project and collapse the lower register onto the eigenstate having eigenvalue given by the phase as measured in the upper register.

See also Wocjan and Zhang here. If I understand your question, they call this problem the "Local Hamiltonian Eigenvalue Sampling" problem.

They define this natural probability distribution based on the squared overlap of their initial state $$|\psi\rangle$$ with the eigenstates of the Hamiltonian. Their initial state runs through various (binary) strings, which could be done a polynomial number of times; you could also sample from the same fiducial state over and over again, and perhaps get different eigenvalues in the upper register (and hence necessarily have different eigenstates in the lower register).

• Do we know anything in the general case about whether the number of eigenstates you cannot prepare in polynomial time is exponentially large in qubit number compared to the polynomially-big states you can prepare? Jul 9, 2023 at 2:27
• I’m not sure I understand where you are going. An exponential-sized matrix certainly has an exponential number of eigenvalues/eigenvectors. For a generic local Hamiltonian I’d guess that most states are inaccessible, certainly with local eigenvalue Hamiltonian sampling, because the overlap with the fiducial state is too small (too low probability) to ever be sampled. Jul 9, 2023 at 2:54
• I guess I just wanted to know if there are "unphysical" eigenstates (as defined by Poulin et al), just like there are unphysical volumes of Hilbert space. And if the "physical" eigenstates are only polynomially big, with an exponentially large number of eigenstates which basically are irrelevant. Jul 9, 2023 at 3:13
• Does my last comment make any sense? Maybe the answer is trivial... Jul 12, 2023 at 1:55
• I don’t know - I’m of two minds. Certainly you could never have possession of an exponential number of eigenstates, but perhaps the density of states/the eigenvalues are normally distributed and you could in principle access most eigenstates except for the tail of the normal distribution, by doing Wocjan-Zhang sampling on different fiducial states… Other than that I’ve nothing to say, sorry! Jul 12, 2023 at 3:35