2004/08/31 by S. Virmani, Susana F. Huelga, Martin B. Plenio · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Bipartite graph #Class (philosophy) #Combinatorics #Computer science #Controlled NOT gate #Dephasing #Discrete mathematics #Mathematical analysis #Mathematics #Noise (video) #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum and electron transport phenomena #Quantum computer #Quantum entanglement #Quantum gate #Quantum mechanics #Qubit #Topology (electrical circuits) #Upper and lower bounds #quant-ph
paper · pdf · doi:10.1103/physreva.71.042328
published as Phys. Rev. A. 71, 042328 (2005) · 12 pages, 3 figures. v2: small typos changed, no change to results
arxiv created 2004/09/07 · openalex publication_date 2005/04/19 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
We investigate the amount of noise required to turn a universal quantum gate set into one that can be efficiently modeled classically. This question is useful for providing upper bounds on fault-tolerant thresholds, and for understanding the nature of the quantum-classical computational transition. We refine some previously known upper bounds using two different strategies. The first one involves the introduction of bientangling operations, a class of classically simulable machines that can generate at most bipartite entanglement. Using this class we show that it is possible to sharpen previously obtained upper bounds in certain cases. As an example, we show that under depolarizing noise on the controlled-NOT gate, the previously known upper bound of 74% can be sharpened to around 67%. Another interesting consequence is that measurement-based schemes cannot work using only two-qubit nondegenerate projections. In the second strand of the work we utilize the Gottesman-Knill theorem on the classically efficient simulation of Clifford group operations. The bounds attained using this approach for the \ensuremathπ∕8 gate can be as low as 15% for general single-gate noise, and 30% for dephasing noise.