Yeah i get that, but i don't really care about that promise. I'm curious, today, to see what could be done now with this _existing system_ if pushed even further and what kind of error bars will be seen compared to existing calcs. I'm sure these folks must be playing around with all sorts of things that cant be put in a nice paper right now.
I 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.
There'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.
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".
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.
My 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).
For the moment the “killer apps” involve simulating quantum systems: Chemistry (catalysts etc), microbiology (protein folding), nuclear / particle physics
For people who aren't familiar with quantum chemical simulations: the Hartree-Fock method is the first method developed to predict quantum behavior of molecules, and it is still widely used. This paper is important because it shows how a quantum computer can simulate a chemical system.
20 comments
[ 3.1 ms ] story [ 44.6 ms ] threadPlease skip Shor's algorithm, I understand this part. What else is there?
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_s...
> 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.