Hello,

We noticed you're browsing in private or incognito mode.

To continue reading this article, please exit incognito mode or log in.

Not an Insider? Subscribe now for unlimited access to online articles.

Linear Equations Go Quantum

Quantum computers may actually be useful

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.”

This story is part of the January/February 2010 Issue of the MIT News Magazine
See the rest of the issue
Subscribe

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.”

Become an MIT Technology Review Insider for in-depth analysis and unparalleled perspective.

Subscribe today
Next in MIT News
Want more award-winning journalism? Subscribe and become an Insider.
  • Insider Plus {! insider.prices.plus !}* Best Value

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus the digital magazine, extensive archive, ad-free web experience, and discounts to partner offerings and MIT Technology Review events.

    See details+

    What's Included

    Unlimited 24/7 access to MIT Technology Review’s website

    The Download: our daily newsletter of what's important in technology and innovation

    Bimonthly print magazine (6 issues per year)

    Bimonthly digital/PDF edition

    Access to the magazine PDF archive—thousands of articles going back to 1899 at your fingertips

    Special interest publications

    Discount to MIT Technology Review events

    Special discounts to select partner offerings

    Ad-free web experience

  • Insider Basic {! insider.prices.basic !}*

    {! insider.display.menuOptionsLabel !}

    Six issues of our award winning print magazine, unlimited online access plus The Download with the top tech stories delivered daily to your inbox.

    See details+

    What's Included

    Unlimited 24/7 access to MIT Technology Review’s website

    The Download: our daily newsletter of what's important in technology and innovation

    Bimonthly print magazine (6 issues per year)

  • Insider Online Only {! insider.prices.online !}*

    {! insider.display.menuOptionsLabel !}

    Unlimited online access including articles and video, plus The Download with the top tech stories delivered daily to your inbox.

    See details+

    What's Included

    Unlimited 24/7 access to MIT Technology Review’s website

    The Download: our daily newsletter of what's important in technology and innovation

/3
You've read of three free articles this month. for unlimited online access. You've read of three free articles this month. for unlimited online access. This is your last free article this month. for unlimited online access. You've read all your free articles this month. for unlimited online access. You've read of three free articles this month. for more, or for unlimited online access. for two more free articles, or for unlimited online access.