# 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

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$ and $b$, which describe the two systems in isolation, their composite state is described by the tensor product of these two vectors: $a \otimes b$. If you operate on $a$ with matrix $U$, you get the composite state $(Ua) \otimes b$, 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 + 11)$ is not the tensor product of any two vectors (verify this as an excercise). In such states, measuring qubit $a$ has an effect on $b$. 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+11)$, 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+1) \otimes (0 - 1)$, 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.
(Does anybody know how to do Dirac's bra-ket notation in stackexchange $\LaTeX$?)
• On Latex: $\langle x |$ becomes $\langle x |$. So, you probably want \langle and \rangle. – D.W. Oct 12 '15 at 22:42