Hi all,
today's meeting has been postponed till tomorrow, to avoid overlapping with the Schrödinger lecture at 4:15. Cyril Stark is back in town, and will tell us about the computational complexity of quantum tomography. See the title and abstract below.
Best,
-joe
---------
Title: Inference of low-dimensional quantum models is NP-hard
Abstract: Learning a lowest-dimensional quantum model describing experimentally measured data is NP-hard. I will briefly sketch how you can prove this claim. We will see that NP-hardness follows from a reduction of 3-coloring to the problem of analyzing an experiment in the prepare-and-measure setting with missing data (i.e., not all inner products between the experimental states and the experimental measurement operators have been determined by the experimentalist). We conclude that there exists no efficient algorithm to learn optimal effective quantum models describing measured data (unless P = NP). The talk is self-contained and requires no familiarity with complexity theory.