An upper bound on the threshold quantum decoherence rate
Alexander Alexandrovich Razborov · CERN Document Server (European Organization for Nuclear Research) · 2004
Let $\\eta_0$ be the supremum of those $\\eta$ for which every poly-size quantum circuit can be simulated by another poly-size quantum circuit with gates of fan-in $\\leq 2$ that tolerates random noise independently occurring on all wires at the constant rate $\\eta$. Recent fundamental results showing the principal fact $\\eta_0>0$ give estimates like $\\eta_0\\geq 10^{-6}-10^{-4}$, whereas the only upper bound known before is $\\eta_0\\leq 0.74$. In this note we improve the latter bound to $\\eta_0\\leq 1/2$, under the assumption $QP\ ot\\subseteq QNC^1$. More generally, we show that if the decoherence rate $\\eta$ is greater than 1/2, then we can not even store a single qubit for more than logarithmic time. Our bound also generalizes to the simulating circuits allowing gates of any (constant) fan-in $k$, in which case we have $\\eta_0\\leq 1-1/k$.