NP problems, post-selection and weak measurements

Jeff Tollaksen; Debabrata Ghoshal

doi:10.1117/12.666423

12 May 2006 NP problems, post-selection and weak measurements

Jeff Tollaksen, Debabrata Ghoshal

Proceedings Volume 6244, Quantum Information and Computation IV; 62440S (2006) https://doi.org/10.1117/12.666423
Event: Defense and Security Symposium, 2006, Orlando (Kissimmee), Florida, United States

Abstract

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.

Citation Download Citation

Jeff Tollaksen and Debabrata Ghoshal "NP problems, post-selection and weak measurements", Proc. SPIE 6244, Quantum Information and Computation IV, 62440S (12 May 2006); https://doi.org/10.1117/12.666423

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available