Entanglement—a uniquely quantum phenomenon that intimately links the fate of subatomic particles even if they reside on opposite sides of the galaxy—is a key reason why quantum computers are so much more powerful than their ordinary, “classical” counterparts. Entanglement also enables quantum computers to harness quantum complexity, which describes the number of steps it takes to solve a problem. Quantum complexity renders it impossible to replicate a true quantum system on a non-quantum computer.
But exactly how quantum entanglement is related to quantum complexity—and how much entanglement is necessary to fully exploit it—have remained a mystery. Alexey Gorshkov and his colleagues at the Joint Quantum Institute and the Joint Center for Quantum Information and Computer Science, research partnerships between the National Institute of Standards and Technology and the University of Maryland, in collaboration with researchers at the University of Chicago, have now found a partial answer.