4 ms·

> Having said that, the biggest caveat to the “10^25 years” result is one to which I fear Google drew insufficient attention. Namely, for the exact same reason

by bambax 2y ago

> Having said that, the biggest caveat to the “10^25 years” result is one to which I fear Google drew insufficient attention. Namely, for the exact same reason why (as far as anyone knows) this quantum computation would take ~10^25 years for a classical computer to simulate, it would also take ~10^25 years for a classical computer to directly verify the quantum computer’s results!! I don't understand that part, can someone explain? There should be plenty of problems that take a long time to solve, but are trivial to verify? Like for example factoring extremely large numbers that are the product of a few very large primes? Maybe not on the order of 10^25 years, but still?

refulgentis 2y ago
This computation is... handwaves, most handwaving I've done in a while...initializing a random state, and it's well-understood whether this state was randomly initialized isn't computable in a reasonable timeframe on classical computers. ends extreme handwaving This nerd sniped a bunch of us, because it sounds like "oh we proved P!=NP", the keys to understanding are A) hanging onto the this in "this computation" (this is easier when you're familiar with the computation and it's contextual history in the field) B) remembering prime factors as a plausible application of QC. Then faced with the contradiction of B, it's neatly resolved by "yes, but the quantum computer isn't big enough to do prime factorization yet" As noted somewhat sideways in the blog, if someone has a computation that is A) not classically computable in a reasonable timeframe B) is computable on a miniscule quantum computer C) can be verified on a classic computer in a reasonable timeframe, a lot of researchers will be excited.
- jl6 2y ago
  Does this mean that the problem of not being able to verify QC results will go away in the scenario where we have a large enough QC to solve an NP problem?
  - refulgentis 2y ago
    Correct, you nailed it. FWIW: There were some really cool comments on the last article re: Willow. One of them being, a reference to a apparently well-known "roadmap" of quantum scaling that apparently got written up a few years back. Apparently the Willow result was the 2026 baseline projection. So their message was "well...not too big a deal, we achieved 2026 at ~2025." Also said that the same roadmap would have that achieved in 15-20 years.

by bambax 2y ago

refulgentis 2y ago

This computation is... handwaves, most handwaving I've done in a while...initializing a random state, and it's well-understood whether this state was randomly initialized isn't computable in a reasonable timeframe on classical computers. ends extreme handwaving This nerd sniped a bunch of us, because it sounds like "oh we proved P!=NP", the keys to understanding are A) hanging onto the this in "this computation" (this is easier when you're familiar with the computation and it's contextual history in the field) B) remembering prime factors as a plausible application of QC. Then faced with the contradiction of B, it's neatly resolved by "yes, but the quantum computer isn't big enough to do prime factorization yet" As noted somewhat sideways in the blog, if someone has a computation that is A) not classically computable in a reasonable timeframe B) is computable on a miniscule quantum computer C) can be verified on a classic computer in a reasonable timeframe, a lot of researchers will be excited.

jl6 2y ago
Does this mean that the problem of not being able to verify QC results will go away in the scenario where we have a large enough QC to solve an NP problem?
- refulgentis 2y ago
  Correct, you nailed it. FWIW: There were some really cool comments on the last article re: Willow. One of them being, a reference to a apparently well-known "roadmap" of quantum scaling that apparently got written up a few years back. Apparently the Willow result was the 2026 baseline projection. So their message was "well...not too big a deal, we achieved 2026 at ~2025." Also said that the same roadmap would have that achieved in 15-20 years.