Speaker
Description
Contextuality is a fundamental, rigorous marker of non-classicality exhibited by quantum theory. Therefore, it seems natural to expect this non-classical feature to play a vital role as a resource for quantum computational advantage. Indeed, many such links have been unveiled recently, and many of these results boil down to contextuality relative to Pauli observables. For example, in [1] it was shown that contextuality is a necessary resource for universal quantum computation via Magic State Distillation (MSD). In [2], it was shown that the measurement-based quantum computation (MBQC) model (with mod 2 classical control) cannot compute nonlinear Boolean functions without the presence of contextuality. Both these results involve contextuality with respect to Pauli observables only. A recently proposed universal model called Pauli-based computation (PBC) model involves sequential measurement of adaptively-chosen commuting Pauli observables on an initially prepared magic state [3]. On the other hand, hybrid algorithms like variational quantum eigensolvers (VQEs), which are considered strong candidates for witnessing practical quantum advantage in NISQ devices, also involve measurements of Pauli observables in each iteration. In [4], the authors focused on the measurement part of VQE and defined a contextuality test on them. Subsequently, in [5], they showed that a failure of the test (i.e. lack of contextuality) makes classical simulation of the VQE an NP-complete problem, i.e. at worst classically hard (as opposed to quantumly hard, represented by the QMA complexity class). This ubiquity of Pauli observables makes it crucial to extract as much as we can about their contextuality aspects.
In this work, we initiated this study by considering $k$-cycle contextuality scenarios, where the measurement compatibility structure is described by a cycle of arbitrary size $k$. For a given $n$, we provide an upper bound on the maximum size $k$ of a cycle realizable by $n$-qubit Pauli observables. We then prove that no such $k$-cycle Pauli realization for $k > 4$ can witness contextuality (on any quantum state), whereas for $k = 4$ each Pauli realization produces maximal contextuality. Finally, we delineate the effect of cycles on the contextuality of arbitrary scenarios realizable by Pauli observables in light of Vorob'ev’s theorem [6], which necessitates the presence of cycles to witness contextuality in arbitrary scenarios.
References:
[1] Howard, Mark, Joel Wallman, Victor Veitch, and Joseph Emerson. "Contextuality supplies the ‘magic’for quantum computation." Nature 510, no. 7505 (2014): 351-355.
[2] Raussendorf, Robert. "Contextuality in measurement-based quantum computation." Physical Review A 88, no. 2 (2013): 022322.
[3] Bravyi, Sergey, Graeme Smith, and John A. Smolin. "Trading classical and quantum computational resources." Physical Review X 6, no. 2 (2016): 021043.
[4] Kirby, William M., and Peter J. Love. "Contextuality test of the nonclassicality of variational quantum eigensolvers." Physical review letters 123, no. 20 (2019): 200501.
[5] Kirby, William M., and Peter J. Love. "Classical simulation of noncontextual Pauli Hamiltonians." Physical Review A 102, no. 3 (2020): 032418.
[6] Vorob’ev, N. "Markov measures and Markov extensions." Theory of Probability & Its Applications 8, no. 4 (1963): 420-429.
