Complexity of compatible measurements

Skrzypczyk, Paul; Hoban, Matty J.; Sainz, Ana Belén and Linden, Noah. 2020. Complexity of compatible measurements. Physical Review Research, 2(2), 023292. ISSN 2643-1564 [Article]

PhysRevResearch.2.023292.pdf - Published Version
Available under License Creative Commons Attribution.

Download (325kB) | Preview

Abstract or Description

Measurement incompatibility is one of the basic aspects of quantum theory. Here we study the structure of the set of compatible, i.e., jointly measurable, measurements. We are interested in whether or not there exist compatible measurements whose parent is maximally complex, in the sense of requiring a number of outcomes exponential in the number of measurements, and related questions. Although we show this to be the case in a number of simple scenarios, we show that generically it cannot happen, by proving an upper bound on the number of outcomes of a parent measurement that is linear in the number of compatible measurements. We discuss why this does not trivialize the problem of finding parent measurements, but rather shows that a trade-off between memory and time can be achieved. Finally, we also investigate the complexity of extremal compatible measurements in regimes where our bound is not tight and uncover rich structure.

Item Type:


Identification Number (DOI):

Related URLs:

Departments, Centres and Research Units:



16 October 2019Submitted
14 May 2020Accepted
5 June 2020Published

Item ID:


Date Deposited:

19 Jun 2020 10:39

Last Modified:

03 Aug 2021 15:05

Peer Reviewed:

Yes, this version has been peer-reviewed.


View statistics for this item...

Edit Record Edit Record (login required)