The HHL algorithm's BQP-completeness relies on its ability to simulate arbitrary quantum computations, which depend crucially on quantum interference—an effect enabled by complex or negative matrix entries. When restricting the matrix ( A ) and the vector ( |b\rangle ) to have entries only in ({0,1}), several key issues arise:

1. Lack of Interference Mechanism: Quantum interference, e...

Short answer: Not with the known proofs, and very likely not. All existing BQP–hardness proofs for the quantum linear systems problem (QLSP/HHL) fundamentally use negative (or complex) matrix elements to encode quantum phases. If you forbid those and insist that every entry of A and of b is in {0,1}, the standard reduction to a generic quantum computation breaks down. Moreover, under natural extra...

First, recall that the HHL algorithm is BQP-complete for general matrices and vectors (with complex e...

Below is a sketch of why one does ​not​ get a BQP‐hardness proof once you insist that all matrix‐entries (and all amplitudes of the right‐hand side |b〉) lie in {0,1}. In fact nobody has yet shown that “HHL with 0–1 matrices” remains BQP‐hard; all of the existing BQP‐completeness reductions (both the original one via phase‐estimation / linear‐system‐inversion and the Janzing–Wocjan style “matrix‐p...

Short answer
We do not know.
The quantum–linear–systems problem remains in BQP when the input matrix A and the right–hand side |b⟩ contain only the symbols 0 and 1, because the HHL algorithm itself does not use negative numbers in the input—it creates the necessary phases during the computation. What is not known is whether this sign-free version is still BQP-hard. Every published BQP-hardne...

This is a great question that touches on the relationship between computational complexity and the structure of quantum interference.

The short answer is: No, HHL is likely not BQP-complete when restricted to matrices with entries in {0,1}.

Here's why:

The Role of Negative/Complex Amplitudes in BQP

As you correctly noted, the ability to have negative or complex amplitudes is fundamental...

Excellent question. You've hit on a very subtle but crucial point in quantum complexity theory, and your intuition is spot on.

The short answer is: No, HHL is not expected to be BQP-complete if the matrix A and vector |b⟩ are restricted to have entries only in {0, 1}. In fact, this restricted problem is strongly believed to be in the classical complexity class AM (Arthur-Merlin), and ...

Is HHL Still BQP-Complete with Only {0,1} Matrix Entries?

Based on the evidence provided, it's highly likely that HHL is not BQP-complete when entries of A and b are restricted to {0,1}.

Why the {0,1} Restriction Matters

The standard BQP-hardness reduction for HHL relies crucially on encoding arbitrary quantum computations into the linear system. Let's analyze why the {0,1} restriction...

Short answer
We do not know how to make the usual HHL–hardness construction work if one is only allowed a matrix whose entries are contained in the set {0,1}.
In fact, if one imposes this restriction the linear–systems problem very likely becomes strictly easier: it can be placed in the interactive-proof class AM by a straightforward approximation procedure, whereas a BQP-hard instance would i...