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\}$ ?

  • $\begingroup$ You're asking two different questions. The question about whether HHL is BQP-complete, if all the entries of A and |𝑏⟩ are in {0,1}, is clear enough. But you're never going to construct A = I - U exp(-1/T) and still have coefficients in {0,1}, so it's not clear how that construction could play any role. So, are you asking about the role of the minus sign in the construction, or are you asking about constraining the values of A? $\endgroup$ Aug 24, 2020 at 11:49
  • $\begingroup$ So, you've added some commentary about the role of negative entries, but the main question (the title, the reasonable question towards the end) is still about {0,1} entries. Also: in your recent edit, it's not clear that the claim about $A = I - U\exp(-1/T)$ is what you intend to claim (do you mean $A^{-1}$ by chance?), or that the statement that you might like to make is correct (what about the special case where $U$ is constructed only from classical reversible gates?). $\endgroup$ Aug 25, 2020 at 10:13
  • $\begingroup$ I'd be willing to have a go at editing the question, if what you'd like is something specifically addressing the case where A and |𝑏⟩ have {0,1} entries, together with some remarks putting the question in context. As it stands, it still feels a bit as though you're asking one thing because you want to know the answer to something else. $\endgroup$ Aug 25, 2020 at 10:15
  • 1
    $\begingroup$ I've made some changes. I think I understood your question better once I read it with a different emphasis, and I've tried to amplify that emphasis. $\endgroup$ Aug 25, 2020 at 13:15
  • 1
    $\begingroup$ (Having said that, seeing how having entries of {0,1} for $A$ is still not the same as having {0,1} entries for $A^{-1}$ or a matrix $\tilde A$ whose powers you would like to learn about, I still think that having non-negative entries for $A$ itself is a bit of a red herring... once you take the inverse of $A$, negative entries can still arise, shedding no further light on the question quantum computational difficulty without destructive interference.) $\endgroup$ Aug 25, 2020 at 13:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.