[leftmargin = 0pt, font = ]
Hamiltonian simulation.
To prepare an eigenstate \(\ket {\phi _i}\)  we start from the uniform superposition \(\ket {\phi } = \sum _{I \in \operatorname{Cl}(\mathcal {O})} \ket {I}\)  (normalization omitted). Then we use phase estimation on the operators \(U_j = e^{iT_{n_j}}\)  to project onto an eigenstate \(\ket {\phi _i}\) . Since the matrices of the operators \(T_{n_j}\)  are sparse, standard Hamiltonian simulation techniques can be used to implement the unitaries \(U_j\) . However, for an integer \(t > 0\) , the cost of simulating \(U_j^t = e^{iT_{n_j}t}\)  depends linearly on \(t\) . More precisely, the simulation cost depends linearly on \(st {T_{n_j}}_{\max }\)  [1]}, where \(s\)  is the sparsity degree of \(T_{n_j}\) , i.e., the maximum number of nonzero entries in any row, and \({T_{n_j}}_{\max }\)  is the largest entry of \(T_{n_j}\)  in absolute value. This means, using phase estimation, we can approximate the eigenvalues of the \(T_{n_j}\)  only to accuracy \(1 / \operatorname{poly}(\kappa )\) .
Projecting onto an eigenstate.
To be able to project onto a single eigenstate, we cannot use only one of the \(T_{n_j}\) , since in that case we would need an exponentially accurate phase estimation. However, if we run a polynomially accurate phase estimation for all the \(T_{n_j}\) , we might be able to project onto a random eigenstate \(\ket {\phi _i}\) . For this to hold, one needs to make some heuristic assumptions on the distribution of the eigenvalues of the Heck operators. Such distributions are already studied in the literature [2]}, [3]}, [4]}, but a formal treatment of the running time of the above projection based on these distributions is nontrivial.

