Implementation of quantum measurements using classical resources and only a single ancillary qubit

We propose a scheme to implement general quantum measurements, also known as Positive Operator Valued Measures (POVMs) in dimension $d$ using only classical resources and a single ancillary qubit. Our method is based on the probabilistic implementation of $d$-outcome measurements which is followed by postselection of some of the received outcomes. We conjecture that the success probability of our scheme is larger than a constant independent of $d$ for all POVMs in dimension $d$. Crucially, this conjecture implies the possibility of realizing arbitrary nonadaptive quantum measurement protocol on a $d$-dimensional system using a single auxiliary qubit with only a \emph{constant} overhead in sampling complexity. We show that the conjecture holds for typical rank-one Haar-random POVMs in arbitrary dimensions. Furthermore, we carry out extensive numerical computations showing success probability above a constant for a variety of extremal POVMs, including SIC-POVMs in dimension up to 1299. Finally, we argue that our scheme can be favourable for the experimental realization of POVMs, as noise compounding in circuits required by our scheme is typically substantially lower than in the standard scheme that directly uses Naimark's dilation theorem.
5 pages + 14 pages of appendices; v2: improved narration, fixed typos; comments and suggestions are welcome