We introduce two models of space-bounded quantum interactive proof systems, $\mathbf{QIPL}$ and $\mathbf{QIP_\mathrm{U}L}$. The $\mathbf{QIP_\mathrm{U}L}$ model, a space-bounded variant of quantum interactive proofs ($\mathbf{QIP}$) introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000), restricts verifier actions to unitary circuits. In contrast, $\mathbf{QIPL}$ allows logarithmically many intermediate measurements per ... more >>>

Driven by exploring the power of quantum computation with a limited number of qubits, we present a novel complete characterization for space-bounded quantum computation, which encompasses settings with one-sided error (unitary coRQL) and two-sided error (BQL), approached from a quantum (mixed) state testing perspective:
- The first family of natural ... more >>>

We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously ... more >>>