I'm studying BQP-completeness proofs of a number of interesting problems of Janzing and Wocjan, and Wocjan and Zhang. Janzing and Wocjan show that estimating entries of matrix powers $(A^m)_{ij}$ with $A_{ij}\in\{-1,0,1\}$ is (promise) BQP-complete. That is, the problem is both in BQP, and can simulate other problems in BQP.
Janzing and Wocjan emphasize that their BQP-hardness reduction requires a negative-sign in an entry of $A$ to simulate interference afforded by BQP algorithms. At a critical point in their reduction they apply a (conditional)-$Z$ rotation, which leads to a matrix $A$ with a negative entry. I don't think their proof of BQP-hardness would carry over when entries $A_{ij}$ are strictly non-negative, e.g. in $\{0,1\}$. Indeed, I believe that such a restricted matrix-powers problem may be amenable to some form of Stockmeyer approximation, e.g. in $\mathsf{AM}$, and hence not BQP-complete under the reasonable hypothesis that $\mathsf{BQP}\not\subseteq\mathsf{AM}$.
The proof of BQP-hardness of matrix powers appears initially to be similar to the BQP-hardness of the HHL algorithm, which was wonderfully summarized by @DaftWullie here. However, HHL considers the Taylor-series expansion of $A^{-1}$, where $A=I-Ue^{-1/T}$ and $U$ is a unitary operator which simulates a given unitary circuit with a clock register construction — so that $U$ (and powers of $U$) will have negative or complex entries, if any of the gates in the circuit do. For the case $\tilde A = U \mathrm{e}^{-1/T}$, this again suggests that the BQP-completeness of estimating entries of matrix powers $\tilde A^m$ is associated with whether $\tilde A$ has entries apart from non-negative reals.
Given this, considered as a special case of HHL which is motivated by the comparison to the problem of Janzing and Wocjan, I'd like to know: is HHL still BQP-complete if all of the entries of $A$ and $\lvert b \rangle$ are in $\{0,1\}$ ?
