# Computational Speedups via Entanglement

*This is the **technical version** for **Science in Perspective**, my weekly science podcast. I examine a distinct area of scientific research each week, to uncover **universal techniques** that might prove useful more broadly. I also **conjecture** **new** **possibilities** **and** **directions** for that week’s area of science, and look to encourage **independent scholarship**. The podcast episodes themselves are far more high level, geared toward laymen, while these articles take a deeper technical tour of the core concepts. If you’re interested in becoming a member of Science in Perspective you can do so **here**.*

## “Searching” the Possibility Space with Interference

In **any** **problem**, there is a **possibility** **space** that must be** explored **in order to find the answer/s.

In **classical** **computing** this is done sequentially (for the most part) as no amount of classical parallelism can search all things at once (for a nontrivial problem).

In quantum computing “searching” the entire possibility space at once is indeed possible thanks (it is believed) to the properties of **superposition** and **entanglement**. A conceptual way to understand this is that superposition allows all possible configurations of the system/problem to be represented at once:

Since the superposition of all possible states can be setup to interfere constructively and destructively, an interfering mechanism can be used to search the entire space at once, as correct solutions will constructively interfere, and incorrect answers will destructively interfere.

## Grover’s Algorithm; Superposition and Entanglement

A common algorithm to use in quantum computing is **Grover’s algorithm**. Here are its core parts:

**Hadamard Gate**

First, a Hadamard gate places qubits into an equal superposition of all possible states. So, applying Hadamard gates to all 𝑛 qubits creates a superposition of all 2ⁿ possible basis states:

**Grover’s Iterate**

After the Hadamard gate has create a uniform superposition of all possible basis states, Grover’s iterate (also called the Grover operator) is used to **amplify the probability amplitudes** of the marked states (the solutions) while suppressing the unmarked states.

This occurs via 2 steps; *phase inversion* and *inversion about the mean*.

**Phase Inversion (“Oracle”)**

The Oracle **marks the correct states **(solutions) by **inverting their phase**. At this point, there is no change in the probability amplitude of the solutions, but this marking **sets solutons apart from non-solutions** in the superposition:

The system is now in a superposition of marked and unmarked states.

**Inversion about the Mean (Diffusion Operator)**

This step amplifies the probability amplitude of the marked states while decreasing the amplitude of the unmarked states. To understand how this happens, recall that the marked states now have negative probability amplitudes (due to the phase flip from the previous step), and the unmarked states have positive amplitudes. The goal is to amplify the amplitudes of the marked states to make them more likely to be observed **when the system is measured**. Marked states are ** reflected** and their amplitudes become positive and larger, while the unmarked states are moved closer to zero.

The **diffusion** **operator** that achieves this is given by:

Notice the use of **outer product**.

First, **some** **basics**…quantum states are written using **Dirac** **notation**, where a “ket” represents a column vector and a “bra” represents a row vector:

The outer product** ∣𝜓₀⟩⟨𝜓₀∣** creates a matrix (or operator) from the ket and bra, which can be used to **perform operations on quantum states:**

When this operator is applied, it means we can take a given quantum state (since the application of the Oracle and diffusion operator give us new quantum states as Grover’s algorithm evolves the system via its iterations) **∣𝜓⟩** and **extract the component **of that state that is aligned with **∣𝜓₀⟩**, which essentially** projects the evolved quantum state onto the original uniform superposition** that was created by the Hadamard gate (i.e. essentially calculating how much of** ∣𝜓⟩ **is “in the direction” of** ∣𝜓₀⟩**).

Note: This process is akin to how we can project a vector onto another vector in classical geometry, extracting the part of the first vector that lies in the direction of the second.

What all this does is essentially create the interference that constructively reinforces solutions and diminishes wrong answers.

## Defining Entanglement (Geometrically) and Tracking with Grover’s Algorithm

To get a sense of **whether or not entanglement is playing a key role in the ability to find solutions faster** than the classical regime, the authors of the referenced paper provide a **geometric definition of entanglement**:

… and use that to see if it increases as the number of iterations in Grover’s algorithm increases.

Let’s explore this geometric definition of entanglement first. Consider how a **separable** (*unentangled*) state is a state that can be **written as a tensor product of individual qubit states**:

But an **entangled state **cannot be written this way. For example, the Bell state:

…cannot be factored into a product of two independent single-qubit states.

Back to the author’s geometric definition of entanglement. The geometric measure of entanglement quantifies** how far a given state is from the closest separable state**. We can see where this notion of **distance** comes from by noting the use of the **square of the inner product** between states, which yields a **probability that measuring the entangled state would yield the separable state**:

Recall from linear algebra that the inner product (dot product) between two vectors gives 0 if the vectors are **orthogonal**. In quantum mechanics, if two states are orthogonal, they represent **distinct, non-overlapping possibilities** (i.e. measuring one will never yield the other). By taking the square of the inner product (which gives a probability as per the Born rule) you are now considering the probability that, if the system is in state ∣𝜓⟩ it will be found in state ∣𝜙⟩ when measured. Probably a better way to say this is, **as long as the inner product between two quantum states is non-zero, there is a chance that both states could be found as possible outcomes when measured**. So, in the above expression, you are essentially asking: what is the largest probability that the entangled state ∣𝜓⟩ will behave like a separable state ∣𝜁⟩.

