# Requirement of vector 'b' in the definition of Phase Estimation Sampling (PES)

In this paper (last paragraph, page 3) by Wocjan and Zhang, the definition of PES requires vector/bit string b. The phase estimation problem (PE) very much inspires the definition.

I cannot understand the vector b requirement in the PES definition.

I guess it has some connection to the 'distance/measure' defined in the sample space. Perhaps vector b brings a weight factor to account for uniformity in the definition. (or, states/vectors nearby b need to be more precisely estimated than the faraway vectors to b.)

The discussion in question appears to be discussing usage of the Quantum Phase Estimation algorithm when we do not have access to an eigenstate $$|\eta_j \rangle$$ of the unitary matrix $$U$$ in question. This is almost always the case in practice as one may assume that the task of obtaining an eigenstate is similarly as hard as finding an eigenvalue $$\lambda_j = e^{2\pi\phi_j}$$, which is the main purpose of QPE.
The paper you have linked suggests using a bit string-encoded state $$|b\rangle$$ as an approximate eigenstate $$|\eta_j \rangle$$, such that the probability of success now depends on the squared overlap: $$P_{\text{success}} \propto |\langle b|\phi_j\rangle|^2$$.
• +1 but the paper makes no claims as to whether $|b\rangle$ is an approximate eigenstate of $U$ or not; rather, a key point of the paper is to imply that merely sampling from the probability distribution induced by $U$ and $|b\rangle$ together, with probability given by the squared overlap of $|\langle \phi_j | b\rangle|^2$, is, as a sampling problem, BQP-complete. It may be convenient for $|b\rangle$ to be a computational basis state, but that's not required for the BQP-completeness proof (only that $|b\rangle$ is easy to prepare). Mar 23 at 23:43