Wednesday, April 10, 2013

1304.2667 (Matty J. Hoban et al.)

Exact sampling and entanglement-free resources for measurement-based
quantum computation
   [PDF]

Matty J. Hoban, Joel J. Wallman, Hussain Anwar, Naïri Usher, Robert Raussendorf, Dan E. Browne
We identify a family of quantum computations whose output is likely hard to exactly simulate (sample) classically. Specifically, if the output distributions can be efficiently and exactly simulated classically then the polynomial hierarchy from computational complexity theory collapses at its third level. We demonstrate that these circuit familes can be implemented in MBQC using resources states with zero entanglement and zero quantum discord, that is, states which are essentially classical probability distributions. This work shows that families of states exist which violate no Bell inequality, but which are nevertheless unlikely to be efficiently realizable in any theory respecting classical notions of computational complexity - such correlations thus possess a complexity theoretic nonclassicality.
View original: http://arxiv.org/abs/1304.2667

No comments:

Post a Comment