4 ms·
I 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
by reidacdc 6y ago
I 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.