# sf.apps.similarity¶

Tools to construct graph kernels from GBS.

The graph kernel is built by mapping GBS samples from each graph to a feature vector. Similarity between graphs can then be determined by calculating the overlap between these vectors.

The functionality here is based upon the research papers: .

Graph similarity

## Coarse-graining GBS samples¶

GBS feature vectors can be composed of probabilities of coarse-grained combinations of elementary samples. We consider two coarse grainings:

• Orbits: Combine all samples that can be made identical under permutation. Orbits are written simply as a sorting of integer photon number samples in non-increasing order with the zeros at the end removed. For example, [1, 1, 2, 0] and [2, 1, 0, 1] both belong to the [2, 1, 1] orbit.

• Events: Combine all $$k$$-photon orbits where the maximum photon count in any mode does not exceed a fixed value $$n_{\max}$$ into an event $$E_{k, n_{\max}}$$. For example, orbits [2, 1], [1, 1, 1] are part of the $$E_{k=3, n_{\max}=2}$$ event, while orbit  is not.

This module provides the following tools for dealing with coarse-grained orbits and events.

## Creating a feature vector¶

A feature vector of a graph can be created by choosing a collection of orbits or events and evaluating their probabilities with respect to GBS with the embedded graph. These probabilities are then selected to be elements of the feature vector. Evaluating the probabilities of orbits or events can be achieved through two approaches:

• Direct sampling: infer the probability of orbits or events from a set of sample data.

• Monte Carlo approximation: generate samples within a given orbit or event and use them to approximate the probability.

In the direct sampling approach, $$N$$ samples are taken from GBS with the embedded graph. The number that fall within a given orbit or event $$E$$ are counted, resulting in the count $$c_{E}$$. The probability $$p(E)$$ of an orbit or event is then approximated as:

$p(E) \approx \frac{c_{E}}{N}.$

To perform a Monte Carlo estimation of the probability of an orbit or event $$E$$, several samples from $$E$$ are drawn uniformly at random using orbit_to_sample() or event_to_sample(). Suppose $$N$$ samples $$\{S_{1}, S_{2}, \ldots , S_{N}\}$$ are generated. For each sample, this function calculates the probability $$p(S_i)$$ of observing that sample from a GBS device programmed according to the input graph and mean photon number. The sum of the probabilities is then rescaled according to the cardinality $$|E|$$ and the total number of samples:

$p(E) \approx \frac{1}{N}\sum_{i=1}^N p(S_i) |E|.$

The sample mean of this sum is an estimate of the rescaled probability $$p(E)$$.

This module provides functions to evaluate the probability of orbits and events through Monte Carlo approximation.

Similar to the sample() function, the MC estimators include a loss argument to specify the proportion of photons lost in the simulated GBS device.

One canonical method of constructing a feature vector is to pick event probabilities $$p_{k} := p_{E_{k, n_{\max}}}$$ with all events $$E_{k, n_{\max}}$$ having a maximum photon count $$n_{\max}$$ in each mode. If $$\mathbf{k}$$ is the vector of selected events, the resultant feature vector is

$f_{\mathbf{k}} = (p_{k_{1}}, p_{k_{2}}, \ldots).$

This module allows for such feature vectors to be calculated using both the direct sampling and Monte Carlo approximation methods.

Functions

 event_cardinality(photon_number, …) Gives the number of samples belonging to the input event. event_to_sample(photon_number, …) Generates a sample selected uniformly at random from the specified event. feature_vector_mc(graph, event_photon_numbers) Calculates feature vector using Monte Carlo estimation of event probabilities according to the input graph. feature_vector_sampling(samples, …[, …]) Calculates feature vector with respect to input samples. orbit_cardinality(orbit, modes) Gives the number of samples belonging to the input orbit. orbit_to_sample(orbit, modes) Generates a sample selected uniformly at random from the specified orbit. orbits(photon_number) Generate all the possible orbits for a given photon number. prob_event_mc(graph, photon_number, …[, …]) Gives a Monte Carlo estimate of the GBS probability of a given event according to the input graph. prob_orbit_mc(graph, orbit[, n_mean, …]) Gives a Monte Carlo estimate of the GBS probability of a given orbit according to the input graph. sample_to_event(sample, max_count_per_mode) Provides the event corresponding to a given sample. sample_to_orbit(sample) Provides the orbit corresponding to a given sample.