Centrum Wiskunde & Informatica: Designing Random Walk Algorithms for Quantum Computing
Bringing Quantum Computers Closer to Reality
In brief…
+ 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.
Random walk algorithms are used when a computer is looking for something but doesn’t know how to find it.
+ 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.
Source: Centrum Wiskunde & Informatica. Sarah Binns, Bringing Quantum Computers Closer to Reality…
Content may have been edited for style and clarity.
