3 ms·
> Lattice problems cannot be reduced to either class of problems for which quantum provides speedups. Essentially any problem can be poised as an unstructured
by nullc 5y ago
> Lattice problems cannot be reduced to either class of problems for which quantum provides speedups.
Essentially any problem can be poised as an unstructured search. But the quantum speedup for generic unstructured search is modest-- a sqrt in the number of operations. This can be compensated just by doubling the number of bits of the effective search space.
- SideQuark 5y agoUnstructured search has sqrt n speedup once all items are loaded, which generally takes O(n) classical time anyways, so Grover doesn't generally present a sqrt speedup for crypto (or any database search where the database is not already loaded as a quantum state). But the idea is right, sqrt speedups even if possible would not weaken crypto enough to break it since encoding would still be exponentially faster, and that's all that's needed for crypto: encoding sufficiently faster than decoding without knowing a secret.
- nullc 5y agoThe 'database' can be a function implemented as a quantum circuit, e.g. a function that takes a candidate private key (and noise inputs) and computes a public key from it and compares it to the target's key. Grover gets handed this function as an oracle and asked to find the input that makes it return 1, which it can do with sqrt(|key|) operations. Of course, the circuit for reversibly computing a public key ends up ginormous... but it's still vastly smaller than the keyspace. And if we were limiting ourselves to the practical we wouldn't be talking about quantum computers. :P