3 ms·

> Furthermore, we know what the quantum collision-finding algorithm is optimal—no faster algorithm can be found. There's two problems with this: First, I'm no

> Furthermore, we know what the quantum collision-finding algorithm is optimal—no faster algorithm can be found. There's two problems with this: First, I'm not aware of any proof that Brassard et al.'s algorithm is optimal. Grover's algorithm is optimal, but it is optimal for searching for a specific output value given an arbitrary function. Obviously this optimality doesn't carry over to collision finding because Brassard et al.'s algorithm is superior to a naive use of Grover's for that purpose! Second, even if Brassard's algorithm is optimal in the usual sense, it would be optimal if given an arbitrary function. Specific weaknesses in specific hash functions could still result in methods that would beat it. If you could prove it was the best method for finding hash collisions, even against algorithms designed for specific hash functions, you would have to conclude that the best way to break MD5 on a quantum computer is Brassard's algorithm. That would be a big problem, since we already have better classical methods, and classical algorithms transfer trivially to quantum computers (with the same asymptotic properties). Someone's proof would have to be inconsistent, or ZFC would have to be inconsistent or something crazy like that!

DannyBee 10y ago
"First, I'm not aware of any proof that Brassard et al.'s algorithm is optimal." Also, it's really not clear from this post why you can't play the same kind of parallelization game. (IE if the underlying thing it provides is a faster way to do x, why can't you parallelize that x in the same way) Actually, it looks like bernstein points out you can do this, so the author of this post is essentially comparing a crappy technique to a good one, and saying "The good one is better". It turns out they are the same in the end and it's just cheaper to build normal machines than quantum ones. That seems more reasonable to me than "this technique is slower than the best classical one". It's not. It's just cheaper. That's all. He also says bernstein brilliantly explains why even better quantum algorithms will never win, but actually, bernstein just conjectures that :) " there are several obvious ways to combine quantum search with the rho method, but I have not found any such combinations that improve performance, and I conjecture that—in a suitable generic model—no such improvements are possible." That's a pretty easy conjecture to always make - "i haven't found a way to make this faster, so i conjecture a way to make it faster doesn't exist". These types of conjectures are often very wrong, which is why we have proofs ;)

DannyBee 10y ago

"First, I'm not aware of any proof that Brassard et al.'s algorithm is optimal." Also, it's really not clear from this post why you can't play the same kind of parallelization game. (IE if the underlying thing it provides is a faster way to do x, why can't you parallelize that x in the same way) Actually, it looks like bernstein points out you can do this, so the author of this post is essentially comparing a crappy technique to a good one, and saying "The good one is better". It turns out they are the same in the end and it's just cheaper to build normal machines than quantum ones. That seems more reasonable to me than "this technique is slower than the best classical one". It's not. It's just cheaper. That's all. He also says bernstein brilliantly explains why even better quantum algorithms will never win, but actually, bernstein just conjectures that :) " there are several obvious ways to combine quantum search with the rho method, but I have not found any such combinations that improve performance, and I conjecture that—in a suitable generic model—no such improvements are possible." That's a pretty easy conjecture to always make - "i haven't found a way to make this faster, so i conjecture a way to make it faster doesn't exist". These types of conjectures are often very wrong, which is why we have proofs ;)