A lower bound on the space overhead of fault-tolerant quantum computation

Abstract

The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation stating that arbitrarily long quantum computations can be performed with a polylogarithmic overhead provided the noise level is below a constant level. A recent work by Fawzi, Grospellier and Leverrier (FOCS 2018) building on a result by Gottesman (QIC 2013) has shown that the space overhead can be asymptotically reduced to a constant independent of the circuit provided we only consider circuits with a length bounded by a polynomial in the width. In this work, using a minimal model for quantum fault tolerance, we establish a general lower bound on the space overhead required to achieve fault tolerance. For any non-unitary qubit channel $\mathcal{N}$ and any quantum fault tolerance schemes against $i.i.d.$ noise modeled by $\mathcal{N}$, we prove a lower bound of $\max \left\{\mathrm{Q}(\mathcal{N}{)}^{-1}n,{\alpha }_{\mathcal{N}}\log T\right\}$ on the number of physical qubits, for circuits of length $T$ and width $n$. Here, $\mathrm{Q}(\mathcal{N})$ denotes the quantum capacity of $\mathcal{N}$ and ${\alpha }_{\mathcal{N}}>0$ is a constant only depending on the channel $\mathcal{N}$. In our model, we allow for qubits to be replaced by fresh ones during the execution of the circuit and we allow classical computation to be free and perfect. This improves upon results that assumed classical computations to be also affected by noise, and that sometimes did not allow for fresh qubits to be added. Along the way, we prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude damping noise resolving a conjecture by Ben-Or, Gottesman, and Hassidim (2013).

arXiv comment22 pages, 2 figures, an earlier version of this paper appeared in proceedings of ITCS 2022. In the current version, Lemma 10 has been simplified and some bounds are improved

References in corpus (27)

• Fault-tolerant quantum computation by anyons
• Mixed State Entanglement and Quantum Error Correction
• Quantum Error Correction for Quantum Memories
• Quantum Computing with Very Noisy Devices
• Fault-tolerant quantum computation with high threshold in two dimensions
• Roads towards fault-tolerant universal quantum computation
• Surface code quantum computing by lattice surgery
• Optimal Universal and State-Dependent Quantum Cloning
• Quantum computing with nearest neighbor interactions and error rates over 1%
• Resilient Quantum Computation: Error Models and Thresholds
• Confinement-Higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory
• Quantum memories at finite temperature
• Experimental demonstration of topological error correction
• Ultrahigh Error Threshold for Surface Codes with Biased Noise
• Fault-tolerant quantum computation against biased noise
• On Quantum Fidelities and Channel Capacities
• Constant overhead quantum fault-tolerance with quantum expander codes
• Quantum accuracy threshold for concatenated distance-3 codes
• Continuity of quantum channel capacities
• Super-Activation of Zero-Error Capacity of Noisy Quantum Channels
• Limitations of Noisy Reversible Computation
• Classical simulatability, entanglement breaking, and quantum computation thresholds
• Fault-tolerant quantum computation with asymmetric Bacon-Shor codes
• The Fibonacci scheme for fault-tolerant quantum computation
• Semidefinite programs for completely bounded norms
• Strictly contractive quantum channels and physically realizable quantum computers
• Fault-Tolerant Quantum Computation with Constant Overhead

Cited by in corpus (2)

• Resonant Multilevel Amplitude Damping Channels
• A Converse for Fault-tolerant Quantum Computation