2003/10/21 by Alexander Razborov, Alexander A. Razborov, Razborov, Alexander A. · 1 citation
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0310136
9 pages
arxiv created 2003/10/21 · openalex publication_date 2003/10/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let η0 be the supremum of those η for which every poly-size quantum circuit can be simulated by another poly-size quantum circuit with gates of fan-in ≤ 2 that tolerates random noise independently occurring on all wires at the constant rate η. Recent fundamental results showing the principal fact η0>0 give estimates like η0≥ 10-6-10-4, whereas the only upper bound known before is η0≤ 0.74. In this note we improve the latter bound to η0≤ 1/2, under the assumption QP\not⊆ QNC1. More generally, we show that if the decoherence rate η 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 η0≤ 1-1/k.