up vote 7 down vote favorite

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?

share|improve this question
up vote 3 down vote accepted

Indeed, there are already parameterised quantum algorithms. I describe just two examples, one fairly famous and one fairly recent:

  • 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.

  • There are also quantum algorithms for semidefinite programming, with complexity parameterised by the dimension of the input matrix, the row-sparsity of the input matrix, the number of constraints, and bounds on the size of primal and dual solutions.

As quantum computers will initially be much more expensive and less available than classical computers, and have a slower clock speed to boot, it makes a great deal of sense to look for parameterised quantum algorithms: ones which will prove effective for problems of interest, under conditions of interest, allowing us to pinpoint use-cases where quantum computers can be particularly effective.

share|improve this answer
  • A nice answer, thank you. The last paragraph confirms my suspicions about the utility of parameterised analysis for quantum algorithms. It is nice to see that this is indeed used in some form. (although it seems the connection to FPT isn't mentioned explicitly. Perhaps time will tell whether making the explicit connection would be of use) – Discrete lizard Apr 5 at 17:45

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.