# Where does entanglement fit into quantum computing?

I've been reading up on quantum computing online from various sources, including this link http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm.

I get how quantum gates work, destructive interference, and how you can simulate a quantum computer using matrix math and complex numbers.

Does entanglement have a use in quantum computing? I haven't yet seen anything explicitly talk about entanglement and whether it's used in QC, but I feel like it's possible it might be implicitly stated and I could be missing it - or maybe not!

Thanks!

• qubits are entangled in the quantum gates. as an example of this, bells experiment is sometimes referred to in terms of CNOT gates. – vzn Oct 11 '15 at 16:51

## 1 Answer

The entanglement of quantum particles is, implicitly or explicitly, the reason why quantum computing is so fast. You will know by now that a qubit (implemented for example as a photon's polarization) can be represented as a unit vector of two complex numbers, and that it may be manipulated by a 2-by-2 matrix of complex numbers. If you have two quantum systems described by their respective state vectors $$|a\rangle$$ and $$|b\rangle$$, which describe the two systems in isolation, their composite state is described by the tensor product of these two vectors: $$|a\rangle \otimes |b\rangle$$. If you operate on $$|a\rangle$$ with matrix $$U$$, you get the composite state $$(U|a\rangle) \otimes |b\rangle$$, and so forth.

Entanglement comes when you operate on this composite state and bring it to a state which cannot emerge as the tensor product of two state vectors. For example, the state $$\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$$ is not the tensor product of any two vectors (verify this as an excercise). In such states, measuring qubit $$|a\rangle$$ has an effect on $$|b\rangle$$. For example, if you performed a partial measurement (that is, a measurement of ostensibly only one qubit) on the most significant bit of $$\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$$, and you measured it to be $$0$$, then measuring the least significant bit will yield $$0$$ with certainty, too, and vice versa.

A good first example for studying entanglement is Deutsch' problem, where the algorithm goes from $$(|0\rangle+|1\rangle) \otimes (|0\rangle - |1\rangle)$$, a state which can be expressed as the tensor product, to a state which can no longer be expressed as any tensor product, using an operator which cannot be expressed as the tensor product of two operators.

• On Latex: $\langle x |$ becomes $\langle x |$. So, you probably want \langle and \rangle. – D.W. Oct 12 '15 at 22:42