5 ms·
I cannot find the answer to this anywhere: what algorithms will we actually use the quantum computers for? Please skip Shor's algorithm, I understand this part
by anthony_r 6y ago
I cannot find the answer to this anywhere: what algorithms will we actually use the quantum computers for?
Please skip Shor's algorithm, I understand this part. What else is there?
- codeulike 6y agoI get the impression no-one really knows because the potential capabilities and engineering realities knock up against the limits of what we understand. They are experimental machines that work in a way we barely understand. So maybe something really revolutionary, or maybe just more efficient Netflix recommendations.
- anthony_r 6y agoThere's pretty good understanding on how quantum mechanics works (for decades), and you can easily write theoretical algorithms for such computers. It can be all expressed with matrix multiplications. See Shor's algorithm for an example.
- bjornorn 6y agoHartree-Fock?
- anthony_r 6y agoYes, this is what I'm thinking too might be the killer feature. But specifically - what would be easier to simulate?
- reidacdc 6y agoI am far from an expert, but as I understand it, Shor's factorization algorithm is a gateway to lots of fast crypto, so it's "enabling technology" for a lot of crypto and number-theoretic applications, not an end-point. There is also Grover's search algorithm, which can retrieve items from an N-element list with fewer than N operations. In the quantum chemistry world, there is work underway to build QC circuits that act as models for natural systems, "natively" capturing the exchange and correlation structure. I've seen model Hamiltonians for small molecules, and this work seems to be in that family also. There are also folks who can do linear algebra on sufficiently sparse, well-conditioned matrices[1]. From what I have read, quantum computers really are very different, a good way to think about them is as super-efficient correlation-finding or correlation-generating machines. Asking "What Von Nuemann algorithm can I put on this?" is the wrong question. If you can devise a correlation solution to your problem, then a quantum computer will be a good tool for you. To re-disclaim, I am not an expert, I'm a reasonably technical interested bystander. For me, the "Oh, I get it!" book was Yanofsky, "Quantum Computing for Computer Scientists". [1] https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_s...
- anthony_r 6y agoThanks for the link, it does seem interesting. > What Von Nuemann algorithm can I put on this? I am very far from asking this question, thinking about the memory architecture is far too detailed here :). If anything it's about P vs BQP. Or probably even more so about heuristics and approximate algorithms, as in practice that's what is used for hard problems.
- kalium-xyz 6y agoDoes quantum do a different memory arch?
- anthony_r 6y agoMy point is that it's irrelevant at this point, as those machines do not yet exist. The existing experimental setups and theoretical models are most closely related to boolean circuits (vs a Turning machine or a RAM machine or lambda calculus or whatever is your favourite computation model). But you can still show gains on some sets of problems (like integer factorisation).
- marcosdumay 6y agoYes, quantum fuses the memory with the CPU. Taking the data out of your processing unity is a classical copy and will cause decoherence.
- pa7x1 6y agoGrover's algorithm provides a quadratic speed up to any brute force search. i.e. from O(N) to O(sqrt(N)).
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]
- s1dev 6y agoFor the moment the “killer apps” involve simulating quantum systems: Chemistry (catalysts etc), microbiology (protein folding), nuclear / particle physics