/sci/ - Science & Math » Thread #13349433

59KiB, 799x802, r_2155237_ktVZD.jpg

View Same Google iqdb SauceNAO

Theoretical computer science question

Anonymous Fri 02 Jul 04:38:02 2021 No.13349433 View Reply Original Report

Quoted By: >>13349466 >>13351929 >>13355498

Does MIP* = RE's major breakthrough mean quantum computers are more powerful than turing machines?

Henry Yuen's youtube comment on this video https://www.youtube.com/watch?v=HL7DEkXV_60 (should be one of the top comments) explains that with the help of quantum computers, it is possible to solve a problem that has been proven to be unsolvable by a turing machine.

Does that mean quantum computers are effectively hypercomputers more powerful than turing machines?

Bonus Question : If we, humans, were able to find a way to surpass the Turing barrier, would that mean the human mind is more powerful than a turing machine, making us effectively hypercomputers?

Anonymous

Anonymous Fri 02 Jul 2021 04:51:08 No.13349466 Report

Quoted By: >>13349487 >>13349498

>>13349433
MIP* = RE says that literally an infinite amount of entanglement is capable of verifying a solution to the halting problem in polynomial time. The result is suggestive of the computational power of quantum entanglement but it doesn't say anything about quantum vs classical Turing machines, even in the abstract.

Anonymous

Anonymous Fri 02 Jul 2021 05:00:26 No.13349487 Report

Quoted By: >>13349498 >>13353408

>>13349466
>The result is suggestive of the computational power of quantum entanglement
yes

>but it doesn't say anything about quantum vs classical Turing machines, even in the abstract.
that part, I don't understand. A classical turing machine cannot verify a solution to the halting problem, but a machine using quantum entanglement can. In my mind, that does say a lot about quantum vs classical Turing machines, it means they are more powerful if they can solve something turing machines can't solve.

Anonymous

Anonymous Fri 02 Jul 2021 05:04:14 No.13349498 Report

Quoted By:

>>13349466
>>13349487
also power != efficiency, right? When I mean power I mean power in TCS classification

Anonymous

Anonymous Fri 02 Jul 2021 05:44:03 No.13349588 Report

Quoted By:

existential bump of interest

Anonymous

View Same Google iqdb SauceNAO 1623687616675.png, 384KiB, 526x526

Anonymous Fri 02 Jul 2021 14:35:55 No.13350778 Report

Quoted By:

Anonymous

Anonymous Fri 02 Jul 2021 20:25:02 No.13351929 Report

Quoted By: >>13351994

>>13349433
I don't actually understand most of these kinds of questions about quantum computing. They don't really make much sense to me and I just did a course on quantum information. It seems more fruitful to just build up encoding schemes than it does to talk about the hardware underlying them.

Anonymous

View Same Google iqdb SauceNAO Emrd3pCUUAA247q.jpg, 424KiB, 1536x2048

Anonymous Fri 02 Jul 2021 20:43:51 No.13351994 Report

Quoted By: >>13352008

>>13351929
regardless if it's quantum computation or not,
I think the point is "simply" trying to know if this breakthrough provides a solution to an uncomputable problem. IF it does, than surely it's the proof that we found a way to break the turing barrier, right....?

But that seems to good to be true, I'm trying to figure out if there's a trap somewhere...

Anonymous

Anonymous Fri 02 Jul 2021 20:47:49 No.13352008 Report

Quoted By: >>13352083 >>13355407

>>13351994
I don't understand what you are trying to say, no person is arguing that quantum computing solves the halting problem. That is absolutely not the case. Don't believe anything you read in pop-sci articles. If you want to know more about the topic scott aaronsons blog is a fantastic resource of commentary on the state of the art in quantum computing.

Anonymous

View Same Google iqdb SauceNAO 1602130379140.jpg, 261KiB, 1280x1280

Anonymous Fri 02 Jul 2021 21:17:29 No.13352083 Report

Quoted By:

>>13352008
>scott aaronsons
alright thanks I'll check it out

>>13352008
>I don't understand what you are trying to say
if I can reword it without linking popsci videos:

Henry Yuen, wrote this article : https://arxiv.org/abs/2001.04383 (it's apparently a major breakthrough)

In this article, does he show a recursively enumerable solution, to a previously non-recursively enumerable problem? Maybe I simply misunderstood MIP* = RE

Anonymous

Anonymous Fri 02 Jul 2021 21:32:35 No.13352142 Report

Quoted By: >>13352182

someone answered it on reddit less than an hour ago : To summarize: No, this paper does not provide an example of something a quantum computer can compute that a Turing computer can't.

I believe you have misunderstood Henry's comment. The problem in question isn't the halting problem (given any Turing machine and input, will it halt). Rather, the problem is to prove that a program halts, given that it halts. As Henry describes, there is a simple means of solving this problem that Turing computers are capable of-They can list out the steps leading to the program's halting.

What the quantum computer can do that the Turing computer can't is the following. Given a Turing computer and input that halts, once the quantum computer knows that the process halts (which can take arbitrarily long to determine by itself), it can provide proof that the process halts in constant time.

Key points: This problem has no relevance to solving the halting problem, because the quantum computer needs to know that the process halts to proceed. Turing computers can also solve this problem, but the time to provide an answer can be arbitrarily long for given inputs.

To your bonus question: In theory, the answer is yes, but it is quite hard to do so. To prove that a computer (Turing or human) can solve a problem, you must prove that they can solve it for all inputs. Our current rules of mathematics are describable by a Turing computer, so we would need to provide this proof with something that transcends current mathematics. Additionally, solving the problem for some inputs is not proof we can solve it for all inputs.

follow next post

Anonymous

Anonymous Fri 02 Jul 2021 21:43:41 No.13352182 Report

Quoted By:

>>13352142
Secondly, a very substantial implication of the answer being yes would be that either: Turing computers cannot simulate the laws of physics, or the laws of physics do not fully describe the function of the human brain. As it currently stands, it seems that both of those aren't true - physics fully explains the human brain, and a quantum computer can simulate the laws of physics. (It is 100% true that a quantum computer can simulate our current laws of physics, while it is likely that it can simulate whatever the true laws of physics are).

Anonymous

Anonymous Sat 03 Jul 2021 04:12:38 No.13353408 Report

Quoted By:

>>13349487
The keyword is "infinite amount of entanglement". Specifically, the verifier requires quantum provers with a maximally entangled state on an infinite-dimensional Hilbert space. A corollary of this result is that there are unique types of correlations on such spaces which cannot even be approximated by finite-dimensional systems.
Quantum Turing machines, as far as I am aware, are defined on finite-dimensional spaces.

Anonymous

Anonymous Sat 03 Jul 2021 17:34:55 No.13355407 Report

Quoted By:

>>13352008
I would second the recommendation about Scott Aaronson, his blog has fantastic explanations of the significance and bullshit level of most new findings that come out.

Anonymous

Anonymous Sat 03 Jul 2021 18:03:42 No.13355498 Report

Quoted By:

>>13349433
Why do people get hyped over entanglement? Anyone can entangle macroscopic objects no problem, its basic conservation laws

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches