Thursday, April 28, 2022

Pessimal quantum algorithms

I was reading about sorting algorithms the other day and stumbled upon the amusing topic of pessimal algorithms, which are horribly slow algorithms that "[do] indeed progress steadily towards [their] stated goal even though [they] may have very little enthusiasm for (or even a manifest aversion to) actually getting there."

Two examples of pessimal sorting algorithms are slowsort and bogosort, which have non-polynomial scaling (factorial scaling in the case of bogosort). Slowsort uses a multiply-and-surrender approach, while bogosort chooses random permutations until it obtains the correctly-sorted list.

A simple quantum version of bogosort might be a circuit composed of a single Hadamard gate applied to each qubit, followed by measurement; this similarly samples uniformly over the solution space, repeating until the correct answer is measured.

More generally, pessimal quantum algorithms might exploit maliciously-tuned quantum interference to obtain scaling worse than the most pessimal classical algorithm, for example by engineering destructive interference to suppress the probability of measuring the correct solution.

Are there any known examples of pessimal quantum algorithms exhibiting a rigorously-proven quantum slow-down? Pessimists might point to certain variational quantum algorithms and approaches based on mapping efficiently-solvable problems to more difficult problems such as finding ground states of quantum spin networks as potential candidates.

Pessimal quantum algorithms could be one of the first killer applications of quantum computers, satisfying clients who want to find spooky quantum solutions to their problems (efficiency be damned!) and hardware developers seeking to maximise the utilisation of their shiny new quantum processors.


No comments:

Post a Comment