A proof is an amazing wonderful 🎉 thing… So I am wondering why the word “only” is in this sentence: “Researchers have obtained only mathematical proofs that quantum computers will offer large gains over current, classical computers” https://www.nature.com/articles/d41586-023-01692-9
@monsoon0 - because if you can't build the quantum computers that would run these algorithms, a mathematical proof that the algorithms could in theory offer large gains is not completely satisfying.
(Yes, the sentence didn't distinguish the algorithm and the quantum computer that would run it. The algorithms, being mathematical entities, are something you can prove theorems about. The computers that would run them effectively, being machines that nobody knows how to design yet, are not.)
@johncarlosbaez@monsoon0 I’d also like to point out that these “proofs” all rest upon unproven complexity theoretic conjectures, similar to NP != P. For example the belief that quantum computers provide any asymptotic improvements boils down to something like factoring being efficient for quantum computers but not classical. That relies on NP inetersect co-NP != P. These are widely believed to be true, but are not proven just yet. Further, we still have no clear formulation when concrete problems such as the electronic structure problem can be approximated efficiently by classical comps, which would be great to have. I have no clue what kind of complexity arguments would be needed for a statement of that sort.
@johncarlosbaez The issue I am concerned with is more about how the word “only” casts aspersions on what are (I hope!) valid mathematical constructs. Without them, the bridge we are walking along to get to operational quantum computers would be even more flimsy than we imagine, no?
@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:
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:
@johncarlosbaez@monsoon0@drdunk I have nothing substantial to add, just the observation (probably unnecessary for most people on mathstodon, but just in case it helps) that the reason log N matters is that it is (roughly) the number of digits in N, so it's the size of the input representing N, and complexity is usually measured in terms of the size of the input.
Add comment