Using Grover’s Search for MST
A tale of two (or more) cities
Let’s say you have a collection of cities on a map, and you want to connect them all. You have a list of potential roads, each connecting two cities and each having a different cost. You’re on a budget, so how do you decide which roads to build while keeping the total cost as low as possible? This, in short, is the minimum spanning tree (or MST) problem. Formally, a minimum spanning tree is a graph consisting of the subset of edges which together connect all connected nodes, while minimizing the total sum of weights on the edges.
Borůvka’s algorithm
Now, how do we go about finding such a graph? First, let’s look at a classical algorithm called Borůvka’s algorithm. (Don’t worry, we’ll add the quantum back in later, I promise.) The procedure works as follows:
- Initialize each node to be its own tree
- For each tree in the forest, find the cheapest (lowest-weight) edge that connects it to another tree
- Add each such edge to the MST
- Merge the trees now connected by an edge
- Repeatedly search and merge until only one tree remains
On a graph with V vertices and E edges, this finds an MST in O(E log V) time. That’s as good as a classical approach gets for this particular problem. Now, the question is: can we use quantum computing to make this faster? In this article, I’ll go over an optimization for the edge-finding step using a modified Grover’s search. But first, let’s take a step back and review the mechanics of the standard Grover’s search.
Standard Grover’s search intuition
This circuit consists of two unitary operations, the oracle (written as U_f) and the diffusor (written as R).
The oracle induces a phase flip only for the ‘correct’ element. Here, the ‘correct’ element is the state where all qubits are in the 1 position. Let’s look at a 2-qubit example. If we start with |Ψ> = 1/2 (|00> + |01> + |10> + |11>), then after applying the oracle we get U_f|Ψ> = 1/2 (|00> + |01> + |10> - |11>).
In the circuit, we achieve this using a multi-control-Z gate, which only performs the Pauli Z operator on the (n-1)th bit if bits 0 through n-2 are all in the 1 state. The Pauli Z operator in turn only introduces a negative sign when the (n-1)th bit is in the 1 state, meaning the circuit selects for the all-ones state. (Okay, technically the circuit uses a multi-control-X or MCX gate, but HXH = Z so it functions the same way.)
The diffusor inverts the amplitudes of each state in the superposition around the mean of all amplitudes. As a result, this amplifies the effect of the oracle. Mathematically, the diffusor unitary is the matrix R = 2|ψ><ψ|−I. The proof that this really does work out is an exercise left to the reader. But before that, here’s a graphic to better show the intuition of how this works:
However, one amplification isn’t enough. Thus, we repeatedly apply the oracle and diffusor until the probability of measuring the ‘correct’ state is very high, and the probability of measuring other states is very low. This occurs after T = ⌈πN√4⌉ repetitions, where N = the total number of states, or 2^n with n = the number of qubits. After that, applying more cycles starts to degrade the superposition, so it’s important to get the timing just right.
Minima-finding modifications
To create an algorithm that finds the minimum in a list, we’re going to need two more oracles that build on the basic one we saw earlier. I’ve named them the equal oracle and the less-or-equal oracle
The equal oracle takes in a value v as an argument and ‘marks’ (by inducing a phase flip) the state which matches the binary representation of v. It does this by ‘transforming’ v into the binary number with all 1’s using Pauli X gates on specific qubits. For example, if v = 10110₂, then we would flip the second and fifth qubits to turn v into 11111₂. Then, we can use the all-ones oracle we prepared earlier to induce a phase flip and then undo the bit flips by applying Pauli X gates to the second and fifth qubits again. Now, the state that represents 10110₂ has a phase change.
The less-or-equal oracle takes in a value v as an argument and marks all states with a binary representation less than or equal to v. For example, if we take v = 0011₂, the less-or-equal oracle would induce a phase flip on |0000>, |0001>, |0010>, and |0011>. It does this by running the equal oracle on all values from 0 to v.
Ok, now that we’ve constructed our final oracle, we can actually put together the algorithm.
- Randomly choose a value j out of the possible answers
- Run Grover’s search using the less-or-equal oracle
- Update j with results of search
- Repeat this T times, with T = 22.5√N + 1.4 log₂²(N)
By doing this, we can bring Borůvka’s algorithm to a time complexity of O(√(VE)).
Limitations
Unfortunately, this optimization doesn’t solve everything. I ran the minima-finding Grover’s search on a 4-qubit system with various input values. Here’s my results:
By the time we reach val = 3, the search already stops giving useful information. Thus, in order to query larger values, we must pad out the state space by adding larger numbers, increasing the number of qubits used.
Either way, I still think it’s a pretty cool example of how quantum computing can help improve upon classical algorithms.
Citations
ACM Transactions on Quantum Computing, Volume 3, Issue 4. December 2022. Article No.: 18, pp 1–92. https://doi.org/10.1145/3517340
https://github.com/lanl/quantum_algorithms
https://qiskit.org/textbook/ch-algorithms/grover.html#3qubits
