# Role of entanglement in quantum computing

I'm not a physicist and thus, I'm looking for a simple explanation on the role of entanglement in making quantum computers fast. I got a good analogy of a qubit: a coin tossed in the air can be thought of as being in both states. Thus, 2 qubits can be thought of as storing 00, 10, 01, 11, all at the same time. However, I do not understand the role of entanglement in making quantum computers fast (in simpler terms!). Okay, we have bunch of qubits entangled in the sense that I can know the state of one based on the other: so what? How does this make quantum computations faster? Again, I want to understand it in the very, very simple terms (analogy similar to the coin toss would be best).

I understand that most people could explain it, but the challenge is to explain it in very basic terms.

• Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer.
– Community Bot
Aug 4, 2022 at 19:38

It's not true that entanglement is what makes quantum computers faster. The Gottesman-Knill theorem showed that many quantum algorithms that rely on entanglement can be efficiently implemented classically as well. As the Wikipedia article I linked for the Gottesman-Knill theorem says, it is not terribly well-understood as to where the quantum speedup comes from.

Having said that, the simple reason as to why one would expect entanglement to be the reason behind quantum speed ups is the following: if you have $$n$$ classical bits, you need $$n$$ classical bits to describe a possible state of this system. On the other hand, if you have $$n$$ qubits, you need $$\mathcal{O}(2^n)$$ classical bits to describe a possible state of this system. However, if you only allow unentangled states of $$n$$ qubits then you only need $$\mathcal{O}(n)$$ classical bits to describe a possible state of the system. Thus, the very crude intuition is that if you manage to do computation using entangled states of $$n$$ qubits, you're somehow juggling around information that would need $$O(2^n)$$ classical bits to represent -- and thus, you should get a speed up. Again, notice that this is very crude reasoning, for example, even tho you need $$\mathcal{O}(2^n)$$ classical bits to describe an $$n$$ qubit state, you cannot encode $$\mathcal{O}(2^n)$$ classical bits in $$n$$ qubits to communicate with someone. The idea is that even if you can't extract more than $$n$$ bits of classical information when you actually read off an $$n$$ qubit state, clever computation algorithms might be able to somehow use the larger phase space behind the scenes without violating the rule that when someone finally reads the $$n$$ qubit state, they don't extract more than $$n$$ bits of classical information.

• Thank you! However, I have a question. You write: "if you only allow unentangled states of n qubits then you only need O(n) classical bits to describe a possible state of the system". Is there a way to understand this by some sort of analogy? I'm just not sure why that statement is true.
– Alex
Aug 8, 2022 at 23:17
• I assume people just don’t understand it themselves.
– Alex
Aug 12, 2022 at 18:54

David Deutch has argued that quantum computers work by running the computation in lots of parallel universes simultaneously, arranging them so that the wrong answers all get cancelled out.

If you entangle $$n$$ qubits, that is like running the computation in $$2^n$$ parallel universes. Every extra qubit doubles your processing power. If you can get 32 qubits working together, that's like having $$2^{32}=4294967296$$ processors running in parallel - a lot faster than 1 classical processor! If you can get 1000 qubits entangled, that's like having a classical computer bigger than the observable universe!

Quantum computers can only do this for certain specialised sorts of problems, where it is structured so that you apply the same short calculation to lots of inputs simultaneously, and where you can find a way to sum/cancel solutions to pick out the one you want. You couldn't use it for a calculation where you had to run through that many steps sequentially. And a lot of the sorts of problems that quantum computers can be made to work on can also often be sped up by clever classical-only shortcuts, so it's tricky figuring out a problem where they are unambiguously better.