Implementation of general quantum measurements using only a single ancillary qubit and postselection

With the aim to reduce resources for near-term quantum computers, we propose a scheme to implement a general quantum measurement (POVM) in dimension d using only classical resources and a single ancillary qubit. This method is based on probabilistic implementation of d-outcome POVMs, which is followed by postselection on some of the outcomes. In an earlier work, a similar scheme requiring no ancillary qubits was proposed, and its success probability scaled as 1/d. Contrastingly, for Haar random rank-one POVMs with at most d^2 outcomes, our scheme's success probability doesn't go to zero with d. We conjecture that this is true for all POVMs in dimension d. Numerical computations showing constant success probability for SIC-POVMs in dimension up to 323, support this conjecture. Additionally, for the gate noise model used in the recent demonstration of quantum computational advantage (https://www.nature.com/articles/s41586-019-1666-5), it's shown that noise compounding in circuits which implement Haar-random POVMs by our scheme is substantially lower than the scheme that directly uses Naimark’s dilation theorem.