Moonshot of our century

The travelling salesperson wants to get home to her family, but she still has to finish her route.

That route could be much faster if Perimeter and University of Waterloo PhD student Xiu-Zhe (Roger) Luo achieves his goal of writing algorithms that will speed up quantum computers.

The travelling salesperson is of course not a real person but a mathematical character in what is known as a combinatorial optimization problem, which is quite real in the age of e-commerce that we are living in.

In the travelling salesperson example, the sales agent is asked to map out the fastest route to a large number of cities, without stopping at the same city twice. A similar class of problems tackles the optimal way to pack a knapsack or a bin containing a huge number of items of different shapes, sizes, values, or usefulness, without exceeding a certain weight or load limit.

Almost all areas of commerce – including shipping logistics, telecommunication networks, automotive and aircraft design, and financial trading and portfolio management – are interested in optimization problems. They all want to create more efficient, cost-effective, and tailored products and services.

The problem is that optimization is hard.

Many optimization problems can be reduced by working with what is known in graph theory as the maximum independent set problem. In this problem, the computer is tasked to find the largest independent set in a graph, where an independent set consists of a set of vertices structured so that no two vertices are adjacent.

When there are many possible configurations, there is no easy way to obtain the best solution without exploring all the possibilities. This makes for hard and slow work, even for a quantum computer.

That’s why quantum computer scientists all over the world are trying to design quantum algorithms to speed up the job. This is where Luo’s PhD work on understanding the physics behind quantum computing algorithms comes in.

Luo is part of the Perimeter Institute Quantum Intelligence Lab (PIQuIL), a research centre and training hub led by Roger Melko. Melko is an associate faculty member at Perimeter and professor at the University of Waterloo, and is also Luo’s PhD supervisor.

Luo recently completed an internship with a team at QuEra Computing, a company located in Boston, near Harvard University. There, he was part of a collaboration of scientists from QuEra, Harvard, MIT, the University of Innsbruck, and other institutions that achieved a quantum computing speed-up on the maximum independent set problem.

A paper on this work, titled “Quantum optimization of maximum independent set using Rydberg atom arrays,” was recently published in Science magazine. Luo was one of the contributing authors. The study was co-led by Mikhail Lukin, George Vasmer Leverett Professor of Physics at Harvard and co-director of the Harvard Quantum Initiative; Markus Greiner, also George Vasmer Leverett Professor of Physics at Harvard; and Vladan Vuletic, Lester Wolfe Professor of Physics at MIT.

An important goal in quantum computing research is to understand which problems quantum computers can solve faster than classical (non-quantum) computers and how big the speed-up can be using various quantum computing algorithms.

In this recent work, the team put their own and other algorithms to the test. With one of their algorithms, they achieved a ‘super-linear quantum speed-up’ in solving a maximum independent set problem. In other words, their 289-qubit quantum computer was able to solve the problem in fewer steps than it would take for a classical computer using the same number of processors.

“A deep understanding of the underlying physics of the quantum algorithm as well as the fundamental limitations of its classical counterpart allowed us to realize ways for the quantum machine to achieve a speedup,” said Madelyn Cain, Harvard graduate student and one of the lead authors, in a press release.

Though he is still working on his PhD thesis (which he expects to complete in 2024), Luo has already been recognized for his work in understanding the physics behind the algorithms for quantum computers.

Last year, he won the inaugural Wittek Quantum Prize for Open Source Software. The prize, administered by the Quantum Open Source Foundation, celebrates open source software contributors in quantum computing. Luo won the prize from a competitive pool of more than 50 candidates.

Luo’s connection to Melko and Perimeter was invaluable in helping Luo on his quest to learn more about how QuEra’s quantum computer works. Melko and his team at PIQuIL often work in collaboration with Lukin and other scientists at QuEra; through that connection, Luo was able to secure an internship position.

“My personal goal was to learn more about QuEra and how their hardware works. I’ve learned a lot. My next step is to work on more theories,” Luo says.

A few years ago, Google achieved the long-sought ‘quantum advantage’ goal of demonstrating that its quantum computer can solve a certain type of mathematical problem, involving random numbers, more efficiently than regular classical computers.

“But the task they ran was carefully selected and didn’t have a practical application,” Luo says. “The general picture of our work is to achieve a speed-up using a quantum machine on problems that have useful applications.”

That work continues. “For next step, we’re hoping we can see some quadratic speed-up,” Luo says. A quadratic speed-up means the quantum computer would be solving in a thousand steps a problem that would normally take a classical computer a million steps.

Luo’s contribution to the recent work demonstrates the power of the collaborations that Perimeter and the PIQuIL team has with academic and industry-oriented partners, Melko says.

Currently, the PIQuIL team is working on state-of-the-art algorithms and using quantum computers to enhance the artificial intelligence (AI) systems used in a large number of industries. “We help both academics and industry with advanced AI,” says Melko. Meanwhile, AI can in turn help develop algorithms to improve quantum computing systems.

These collaborations are also important to Perimeter graduate students because it opens opportunities in industry while they are pursuing their academic research goals, Melko adds. Such opportunities can be difficult to come by in more traditional academic environments.

Melko notes that Canada has long been a recognized leader in the quantum computing space.

A Canadian start-up, Xanadu, recently made a claim of having a quantum advantage, meaning that their quantum computer has carried out a specific computational task that would be intractable for a classical computer.

Meanwhile, another Canadian company, D-Wave, pioneered a process known as quantum annealing and was the first out of the gate in using that approach to solve optimization problems for industry.

But the D-Wave system needs liquid helium to cool the quantum chips to near absolute zero. Other companies that are interested in optimization are using different approaches to solve these practical problems in a more energy-efficient and cost-effective way. QuEra, for example, uses lasers that can trap and cool individual atoms in a table-top set-up.

The future economy will depend on the ability to scale up the power of quantum computers while also making them cost efficient. “We are starting to address the question of whether we can scale quantum computers so that they can solve useful problems even if they look small,” Melko says.

The researchers at PIQuIL are working with companies and academic partners to help them achieve that goal, he adds.

“Canada has led this quantum computing space for years, but it is nice to have these international collaborations with academic groups and companies,” Melko says.

The race is on to build small but powerful quantum computers for commercial uses. “This is the moonshot of our century,” Luo says.