sf.apps.sample

Functionality for generating GBS samples using classical simulators.

Generating samples

An \(M\) mode GBS device can be programmed by specifying an \((M \times M)\)-dimensional symmetric matrix \(A\) [15]. Running this device results in samples that carry relevant information about the encoded matrix \(A\). When sampling, one must also specify the mean number of photons in the device, the form of detection used at the output: threshold detection or photon-number-resolving (PNR) detection, as well as the amount of loss.

The sample() function provides a simulation of sampling from GBS.

Here, each output sample is an \(M\)-dimensional list. If threshold detection is used (threshold = True), each element of a sample is either a zero (denoting no photons detected) or a one (denoting one or more photons detected), conventionally called a “click”. If photon-number resolving (PNR) detection is used (threshold = False) then elements of a sample are non-negative integers counting the number of photons detected in each mode. The loss parameter allows for simulation of photon loss in the device, which is the most common form of noise in quantum photonics. Here, loss = 0 describes ideal loss-free GBS, while generally 0 <= loss <= 1 describes the proportion of photons lost while passing through the device.

Samples can be postselected based upon their total number of photons or clicks and the numpy random seed used to generate samples can be fixed.

Generating subgraphs

There are two forms to represent a sample from a GBS device:

  1. In the form returned by sample(), each sample is a length \(M\) list of counts in each mode, e.g., the sample [2, 1, 2, 0, 1] denotes two photons in mode 0, 1 photon in mode 1, and so forth.

  2. The alternative representation is a list of modes where photons or clicks were observed, e.g., the above sample can be written alternatively as [0, 0, 1, 2, 2, 4].

Converting from the former representation to the latter can be achieved with:

modes_from_counts(s)

Convert a list of counts to a list of modes where photons or clicks were observed.

Graphs can be encoded into GBS through their adjacency matrix. Resultant samples can then be used to pick out nodes from the graph to form a subgraph. If threshold detection is used, any nodes that click are selected as part of the subgraph. For example, if a sample is [1, 1, 1, 0, 1] then the corresponding subgraph has nodes [0, 1, 2, 4]. This can be found using:

>>> modes_from_counts([1, 1, 1, 0, 1])
[0, 1, 2, 4]

A collection of GBS samples from a graph, given by sample() in the first form, can be converted to subgraphs using:

to_subgraphs(samples, graph)

Converts samples to their subgraph representation.

A typical workflow would be:

>>> g = nx.erdos_renyi_graph(5, 0.7)
>>> a = nx.to_numpy_array(g)
>>> s = sample(a, 3, 4)
>>> s = to_subgraphs(s, g)
[[0, 2], [0, 1, 2, 4], [1, 2, 3, 4], [1]]

The subgraphs sampled from GBS are likely to be dense [5], motivating their use within heuristics for problems such as maximum clique (see clique).

Including node weights

Some graphs are composed of nodes with weights. These weights can correspond to relevant information in an optimization problem and it is desirable to encode them into GBS along with the graph’s adjacency matrix. One canonical approach to doing this is to use the \(WAW\) encoding [8], which rescales the adjacency matrix according to:

\[A \rightarrow WAW,\]

with \(W=w_{i}\delta_{ij}\) the diagonal matrix formed by the weighted nodes \(w_{i}\). The rescaled adjacency matrix can be passed to sample(), resulting in a distribution that increases the probability of observing a node proportionally to its weight.

Functions

modes_from_counts(s)

Convert a list of counts to a list of modes where photons or clicks were observed.

postselect(samples, min_count, max_count)

Postselect samples by imposing a minimum and maximum number of photons or clicks.

sample(A, n_mean[, n_samples, threshold, loss])

Generate simulated samples from GBS encoded with a symmetric matrix \(A\).

seed(value)

Seed for random number generators.

to_subgraphs(samples, graph)

Converts samples to their subgraph representation.

waw_matrix(A, w)

Rescale adjacency matrix to account for node weights.