24
$\begingroup$

It is well established that there exists a noise threshold for quantum computation, such that below this threshold, the computation can be encoded in such a way that it yields the correct result with bounded probability (with at most polynomial computational overhead). This threshold depends on the encoding used and the exact nature of the noise, and it is the case that results from simulation often give thresholds much higher than what can be proved for adversarial noise models.

So my question is simply what is the highest lower bound that has been proved for independent stochastic noise?

The noise model I am referring to is the one dealt with in quant-ph/0504218, where Aliferis, Gottesman and Preskill prove a lower bound $2.73 \times 10^{-5}$. Note, however, I do not care which type of encoding is used, and it need not be restricted to the code considered in that paper. The highest I'm aware of is $1.94 \times 10^{-4}$ due to Aliferis and Cross (quant-ph/0610063). Has this value been improved upon since then?

Improve this question
$\endgroup$
10
  • $\begingroup$ Do you want a numerical or analytical value? $\endgroup$
    – Matty Hoban
    Commented Nov 2, 2011 at 10:31
  • $\begingroup$ I'm happy with either as long as it is actually a proven lower bound, without making further assumptions on the noise other than the maximum probability of error. $\endgroup$
    – Joe Fitzsimons
    Commented Nov 2, 2011 at 10:38
  • 2
    $\begingroup$ Great question: also known as the 1 Million Dollar question in quantum computing. I know that there can be serious improvements when one assumes a specific "architecture" in the sense that how easy or hard it is to interact distant qubits (architecture is different from the error model) For example, see here. I think the [PhD thesis of Bryan Eastin] (arxiv.org/abs/0710.2560) could be a good starting point to have a look at. $\endgroup$
    – Kaveh_kh
    Commented Nov 2, 2011 at 13:39
  • $\begingroup$ @Kaveh_kh: thanks for the link. In case it isn't clear from the question, I mean the best known threshold. $\endgroup$
    – Joe Fitzsimons
    Commented Nov 2, 2011 at 13:47
  • $\begingroup$ @Joe, a comparably well-posed question, having both practical and fundamental implications in simulation science, is "What quantum computer architecture has the lowest proved lower bound for independent stochastic noise, such that PTIME simulation of the (noisy) computation process is possible for all error rates above the bound?" Perhaps Joe Fitzsimons might consider adjoining some version of this question to the original question? $\endgroup$
    – John Sidles
    Commented Nov 2, 2011 at 17:31

2 Answers 2

Reset to default
15
$\begingroup$

The highest threshold lower bound for for independent stochastic noise of which I am aware is $1.04 \times 10^{-3}$ by Aliferis, Gottesman and Preskill (quant-ph/0703264). They analyze Knill's teleportation-based scheme with postselection.

If you are willing to consider independent depolarizing noise, then I know of two slightly higher lower bounds: $1.25\times 10^{-3}$ by Aliferis and Preskill (arXiv:0809.5063) and $1.32 \times 10^{-3}$ by myself and Ben Reichardt (arXiv:1106.2190).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Depolarizing noise is a little less general than what I was looking for. The paper by Aliferis, Gottesman and Preskill you mention seems to be the answer to my question. Weirdly, now that you mention it and summarize the paper, it seems that I did see that paper when it came out, but it had drifted from my memory. Thanks, your answer is extremely helpful! $\endgroup$
    – Joe Fitzsimons
    Commented Nov 2, 2011 at 18:41
6
$\begingroup$

The best that I am aware of is in the surface code proposal due to Fowler et al (arXiv:0803.0272), where it is shown that they achieve a bound of 0.75%.

Improve this answer
$\endgroup$
4
  • $\begingroup$ @Pitor: Thanks for fixing the link for me. I originally posted this from mobile, but the mobile StackExchange is a bit buggy... $\endgroup$
    – Chris Granade
    Commented Nov 2, 2011 at 21:53
  • 2
    $\begingroup$ The Fowler et al. result is an estimate (for depolarizing noise), not a lower bound. $\endgroup$
    – Adam Paetznick
    Commented Nov 3, 2011 at 0:22
  • $\begingroup$ Yes, I'm aware of lots of estimates in this range (Raussendorf, Harrington and Goyal's papers, Knill's 3% paper etc.) but what I'm looking for is proven lower bounds. $\endgroup$
    – Joe Fitzsimons
    Commented Nov 3, 2011 at 4:28
  • $\begingroup$ My apologies, then, for misunderstanding Fowler's results. $\endgroup$
    – Chris Granade
    Commented Nov 3, 2011 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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