5 ms·
Quantum Speedup Found for Class of Hard Problems
- the8472 2y agopreviously: https://news.ycombinator.com/item?id=41753626 https://news.ycombinator.com/item?id=41753626
- colordrops 2y agoIs prime factoring (e.g. Shor's algorithm) not a clear example of where quantum computers would clearly outperform classical ones? Why the skepticism?
- gaugefield 2y agoAre you talking about the skepticism from Kalai or more general skepticism (from wider group people, which is more about its application to optimization problem, not prime factoring)?
- foota 2y agoI think the goal here is to find more useful algorithms that benefit from quantum computing. Being able to factor primes efficiently is only useful for the sake of the cryptographers' job security :-)
- whysosadge 2y agoI’m exaggerating a lot here, but one concern people have with quantum computing is what if it breaks all cryptography, but doesn’t help us solve “useful” problems. The what if is pulling a lot of weight here but I hope it makes my point.
- zelphirkalt 2y agoI guess that would be about asymmetrical encryption. Which is today indispensable for a lot of infrastructure. Still, there's symmetrical encryption, which is mostly untouched by Shor's algorithm.
- jfengel 2y agoSymmetrical encryption requires key distribution, which presents new areas of attack. Though there is also quantum key distribution, which will probably be solved as soon as quantum algorithms can break classical encryption.
- pclmulqdq 2y agoQKD is essentially a layer 1 protocol. It's not in the same realm as symmetric key establishment. That said, there are quantum-resistant key establishment algorithms out there, and more likely one of them will be selected.
- fsh 2y agoQKD also needs key distribution to prevent MITM attacks. It behaves almost exactly like a classical stream cypher, except that it cannot be package-routed, is many orders of magnitude slower, and is prone to side-channel attacks.
- whysosadge 2y agoDepending on the use case. Symmetric crypto varies. For example, if your source only has 100 bits of classical entropy. For example, fuzzy extractors. It becomes manageable to break it now with a QC.
- adastra22 2y agoQuantum computing is extremely useful for accurate computational chemistry, which impacts everything from materials science to medicine.
- gaugefield 2y agoThat statement alone does not paint the whole picture. It also has to be better in terms of some metric (e.g. accuracy, computation time, size of molecules simulatable) when compared to classical ones.
- adastra22 2y agoIt makes accurate simulation of quantum mechanical systems of relevance (e.g. molecules) even possible. DFT simulations are full of approximations just to get them to be able to run on classical supercomputers. Nobody does a full solution of Schrödinger's equation. With a sufficiently sized quantum computer, you could.
- stared 2y agoThe 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 ago
- soganess 2y agoFactoring hasn't been shown to be NP-complete. It maybe the case that it's in P (and we just don't have an algo yet) or it maybe the case that it is an NP intermediate problem.
- hannob 2y agoI think it's clear that factoring works if you can build a scalable quantum computer. But: 1. It's a very lonely example. 2. It's not clear how big the market is for "you can break encryption from the past, but not current encryption, because once QCs arrive, everyone will obviously move away from QC-breakable encryption". And I'm not aware of any other reasons why factoring large numbers would be useful beyond breaking encryptions.
- adgjlsfhk1 2y agoI really wish this article said what the big O runtime for the classical and quantum algorithms are
- fintler 2y agoIf I’m reading it right: dqi = O(m^2) classical = O(2^n) m = variables n = constraints
- kvathupo 2y agoThey're not easily comparable since quantum complexity refers to the upper bound on queries to some black-box "quantum oracle", which exists on the gate-level. A classical parallel would perhaps be queries to a translation lookaside buffer, which can be regarded as a gate-level black-box (I'm sure people who actually work in hardware already smell blood!). By contrast, classical complexity, as in sorting algorithms, is reasoned about in higher-level programming languages, whose operational complexity is hard to describe down to the bit-level. I'm curious if anyone more knowledgeable could argue one-way-or-another if this is a boon to the quantum-computers-will-probably-be-faster-in-realization camp.
- adastra22 2y agoI am also relatively new to this, but I believe there is an apples-to-apples comparison with the number of gate operations required to solve an instance of a problem.
- soganess 2y agoIt's an approximation algorithm. It's not about the runtime. It's about the worst or average case approximation quality while remaining in a polynomial budget.
- deleted 2y ago[deleted]
- graycat 2y ago> It's an approximation algorithm. Clear. Nice. Thanks. In that case, for the Traveling Salesman problem, build a minimum spanning tree and traverse that -- old result.
- ra120271 2y agoOT: Is there an accessible ground up presentations on Quantum so that I can self up skill? I’m thinking of something like the equivalent Zero to Hero by Andrej Karpathy for AI.