I am trying to solve a minimum spanning tree problem using Grover's Algorithm. To accomplish this I would need to search a list for the minimum weight or edge for each point, for example:

Given the following list:

enter image description here

How would one use Grover's algorithm to search for the minimum weight ie. 1 and then return the values (C, G). I am trying to understand how this problem would be practically applied on either an actual quantum processor or the simulator. I know that an oracle is needed to give the values, but how would this be implemented. Any help is appreciated.

  • 1
    $\begingroup$ A good reference is Dürr et al ("Quantum query complexity of some graph problems"), where they explicitly solve this problem using Grover search (and minimum finding, as in cnada's post below). In this paper, your model is called the "adjacency array model". $\endgroup$
    – smapers
    Jun 7 '19 at 8:46

Just giving two possibilities. There may be others more efficient but that can be a good start.

Let us take your case. You have a graph with 8 points. Say we index each point by an integer alphabetically: A=0,B=1,C=2,...H=7. You can represent them in supperposition using a 3-qubit register and the Hadamard transform. Add another 3-qubit register. This give us all possible connexions between points:

$$ \frac{1}{8} (| AA \rangle + | AB \rangle + | AC \rangle + ... + | GH \rangle) $$ Of course, in that case, we consider we can have loops and we also have connexions that may not exist in our graph.

Then using another register, you can compute the edge value for a connexion (using for example a controlled-adder circuit to add the edge value depending on the connexion computational basis):

$$ \frac{1}{8} (| AA \rangle + | AB \rangle + | AC \rangle + ... + | GH \rangle) | 0\rangle \rightarrow \frac{1}{8} (| AA \rangle | 0\rangle + | AB \rangle | 5\rangle + | AC \rangle | 7\rangle + ... + | GH \rangle | 6\rangle) $$

Also, another way I can think of is to assign an integer index to the connexion/edges of the graph themselves , which lets you work on only one register for storing the index. You just need enough qubits to have all edges indices in superposition. And again, use another register to compute their values like above.

Now for the search, you would look at the edge value register when searching. You can use Durr and Hoyer's adaptation of Grover search to find the minimum. Or in your case, directly implement an oracle that recognizes the value 1 in the edge/value register (imagine this would be your first check/try to find the minimum) and use a simple Grover search.


Your Answer

