Error mitigation for partially error-corrected quantum computers

We present a method for quantum error mitigation on partially error-corrected quantum computers - i.e., computers with some logical qubits and some noisy qubits. Our method is inspired by the error cancellation method and is implemented via a circuit for convex combinations of channels which we introduce in this work. We show how logical ancilla qubits can arbitrarily reduce the sampling complexity of error cancellation in a continuous space-time tradeoff, in the limiting case achieving $O(1)$ sample complexity which circumvents lower bounds for sample complexity with all known error mitigation techniques. This comes at the cost of exponential circuit depth, however, and leads us to conjecture that any error mitigation protocol with (sub-)polynomial sample complexity requires exponential time and/or space, even when logical qubits are utilized as a resource. We anticipate additional applications for our quantum circuits to implement convex combinations of channels, and to this end we discuss one application in simulating open quantum systems, showing an order of magnitude reduction in gate counts relative to current state-of-the-art methods for a canonical problem.