211 citations · 1.2k across the 74 of their papers we have counts for
4 papers · 2 filters
BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
Dominik Janzing, Pawel Wocjan
We describe two BQP-complete problems concerning properties of sparse graphs having a certain symmetry. The graphs are specified by efficiently computable functions which output th…
Several natural BQP-Complete problems
Pawel Wocjan, Shengyu Zhang
A central problem in quantum computing is to identify computational tasks which can be solved substantially faster on a quantum computer than on any classical computer. By studying…
Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete
Dominik Janzing, Pawel Wocjan
Let A be a real symmetric matrix of size N such that the number of the non-zero entries in each row is polylogarithmic in N and the positions and the values of these entries are sp…
The Jones polynomial: quantum algorithms and applications in quantum complexity theory
Pawel Wocjan, Jon Yard
We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum ci…