4 ms·
It would be a reduction of discrete-log/factorization to some algorithm with known lower bounds on runtime/space for a given probability of success.
by AlexCoventry 5y ago
It would be a reduction of discrete-log/factorization to some algorithm with known lower bounds on runtime/space for a given probability of success.
- dane-pgp 5y agoBut could there ever be a guarantee that no more efficient algorithm could be found? I agree that, given an algorithm, you can reason about the runtime/space/probability requirements that it places on an implementation, but you also have to contend with different models of computation. According to Wikipedia, the "quantum complexity-theoretic Church–Turing thesis" states that: "A quantum Turing machine can efficiently simulate any realistic model of computation."[0] but even assuming this is true, and that we could build a practical general purpose quantum computer, the word "efficiently" here only means "up to polynomial-time reductions", and I don't think we can know in advance what polynomial-time reductions could be discovered. [0] https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#Variations https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#V...