In this way, hopefully you can see how this provides a geometric measure of entanglement for a given quantum state that is measured.

## Analytical versus Numerical

The analytical results are **ultimately** **intractable**, so numerical results were used to explore the **dynamics of entanglement**.

First, a quick elucidation as to why **analytical** calculations become **intractable**. As the number of qubits increases, the size of the Hilbert space (the vector space in which the quantum states live) grows exponentially. This exponential growth means that to describe the state of a system with 𝑛 qubits, you need to handle 2ⁿ different **coefficients** that describe the probability amplitudes for each possible state in the superposition. For a 10-qubit system this would be 1024 possible states, 1,048,576 for a 20-qubit system; far too many to write by hand. Hence, the need for numerical calculations.

## Entanglement Dynamics

So, what do the numerical results tell us about the **dynamics of entanglement? **Here are what I consider the main results:

**Entanglement Increases with Iterations**

The amount of entanglement in the system is shown to increase with the number of iterations of Grover’s algorithm.

Let’s consider what is happening here.

As the Grovers iterate keeps introducing correlations into the super-positioned system (which is what the *phase inversion* [*oracle*] and* inversion about the mean* [*diffusion*] do), the entanglement increases, which causes the amplitudes of the correct solutions to become amplified and the incorrect solutions to become depressed. A way to understand how these amplitudes are changing is in terms of an abstract **rotation** inside the **Hilbert space of possibilities**:

Each application of the Grover iterate *G* rotates the quantum state by a fixed angle in the two-dimensional space spanned by ∣𝑆ₒ⟩ and ∣𝑆₁⟩; the **subspaces of unmarked and marked states**. This is a pretty abstract interpretation of what might happen physically, but it helps formalize our understanding of what’s happening.

**2. Entanglement Peaks Midway and Decreases**

The optimal number of iterations (or rotations in Hilbert space) in Grover’s algorithm occurs when the system achieves the** best interference** — this is the point at which the marked states’ amplitudes are maximally amplified, and the unmarked states’ amplitudes are maximally suppressed. This is effectively rotating the system’s quantum state vector toward the marked states in Hilbert space.

But, if you keep applying Grover’s operator, the system continues to rotate in Hilbert space. This means that past a certain point, instead of amplifying the marked states further, the continued rotation starts to undo the amplification. In other words, **past some optimal point **you are rotating away from the solution, which means getting **lower quality interference**, thus the **peak in Figure 2**.

**3. Dependence on the Number of Qubits (n)**

The authors showed that the maximum entanglement reached during the algorithm increases as the number of qubits (n) increases. This shows that the **complexity and interdependence between qubits** increase as the system grows.

**4. Entanglement Dynamics with Multiple Marked States (M > 1)**

The authors also showed that when there are more marked states, **the peak of entanglement shifts** to later iterations. So, the more marked states there are, the **longer it takes for the entanglement to peak**. The implication here is that if using a large number of qubits (which would be needed to model realistic systems) it is still (as with classical) going to take longer to get the answer.

## Possible Application: Consider more Realistic Applications for QC

Most quantum computing reseearch uses purely theoretical benchmarks. We saw how the now embarrassing statement made by Google in 2019 in their paper on Quantum supremacy (“*the equivalent task for a state-of-the-art classical supercomputer would take approximately 10,000 years*”) ended up being beaten by a classical computer just a few years later. Sigh.

Listen to my** ****Science in Perspective** episode on this topic to learn more.

# Universal Technique:

Consider how the possibility space of a hard problem might better be searched by **leveraging physical properties**, like the use of constructive and destructive interference in quantum computing. For example, how about using **optical** **systems** for optimization problems, whereby light could used to explore large possibility spaces via constructive and destructive photons interference. Perhaps **mechanical** **metamaterials** could settle into configurations that solve optimization problems. Perhaps **chemical** **signaling** could be used to find paths or other answers. How about using **turbulence**, **pressure** **gradients** or **flow** **patterns**? **Magnets** and **spin** **glasses** also come to mind. **Molecules**? **Acoustics**? Various forms of **entropy** measurement on physical systems?

We have seen how quantum computing can be modeled as a search through the possibility space via **an abstract rotation of amplitudes inside the Hilbert space of possibilities**. This means operations can be applied to change the probability amplitudes associated with different possible outcomes, allowing *interference* to *physically* find solutions more effectively.

So, why not decision pathways in **economics**? Applying a “rotation” is akin to an intervention (e.g., policy change) that adjusts the probabilities of different economic outcomes. The state of a **biological** **system** can be modeled as a probability distribution over various traits or genetic configurations. A “rotation” here is analogous to evolutionary pressures, environmental changes or artificial selection to change the probability of traits.

The point is, it’s not ultimately about quantum computing, it’s about **adjusting probabilities through controlled transformations**.

When faced with a situation where you expect the probabilities of a system to change due to some external intervention, consider modeling the scenario as an abstract rotation of amplitudes inside its space of possibilities, and how that might physically (or informationally) change the nature of what arises.