  The uncertainty principle, originally formulated by Heisenberg, dramatically
illustrates the difference between classical and quantum mechanics. The
principle bounds the uncertainties about the outcomes of two incompatible
measurements, such as position and momentum, on a particle. It implies that one
cannot predict the outcomes for both possible choices of measurement to
arbitrary precision, even if information about the preparation of the particle
is available in a classical memory. However, if the particle is prepared
entangled with a quantum memory, a device which is likely to soon be available,
it is possible to predict the outcomes for both measurement choices precisely.
In this work we strengthen the uncertainty principle to incorporate this case,
providing a lower bound on the uncertainties which depends on the amount of
entanglement between the particle and the quantum memory. We detail the
application of our result to witnessing entanglement and to quantum key
distribution.
