I recently learned about QuEra and I am very impressed with the hardware.
For computing Maximal Independent Sets via QuEra, we require the graph to be a unit-disk graph. I understand that, in applications, graphs that arise are often already embedded in the plane, so it might be easy to tell if it is a unit disk graph.
However, I was interested in trying to use the MIS optimization on some abstract graphs which are of interest to researchers. These are abstract graphs and it is not known (to me) if they are unit-disk graphs.
I did some research and, it turns out that it is generally a very hard computational problem to determine if it is a unit disk graph, and if so, find an embedding that realizes the unit disk condition. But I some heuristic algorithms can be/have been developed for this purpose.
My question is: Are there any code libraries, possibly open source, which can, possibly using heuristics, attempt to determine whether or not a given abstract graph is a unit-disk graph, and if so provide a unit-disk embedding of the graph? I do think such a library would probably be useful in searching for new use-cases of MIS computation using quEra.
You ask a great question and I believe I understand it in two parts:
Are there tools to convert an arbitrary graph to a unit-disk graph (UDG)
Can there be a unit-disk embedding of the UDG
I’ve relayed your first question to Jonathan Wurtz, one of algorithms expert here at QuEra and his answer was that determining if a graph is Unit Disk is a hard computational question and you are better of just trying to convert your graph in question to a Unit Disk Graph to see if it was one to begin with. The catch is this method can produce false negatives (a UDG does not map to a UDG) but no false positives (a non UDG maps to a UDG).
If your graph is “close” to a UDG you can consider forced directed optimization to nudge vertices in the graph to get UDG form.
If you have an arbitrary graph you are trying to turn into a UDG you can consider taking the the Gram matrix of your graph’s distance matrix and then using the eigendecomposition of the gram matrix to inform a projection onto positions.
This Python code snippet may be of use:
def eigen_layout(G,dimension = 2):
"""
Computes positions on a graph [ G ] based on the distance matrix.
The distance matrix is the shortest distance between any two nodes.
It does this via a projection of the Gram matrix down to a dimension [ dimension ].
If the dimension is equal to the size of the graph, then
the mapping is exact.
This is useful for graphs which actually have some underlying 2d structure,
because on long scales the distance does actually scale in a euclidian sense.
"""
N = len(G.nodes)
# Compute the distance matrix
D = zeros([N,N])
dd = dict(nx.algorithms.shortest_paths.generic.shortest_path_length(G))
for i in range(N):
for j in range(N):
D[i,j] = dd[i][j]
# Compute the Gram matrix https://math.stackexchange.com/questions/156161/finding-the-coordinates-of-points-from-distance-matrix
M = ((D[:,0:1]**2 + D[:,0:1].T**2) - D**2)/2
# Eigen-decomposition. Gram matrices are PSD and Hermetian.
eigees = linalg.eigh(M)
if eigees[0][0]<0:
max_dimension = sum(eigees[0]>0)-1
Warning('Graph is non-dimensional! Maximum dimension is {:0.0f}'.format(max_dimension))
# Positions are eigenvectors, weighted by the eigenvalue.
X = (eigees[1][:,-dimension::] * sqrt(eigees[0][-dimension::])).T
return {i:X[:,i] for i in range(X.shape[1])}
As for the second part of your question I might need some more clarification to answer it. Are you asking if a graph that is already UDG can work with the Blockade Radius or are you looking for the ability to convert an arbitrary graph and have an embedding as a UDG?
Thanks for the reply. I was really only asking one question, which is how, in practice, to convert an arbitrary graph into a unit disk graph. (I agree this is a computationally difficult problem in principle, so solutions which only sometimes work are the best we can hope for.)
I’ll try playing around with this code snippet and let you know if I can find any interesting applications to use on Quera.