Quantum invariants and the graph isomorphism problem

Three graph invariants are introduced which may be measured from a quantum graph state and form examples of a framework under which other graph invariants can be constructed. Each invariant is based on distinguishing a different number of qubits. This is done by applying different measurements to the qubits to be distinguished. The performance of these invariants is evaluated and compared to classical invariants. We verify that the invariants can distinguish all nonisomorphic graphs with nine or fewer nodes. The invariants have also been applied to “classically hard” strongly regular graphs, successfully distinguishing all strongly regular graphs of up to 29 nodes, and preliminarily to weighted graphs. We have found that, although it is possible to prepare states with a polynomial number of operations, the average number of preparations required to distinguish nonisomorphic graph states scales exponentially with the number of nodes. We have so far been unable to find operators which reliably compare graphs and reduce the required number of preparations to feasible levels.

Figure 1

Schematic showing an example network or graph and the associated adjacency matrix that represents it. The adjacency matrix is constructed by numbering each node and associating each row and column with a node. Ones are then entered into the positions corresponding to connected nodes and zeros are entered otherwise. The set of adjacency matrices associated with the set of isomorphic graphs are those that are formed from simultaneously permuting the matrices' rows and columns.

Figure 2

We show the Wigner functions for the set of all five-node graphs that are not isomorphic. Note that the color maps have been scaled for each figure to maximize feature clarity. We have done this to better enable the reader to see the functional form of each graph (this does, however, mean that a direct comparison between plots in terms of magnitude is not possible). We have also computed the Wigner functions for all graphs of fewer than ten nodes and can use them to identify all graphs of fewer than eight nodes. Graphs with eight or nine nodes can still be efficiently identified by using anagraph measurements which have the form given in Eq. (18).

Figure 3

Equal-angle Wigner function (given by $〈{\widehat{\mathrm{\Pi }}}_{\frac{1}{2}}\left(\mathit{\theta },\mathit{\varphi }\right)〉$) and construction circuit for graph number 34 in Fig. 2. The sphere is the theoretical plot and the discs on its surface show the experimental data, measured at that point on the equal-angle sphere using IBM's five-qubit machine via Quantum Experience. The unmarked gates represent controlled-Z gates. We note that the IBM Experience machines are still in development and that the deviations between theory and experiment seen here are to be expected. However, we were able to use the simulator in the IBM Experience to obtain exact agreement with our own theoretical predictions, showing that the process works in principle.

Figure 4

One standard deviation about the expectation value of the equal-angle Wigner function for graph number 34 in Fig. 2. The data points are distributed over a spiral covering the sphere. The standard deviation is theoretically calculated based upon 1000 preparations of the state. This distribution of points was used to facilitate a plot, but not for comparing states since it is nonuniform.

Figure 5

Experimentally obtained anagraph values for the five node graph numbered 34 in Fig. 2. The error bars show one standard deviation based upon 4096 preparations. They can be reduced by varying the parameter $\alpha$ in Eq. (17). For each qubit the data points show the values for ${\widehat{\sigma }}_I$, $\widehat{{\sigma }_x}$, $\widehat{{\sigma }_y}$, and ${\widehat{\sigma }}_z$ from left to right. The experimentally obtained variances closely match the theoretically obtained values, giving poor signal to noise as the number of qubits increases. Varying $\alpha$ improves signal to noise at the cost of making anagraph values of nonisomorphic graphs more similar.

Figure 6

Expected number of preparations $p_N$, to distinguish graphs using anagraph values. The value is the expected number of samples to have one standard deviation between results, based on up to 200 pairs of graphs per vertex count. The 13, 16, and 18 node values are based off only two graphs each, giving only a rough estimate of the scaling.

Figure 7

Shown above in the first row are the equal-angle Wigner functions of the five-node graph numbered 13 in Fig. 2 and a weighted graph which is structurally similar to it ($\omega =0.9\pi$ on all edges). In the second row we show randomly weighted graphs also with a similar form with average $\omega$ values of $0.95\pi$ and $0.9\pi$, respectively. Due to weighted connections the resultant functions are slightly distorted from that originally obtained on the top left. However, the topography of the function appears to be robust to small changes in the edge weights.