The concept of quantum computing was first proposed back in the 1980s and since then the race has been on to develop the first reliable, scalable quantum computer. Done right, this revolutionary technology could rapidly accelerate developments in fields like machine learning, drug development, finance, and cryptology. However, quantum computers are proving exceedingly difficult to build and program. Today’s early models are small, unstable, and can’t outperform normal computers at simple tasks. When the first fully-functional quantum computers are finally built they will likely have extremely small memories, so they will require specially-designed algorithms that don’t use a lot of memory.
Random Walk Algorithm
Stacey Jeffery is a tenure-track researcher at Centrum Wiskunde & Informatica (CWI) in Amsterdam who designs these types of algorithms. One of the algorithms she focuses on is a type of classic algorithm called a random walk algorithm. Random walk algorithms are used when a computer is looking for something but doesn’t know how to find it. “Think of it like looking for a bathroom in an unfamiliar city without a map or smartphone to help,” explains Stacey. All you can do is wander down the streets and turn left or right at random until eventually you find a bathroom. A random walk algorithm doesn’t use a lot of memory because the computer only needs to remember where it is right now, not where it’s been.
Stacey and her collaborators recently made a major breakthrough in the random walk algorithm. They showed that every random walk algorithm (not just special cases) can be made faster by using a quantum computer, which is something researchers have been trying to demonstrate for 15 years. Quantum computers can find solutions faster thanks to a physics principle called superposition. While a regular computer bit stores information as either a 0 or a 1, superposition allows a quantum computer bit to represent both 0 and 1 at the same time. Think of it like flipping a coin but then not checking to see whether it landed on heads or tails. The result is in a sense both heads and tails at the same time, or even a little bit heads or a little bit tails.
Going back to the bathroom analogy, a classical random walk algorithm tries one of many different potential paths to the bathroom at random in order to find the right one. However, in a quantum random walk algorithm, superposition causes different paths to interfere with each other. Sometimes two paths can actually add up while two others can actually cancel each other out. The goal is to have the good paths all add up and the bad paths all cancel each other out, leaving you with only the good paths to the bathroom.
