On the role of entanglement and statistics in learning (Supplementary material)

Outer products are indicated by the notation |ψ ϕ|. Pure states correspond to rank 1 mixed states. We will often label the mixed state corresponding to a pure state |ψ by ψ (instead of |ψ ψ|). Note that this is defined up to an absolute phase, i.e. |ψ and e The expectation value of an observable is given by Tr[M ρ]. Let binary random variable b {0, 1} be uniformly distributed. Similarly, let |ψ and |ϕ be arbitrary quantum states and M an obervable on their Hilbert space. Proof. 1. Choose ϕ = δ(p(x) > q(x)) δ(q(x) p(x)), where δ() is an indicator function from boolean clauses to {1, 0} which evaluates to 1 if its argument evaluates to true and evaluates to 0 if its argument is false.