122 citations · 289 across the 18 of their papers we have counts for
Showing 2006Show all
3 papers · 1 filter
quant-ph2006★ 14 cited
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…
quant-ph2006★ 30 cited
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…
quant-ph2006★ 3 cited
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…