Extracting Quantum Entanglement (General Entanglement Purification Protocols)

We study the problem of general entanglement purification protocols. Suppose Alice and Bob share a bipartite state $\rho$ which is ``reasonably close'' to perfect EPR pairs. The only information Alice and Bob possess is a lower bound on the fidelity of $\rho$ and a maximally entangled state. They wish to ``purify'' $\rho$ using local operations and classical communication and create a state that is arbitrarily close to EPR pairs. We prove that on average, Alice and Bob cannot increase the fidelity of the input state significantly. We also construct protocols that may fail with a small probability, and otherwise will output states arbitrarily close to EPR pairs with very high probability. Our constructions are efficient, i.e., they can be implemented by polynomial-size quantum circuits.