Please note: This master’s research paper presentation will take place online.
Nicholas Allen, Master’s candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Ashwin Nayak
Many important tasks in quantum information processing involve synthesizing quantum states or implementing unitary transformations. Traditional complexity theory, which typically addresses problems with classical inputs and outputs, does not readily capture the computational hardness of these inherently quantum tasks. One such task is the quantum one-shot compression problem, where the goal is to compress a single, unknown quantum state drawn from a known ensemble using as few qubits as possible.
In this work, we investigate the computational hardness of the quantum one-shot compression problem using various tools from complexity theory and information theory. First, we begin by upper bounding the unitary complexity of the problem via a reduction to the Uhlmann transformation problem, before discussing lower bounds based on pseudorandom state generators and other quantum cryptographic primitives. Next, we describe algorithms for the task under different error criteria based on semidefinite programming, assuming complete classical descriptions of the source. Afterwards, we attempt to derive structural characterizations of compression protocols, with connections to partially entanglement breaking channels and the Knill-Laflamme conditions for quantum error correction. Finally, we explore generalizations to related tasks such as state redistribution before showing that the problem of testing “closeness” to product states is strongly NP-hard. Our results provide new insight into the complexity and structure of quantum compression in the one-shot setting.
Attend this master’s research paper presentation virtually on Zoom.