Quantum computers are really difficult to build. No-one has yet managed to build one that can do something that a classical computer can’t do more quickly and easily. However, if someone does manage to build a quantum computer of reasonable power it could make all sorts of computations possible that aren’t practical today. For example, a quantum computer might be able to solve chess (predict whether black or white would win, or if it would be a draw, if both players made the best possible moves).
Current avenues of research for quantum computers seem to mostly involve building something that looks sort of similar to a classical computer, with bits and gates that can hold both 0s and 1s at the same time (and which can be entangled with other gates/bits).
This article got me wondering if there might be another (possibly easier) way to go about quantum computing. Imagine you have an irreguarly shaped loop of wire, that bends and twists at all sorts of strange angles in three dimensions. For some reason you wish to find the surface which has that loop as its perimeter, but with the smallest possible area. This is quite a difficult problem computationally, but extremely easy physically – to solve it all you need to do is put some detergent in some water and dip your loop of wire into it. The resulting soap bubble film will be exactly the surface you are looking for. The difficult problem is made easy by the massively parallel nature of the many molecules of soap and water.
Suppose we found a physical way to solve a certain class of hard computing problems (“NP complete problems”, to use a technical term). There is a theorem in computer science that (effectively) says if you can solve one NP complete problem, you can solve them all by rephrasing the unsolved problem in terms of the solved one. So all we would need to do would be to find a physical “computer” that could solve a particlar type of NP complete problem.
Quantum mechanics is extremely difficult to simulate on a computer, because every particle is “spread out” and computations must be done at each point in space to figure out what what will happen. There are some shortcuts for simple situations, but even moderately complex molecules are beyond our ability to simulate with a high degree of accuracy.
Perhaps it would be possible to solve some NP complete problem that would take centuries to solve with today’s computers by transforming it into some physical problem which could be solved by a quantum-mechanical analog computer (maybe something like a Bose-Einstein condensate interacting with atoms fixed in particular positions on some substrate), reading off the answer and then transforming it back into the answer of the original problem.
[Edited to add] Since writing this I have realized that analog quantum computers don’t really add anything because you can effectively only measure digital information. Even when making a measurement of some analog quantity your instruments are only so accurate so there will be a finite number of significant figures that you actually read off.
