How Quantum Computers Use Entanglement to Outperform Classical Computers

The Qubit

The qubit is the fundamental unit of quantum computing. The classical computer works with bits which can have either of two values, 0 or 1. The qubit exists in a superposition of 0 and 1. We represent the state as some complex number times each state 0 and 1 where the square of the magnitudes of the complex number represents the probability of measuring the qubit in the respective state. Hence the qubit exists as a superposition of both values 0 and 1 and only collapses to a single value when measured.

Quantum Entanglement

Quantum entanglement refers to the phenomenon where some property of each particle in a group is connected to the entire group regardless of distance. Consider a subatomic particle that decays into a pair of particles. Due to the conservation laws such as the conservation of momentum, these two particles are entangled. The particles are quantum and hence exist in a superposition of values. For example consider an intrinsic property of particles called spin. If a spin 0 particles decays into a pair of spin 1/2 particles, the total spin must be conserved and the emitted particles exist in a superposition of +1/2 and -1/2. However when we measure the spin of one of these particles, we immediately know the spin of the other particle is the opposite due to the conservation law. This occurs regardless of the distance between the particles.
The Bell states are the simplest example of quantum entanglement for 2 qubits. They are given by:

Image Credit: Quantum Computing UK

Here |00> means measuring 0 for both the first and second qubit.
Consider the first state shown above. It exists in a superposition of 00 and 11. If the first qubit is found to be 0, the other is immediately known to be in 1. Bell states have correlations that can be used to perform tasks that are impossible for separable states such as quantum teleportation.

Quantum Logic Gates

Quantum logic gates are the building blocks of quantum circuits. They act on qubits to transform their states and particular gates are essential to quantum teleportation.
The three Pauli gates X,Y,Z represent the three rotations along the x,y,z axes respectively. The Pauli-X gate is referred to as the bit-flip gate as it maps 0 to 1 and 1 to 0. The Pauli-Z gate is referred to as the phase-flip gate as it maps 0 to 0 and 1 to -1.
The controlled NOT gate (CNOT) acts on 2 or more qubits. For 2 qubits, if the first qubit is 0, it leaves both qubits unchanged. If the first qubit is 1, it applies the Pauli-X/bit-flip gate to the second qubit.
The Hadamard gate acts on a single qubit. It maps each qubit into an equal superposition of 0 and 1. These gates are used to exploit quantum teleportation.

Quantum Teleportation

Let’s consider two observers Alice and Bob who are in two different places. We consider 3 qubits labelled A, B, C. Initially B and C are entangled and in a Bell state while A is in some particular superposition of 0 and 1. Qubit A is the one we want to teleport. It’s state is shown below:

Alice keeps qubits A and B while qubit C is sent to Bob.

Next, a CNOT gate is applied to A and B and a Hadamard gate is applied to the first qubit. Mathematically, this simplifies the total state into a superposition of 4 terms as shown below.

Image Credit: Matthew Silverman, “Quantum Teleportation,” 2023. Accessed via https://pennylane.ai/qml/demos/tutorial_teleportation

Alice then measures both qubits, collapsing their states and sends the result to Bob.
Bob can receive 4 possible states, 00, 01, 10, 11.
If it is 00, then Bob’s qubit C is in the initial state A
If it is 01, then Bob applies the bitflip gate to C and it is then in the state A.
If it is 10, then Bob applies the phase-flip gate to C and it is then in the state A.
If it is 11, then Bob applies both the bitflip and the phase-flip gate to C and it is then in the state A.

Hence Bob’s qubit ends up in the state A despite never interacting with it directly and Alice collapsing it during measurement. We say the state A has teleported from Alice to Bob.

Grover’s Algorithm

This algorithm uses entanglement to outperform a classical computer in the unstructured search problem. We are given a set of N elements and we want to find a single particular element in the set. A classical computer would check every element of the list until it finds the correct one. This takes an average of N/2 steps and a maximum of N-1. Hence it is order N.
Using Grover’s Algorithm, we can reduce this to order square root of N.
Firstly, the initial state of N elements is entangled.
Next the oracle acts on the state.
The oracle acts on a state by inverting its phase if it is the correct element and leaving it unchanged if it not. Since this phase flip does not change the square of the probability amplitudes this act is invisible to measurement.
We want to somehow separate the correct value from the others by increasing its probability amplitude. This can be achieved by using the diffusion operator. Conceptually, it finds the average amplitude and reflects each state about the average.
By repeating these 2 steps, over time the correct state’s phase is flipped continuously and then reflected which causes its probability amplitude to rise above other states. This allows us to identify the correct element with high probability in a shorter time compared to classical computers.

In summary, quantum computers take advantage of quantum phenomena such as superposition and entanglement to outperform classical computers. The phenomenon of quantum teleportation displays the manipulation of entanglement in order to achieve new ways of communication. Grover’s algorithm is a simple example that showcases how quantum algorithm can surpass classical search.

References