Thomas Watson, Dieter van Melkebeek

We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are complete problems for the first and second levels of the counting hierarchy, respectively. We prove that for every real $d$ and every positive real $\epsilon$ ... more >>>

Dieter van Melkebeek, Thomas Watson

We give two time- and space-efficient simulations of quantum computations with

intermediate measurements, one by classical randomized computations with

unbounded error and the other by quantum computations that use an arbitrary

fixed universal set of gates. Specifically, our simulations show that every

language solvable by a bounded-error quantum algorithm running ...
more >>>