What is entangelement? - RPIQuantumComputing/QuantumCircuits GitHub Wiki

Entangelement, the second star to the show

In the page before, I discussed what a qubit is. However, we don't really work with computers that are just one bit. So, to truely explain quantum computing, we need to have multiple bits. Now, for classical computing, the extension is quite trivial, one can consider the bits seperately. Quantum computers allow a more sigificant level of intimacy between its qubits than classical computers do. Just like a normal computer, two bits produces the following "pure states," a state that can be explained classically, $\ket{00}, \ket{01}, \ket{10}, \ket{11}$. For $n$-bits, one has $2^{n}$ state, i.e. with each bit we have all the prior states before (append a zero the the front without changing the value) or we just append a $1$ in front of our existing bits, different from the prior state, thus one doubles the number of possibilities each time one adds an additional bit. However, a normal computer can only be in a single pure state at one point in time. This limitation does not exist in quantum computing due to an effect called entanglement.

Entangelement is best explained by example $\frac{1}{\sqrt{2}}(\ket{00} + \ket{11})$. If we observe this state, if one of the qubits are 0 or 1, we instantly know the other qubit is the same value, however both are "undecided" as being $\ket{0}$ or $\ket{1}$. Classically, there is no analogue. Mathmatically, this observation results in an non-seperatable state, specifically one that cannot be factored into individual qubit states. Although seemingly innocent, the fact that we must consider a statevector of the permutations of the bitstrings instead of a statevector of the individual qubits changes the difficulty of classically simulating quantum computers quite significantly. Now, for $n$-qubits, one must maintain and apply square matrix multiplications a vector of size $2^{n}$.

Although a complex computation for sure, such an effect does not instantly give quantum computers an exponential speed up; we still only get one result when measuring and, based on what we know now, our desired output is just one of the exponentially many outputs meaning that it is very unlikely we get the correct answer. How disappointing...should we give up? No, luckily quantum computers have one more trick up their sleaves, interference, which will discussed in the next page.