Entanglement

Two or more qubits are entangled when their joint state cannot be written as a product of states of the parts. A measurement on one subsystem then changes the description of the others. Entanglement is a resource in communication protocols and a liability when it is unwanted correlation with the environment. That second case is decoherence.

In Shor's algorithm, modular exponentiation writes a^x mod n into a second register and entangles it with the exponent register. The quantum Fourier transform produces useful interference only if that joint state is intact. Nielsen and Chuang is the reference for the definition. The algorithm page, not this entry, is the place for the factoring bound.