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


1 Answer 1


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

Using a bit string encoded initial state sometimes works quite well. Indeed, when using QPE to estimate an eigenvalue of a Hamiltonian H (which we encode in a unitary matrix U) in quantum chemistry, we call such a state the Hartree-Fock state. The ordered bit string corresponds to the occupation of molecular orbitals as determined by the Hartree-Fock method.

  • 3
    $\begingroup$ +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). $\endgroup$ Mar 23 at 23:43
  • $\begingroup$ @MarkSpinelli, point taken. Now I recognise this is complementing the jsbaker's argument in the context (Wocjan's paper.) $\endgroup$ Mar 24 at 17:44

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.