Are there works on "quantum parametrized complexity"?

Question

I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. I don't know if researchers in quantum complexity have started using parameterized complexity or not, so I will not comment on that. I tried to search on google but did not find able to find anything.

Question : Are there works on "quantum parametrized complexity"?

Answer 1

As far as I'm aware, parameterized complexity theory has not been formally introduced to quantum computing so far.

Many problems in the field, though, are well-known to be tractable once a key parameter is fixed, such as constant spectral gaps of local Hamiltonian operators, or bounded condition numbers of various matrices. Fixing the parameter often lead to tractable subclasses of problems (see Matrix Product States and Lieb-Robinson bounds) or efficient classical or quantum algorithms (e.g. Harrow-Hassidim-Lloyd algorithm), for which the general problem is usually exponential in that parameter.

There are some works that explicitly use standard parameters of the fixed-parameter tractability (FPT) literature, e.g.

• Markov and Shi [https://arxiv.org/abs/quant-ph/0511069] show how to efficiently and classically compute acceptance probabilities of quantum circuits viewed as tensor networks with bounded tree-width
• Bravyi [https://arxiv.org/abs/0801.2989] shows how to contract matchgate circuits on non-planar graphs with bounded genus
• Van den Nest and Briegel [https://arxiv.org/pdf/quant-ph/0610040.pdf] show that measurement-based quantum computing, which is performed on a family of graph states G, can be classically efficiently simulated if G has a decidable C$_2$MS logic theory (based on a result of Courcelle and Oum implying bounded rank-width of such graphs).

Answer 2

There is the following recent work:

https://arxiv.org/abs/2203.08002