Communications of the ACM
The Power of Quantum Complexity
Credit: Getty Images
For decades, computer scientists have compared the fundamental difficulty of solving various tasks, such as factoring a number or finding the most efficient route for a traveling salesperson. Along this way, they have described an alphabet soup of computational complexity classes and formal techniques for showing how various classes relate to each other.
The advent of quantum computers has introduced new flavors into such classification. It also has given urgency to understanding the potential of these still-limited machines, including the role of mysterious correlations of distant particles, known as entanglement. A recent manuscript concludes that incorporating entanglement into a well-known framework could allow verification of a staggering range of proofs, no matter how long they are.
No entries found