6 ms·

It'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 tha

It'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 ago
That'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 ago
  Grover'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 ago
This 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 ago
  Which statement are you saying demonstrates why people shouldn't take quantum complexity theory seriously?
  - scottlocklin 7y ago
    BQP 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 ago
      So we shouldn't take research into things that don't exist yet seriously?
      - scottlocklin 7y ago
        Designing 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!
        doubleunplussed 7y ago
        At what odds would you bet that we won't see a quantum computer outperforming a classical computer on any problems in the next, say, 20 years?
    - doubleunplussed 7y ago
      The qbits and unitaries don't have to be perfect - it's about how things scale when you add qbits. Quantum error correction shows that you can add more qbits to make up for imperfection, and still be left with a quantum computer, i. e. the imperfection hasn't demoted the thing to a classical computer. Of course they haven't built one yet, but none of the difficulties encountered so far have involved discovering new physics, which is what you would need to do to rule out quantum computers since the laws of physics as currently understood permit them.
- thechao 7y ago
  You’re merely goalposting Scott “Quantum Computing Fists of Fury” Aaronson’s trilemma. If you have proof that quantum computers are physically unrealizable, I’ll happily help you publish that paper. There’s no way my brother could belittle my lack of education if I had a Turing Award or Nobel Prize, or two.
- inflatableDodo 7y ago
  I'm betting on n. Where n stands for us not fully understanding how causality works yet, or a lot about what the hell is going on in general. I'm also rooting for something interesting emerging unexpectedly from Umbral Moonshine, because who can't help but love the Monster Group? https://www.quantamagazine.org/mathematicians-chase-moonshine-string-theory-connections-20150312 https://www.quantamagazine.org/mathematicians-chase-moonshin...

wbl 7y ago

That'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 ago
Grover'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 ago

This 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 ago
Which statement are you saying demonstrates why people shouldn't take quantum complexity theory seriously?
- scottlocklin 7y ago
  BQP 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 ago
    So we shouldn't take research into things that don't exist yet seriously?
    - scottlocklin 7y ago
      Designing 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!
      - doubleunplussed 7y ago
        At what odds would you bet that we won't see a quantum computer outperforming a classical computer on any problems in the next, say, 20 years?
  - doubleunplussed 7y ago
    The qbits and unitaries don't have to be perfect - it's about how things scale when you add qbits. Quantum error correction shows that you can add more qbits to make up for imperfection, and still be left with a quantum computer, i. e. the imperfection hasn't demoted the thing to a classical computer. Of course they haven't built one yet, but none of the difficulties encountered so far have involved discovering new physics, which is what you would need to do to rule out quantum computers since the laws of physics as currently understood permit them.
thechao 7y ago
You’re merely goalposting Scott “Quantum Computing Fists of Fury” Aaronson’s trilemma. If you have proof that quantum computers are physically unrealizable, I’ll happily help you publish that paper. There’s no way my brother could belittle my lack of education if I had a Turing Award or Nobel Prize, or two.
inflatableDodo 7y ago
I'm betting on n. Where n stands for us not fully understanding how causality works yet, or a lot about what the hell is going on in general. I'm also rooting for something interesting emerging unexpectedly from Umbral Moonshine, because who can't help but love the Monster Group? https://www.quantamagazine.org/mathematicians-chase-moonshine-string-theory-connections-20150312 https://www.quantamagazine.org/mathematicians-chase-moonshin...