How entanglement provide speedup?

Hi Everyone, I am trying to understand the entanglement studying the codebook.
The Exercises I.12.1(a) says that we can get the combined state of two qubits by doing the tensor product as shown below.

The exercise I.12.1(b) says that the below state we cannot get by tensor product by any way we try. We can get that state by using CNOT gate.

Even after trying a lot, I really donot understand how this property of entanglement provide a quantum computer so much speedup?

The strength of quantum computing is that it can represent a very large space (2^n x 2^n) with very few resources (n qubits). One way of looking at it is that entanglement means that the state you are working on must necessarily be represented in a space of that size. If there were no entanglement, it could be put as a product of smaller things and easily simulated on a classical computer. There are many other interpretations but I hope this one will help you a little bit :slight_smile:

1 Like

Thank you @Guillermo_Alonso for the response.
My question is that how the quantum computing with the help of its entanglement property provides speedup.
For example, suppose you have to do matrix multiplication. You can easily parallelize calculations using large number of processors and this justifies the speedup gained in High Performance Computing.
How to justify the reason for speedup in quantum computing? Is it entanglement ? Is it superposition?

Hey @Manu_Chaudhary , I think this is a complicated question to answer ‘generally’.
In short, it’s the entire mathematical structure of quantum physics that enables us to potentially reach awesome improvements upon classical algorithms. :slight_smile:

Here’s an idea: check out this demo: Grover’s Algorithm | PennyLane Demos
It explains and implements a simple quantum algorithm that gives you a much ‘shorter’ solution compared to what you would do classically. I think this is probably going to help you understand some of the basics of what you’ve been wondering about.