Adam Bouland
  • Member for 8 years, 11 months
  • Last seen more than a month ago
Books/Lecture Notes on Parametrized Complexity
23 votes

A good place to start is "Parameterized Complexity Theory" by Jörg Flum and Martin Grohe, published by Springer.

View answer
FPT algorithm for Partial k-tree Isomorphism
Accepted answer
6 votes

As M. Kanté pointed out, it's open whether or not graph isomorphism is FPT when parameterized by tree-width. Furthermore, I don't believe there is any complexity-theoretic barrier to creating an FPT ...

View answer
theorems for universal set of quantum gates for SU(d)
Accepted answer
5 votes

I'm not aware of any proof that the Clifford group + any non-Clifford element gives a universal set of quantum gates. The closest related result that I know is that the Clifford group + any non-...

View answer
Geometric Interpretation of Computation
5 votes

Nielsen et al. showed that quantum computing has a geometrical interpretation. Specifically, they showed that finding a short quantum circuit to perform a target unitary $U$ is equivalent to finding a ...

View answer
Clarification for argument in proof of search in N^1/3 queries with hidden variables/non-collapsing measurements
4 votes

The short answer is that the state we wrote down is only an approximation in the large $n$ limit (which is all that is required to prove the upper bound). The state isn't normalized for finite $n$, ...

View answer