Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Unix forking the universe by running IBM's free online quantum computer

parel.es

Post reply on HN
Print view View original

41–50 of 50 posts

Re: Unix forking the universe by running IBM's free online quantum computer

#41

Post by eynsham »

Dylan16807 wrote: post #36
eynsham wrote: post #34

Earlier quoted context omitted.

Since quantum computers can stimulate classical computers, presumably they can solve NP-complete problems, since classical computers, by definition, can. Perhaps you mean that they can’t solve NP-complete problems in polynomial time, but we don’t even know that of classical computers, so you would presumably have shown that P≠NP, which would be fairly impressive.

So you're nitpicking it for being too strong of a statement and too weak of a statement at the same time? How about this, they can't do the thing NP stands for. They can't run a generic polynomial-time algorithm in a nondeterministically-branching way, and then pick the winner.

I considered multiple readings of the claim. Obviously different readings may differ in strength. I do not exclude a reading that is neither too strong nor too weak; the comment is an invitation to give one, which you appear to have taken up.

I do not see the distinction between what you have written in the second paragraph and the claim that P≠NP.

Re: Unix forking the universe by running IBM's free online quantum computer

#42

Post by xvilka »

timmattison wrote: post #30
andrewp123 wrote: post #25

Earlier quoted context omitted.

Correct - superposition doesn't fork the world - measurement does. And correct, you can't communicate with the other universe after the split has happened [1]. I'm glad you mentioned that quantum computers can't solve NP-complete problems - my next blog post was going to be about why. Here's an overview of what I plan on saying: A typical quantum algorithm like Shor's works by sending every possible input through a g…

Where is the best place a layman can dig into this statement “You do this by taking advantage of the fact that the superposition is a periodic function and the amplitude repeats.”? I’ve seen articles hinting at this in an obtuse way but I’d love to see something more approachable to help wrap my head around it.

PBS Space Time [1][2] is good channel covering such topics.

[1] https://www.pbs.org/show/pbs-space-time/

[2] https://www.youtube.com/channel/UC7_gcs09iThXybpVgjHZ_7g

Re: Unix forking the universe by running IBM's free online quantum computer

#44

Post by Dylan16807 »

eynsham wrote: post #41
Dylan16807 wrote: post #36

Earlier quoted context omitted.

So you're nitpicking it for being too strong of a statement and too weak of a statement at the same time? How about this, they can't do the thing NP stands for. They can't run a generic polynomial-time algorithm in a nondeterministically-branching way, and then pick the winner.

I considered multiple readings of the claim. Obviously different readings may differ in strength. I do not exclude a reading that is neither too strong nor too weak; the comment is an invitation to give one, which you appear to have taken up. I do not see the distinction between what you have written in the second paragraph and the claim that P≠NP.

If P=NP, then there must exist a deterministic polynomial solution for any NP problem.

Because it is deterministic, that means it's using a different algorithm than the straightforward nondeterministic solution.

So any Turing machine can solve the problem, but it will have to use the former algorithm. It can't use the latter algorithm.

A lot of people think of quantum computers as basically a nondeterministic Turing machine, and the wording in the parent post is an attempt to correct that misconception.

Re: Unix forking the universe by running IBM's free online quantum computer

#45

Post by hi-v-rocknroll »

Here's a better reduction of CC vs. QC: QC doesn't introduce a new type of magic computing. It only accelerates certain algorithms that a CC could also compute. The present state of manufacturing technology has relegated these to essentially toys because they do not yet contain sufficient numbers of QDs to meaningfully threaten cryptography through accelerated prime factorization or matrix inversion. And I'm sure QC devices also release magic smoke, albeit cryogenically-cooled smoke, when excessive voltage is applied. (ElectroBOOM should investigate.)

Re: Unix forking the universe by running IBM's free online quantum computer

#47

Post by eynsham »

Dylan16807 wrote: post #44
eynsham wrote: post #41

Earlier quoted context omitted.

I considered multiple readings of the claim. Obviously different readings may differ in strength. I do not exclude a reading that is neither too strong nor too weak; the comment is an invitation to give one, which you appear to have taken up. I do not see the distinction between what you have written in the second paragraph and the claim that P≠NP.

