#1 Computational Complexity: Classic and Quantum
发表于 ： 2025年 1月 28日 23:01
Some interesting slides
https://github.com/yong-yao/quantum-com ... lexity.pdf
Computational Complexity: Classic and Quantum
What is computing? Now we have Turing machine as the answer of this question and we believe it is the right answer. We turned this belief into Church-Turing thesis, which says that Turing machine can simulate all computing that we can physically implement.
Then how efficient is Turing machine? One of the most amazing discovery in computer science is NP-complete problems. Can Turing machine resolve NP-complete problems efficiently? This is one of the most challenge problems in our human intelligence. Until now we have not proven any computing model is more efficient (exponential speedup) than Turing machine. We turned this fact into strong Church-Turing thesis which says all Turning equivalent models -- which can be physically implemented -- is as efficient as Turing machine.
Quantum computer can factor integer exponentially faster than the best know classic algorithm. But we have not proved that the best classic algorithm is the best we can do. Can quantum computing break strong Church-Turing thesis? Until now we don't know. And people in computational complexity field believe the answer is NO. They believe quantum computing cannot resolve NP-complete problems efficiently.
Quantum physics can help. We have Peter Shor's algorithm and Grove's algorithm. Also, most recently we have MIP*=RE. Is entanglement not computable? If yes, we may be able to use it to separate P from PSPACE which should be a big achievement in computational complexity theory.
Some people think computing as a physical process and we should find its limit from physical laws. One very interesting view is the way around. We can try to valid physics theory from computational complexity point and turn strong Church-Turing these as a physic principle. Any physic theory that violates it should not be considered as a valid physic theory.
Why NP?=P is so hard? Yes, it is hard because people tried all kind of ways but still cannot get the mystery of it. It is deeply related to the way how our human reasoning.
Infinite caused trouble to our human couple of times in the history. Each time we resolve the trouble we have deeper understand of our human intelligence.
Are halting problem and P vs NP the troubles that infinity causes to the way we do reasoning?
For details, ref to following link to get the slides. A Tour to Computational Complexity Theory Perspective: Classic and Quantum
Gihub link https://github.com/yong-yao/quantum-com ... lexity.pdf
https://github.com/yong-yao/quantum-com ... lexity.pdf
Computational Complexity: Classic and Quantum
What is computing? Now we have Turing machine as the answer of this question and we believe it is the right answer. We turned this belief into Church-Turing thesis, which says that Turing machine can simulate all computing that we can physically implement.
Then how efficient is Turing machine? One of the most amazing discovery in computer science is NP-complete problems. Can Turing machine resolve NP-complete problems efficiently? This is one of the most challenge problems in our human intelligence. Until now we have not proven any computing model is more efficient (exponential speedup) than Turing machine. We turned this fact into strong Church-Turing thesis which says all Turning equivalent models -- which can be physically implemented -- is as efficient as Turing machine.
Quantum computer can factor integer exponentially faster than the best know classic algorithm. But we have not proved that the best classic algorithm is the best we can do. Can quantum computing break strong Church-Turing thesis? Until now we don't know. And people in computational complexity field believe the answer is NO. They believe quantum computing cannot resolve NP-complete problems efficiently.
Quantum physics can help. We have Peter Shor's algorithm and Grove's algorithm. Also, most recently we have MIP*=RE. Is entanglement not computable? If yes, we may be able to use it to separate P from PSPACE which should be a big achievement in computational complexity theory.
Some people think computing as a physical process and we should find its limit from physical laws. One very interesting view is the way around. We can try to valid physics theory from computational complexity point and turn strong Church-Turing these as a physic principle. Any physic theory that violates it should not be considered as a valid physic theory.
Why NP?=P is so hard? Yes, it is hard because people tried all kind of ways but still cannot get the mystery of it. It is deeply related to the way how our human reasoning.
Infinite caused trouble to our human couple of times in the history. Each time we resolve the trouble we have deeper understand of our human intelligence.
Are halting problem and P vs NP the troubles that infinity causes to the way we do reasoning?
For details, ref to following link to get the slides. A Tour to Computational Complexity Theory Perspective: Classic and Quantum
Gihub link https://github.com/yong-yao/quantum-com ... lexity.pdf