3 ms·
Reading as somebody who is not in the field, and writing this down to read the responses of those who are more qualified: How I understand it: the "computation
by acqq 7y ago
Reading as somebody who is not in the field, and writing this down to read the responses of those who are more qualified:
How I understand it: the "computation" is actually "sampling" the cubits? And then sampling results in the sets of random numbers, which don't have uniform but some specific distribution (specific for quantum effects). Then they claim that such a distribution could not be achieved using classical computer so fast, if the classical computer has to do the simulation of the cubits. And therefore, they claim that their quantum process is better.
But couldn't one do a similar conceptual setup even before, e.g. measuring some noise source (e.g. a semiconductor based diode etc) and then claiming that measuring the source is faster than simulating on the digital computer the analog behavior of the noise source?
The interesting step here is that the source is not a single element but a set of quantum qubits, which is much harder to simulate, but on another side it appears that dealing with the behavior that doesn't allow e.g. Shor algorithm on the same setup is avoided by decision to do what was done.
Seems like a clever trick, but I miss in which aspects it makes the hoped-for outcome (e.g. breaking some crypto keys using Shor) in any way more achievable than before.
Please don't assume that I really know what I write, but consider this as a possibility to explain to the not fully informed public which however shows an interest in the topic.
- The_rationalist 7y agoI guess you just clarified why this is bullshit and why quantum supremacy still doesn't exist.
- reikonomusha 7y ago“Quantum supremacy” should be taken as a mathematical term with a mathematical definition in the same way we have definitions for what it means for a problem to be “hard” in the complexity theoretic sense.
- someguy12342 7y agoNo, the distribution is thought to be hard for any classical algorithm (this is still being worked on - there are still ongoing theory development for showing it is harder and harder), and by extension, any classical process. Yes, the problem is very contrived - the distribution being sampled is given by the distribution you get from sampling from a randomly sampled quantum circuit. Of course this is easy on a quantum computer because you can just throw on the randomly chosen gates and measure it. I don't think it will be very useful in a application sense. This problem was designed for the very purpose of showing a "quantum supremacy" as soon as possible. Also, from what I know, there is still a problem in the whole verification aspect for this problem. That is, even if it can sample from the distribution, it is difficult to verify that in fact the correct distribution was sampled. This is in contrast to the problem of factoring, where to verify the computation we just need to multiply the numbers together to check these are indeed the factors. A remedy I have heard of this (I think from Scott Aarsonson) is that we can modify the parameters so that the output is just within the limits of verifiability with a big supercomputer, and that should be good enough to show supremacy was achieved (EDIT: this is precisely what OP's article says it will do). I think this might be bending what is meant by the term "quantum supremacy" too much, but it's a pretty arbitrary point in computational power anyways , so I'm not too concerned. If you're interested in more about quantum supremacy, these two articles have a lot of information: 1. Quantum Computational Supremacy Aram W. Harror, Ashley Montanaro (2018) https://arxiv.org/pdf/1809.07442.pdf https://arxiv.org/pdf/1809.07442.pdf 2. Complexity-Theoretic Foundations of Quantum Supremacy Experiments Scott Aaronson, Lijie Chen (2016) https://arxiv.org/pdf/1612.05903.pdf https://arxiv.org/pdf/1612.05903.pdf
- the8472 7y ago> A remedy I have heard of this (I think from Scott Aarsonson) is that we can modify the parameters so that the output is just within the limits of verifiability with a big supercomputer, and that should be good enough to show supremacy was achieved. That is what TFA does.
- someguy12342 7y agoSorry, somehow I missed that in the abstract.
- comnetxr 7y agoThere's additional piece to this that you are missing: while the classical simulation is _hard_ (i.e. increasingly hard for larger and larger number of qubits or circuit depths), it _can_ be computed with enough computational power for small number of qubits <=50 and depths<=20. (To get the classical simulation to 50 qubits was an achievement in itself and required a huge amount of compute power provided by google, without which they'd probably be only able to compute it for 30-40 qubits.) And where the classical computer can compute the result, the quantum computer does get the same answer with some probability (not a particularly high probability in absolute sense, but much higher than you would expect than if the quantum computer didn't work.)
- comnetxr 7y agoTherefore the win here is that they have verified that a 50 qubit quantum computer "works" (success rate > 10^-3 > 0.) No classical computer could verify a 100 qubit quantum computer in the same way (but you could verify various 50 qubit subsections of the 100 qubit quantum computer). Alternatively, if they had two such 50 qubit devices (and presumably they will soon) they can verify the second one with the first much quicker than they can verify the first with a classical computer, so in that sense the quantum computer beats a classical computer at some task.
- trucho 7y agoyou lost me at "presumably they will" ...
- jayd16 7y agoA noise distribution is easy to simulate. If you had some chip that took input and gave reproducible output that was impossible to simulate classically, I think you'd actually have something of interest.