Once the absolute value is determined, the goal of the second stage is to determine the sign of \(\operatorname{tr}(P_x \rho )\) . Importantly, to achieve our desired prediction error, there is no needed to find the sign for any value of \(x\)  for which the absolute value was found to be very small in the first stage. With \(N_2\)  copies of \(\rho \)  stored in the quantum memory, an entangled measurement can be performed acting on all the copies, whose sole purpose is to determine the sign of \(\operatorname{tr}(P_x \rho )\) , without collecting any further information about \(\rho \) . If both \(N_2\)  and \(|\operatorname{tr}(P_x \rho )|\)  are sufficiently large, this measurement is very likely to return the correct value of the sign. Because the measurement is strongly biased in favor of one of the two possible outcomes, it introduces only a very “gentle” disturbance of the pre-measurement state; therefore, by performing many such measurements in succession acting on the quantum memory register, the sign of \(P_x\)  can be measured reliably for many possible values of \(x\) .
We find that \(N_2=\mathcal {O}(\log (M)/\epsilon ^2)\)  copies of \(\rho \)  suffice to determine the sign of \(\operatorname{tr}(P_x \rho )\)  for \(M\)  different Pauli operators, if \(|\operatorname{tr}(P_x \rho )|> \epsilon \)  for each \(P_x\) .
The second stage can also be more amenable to near-term implementation using a heuristic that groups commuting observables [1]}, [2]}; see Appendix REF  for further discussion.
Together, we obtain an upper bound on the total number of queries \(N_Q=N_1 +N_2\)  to the map \(\operatorname{{\mathcal {E}}}_\rho \)  using our quantum ML protocol.
