# Can the analysis or design of quantum algorithms benefit from parameterised algorithmics?

In the last decades, the field of parameterised algorithms, with fixed parameter tractibility (FPT) as its main tool has been provided new methods to analyse old algorithms and design techniques for new algorithms.

The basic idea of parameterised algorithms is that we 'pick' another parameter of our input other than the size (such as treewidth) and design algorithms that are efficient under the assumption that the chosen parameter is a (small) constant.

I wonder if the analysis and design of quantum algorithms can benefit from this approach. Has this been done, or are there good reasons why this is likely ineffective or ignored so far?

• The HHL subroutine for producing quantum states representing solutions to systems of equations and related algorithms depend on the sparseness of the matrix, but also the condition number $$\kappa$$ of the matrix, in the system of equations. The condition number in particular plays a prominent role in many analyses of this problem — the results are typically $$O(\mathrm{poly}(\kappa) \log(N))$$ algorithms for matrices of size at most $$N \times N$$.
While it doesn't seem as though there is much scope for interesting development on the dependency on $$\kappa$$, bear in mind that it is probably more informative to consider the logarithm of the condition number as the more natural feature of the input. (It is easy to efficiently express matrices with exponentially large condition number.) If we write $$\lambda = \log(\kappa)$$, suddenly that $$\mathrm{poly}(\kappa) = 2^{O(\lambda)}$$ dependency seems more important. And there are other ways in which $$\lambda$$ seems the relevant thing to consider from a complexity-theoretic standpoint fixed-parameter complexity — for instance, if a quantum algorithm could be found with only $$\mathrm{poly}(\lambda)$$ dependency, it would imply that $$\mathsf{BQP = PSPACE}$$. If we consider this to be unlikely in the same way that we consider $$\mathsf{P = NP}$$ to be unlikely, it seems that fixed-parameter tractability in terms of $$\lambda$$ fits in the same spirit as fixed-parameter tractability of $$\mathsf{NP}$$-complete problems.