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.