NP problems, post-selection and weak measurements
Jeff Tollaksen, Debabrata Ghoshal
If operations in a quantum computer were conditioned on the results of a subsequent post-selection measurement, then NP-complete problems could be solved in polynomial time. Using the natural connection between post-selection and NP, we show that this result is un-physical by considering constraints on new kinds of measurements which depend on the future post-selection in a non-trivial way. We review practical quantum information advantages of post-selection.
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 5, 2006•2 citations