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.
Stacey Jeffery is a tenure-track researcher at Centrum Wiskunde & Informatica (CWI) and QuSoft 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.
Collaboration is vital for producing these types of advancements and breakthroughs in theoretical research. Stacey’s work has been facilitated by the fact that CWI is located in Amsterdam Science Park which brings together researchers from eight different universities and institutes into one place. Stacey’s collaborators from the University of Amsterdam sit just across the hall from her so it’s easy for her to bounce ideas off them or quickly get an answer to a pressing question. CWI’s central location makes it the perfect place for Stacey to develop own research group as a recipient of the Women in Science Excellence (WISE) programme grant. The WISE programme offers top female researcher tenure-track positions and start-up funds at Dutch research institutes like CWI.
Working at CWI also allows Stacey to focus on her research and not worry about some of the things that scientists at other institutes have to worry about. “Applying for grants is one of the most time consuming things you have to do as a researcher. CWI has a lot of resources in place to make the process easier and to help you secure funding,” she says.
Although she had applied for (and won) major grants before arriving at CWI, she found going through the grant application process without CWI’s support to be much more daunting. “I’ve really benefited from their help,” she adds.
One of Stacey’s more ambitious goals is to have her algorithms run on actual quantum computers. “If I have a big breakthrough and discover that with a really small amount of memory we can actually solve important problems, then it’s more likely that the algorithms will run in the next few years. But it also depends a lot on how the actual quantum computers progress,” she says. In researching how to bring down the memory requirements for certain types of algorithms, Stacey’s work is helping to make functioning quantum computers a reality sooner.
Written by Sarah Binns, Academic Stories
Stacey explains more about her Quantum research work at CWI in the A&C group video