johncarlosbaez, (edited )
@johncarlosbaez@mathstodon.xyz avatar

@monsoon0 - yes, the math of quantum computing is very helpful. I believe the article was trying to say, in a clumsy way, that the math of quantum algorithms is far ahead of our technology for implementing these algorithms, and there's no guarantee that we'll succeed in implementing them.

As for @drdunk's statement, it's a fact that nobody has proved really good lower bounds on the asymptotic complexity of classical computations For this reason, nobody can prove that quantum algorithms are definitively faster, asymptotically, than classical ones could ever be. What people do instead is prove that some quantum algorithms are faster, asymptotically, than the current 𝑏𝑒𝑠𝑡 𝑘𝑛𝑜𝑤𝑛 classical algorithms.

Consider Shor's algorithm for prime factorization:

https://en.wikipedia.org/wiki/Shor%27s_algorithm

This is one of the main examples of a quantum algorithm that seems to beat what we can do classically. The Wikipedia article states what's known about it. Shor's algorithm for factoring an integer N takes time that's bounded by a polynomial in log N (Wikipedia states a very precise bound that's below O((log N)³)). The current best known classical algorithm takes time that grows faster than any polynomial in log N. But nobody has proved that it's impossible to use classical algorithms to factor integers in a time that's bounded by a polynomial in log N. It's widely believed to be true, but not proved.

To my mind, the most interesting thing about this is the question of why it's so hard to prove good lower bounds on the complexity of algorithms! There's something very deep about this, which "meta-complexity" theory is trying to tackle:

https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/

  • All
  • Subscribed
  • Moderated
  • Favorites
  • random
  • ngwrru68w68
  • rosin
  • GTA5RPClips
  • osvaldo12
  • love
  • Youngstown
  • slotface
  • khanakhh
  • everett
  • kavyap
  • mdbf
  • DreamBathrooms
  • thenastyranch
  • magazineikmin
  • megavids
  • InstantRegret
  • normalnudes
  • tacticalgear
  • cubers
  • ethstaker
  • modclub
  • cisconetworking
  • Durango
  • anitta
  • Leos
  • tester
  • provamag3
  • JUstTest
  • All magazines