TransWikia.com

Is HHL still BQP-complete when the matrix entries are only in {0,1}?

Quantum Computing Asked on May 15, 2021

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}notsubseteqmathsf{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}$ ?

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP