The Complexity of Noise

Alexandre M. Zagoskin

Kaifeng Bu, Dax Enshan Koh, Lu Li +2 more

Noise in quantum systems is a major obstacle to implementing many quantum algorithms on large quantum circuits. In this work, we study the effects of noise on the Rademacher complexity of quantum circuits, which is a measure of statistical complexity that quantifies the richness of classes of functions generated by these circuits. We consider noise models that are represented by convex combinations of unitary channels and provide both upper and lower bounds for the Rademacher complexities of quantum circuits characterized by these noise models. In particular, we find a lower bound for the Rademacher complexity of noisy quantum circuits that depends on the Rademacher complexity of the corresponding noiseless quantum circuit as well as the free robustness of the circuit. Our results show that the Rademacher complexity of quantum circuits decreases with the increase in noise.

Jack D. Hidary

Piotr Gawron, Jerzy Klamka, R. Winiarczyk

Noise effects in the quantum search algorithm from the viewpoint of computational complexity We analyse the resilience of the quantum search algorithm in the presence of quantum noise modelled as trace preserving completely positive maps. We study the influence of noise on the computational complexity of the quantum search algorithm. We show that it is only for small amounts of noise that the quantum search algorithm is still more efficient than any classical algorithm.

Osama M. Raisuddin, Suvranu De

Seare H. Rezenom, Fambirai Takawira

In this letter, we propose a low-complexity graph-based iterative receiver for low-density parity-check (LDPC) coded systems in the presence of strong phase noise. The proposed receiver exploits the inherent circular characteristics of phase noise and uses complex Gaussian density functions to construct the messages. We show the proposed method achieves similar bit-error rate performance as the existing lowest complexity algorithm, and has lower complexity for higher modulation.