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

We propose a scheme to implement general quantum measurements (POVMs) in dimension d using only classical resources and a single ancillary qubit. The method uses probabilistic implementation of d-outcome measurements followed by postselection of some outcomes. We conjecture that the success probability is lower-bounded by a constant independent of d for all POVMs in dimension d, implying arbitrary nonadaptive quantum measurement protocols on d-dimensional systems can be realized with only a single auxiliary qubit and constant sampling overhead. We prove the conjecture for typical rank-one Haar-random POVMs in arbitrary dimensions and provide extensive numerics showing success probability above a constant for various extremal POVMs, including SIC-POVMs up to dimension 1299. We also argue the scheme is favorable experimentally, as circuit noise compounding is substantially lower than in standard Naimark-dilation implementations.