It is instructive to relate the main result on achieving average-case prediction error (Theorem REF ) to quantum probably approximately correct (PAC) learning [1]}, [2]}, [3]}, [4]}, [5]}, [6]}. The latter rigorously established the absence of information-theoretic quantum advantage for learning classical Boolean functions \(h: \lbrace 0, 1\rbrace ^n \rightarrow \lbrace 0, 1\rbrace \) .
This is a special case of predicting functions of the form \(f(x)=\operatorname{tr}\left( O \operatorname{{\mathcal {E}}}(\vert x \rangle \! \langle x \vert )\right)\) .
To see this, we reversibly encode every \(n\) -bit Boolean function \(h\)  in a (unitary) CPTP map that acts on \((n+1)\)  qubits:
\(\operatorname{{\mathcal {E}}}_h(\rho ) = U_h \rho U_h^\dagger , \quad \text{where} \quad U_h\mathinner {|{x, a}\rangle } = \mathinner {|{x, h(x) \oplus a}\rangle } \quad \text{for all} \quad x \in \lbrace 0, 1\rbrace ^n, a \in \lbrace 0, 1\rbrace ,\) 
