For quantum ML, we use the procedure introduced in Appendix REF .
We first perform several repetitions of two-copy Bell basis measurements to estimate absolute values \(|\operatorname{tr}(P_x \rho )|^2\)  for all \(4^n\)  possible inputs \(x\) .
This allows us to immediately identify \(x^*\) .
One could solve for \(x^*\)  by performing Gaussian elimination in \(GF(2)\) . A similar strategy has also been used for learning quantum channels [1]}.
The required sample complexity is \(\mathcal {O}(\log (4^n)) = \mathcal {O}(n)\)  and the numerical experiments confirm this linear scaling.
