Communications of the ACM
Computer Science Proof Unveils Unexpected Form of Entanglement
The PCP theorem (for “probabilistically checkable proof”) says that not only is the final state of bar magnets floating in water (or aspects related to it) incredibly difficult to compute, but so are many of the steps leading up to it.
Credit: Kristina Armitage/Quanta Magazine
A striking new proof in quantum computational complexity might best be understood with a playful thought experiment. Run a bath, then dump a bunch of floating bar magnets into the water. Each magnet will flip its orientation back and forth, trying to align with its neighbors. It will push and pull on the other magnets and get pushed and pulled in return. Now try to answer this: What will be the system's final arrangement?
This problem and others like it, it turns out, are impossibly complicated. With anything more than a few hundred magnets, computer simulations would take a preposterous amount of time to spit out the answer.
Now make those magnets quantum — individual atoms subject to the byzantine rules of the quantum world. As you might guess, the problem gets even harder. "The interactions become more complicated," said Henry Yuen of Columbia University. "There's a more complicated constraint on when two neighboring 'quantum magnets' are happy."
From Quanta Magazine
View Full Article
No entries found