How to Characterize Quantum Physics by Computer Science
February 8, 2017

Quantum physics has a beautiful mathematical representation, but does not have explanations. Our goal is to find "Postulates" of quantum physics, which are meaningful axioms for quantum physics. Recently, physicists believe that information explains quantum physics.

The CHSH game is the minimum setting separating classical physics and quantum physics. The largest winning probability of the CHSH game is 0.75 in classical physics and is 0.854 in quantum physics. A natural question arises: Why does quantum physics prohibit the CHSH winning probability greater than 0.854?

In this talk, two results are introduced:
(1) Brassard, Buhrman, Linden, Methot, Tapp, and Unger (Physical Review Letters 2006):
CHSH winning probability over 0.908 makes communication complexity of arbitrary function 1, i.e., Assume that Alice and Bob have n bits x and y, respectively.
If Alice sends one bit to Bob, then Bob can compute an arbitrary function f(x, y).
(2) Pawlowski, Paterek, Kaszlikowki, Scarani, Winter, and Zukowski (Nature 2009):
CHSH winning probability over 0.854 (the quantum limit) admits implausible communication. Namely, if Alice has 2^n bits, and sends 1.99^n bits to Bob, then Bob can get arbitrary one bit of Alice's 2^n bits.

If time is enough, presenter's result is introduced as well:
(3) Mori (Physical Review A 2016):
Generalization of Brassard et al's argument cannot give a threshold smaller than 0.908.

This talk does not require any knowledge of quantum physics. Concrete mathematics of quantum physics, e.g., Hilbert spaces, Herimitian matrices, etc., do not appear in this talk. What you need is only linear algebra.