If 20th century humans had entrusted complexity theorists with the task of building digital computers, I dare say we would all still be using abacuses. And complexity theorists would still be writing papers about the amazing complexity issues raised by the abacus. Complexity theorists are not known for their skill at building practical things.
Maybe you don’t have the time and energy necessary to grok the definitions and inter-relationships among the hundreds of complexity classes in the Complexity Class Zoo. Maybe you are waiting for an executive summary, issued after complexity theorists figure out a classification theorem for all those classes. Until that executive summary is available, the field of complexity theory will continue to seem hopelessly half-baked to many of us.
Nevertheless, there is no doubt that some very smart people are complexity theorists, and that their work has enriched quantum computing significantly. So it pays off, even if you are a person with a more practical bend of mind, to pay attention to what they are up to. Complexity theorists also help to sell quantum computers to the public, by proving that quantum computers can calculate certain quantities that are totally inaccessible to classical computers. For example, Peter Shor proved that quantum computers can find the factors of very large integers in polynomial time, whereas all known classical algorithms require exponential time to do so. Another example is the recent paper:
This paper is about a topic that is near and dear to my heart, a topic that is key to what my program Quibbs does. The topic is: using a QC to sample probability distributions. So the rest of this blog post will be devoted to giving a brief summary of the AA paper. Perhaps I’ll say enough to pique your interest in the dark arts of complexity theory.
AA propose an optics experiment that would calculate (to a certain precision) a special probability distribution. For photon numbers , the AA optics experiment would take polynomial(n) steps to calculate this probability distribution, if quantum mechanics is to be believed. AA prove (assuming some very plausible conjectures about complexity classes) that a classical computer would require exponential(n) steps to calculate the same probability distribution (to the same precision). For slightly larger than 50, classical computers would take longer than the age of the universe to get an answer.
- number of modes (m is mnemonic for mode)
- total number of photons
- set of m-tuples , where the components are non-negative integers, and where . Each represents the number of photons in the j’th mode and thus is the total number of photons. For example, .
- , where there are ones and zeros. This assumes .
AA consider a conditional probability distribution where
- and is preferable.
- is a unitary transformation produced by an ideal (free of environmental noise) optical device consisting of passive elements (beam splitters and phase shifters). The optical device has input ports and the same number of output ports. A “mode” (i.e., a monochromatic beam of light) enters and exits each input and output port. By assumption, all input modes have the same frequency. Because phase shifters and beam splitters do not affect the frequency of a mode, all modes inside the device are at the same frequency too.
- takes poly(n) bits to specify. It includes all parameters that depends on
Let be an estimate of calculated from a number of samples of . These samples are obtained from a non-ideal experiment with environmental noise. AA assume (they expect experimentalists to corroborate this) that it is possible to perform an optical experiment with elementary gates (beam splitters or phase shifters) for which where for some polynomial of .