4 ms·
The issue is that, apart from the Shor’s algorithm, it is hard to find a quantum algorithm, substantially faster than a classical one. Moreover, since cost of
by stared 2y ago
The issue is that, apart from the Shor’s algorithm, it is hard to find a quantum algorithm, substantially faster than a classical one.
Moreover, since cost of qubits scale exponentially, a slight reduction in the power of a polynomial-time algorithm is not enough to offer a practical benefit.
- kvathupo 2y agoAh, walking across glued trees [1]! Not sure of its practical merits however, aha... [1] - https://arxiv.org/abs/quant-ph/0209131 https://arxiv.org/abs/quant-ph/0209131
- HappMacDonald 2y agoGrover's?
- adastra22 2y ago“Substantially better” is doing the heavy lifting there. Grover’s gets you a sqrt speedup. Double the size of your hash function (SHA512 instead of SHA256) and you’re protected.
- AgentME 2y agoI believe 256 bit symmetric keys and hashes are currently recommended because it's double the classically-secure 128 bit.
- adastra22 2y agoBecause there is a different sqrt speedup concern regarding the birthday paradox / collision resistance. These combine with Grover's to get you a O(N^(1/3)) speedup when finding a collision, making a 256-bit hash have ~85 bits of security against a quantum adversary. You'd need to switch to a 384 bit hash function to keep a 128-bit security threshold. In practice, this means SHA-512.
- adastra22 2y agoCost of qubits does not scale exponentially if we have quantum error correction.
- stared 2y agoDo you know a proof for that? I.e., that for n logical qubits, decoherence time goes down polynomially rather than e^(-a n)? AFAIK (and yes, I could be mistaken!) what we deal with is reducing a susbtantially.