Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

Many years ago, when CSS codes were first invented, the error threshold of p=0.11 was found when bit and phase flips are independent. Has a threshold yet been found for the case of depolarizing noise?

share|improve this question
add comment

3 Answers

up vote 7 down vote accepted

Are you asking about the threshold for minimum distance or for channel capacity? The distinction is whether you want to fix all errors in $p n$ or fewer qubits, or just random errors on $pn$ or fewer qubits. From the way you worded your question, I am assuming you want to fix a random error on $pn$ qubits.

If you choose a random CSS code, and correct it by finding the smallest number of errors total which agree with the syndrome, I believe that asymptotically it should work up to the point where $$ H_2(p) + p\, \log_2 3 = 1, $$ where $H_2(p)$ is the binary entropy function. This gives an error rate of $p=0.189\,$. This is the same rate you get for a random stabilizer code.

The way to see this is to count the number of likely errors with error rate $pn$, and then take the log of this to figure out how many bits need to be in the syndrome to correct them. Unless there is some dependence among the syndrome bits when you restrict to likely errors, this gives the result above. And with random CSS codes, you can show that there is no such dependence.

This might seem to be incompatible with the $p=0.11$ result for independent errors, but it's not. In the case where the bit errors and the phase errors are independent, stabilizer codes can work for a rate of $p= 0.11$ bit errors and $p=0.11$ phase errors, which works out to a rate of $p=0.208$ total errors.

share|improve this answer
add comment

I don't think the maximum threshold over all codes is known, but thresholds above 15% have been shown for specific codes. See, for example, arXiv:0905.0531 (p=0.155), Phys Rev Lett 104 050504 (p=0.164), arXiv:1006.1362 (p=0.152) and arXiv:quant-ph/0606126 (p=0.188).

share|improve this answer
@AshleyStephens: Great edit! Perhaps it should have been an answer it it's own right. –  Joe Fitzsimons Dec 20 '11 at 11:33
add comment

The threshold for depolarizing noise is not known. It is known that the natural way of choosing a random CSS or random stabilizer code does not achieve the thresold. The latest reference I am aware of is quant-ph/0604107 by Smith and Smolin, which extends previous work on degenerate codes by Shor and others. By using a random CSS code concatenated on top of multiple layers of repetition codes, they apparently show a threshold of 19.086% compared to 18.93% from the hashing bound (explained in Peter's answer).

(This answer is based on quickly skimming the Smith-Smolin paper, so I may have missed some subtlety.)

share|improve this answer
I don't think you've missed anything, and I also don't know of any later references that improve this threshold. –  Peter Shor Dec 27 '11 at 12:16
Thanks for your answers. So what exactly is this hashing bound of 0.189, and why can the codes described above beat it? For the case of independent bit and phase flips I suppose that the corresponding bound is H(p_x) + H(p_z) = 1 for p_x the probability of a bit flip on each qubit and p_z for a phase flip. This gives the value of 0.11 when p_x=p_z. Could there be a code like the above that could beat this bound, or is this really the best any code can do? –  Matthew Matic Jan 12 '12 at 13:44
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.