3 ms·
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
by bkcooper 11y 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.