4 ms·

As an amateur trying to read up on quantum computing, I can say these papers are very accessible. The first is the talk referred to in the article that launched

As an amateur trying to read up on quantum computing, I can say these papers are very accessible. The first is the talk referred to in the article that launched the field, and the latter starts with a great literature review: Feynman, Richard. "Simulating Physics with Computers," International Journal of Theoretical Physics, vol. 21, Nos. 6/7, 1982. Shor, Peter W. "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer." 1994. I'm also nearly done with Scott Aaronson's Quantum Computing Since Democritus, which is a popularizing treatment derived from graduate-level lectures. It is demanding but super fun. So one risk to quantum computing I wonder about is the error correction. There are lots of attempts at classical computers that purport to give the same polynomial->exponential speedup, but on closer inspection they just "hide" the exponential requirement, e.g. in the need for exponentially-increasing instrument accuracy. Are there any experts here who can give a reason why error correction in quantum computing will scale polynomially or better? It seems like if we are hiding the exponential in quantum computers somewhere, that's where it will be. EDIT: I think there are practical risks also, e.g. superconductors that only operate at near-absolute-zero, but I'm asking about a theoretical risk that just kills the idea.

bkcooper 12y ago
Are there any experts here who can give a reason why error correction in quantum computing will scale polynomially or better? I'm not sure what kind of scaling you mean in this context, but let me try to answer this. I think the most important result in error correction is the threshold theorem, which (roughly) says that there exists an N such that if you have qubits that are basically error free for N gate operations, you can implement fault tolerant quantum computation. The particular threshold N depends on specifics of the architecture and error encoding that you use. What also depends on the encoding is the number M of logical qubits per physical qubit. As far as I know, it is the case that once you've chosen an encoding, the number of physical qubits needed to realize Q logical qubits should just be MQ, so in that sense the scaling is linear. However, different encodings have wildly different thresholds. Shor's original code that could handle bit flip and phase errors had M=9, I believe, but I don't think the threshold was very good. For a long time, a popular figure quoted for the N you needed for error correction was ~10^4. I think there are state of the art codes ("surface codes") that can get the error threshold down to 10^2 or so, which is close to what's achievable in systems with small numbers of superconducting qubits (which is what IBM and Google are looking at.) But, the number M of physical qubits per logical qubit for a surface code is very, very high, I think on the order of 10^5. (It's been a while. EDIT: I got curious and looked up numbers from a 2012 paper; 10^4 is a better number here. That's still three orders of magnitude more qubits than is typical in state of the art circuits.) So in that sense, there is still a scaling problem.
xnull6guest 12y ago
> Are there any experts here who can give a reason why error correction in quantum computing will scale polynomially or better? Because it takes a finite number of Toffoli/Hadamard/whatever gates to error correct local errors. That is to say it's like check (or ECC) bits in traditional RAM. It's a couple extra transistors per memory location. Error correcting codes in general tend to be very lightweight and can be made to work locally - the the quantum world is the same.

bkcooper 12y ago

Are there any experts here who can give a reason why error correction in quantum computing will scale polynomially or better? I'm not sure what kind of scaling you mean in this context, but let me try to answer this. I think the most important result in error correction is the threshold theorem, which (roughly) says that there exists an N such that if you have qubits that are basically error free for N gate operations, you can implement fault tolerant quantum computation. The particular threshold N depends on specifics of the architecture and error encoding that you use. What also depends on the encoding is the number M of logical qubits per physical qubit. As far as I know, it is the case that once you've chosen an encoding, the number of physical qubits needed to realize Q logical qubits should just be MQ, so in that sense the scaling is linear. However, different encodings have wildly different thresholds. Shor's original code that could handle bit flip and phase errors had M=9, I believe, but I don't think the threshold was very good. For a long time, a popular figure quoted for the N you needed for error correction was ~10^4. I think there are state of the art codes ("surface codes") that can get the error threshold down to 10^2 or so, which is close to what's achievable in systems with small numbers of superconducting qubits (which is what IBM and Google are looking at.) But, the number M of physical qubits per logical qubit for a surface code is very, very high, I think on the order of 10^5. (It's been a while. EDIT: I got curious and looked up numbers from a 2012 paper; 10^4 is a better number here. That's still three orders of magnitude more qubits than is typical in state of the art circuits.) So in that sense, there is still a scaling problem.

xnull6guest 12y ago

> Are there any experts here who can give a reason why error correction in quantum computing will scale polynomially or better? Because it takes a finite number of Toffoli/Hadamard/whatever gates to error correct local errors. That is to say it's like check (or ECC) bits in traditional RAM. It's a couple extra transistors per memory location. Error correcting codes in general tend to be very lightweight and can be made to work locally - the the quantum world is the same.