Skip to Content
MIT News magazine

Linear Equations Go Quantum

Quantum computers may actually be useful
December 21, 2009

In recent years, quantum computers have lost some of their luster. It once seemed that they might be able to solve hard problems exponentially faster than classical computers, but so far, that’s proved true only for the factoring of large numbers. MIT researchers, however, have developed a new algorithm that could solve systems of linear equations with exponential speed–improving video processing, weather modeling, and population analysis, among other applications.

Systems of linear equations are a staple of introductory algebra classes: given three equations with three variables, find values for the variables that make all three equations true. But the new algorithm holds out the possibility of solving trillions of equations with trillions of variables.

For even the easiest trillion-­variable problems, “a supercomputer’s going to take trillions of steps,” says mechanical-­engineering professor Seth Lloyd, who developed the new algorithm along with postdoc Avinatan ­Hassidim and Aram Harrow ‘01, PhD ‘05. “This algorithm will take a few hundred.”

Because the result of the calculation would be stored on quantum bits, however, “you’re not going to have the full functionality of an algorithm that just solves everything and writes it all out,” Lloyd says. That’s because unlike the bits in a regular computer, quantum bits–or qubits–can represent both 0 and 1 at the same time. The trillion solutions to a trillion-variable problem would thus be stored on only about 40 qubits. But extracting all trillion solutions from the qubits would take a trillion steps, eating up all the time that the quantum algorithm saved.

Still, researchers can derive potentially useful information by performing quick measurements on the qubits. “You can figure out, for instance, [the trillion solutions’] average value,” Lloyd says. Such measurements could answer questions like “In this very complicated ecosystem with, like, 10 to the 12th different species, one of which is humans, in the steady state for this particular model, do humans exist?” says Lloyd. “That’s the kind of question where a classical algorithm can’t even provide anything.”

Keep Reading

Most Popular

A Roomba recorded a woman on the toilet. How did screenshots end up on Facebook?

Robot vacuum companies say your images are safe, but a sprawling global supply chain for data from our devices creates risk.

A startup says it’s begun releasing particles into the atmosphere, in an effort to tweak the climate

Make Sunsets is already attempting to earn revenue for geoengineering, a move likely to provoke widespread criticism.

10 Breakthrough Technologies 2023

Every year, we pick the 10 technologies that matter the most right now. We look for advances that will have a big impact on our lives and break down why they matter.

These exclusive satellite images show that Saudi Arabia’s sci-fi megacity is well underway

Weirdly, any recent work on The Line doesn’t show up on Google Maps. But we got the images anyway.

Stay connected

Illustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.