Computational Complexity and Quantum

Computational complexity provides measures of how hard things are to compute.   Taught in many as part of analytics curriculum..   Which define classes of complexity.   Though we would like to define these for things like 'AI', turns out that is still quite difficult to say until we can appropriately define define it. .   So how well will quantum computing be able to solve different levels of complexity?  Another hard question.   Here is a starting look at that problem.   Technical.

The Power of Quantum Complexity   By Don Monroe

Communications of the ACM, March 2021, Vol. 64 No. 3, Pages 15-17  10.1145/3446875

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.

The new result was first posted on a preprint server in January 2020, and immediately stimulated chatter in the vibrant computational-complexity blogosphere, but it has not yet been peer reviewed. Indeed, the authors already have identified a flaw in an earlier paper they built upon, although they later devised an alternate argument that left their conclusions intact.

If it stands up, the proof also will disprove a longstanding mathematical conjecture, with profound implications for both pure mathematics and physics. As a result, "Quite a few people take this to be true and are trying to follow up on it without really fully understanding it," said Vern Paulsen, a mathematician at the University of Waterloo, Ontario, who was not involved in the work. "It just shows how mainstream to the world of science computational complexity is."

"At some point, people who are working far away from computer science will find another proof of this result in their own language," said Henry Yuen of the University of Toronto. For now, however, "There's a lot of computer science concepts that lend themselves very naturally to putting the pieces together." Yuen co-authored the new paper with fellow computer scientists Zhengfeng Ji of the University of Technology, Sydney; Anand Natarajan and Thomas Vidick of the California Institute of Technology, and John Wright of the University of Texas, Austin. ... '