If P=NP, then there must exist a deterministic polynomial solution for any NP problem. Because it is deterministic, that means it's using a different algorithm than the straightforward nondeterministic solution. So any Turing machine can solve the problem, but it will have to use the former algorithm. It can't use the latter algorithm. A lot of people think of quantum computers as basically a nondeterministic Turing…

Well, I also suspect BQP≠NP, but we don’t know that yet either.

I still don’t understand what is meant by ’straightforward nondeterministic solution’. If you mean that QTMs or quantum circuits aren’t formally the same as NTMs, I agree. But nor are two-tape (D)TMs and single-tape DTMs, and yet we have linear speedup. Presumably there is a stronger claim here, but I do not understand what that is.

Re: Unix forking the universe by running IBM's free online quantum computer

#48

Post by Dylan16807 »

eynsham wrote: post #47
Dylan16807 wrote: post #44

Earlier quoted context omitted.

If P=NP, then there must exist a deterministic polynomial solution for any NP problem. Because it is deterministic, that means it's using a different algorithm than the straightforward nondeterministic solution. So any Turing machine can solve the problem, but it will have to use the former algorithm. It can't use the latter algorithm. A lot of people think of quantum computers as basically a nondeterministic Turing…

Well, I also suspect BQP≠NP, but we don’t know that yet either. I still don’t understand what is meant by ’straightforward nondeterministic solution’. If you mean that QTMs or quantum circuits aren’t formally the same as NTMs, I agree. But nor are two-tape (D)TMs and single-tape DTMs, and yet we have linear speedup. Presumably there is a stronger claim here, but I do not understand what that is.

> I still don’t understand what is meant by ’straightforward nondeterministic solution’.

I'm not sure how much better I can phrase it than "run a generic polynomial-time algorithm in a nondeterministically-branching way, and then pick the winner."

Let me lay out a scenario:

You have a problem with 2^n potential answers.

You have a fast polynomial algorithm you can apply to each potential answer, and you want to find the right answer.

A lot of people think that if you use a quantum computer, it will check every answer in parallel and quickly find the answer at polynomial speed.

But it doesn't work like that. To some extent it does check every answer in parallel, but you need to do a lot more to make the correct answer show up out of the noise. Let's say you need to use Grover's algorithm. That cuts 2^n down to 2^(n/2), which is a remarkable speedup but it's still exponential.

It's possible that P=NP and there's a totally different solution for both classical and quantum computers that isn't exponential. But that's a side issue. The important thing here is that it's not being quantum that lets you escape exponential purgatory.

> If you mean that QTMs or quantum circuits aren’t formally the same as NTMs, I agree.

Kind of?

But it's not really about formal equivalences. It's that tons of people think a QTM is literally a NTM.

Re: Unix forking the universe by running IBM's free online quantum computer

#49

Post by andrewp123 »

eynsham wrote: post #34
andrewp123 wrote: post #25

Earlier quoted context omitted.

Correct - superposition doesn't fork the world - measurement does. And correct, you can't communicate with the other universe after the split has happened [1]. I'm glad you mentioned that quantum computers can't solve NP-complete problems - my next blog post was going to be about why. Here's an overview of what I plan on saying: A typical quantum algorithm like Shor's works by sending every possible input through a g…

Since quantum computers can stimulate classical computers, presumably they can solve NP-complete problems, since classical computers, by definition, can. Perhaps you mean that they can’t solve NP-complete problems in polynomial time, but we don’t even know that of classical computers, so you would presumably have shown that P≠NP, which would be fairly impressive.

I can't imagine you believe P=NP.

Re: Unix forking the universe by running IBM's free online quantum computer

#50

Post by eynsham »

andrewp123 wrote: post #49
eynsham wrote: post #34

Earlier quoted context omitted.

Since quantum computers can stimulate classical computers, presumably they can solve NP-complete problems, since classical computers, by definition, can. Perhaps you mean that they can’t solve NP-complete problems in polynomial time, but we don’t even know that of classical computers, so you would presumably have shown that P≠NP, which would be fairly impressive.

I can't imagine you believe P=NP.

I believe that it is an open question. Were I a betting man, I’d bet that P≠NP. I believe it would also be significant to show that P≠NP implies BQP≠NP but that may already be known.
Post reply on HN