Error Correction of Quantum Algorithms: Arbitrarily Accurate Recovery Of Noisy Quantum Signal Processing

Abstract

The intrinsic probabilistic nature of quantum systems makes error correction or mitigation indis-pensable for quantum computation. While current error-correcting strategies focus on correcting errors in quantum states or quantum gates, these fine-grained error-correction methods can incur significant overhead for quantum algorithms of increasing complexity. We present a first step in achieving error correction at the level of quantum algorithms by combining a unified perspective on modern quantum algorithms via quantum signal processing (QSP). An error model of under- or over-rotation of the signal processing operator parameterized by (cid:15) < 1 is introduced. It is shown that while Pauli Z -errors are not recoverable without additional resources, Pauli X and Y errors can be arbitrarily suppressed by coherently appending a noisy ‘recovery QSP.’ Furthermore, it is found that a recovery QSP of length O (2 k c k 2 d ) is sufficient to correct any length- d QSP with c unique phases to k th -order in error (cid:15) . Allowing an additional assumption, a lower bound of Ω( cd ) is shown, which is tight for k = 1, on the length of the recovery sequence. Our algorithmic-level error correction method is applied to Grover’s fixed-point search algorithm as a demonstration.