5 ms·
I've heard the following called "Aaronson's trilemma": Either the extended Church-Turing thesis is false, or quantum computers are impossible, or...there exists
by doubleunplussed 7y ago
I've heard the following called "Aaronson's trilemma": Either the extended Church-Turing thesis is false, or quantum computers are impossible, or...there exists a classical polynomial factoring algorithm that runs in polynomial time.
One of these things must be true, and debates around quantum computing usually focus on the first two. But as argued, we don't have great reasons to believe factoring in polynomial time is impossible. We certainly don't have a proof that no such algorithm exists.
- wbl 7y agoWhat is the extended Church-Turing thesis? We already know quantum computers give speedups beyond classical lower bounds.
- daveFNbuck 7y agoIt's basically that BPP captures all realistic polynomial-time computations. The speedup would have to be sufficient to show something like a problem in BQP that isn't in BPP. I don't think anyone has been able to show that unconditionally yet. You'd also need to accept that Quantum computers are realistic, which is why Aaronson's trilemma includes quantum computers being impossible.
- wbl 7y agoThat's true but Grover search shows that quantum computers can give big speedups so I don't know why I would believe BPP=BQP.
- nabla9 7y agoGrover's algorithm still takes exponentially many operations to solve a search problem that can be brute-forced in exponentially many steps. Much faster, but still in EXPTIME. No jump from exponential to polynomial complexity class.
- scottlocklin 7y agoThis sort of statement is exactly why serious people shouldn't take "quantum complexity theory" seriously. The complexity class BQP is bullshit: there are no quantum computers, the end. Feel free to prove me wrong by building one which does useful calculations. No time limit, until you die, in which case "time's up." Edit add for downvoters: the strong Church Turing thesis is also almost certainly, and very obviously bullshit. How does that make you feel?
- daveFNbuck 7y agoWhich statement are you saying demonstrates why people shouldn't take quantum complexity theory seriously?
- scottlocklin 7y agoBQP doesn't exist: there are no quantum computers. Saying BQP is like saying "magic fairy dust perfect unitary transformers that effectively encode a perfect complex number in the same sense a protractor theoretically can solve NP-complete problems by encoding real numbers."
- daveFNbuck 7y agoSo we shouldn't take research into things that don't exist yet seriously?
- scottlocklin 7y agoDesigning algorithms for a computer architecture that assumes matter behaves in a fairly trivially unphysical way sure seems like a glass bead game to me. Especially considering the hype and baloney around this particular one. There are zero actual quantum computer designs (aka error corrected and capable of factoring large or even small integers into primes) under construction: but everyone runs around like chicken little declaring the sky is falling. I went to a Gordon conference on this subject in the 1990s; as far as I can tell, there has been zero progress in the topic since then. Sure are a lot of press releases though!
- nabla9 7y agoThe original Church-Turing thesis says nothing about computational complexity. Extended Church-Turing thesis says that all Turing machine equivalent computers can compute the same problems withing polynomial time. Quantum computers are not known to be capable of solving NP-Complete problems in polynomial time.
- mokus 7y agoDo we know that quantum effects will actually scale large enough to realize those speed ups for arbitrarily-large problems though?
- Khoth 7y agoTo paraphrase stuff from Scott Aaronson that I can't find right now: The currently known laws of physics say yes, and nobody's proposed any new laws of physics consistent with current observations which say no and don't allow even more computing power.
- heavenlyblue 7y agoYes - is there any extended reading available re. subj.?
- bsder 7y agoFactoring is one of the few quantum algorithms that is odd man out in terms of noise/implementation/scaling/etc. This should be indicating something about the structure of factoring that we don't understand. Out of all the "classical" problems that we might find another algorithm for, "factoring" would be my bet for the one that we are missing a better algorithm.