The search for quantum algorithms

• "The algorithmic discovery that's got to happen is huge," says Jay Gambetta, who leads IBM's quantum computing efforts.

Why it matters: What quantum computers will be useful for and when they might make an impact is debated — but there are a handful of areas where this next generation of computing is most likely to make a difference.

• One is the quantum simulation of materials that could enable researchers to screen hundreds of potential materials for different properties that could be harnessed in new batteries, catalysts and other critical technologies.

How it works: Algorithms are step-by-step instructions for solving a problem.

• Quantum computers run on quantum bits or qubits. Where the bits in a classical computer have only two states, qubits can have many, thanks to the subatomic properties of particles.
• Quantum algorithms need to take advantage of those properties for them to do anything that goes beyond what a traditional computer can already do, says Ashley Montanaro, co-founder and CEO at Phasecraft, a U.K.-based quantum algorithm company.
• Some researchers are focused on simulating materials with the hope of getting insights to direct the development of new materials even from today's smaller, noisier quantum computers.

Zoom in: Simulating a material involves representing the subatomic particles that play a role in its behavior in a way that a quantum computer can process efficiently.

• Phasecraft this week reported it had developed a suite of algorithms that does that by using classical computing to get a rough description of a material before handing it to quantum computing to refine the simulation. The research was published in Nature Communications.
• The approach, which cuts the number of gates needed in a quantum circuit to run simulations, was applied to more than 40 materials to give other researchers a sense of which materials might be simulated sooner.
• Zapata Computing, Algorithmiq and other companies are also working on quantum software.
• "The biggest upcoming breakthroughs in quantum computing won't be about the technology itself," Gambetta says, but from researchers "mapping their most difficult challenges to quantum computers to explore the next frontiers of what's possible."

The challenge: Algorithms in the classical computing world are developed numerically then proved on a classical computer.

• But the quantum hardware that researchers have today is far from a perfect quantum computer that corrects errors and can run the algorithms being developed.
• The complexities of the quantum circuits Phasecraft developed are "still a bit beyond what you can do with today's best quantum hardware," Montanaro says.
• "In the end, nothing can beat actually running an algorithm on a real large-scale quantum computer," Montanaro says. But today's systems are "big enough to give us some understanding of how the algorithm is going to scale up, how it's going to perform, [and] how errors are going to affect it."

But, but, but... The hardware that does exist today could influence how researchers think about quantum algorithms.

• It's a bottom-up approach similar to what's happening in AI, where algorithms are developed based on the hardware testbeds researchers have and are largely heuristic — they aren't precise but quickly come up with close to the right answer.
• The AI world uses some formal algorithms, but "a lot of these problems are not solved in any kind of formal, verifiable sense," says Michael Littman, a computer scientist and director of the National Science Foundation's Division of Information and Intelligent Systems.
• "I would argue to the success of heuristics based on what we've seen in AI," says Roger Melko, a professor of physics at the Perimeter Institute for Theoretical Physics and the University of Waterloo. "We don't have a lot of heuristic development in quantum computing algorithms."

The intrigue: Melko and his collaborators are tapping into the success of one of the most now-famous heuristic algorithms: the large language models that power ChatGPT and other generative AI tools.

• Instead of taking text as input and predicting the next word in a sentence, they are using measurements of the quantum computers — qubit states, correlations, entanglement and other properties.
• Data from quantum computing experiments is used to train a model, allowing researchers to ask a model what happens when one parameter or another in a quantum computer is changed, Melko explains. This approach could cut back on expensive quantum computing time and help to direct the development of quantum devices.
• But, "a year ago? Yeah, it sounded wild," he says.