# 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: [18][19][20].

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 [3] 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. For example, suppose 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 are collected. If $$\mathbf{k}$$ is the vector of selected events, the resultant feature vector is

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

Evaluating the probabilities of orbits or events can be achieved through three approaches:

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

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

• Exact calculation: probabilities are calculated exactly, which involves calculating a large number of hafnians.

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

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

Calculating the probability of any orbit using direct sampling follows the same protocol.

To perform a Monte Carlo estimation of the probability of an event $$E$$, several samples from $$E$$ are drawn uniformly at random using 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)$$. The same protocol applies when estimating the probability of an orbit $$O$$. This time, however, orbit_to_sample() function is used to draw $$N$$ samples and calculate $$p(O)$$.

Calculating exact probabilities can be more expensive but provides the capability of doing simulations without approximations, which might be important for benchmarking GBS similarity applications. For example, exact feature vectors might be preferred in applications where the approximations can drown out the differences in graphs. The exact probability of an orbit is made up of the sum of probabilities of all possible GBS output patterns that belong to it:

$p(O) = \sum_{S \in O} p(S)$

where $$S$$ represents a GBS output pattern. Calculating each $$p(S)$$ requires computing a hafnian, which gets exponentially difficult with increasing photon number. Exact probabilities of events can be calculated by summing over their constituent orbit probabilities.

This module provides functions for feature vectors to be calculated using all the methods listed above, i.e, direct sampling, Monte Carlo (MC) estimation and exact calculations. All methods are also separately implemented for using either events or orbits as the constructing unit of feature vectors. Functions feature_vector_orbits_sampling() and feature_vector_events_sampling() calculate feature vectors using direct sampling and require a list of pre-generated samples.

Functions feature_vector_orbits() and feature_vector_events() can be used to get exact feature vectors. These functions use a keyword argument samples to signal producing either exact or approximate probabilities. samples is set to None to get exact feature vectors by default. To use Monte Carlo estimation, samples can be set to the number of samples desired to be used in the estimation. Similar to the sample() function, these two functions include a loss argument to specify the proportion of photons lost in the simulated GBS device.

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_events(graph, …[, …]) Calculates feature vector of event probabilities for the input graph. feature_vector_events_sampling(samples, …) Calculates feature vector of given events with respect to input samples. feature_vector_orbits(graph, list_of_orbits) Calculates feature vector of orbit probabilities for the input graph. feature_vector_orbits_sampling(samples, …) Calculates feature vector of given orbits 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_exact(graph, photon_number, …) Gives the exact probability of a given event for the input graph. prob_event_mc(graph, photon_number, …[, …]) Gives a Monte Carlo estimate of the probability of a given event for the input graph. prob_orbit_exact(graph, orbit[, n_mean, loss]) Gives the exact probability of a given orbit for the input graph. prob_orbit_mc(graph, orbit[, n_mean, …]) Gives a Monte Carlo estimate of the probability of a given orbit for 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.