Physics is informational

QIP = PSPACE

Rahul Jain, Zhengfeng Jin Sarvagya Upadhyay, John Watrous — arXiv:0907.4737

Known facts:

• IP = PSPACE
• QIP = QIP(3) [Watrous99, KitaevWatrous00]
• QMA = QIP(1) ⊆ PSPACE
• QIP(2) ⊆ PSPACE [JainUpadhyayWatrous09] (uses SDP)
• QIP = QMAM [MarriotWatrous05]

Need to show that QMAM ⊆ PSPACE. The key is to write the verifier’s Maximum Acceptance Probability (MAP) as a SDP and find feasible points. Pick some point of the primal. If they are not, they are (up to a projection) dual feasible points. Then use the MWU in order to improve the solution of the dual. Try log(size of the problem) times.

(and I did not get how to have a good solution of the primal from them) (strong duality?)

QIP = IP : Quantum Interactive Proofs are not more powerful than classical interactive proofs.

Random numbers certified by Bell’s theorem

Antonio Acín, Antoine Boyer and Stefano Pironio — arXiv:0911.3427

How can you trust your random number generators? Seriously: you have to be paranoid about your RNG. Do it yourself! You just need a device that violates Bell inequalities and extract the quantum randomness in it.

Protocol: you have two devices: you feed them with N join random bits and you compute the estimator of the violation of Bell inequalities with their outputs.

Result: A bound on the output entropy as a function of the violation of Bell inequalities: H_∞ ≥ N x f(I-ε) with probability 1-δ. where I is the estimator of the violation, ε and δ are small compared to N and f is a function.

Assumptions

• your devices take bits on input and outputs bits (can have memory)
• your two devices cannot communicate (but they can share entanglement)
• the adversary has bounded quantum memory (it is not composable (yet!))

The output string is not necessary uniform. You need to do randomness extraction to actually have useful randomness.

Adiabatic gate teleportation

Dave Bacon and Steve Flammia — arXiv:0905.0901 and arXiv:0912.2098

Steve is laughing at computer scientists that don’t like integrals.

Adiabatic teleportation: you make teleportion in an adiabatic way…

Adiabatic gate teleportation: you start with a qubit |ψ > and at the end of the teleportation you get U|ψ>

For a 1 qubit gate, you just need to perform a rotation on one qubit of your EPR pair before the usual teleportation. For 2 qubit gates, it is more complicated, you need to use a gadget and make 2 teleportations.