Southwest Quantum Information and Technology

Computational complexity of quantum channels

Presenting Author: Bradley Pearlman, University of Colorado JILA
Contributing Author(s): Graeme Smith

We study the computational complexity of various optimized quantities of quantum channels. Throughout this work, there is a recurring theme that the size of the description of the channel (polynomial in either the input dimension or the number of input qubits) directly influences the complexity of every quantity. The study of quantum channel complexity was most notably initiated by Beigi and Shor [BS08]. Our work extends the machinery they developed in a natural way to prove NP-completeness for computing the coherent information $\mathcal{I}^\textnormal{coh}$ of a multiple-access quantum channel in the long-circuit regime. QMA-hardness results for several quantities (including $\mathcal{I}^\textnormal{coh}$) in the normal-circuit regime are also proven. These hardness results serve as lower bounds for the computational complexity of the associated problem. We define the Maximum Entanglement Transmission problem, which is then shown to be QMA-complete in the normal-circuit regime, and contained in BQP for the long-circuit regime. A pedagogical introduction to quantum circuits, channels and complexity is given in order to make this work as self-contained as possible.

(Session 5 : Sunday from 5:00pm - 7:00pm)