Supervisor: 

Terry Rudolph

Contextuality, nonlocality, preparation independence and the power of quantum computers

If we are given a data table of predicted outcome probabilities for a locality experiment from a theory, what is the computational complexity of showing that that those operational probabilities can be explained by a model that is possibilistically noncontextual? This was the question raised, and partially answered, by Manseld and Fritz[8] in 2011.

The k-outcome Possibilistic locality decision problem, (j; k)-PossLoc is as follows: the problem instance is an element of f0; 1gj+k+n+m, where j and k are the maximum number of measurement outcomes for each measurement on the two subsystems being measured, and n and m are the number of measurements available at each location. This should be thought of as a data table where a 1 indicates a possible outcome and a 0 indicates an impossible outcome. In general, we will take n = m to maintain a single scaling factor; in fact this change is without loss of generality. In the case where j = k, we will denote this problem merely k-PossLoc. While this is not essential, we will also require that the data tables obey a possibilstic no-signalling principle; this merely streamlines the wording of the theorems.