3 ms·

I've been out of this field for a while, if there are any experts with up to date knowledge I'm trying to figure out the following: - Why this particular calcu

I've been out of this field for a while, if there are any experts with up to date knowledge I'm trying to figure out the following: - Why this particular calculation chosen? - With this many qubits I would think they could take some quantum simulations already. Is the gate fidelity not high enough? - Am i reading this correctly that they do no error correction or entabglement distillation?

jd007 7y ago
- This particular problem was artificially constructed with the specific goal of demonstrating quantum supremacy. It has little to none practical use. Essentially they looked what the easiest thing is for current quantum computers to do, and formulated a problem based on that - Because of the above point, this does not mean that the quantum computer can do anything useful (definitely not factor numbers). It is nowhere near high fidelity enough to run highly error corrected algorithms (which Shor's and Grover's algorithms demand) Since this is a mostly theoretical exercise to begin with, it's weird that they mention the computational cost of the classical method in terms of real computer times on supercomputers, and almost don't mention the theoretical bounds. The practical cost doesn't matter much as far as demonstrating quantum supremacy is concerned. As far as I know, the key to claiming true quantum supremacy in this case, is actually the proof of the theoretical complexity of the classical algorithm. The quantum computer is obviously efficient at solving the problem, considering that the problem was constructed with what a QC is good at in mind. And the hardness of any classical algorithms had been somewhat demonstrated already, by Aaronson and Arkhipov in 2011. They managed to show that if there is a polynomial time classical algorithm capable of solving this sampling problem, then the polynomial hierarchy would collapse, which is seen as extremely unlikely (on the same level as showing P=NP). PS: Aaronson recently gave a 3-part lecture at ETH as part of the annual Paul Bernays lectures. Links to recordings and PPTs here: https://www.scottaaronson.com/blog/?p=4301 https://www.scottaaronson.com/blog/?p=4301. Part 3 is specifically about this topic, and gives a good high level overview of the current state. Edit: link to more info on the Aaronson and Arkhipov result, including link to the original paper: https://gilkalai.wordpress.com/2010/11/17/aaronson-and-arkhipovs-result-on-hierarchy-collapse/ https://gilkalai.wordpress.com/2010/11/17/aaronson-and-arkhi...
comnetxr 7y ago
I'm not an expert, but you are correct in that there is no error correction here, and error correction is still a long way off. Around 2016, realizing that running useful quantum algorithms was a long way away and there needed to be earlier roadmarks for quantum devices to signal the progress, the problem of "quantum supremacy" was introduced. The goal is to find the problem with the _easiest_ demonstrable quantum speedup (regardless of usefulness). They proposed a particular sampling problem (running a randomly chosen quantum circuit that has output with a positive probability on many bitstrings, where the exact "speckle pattern" of the probability distribution would only show up if no errors were made when running the circuit.) As the circuit is randomly chosen, it can serve no particular use, except for verification that the computer runs correctly. Relevant papers for more info: https://arxiv.org/pdf/1608.00263.pdf https://arxiv.org/pdf/1608.00263.pdf https://arxiv.org/pdf/1612.05903.pdf https://arxiv.org/pdf/1612.05903.pdf
- comnetxr 7y ago
  They explain in the paper that the quantity plotted in Fig. 4 can also be interpreted as a probability of zero errors of running the circuit. You can see that it goes down quickly with number of qubits and number of cycles, showing the need for either error correction or much improvement in future devices in order to get any useful calculations done. The win here is that the probability of success is non-zero, as they say in the paper: "A single bit or phase flip over the course of the algorithm will completely shuffle the speckle pattern and result in close to 0 fidelity". So the only way to get the right result is to have runs with zero errors.

jd007 7y ago

- This particular problem was artificially constructed with the specific goal of demonstrating quantum supremacy. It has little to none practical use. Essentially they looked what the easiest thing is for current quantum computers to do, and formulated a problem based on that - Because of the above point, this does not mean that the quantum computer can do anything useful (definitely not factor numbers). It is nowhere near high fidelity enough to run highly error corrected algorithms (which Shor's and Grover's algorithms demand) Since this is a mostly theoretical exercise to begin with, it's weird that they mention the computational cost of the classical method in terms of real computer times on supercomputers, and almost don't mention the theoretical bounds. The practical cost doesn't matter much as far as demonstrating quantum supremacy is concerned. As far as I know, the key to claiming true quantum supremacy in this case, is actually the proof of the theoretical complexity of the classical algorithm. The quantum computer is obviously efficient at solving the problem, considering that the problem was constructed with what a QC is good at in mind. And the hardness of any classical algorithms had been somewhat demonstrated already, by Aaronson and Arkhipov in 2011. They managed to show that if there is a polynomial time classical algorithm capable of solving this sampling problem, then the polynomial hierarchy would collapse, which is seen as extremely unlikely (on the same level as showing P=NP). PS: Aaronson recently gave a 3-part lecture at ETH as part of the annual Paul Bernays lectures. Links to recordings and PPTs here: https://www.scottaaronson.com/blog/?p=4301 https://www.scottaaronson.com/blog/?p=4301. Part 3 is specifically about this topic, and gives a good high level overview of the current state. Edit: link to more info on the Aaronson and Arkhipov result, including link to the original paper: https://gilkalai.wordpress.com/2010/11/17/aaronson-and-arkhipovs-result-on-hierarchy-collapse/ https://gilkalai.wordpress.com/2010/11/17/aaronson-and-arkhi...

comnetxr 7y ago

I'm not an expert, but you are correct in that there is no error correction here, and error correction is still a long way off. Around 2016, realizing that running useful quantum algorithms was a long way away and there needed to be earlier roadmarks for quantum devices to signal the progress, the problem of "quantum supremacy" was introduced. The goal is to find the problem with the _easiest_ demonstrable quantum speedup (regardless of usefulness). They proposed a particular sampling problem (running a randomly chosen quantum circuit that has output with a positive probability on many bitstrings, where the exact "speckle pattern" of the probability distribution would only show up if no errors were made when running the circuit.) As the circuit is randomly chosen, it can serve no particular use, except for verification that the computer runs correctly. Relevant papers for more info: https://arxiv.org/pdf/1608.00263.pdf https://arxiv.org/pdf/1608.00263.pdf https://arxiv.org/pdf/1612.05903.pdf https://arxiv.org/pdf/1612.05903.pdf

comnetxr 7y ago
They explain in the paper that the quantity plotted in Fig. 4 can also be interpreted as a probability of zero errors of running the circuit. You can see that it goes down quickly with number of qubits and number of cycles, showing the need for either error correction or much improvement in future devices in order to get any useful calculations done. The win here is that the probability of success is non-zero, as they say in the paper: "A single bit or phase flip over the course of the algorithm will completely shuffle the speckle pattern and result in close to 0 fidelity". So the only way to get the right result is to have runs with zero errors.