Computers could be much more powerful than previously realized

Quantum computers promise huge speedups on some computational problems because they harness a strange physical property called entanglement, in which the physical state of one tiny particle depends on measurements made of another. In quantum computers, entanglement is a computational resource, roughly like a chip’s clock cycles — kilohertz, megahertz, gigahertz — and memory in a conventional computer.

In a recent paper in the journal Proceedings of the National Academy of Sciences, researchers at MIT and IBM’s Thomas J. Watson Research Center show that simple systems of quantum particles exhibit exponentially more entanglement than was previously believed. That means that quantum computers — or other quantum information devices — powerful enough to be of practical use could be closer than we thought.

Where ordinary computers deal in bits of information, quantum computers deal in quantum bits, or qubits. Previously, researchers believed that in a certain class of simple quantum systems, the degree of entanglement was, at best, proportional to the logarithm of the number of qubits.

“For models that satisfy certain physical-reasonability criteria — i.e., they’re not too contrived; they’re something that you could in principle realize in the lab — people thought that a factor of the log of the system size was the best you can do,” says Ramis Movassagh, a researcher at Watson and one of the paper’s two co-authors. “What we proved is that the entanglement scales as the square root of the system size. Which is really exponentially more.”

That means that a 10,000-qubit quantum computer could exhibit about 10 times as much entanglement as previously thought. And that difference increases exponentially as more qubits are added.

Logical or physical?

This matters because of the distinction, in quantum computing, between logical qubits and physical qubits. A logical qubit is an abstraction used to formulate quantum algorithms; a physical qubit is a tiny bit of matter whose quantum states are both controllable and entangled with those of other physical qubits.

A computation involving, say, 100 logical qubits would already be beyond the capacity of all the conventional computers in the world. But with most of today’s theoretical designs for general-purpose quantum computers, realizing a single logical qubit requires somewhere around 100 physical qubits. Most of the physical qubits are used for quantum error correction and to encode operations between logical qubits.

Since preserving entanglement across large groups of qubits is the biggest obstacle to developing working quantum devices, extracting more entanglement from smaller clusters of qubits could make quantum computing devices more practical.

Qubits are analogous to bits in a conventional computer, but where a conventional bit can take on the values 0 or 1, a qubit can be in “superposition,” meaning that it takes on both values at once. If qubits are entangled, they can take on all their possible states simultaneously. One qubit can take on two states, two qubits four, three qubits eight, four qubits 16, and so on. It’s the ability to, in some sense, evaluate computational alternatives simultaneously that gives quantum computers their extraordinary power.