4 ms·
> rising to the non-associative power indices ... in the last two decades has been analyzed and does not have a quantum polynomial algorithm that solves it. Th
by texaslonghorn5 4y ago
> rising to the non-associative power indices ... in the last two decades has
been analyzed and does not have a quantum polynomial algorithm that solves it. The problem is called
Exponential Congruences Problem.
The author uses similar wording a couple times and it is a little ambiguous? Does "does not have" mean a superpolynomial quantum lower bound has been discovered for this algorithm (or is there a reduction to some other important conjectured complexity theorem)? Or is it just that a polynomial algorithm has not been discovered yet?
- jmount 4y agoYeah, knowing there is no poly-time quantum algo would be as big as showing P!=NP. If it is "no known" algo, it is well known not to use the stronger wording. Outside of oracle results an "at least this hard result" is a big deal.
- tromp 4y agoThere is indeed no excuse for saying "there is no" when they mean "there is no known" It's almost as bad as saying that NP stands for Non Polynomial time.
- opheliate 4y agoIt’s probably worth remembering this is a pre-print of the paper. This is the kind of thing that would be corrected when actually published.
- cryptonector 4y agoIt could be a translation error. The author clearly does not speak English as a first language.