PaperlayerView exact revision on arXiv

Source-linked AI summary

Applications of Near-Term Photonic Quantum Computers: Software and Algorithms

Thomas R. Bromley, Juan Miguel Arrazola, Soran Jahangiri, Josh Izaac, Nicolás Quesada, Alain Delgado Gran, Maria Schuld, Jeremy Swinarton, Zeid Zabaneh, Nathan Killoran

arXiv:1912.07634v1quant-phphysics.comp-ph

TL;DR

Near-term quantum computers have limited size, connectivity, and circuit depth, while dedicated software can help users develop quantum algorithms. This paper introduces a Strawberry Fields applications layer for implementing GBS algorithms and shows an example in which its search function finds a planted dense subgraph with density 0.933.

  • Problem

    Near-term quantum computers have limited size, connectivity, and circuit depth, while developing algorithms for them remains a challenge.

    Source: §I · p. 1

  • Method

    The paper introduces a Strawberry Fields front-end applications layer with modules and tools for implementing GBS algorithms.

    Source: §I · p. 2, §III · p. 7

  • Results

    In the example, the GBS-based search found the planted subgraph with density 0.933.

    Source: §2 · p. 13

  • Takeaways & Limitations

    The applications layer brings GBS algorithm implementation tools and examples into Strawberry Fields for users developing and testing algorithms.

    Source: §I · p. 2, §III · p. 7

    Further work is needed to establish these methods’ advantages over classical algorithms, especially their scaling with problem size.

    Source: §V · p. 30

Abstract

from arXiv · show

Gaussian Boson Sampling (GBS) is a near-term platform for photonic quantum computing. Recent efforts have led to the discovery of GBS algorithms with applications to graph-based problems, point processes, and molecular vibronic spectra in chemistry. The development of dedicated quantum software is a key enabler in permitting users to program devices and implement algorithms. In this work, we introduce a new applications layer for the Strawberry Fields photonic quantum computing library. The applications layer provides users with the necessary tools to design and implement algorithms using GBS with only a few lines of code. This paper serves a dual role as an introduction to the software, supported with example code, and also a review of the current state of the art in GBS algorithms.

I. INTRODUCTION

Near-term quantum computers have limited size, connectivity, and circuit depth, while quantum software can help users develop algorithms through high-level tools. This section introduces the Strawberry Fields GBS applications layer and reviews how Gaussian states are prepared and measured in GBS.

I. INTRODUCTION

  • Near-term quantum computers have limited size, connectivity, and circuit depth, motivating tools that make algorithm development easier.Some existing devices may also be sub-universal and tailored to specific tasks.Source: §I · p. 1
  • The Strawberry Fields applications layer provides modules for five GBS application areas, with built-in functions for programming, sampling, and classical post-processing.It also offers visualization, pre-generated datasets, and tutorials.Source: §I · p. 2

II. GAUSSIAN BOSON SAMPLING

  • GBS prepares a multimode Gaussian state using squeezing and linear interferometry, then measures photon numbers in the Fock basis.Displacements can also be used to prepare general pure Gaussian states.Source: §II · p. 3
  • For zero-mean Gaussian states, the output probabilities are determined by the state covariance matrix and detected photon pattern, using a hafnian.The output pattern specifies the submatrix by repeating rows and columns according to detected photons.Source: §II · pp. 3–4
  • With threshold detectors, GBS records whether each mode registers a click, and the output distribution is expressed using the Torontonian.A click indicates one or more photons in that mode.Source: §II · p. 5
  • Photon loss is a relevant near-term optical-device noise, and one simple simulation models equal-strength loss channels on every mode.The loss parameter gives the proportion of photons lost.Source: §II · p. 5

A. Programming a GBS device

A GBS device can be programmed by specifying gate parameters or an equivalent symmetric matrix. Graph adjacency matrices are one such input, and a decomposition maps the matrix to interferometer and squeezing settings.

A. Programming a GBS device

  • In pure-state GBS without displacements, specifying gate parameters is equivalent to specifying the symmetric matrix that characterizes the output distribution.The device can also be programmed directly by specifying the Gaussian state to sample.Source: A. Programming a GBS device · p. 6
  • The Takagi-Autonne decomposition maps the matrix to an interferometer unitary and values that determine squeezing; rescaling controls those values and the mean photon number.The programming procedure decomposes the matrix, programs the interferometer, chooses a scale for the target mean photon number, and sets squeezing parameters.Source: A. Programming a GBS device · p. 6
  • Any undirected graph can be encoded in GBS through its symmetric adjacency matrix, whose entries specify edge weights.The same programming of squeezing and interferometry applies with threshold detectors; only the detectors change.Source: A. Programming a GBS device · p. 7

III. THE STRAWBERRY FIELDS APPLICATIONS LAYER

The Strawberry Fields applications layer is a front-end component for implementing GBS algorithms within a library that also constructs and compiles programs and supports simulator and hardware back ends. Its application modules are complemented by tools for sampling, visualization, data access, and tutorials.

III. THE STRAWBERRY FIELDS APPLICATIONS LAYER

  • The applications layer is a Strawberry Fields front-end component for implementing GBS algorithms, alongside program construction and compilation and simulator or hardware back ends.The paper notes that hardware back ends were planned to come online in the future.Source: §III · p. 7, Figure 3 · p. 8
  • Application-specific modules cover dense subgraph identification, maximum clique, graph similarity, point processes, and vibronic spectra.Auxiliary modules support sampling, visualization, and access to pre-generated data.Source: §III · p. 7, Figure 3 · p. 8
  • The sample module generates GBS samples from a symmetric matrix and mean photon number, with options for detector type, photon loss, and photon-number postselection.The sample function interfaces with the Strawberry Fields Gaussian backend and The Walrus library.Source: §III · pp. 7–8
  • Users can load pre-generated samples and related information through the data module, and use graph and plotting tools for manipulation and visualization.The examples show loading PHat data and plotting a graph.Source: §III · p. 9

IV. APPLICATIONS OF GAUSSIAN BOSON SAMPLING

The paper reviews known GBS algorithms and explains their mathematical formulations and implementation through example code. It characterizes most as heuristic approaches, spanning classical acceleration, statistical modeling, and computation of objects that reveal problem properties.

IV. APPLICATIONS OF GAUSSIAN BOSON SAMPLING

  • The section reviews currently known GBS algorithms, giving each application’s problem, algorithm, and example code for implementation.It serves as both an algorithm review and an introduction to the applications layer.Source: §IV · p. 9
  • Most described GBS algorithms are heuristics that use GBS as a classical-algorithm accelerator, a statistical-modeling method, or a means to compute informative histograms or vectors.The paper presents these approaches as leveraging properties of GBS devices.Source: §IV · pp. 9–10
  • The reviewed algorithms represent the current state of the art in GBS applications, a field the paper describes as nascent.The applications layer is intended to provide tools for further algorithm development.Source: §IV · p. 10

A. Dense subgraph identification

The section formulates dense-subgraph identification as a search for high-density node sets and describes how GBS sampling can seed a classical resizing search across subgraph sizes.

A. Dense subgraph identification

  • Dense-subgraph search seeks the densest k-node induced subgraph by edge density, with extensions across k and to multiple high-density regions.Such dense regions can represent highly connected communities or correlated subsets in networks.Source: A. Dense subgraph identification · p. 10

1. GBS algorithm for dense subgraph identification

  • GBS samples can be interpreted as subgraphs, with their probabilities depending on the hafnian of the corresponding adjacency matrix.The hafnian counts perfect matchings; subgraphs with many perfect matchings are sampled with high probability.Source: §1 · pp. 10–11
  • Because hafnian is correlated with graph density, GBS can seed the search with dense subgraphs, which a Charikar-style degree-based resizing algorithm then explores.The text reports numerical evidence that GBS seeding improved the performance of a range of classical algorithms.Source: §1 · pp. 11–12
  • The algorithm selects a subgraph-size range, removes low-degree nodes above its minimum, adds high-degree nodes below its maximum, and returns the densest found at each size.Ties in resizing are broken uniformly at random.Source: §1 · pp. 11–12
  • The mean photon number controls typical GBS sample size and should match the size at which the densest subgraphs are expected.GBS outputs may include multi-photon events, which represent extended induced subgraphs by replicating nodes according to their photon counts.Source: §1 · pp. 10, 12

2. Using the GBS applications layer

The applications-layer examples show how GBS samples can seed graph searches in Strawberry Fields. They demonstrate a planted dense-subgraph result and describe maximum-clique search, including a reported molecular-docking success-rate increase.

2. Using the GBS applications layer

  • 0.933 density: GBS-seeded search found the planted subgraph, whereas resizing the full graph removed its low-degree nodes and found none.The planted graph has 10 nodes; the example returns it as the densest subgraph of that size.Source: §2 · p. 13
  • For different sizes, the densest subgraphs occupy different graph regions: those under ten nodes are planted, while larger ones are outside it and less dense.Smaller dense subgraphs can be cliques with density 1.Source: §2 · pp. 13–14

1. GBS algorithm for max clique

  • Local search grows a clique using nodes connected to all its members, then swaps using nodes connected to all but one member to reach other cliques.The growth and swap phases alternate until no further move is available.Source: §1 · p. 14
  • The maximum-clique algorithm uses GBS-sampled dense subgraphs as starting points, trims them into cliques, then alternates growth and swaps until a dead end or iteration limit.It returns the largest clique found across the samples.Source: §1 · pp. 14–15
  • For weighted-node graphs, the choice of α trades off density and weight: as α approaches zero sampling becomes weight-independent, while large α favors high-weight subgraphs.Weighted maximum clique is one application of this approach.Source: §1 · pp. 15–16
  • Roughly 30% to 70%: Ref. [40] reported this increase in the molecular-docking algorithm’s success rate when it employed GBS samples.The docking task is mapped to weighted maximum clique.Source: §1 · p. 16

2. Using the GBS applications layer

The clique module combines subgraph shrinking with local search to find maximum cliques from GBS samples. On the 300-node PHat graph, the example finds three cliques of the known maximum size, eight.

2. Using the GBS applications layer

  • The clique module's shrink() and search() functions respectively shrink sampled subgraphs to cliques and apply local search.Source: §2 · p. 16
  • The example loads pre-generated PHat samples, postselects them, converts them to subgraphs, and applies both clique functions.Source: §2 · p. 16
  • Three size-8 cliques found on the 300-node PHat graph are known to be maximum cliques.The graph has multiple maximum cliques of size 8.Source: §2 · pp. 16–17, Figure 7 · p. 17

C. Graph similarity

Graph similarity methods seek mappings and kernels that capture relevant structural properties. GBS graph features use coarse-grained event probabilities, with prior exact-kernel tests outperforming classical kernels on nine of eleven datasets.

C. Graph similarity

  • Graph kernels compare feature vectors to analyze and classify graphs, but mappings must capture properties relevant to each application.Source: C. Graph similarity · pp. 17–18

1. Graph similarity with GBS

  • GBS distributions characterize graph isomorphism, but identifying a differing probability is difficult because there are exponentially many and individual probabilities are typically exponentially small.Source: §1 · p. 18
  • Samples are grouped into permutation-equivalent orbits, then into events E_k,n containing k-photon samples with no mode occupancy above n.This further coarse-graining addresses the exponentially growing number of possible orbits.Source: §1 · p. 18
  • A graph feature vector consists of its GBS event probabilities across selected photon-number values, and isomorphic graphs have identical feature vectors.The choices of photon-number range and maximum per-mode occupancy are configurable.Source: §1 · p. 18
  • GBS kernels computed exactly outperformed three classical graph kernels on nine of eleven datasets in classification tests.The comparisons covered Graphlet Sampling, random walk, and subgraph matching kernels.Source: §1 · p. 19

2. Using the GBS applications layer

The applications-layer example uses GBS samples to build graph features, while the point-process section describes matrix kernels and GBS sampling algorithms. For positive-semidefinite kernels, a quantum-inspired permanental-process sampler has polynomial runtime.

2. Using the GBS applications layer

  • The MUTAG example uses four graphs with 20,000 GBS samples each, and builds two-dimensional feature vectors from events E_8,2 and E_10,2.The graphs represent chemical compounds and carry labels based on mutagenic effect.Source: §2 · pp. 19–20

D. Point processes

  • A matrix point process is specified by a kernel matrix and a matrix function; determinantal processes promote diversity, while hafnian and permanental processes produce clustered samples.For spatial data, clustering means points close to one another; with correlation kernels it means selecting highly correlated variables.Source: D. Point processes · p. 21, §1 · p. 23
  • An RBF kernel encodes spatial proximity: nearby points receive larger kernel entries, and the parameter σ sets the proximity scale.The kernel is positive semidefinite.Source: D. Point processes · pp. 21–22

1. GBS algorithm for point processes

  • GBS can implement hafnian point processes, while a thermal-state variant realizes permanental point processes for positive-semidefinite kernels.Source: §1 · p. 22
  • Thermal-state amplitudes can be sampled as a distribution over coherent states, then transformed through an interferometer and converted into Poisson-distributed photon counts.Source: §1 · pp. 22–23
  • For positive-semidefinite inputs, the quantum-inspired permanental-process algorithm runs in O(m^3), dominated by the Takagi-Autonne decomposition, and generates samples in O(m^2).The paper recommends this algorithm for such inputs because it can scale to large sizes.Source: §1 · p. 23

2. Using the GBS applications layer

The points module constructs an RBF kernel from coordinates and samples a permanental point process. In the illustrated inhomogeneous space, selections concentrate near cluster centers rather than the uniform background.

2. Using the GBS applications layer

  • The points module builds the RBF kernel from an m×n coordinate matrix and scale σ, then samples the corresponding permanental process.Source: §2 · p. 23
  • In the 20×10 grid example, the permanental-process sample exhibits clustering among the selected points.Source: Figure 11 · p. 24, §2 · p. 24
  • For inhomogeneous spaces, RBF-kernel hafnian and permanental processes are more likely to select points that are already close together.Source: §2 · p. 24
  • In a space with two 100-point normal clusters and a 200-point uniform background, most selected points lie near cluster centers, unlike uniform sampling, which would select half from the background on average.Source: §2 · pp. 24–25, Figure 12 · p. 25

E. Vibronic spectra

Vibronic spectra describe molecular transitions involving electronic and vibrational degrees of freedom, with Franck-Condon factors specifying transition probabilities. The Franck-Condon profile gives the spectrum, while calculating it accurately for large molecules remains challenging.

E. Vibronic spectra

  • Vibronic spectra are molecular absorption lines arising from transitions involving both electronic and vibrational degrees of freedom.Such spectra are relevant to applications including photovoltaics and industrial dyes.Source: E. Vibronic spectra · p. 25
  • Franck-Condon factors give the probabilities of electronically allowed vibronic transitions from the ground vibrational state at zero temperature.The ground state is represented by the vacuum of vibrational excitations.Source: E. Vibronic spectra · p. 26
  • The Franck-Condon profile (FCP) specifies the probability of generating a transition at a given vibrational frequency.At zero temperature, the profile is defined for transitions starting from the ground vibrational state.Source: E. Vibronic spectra · p. 26
  • At finite temperature, the FCP accounts for populated initial vibrational modes through their distribution and energies.Low-energy excited modes can be populated, allowing transitions to start from excited vibrational states.Source: E. Vibronic spectra · p. 26
  • Accurately calculating FCPs for large molecules remains challenging, motivating a GBS algorithm to reconstruct vibronic spectra using bosonic quantum properties.The cited methods include, and the large-molecule challenge is noted in.Source: E. Vibronic spectra · p. 26

1. Vibronic spectra with GBS

The GBS vibronic-spectrum algorithm maps the transformation between a molecule’s ground- and excited-state vibrational modes to Gaussian operations. It samples transformed modes to reconstruct transition energies and their spectrum.

1. Vibronic spectra with GBS

  • The Doktorov operator is a Gaussian unitary that connects ground- and excited-state vibrational modes and decomposes into displacement, squeezing, and interferometer operations.This connection uses the mathematical equivalence between photons in optical modes and phonons in vibrational modes.Source: §1 · pp. 26–27
  • The mode transformation generally combines rotation, squeezing, and displacement, represented by corresponding Gaussian transformations in the GBS algorithm.The schematic depicts the ground- and excited-state energy surfaces as paraboloids.Source: Figure 13 · p. 27
  • The Doktorov parameters are determined from molecular inputs including ground- and excited-state frequencies, normal-mode coordinates, and structural displacement.The Duschinsky matrix is obtained from the normal-mode coordinates, and the interferometer and squeezing parameters follow from a singular value decomposition.Source: §1 · pp. 27–28
  • For finite-temperature sampling, the algorithm prepares two-mode squeezed states across 2M modes, applies the Doktorov transformation to the first M modes, and measures all output modes.The squeezing parameters depend on the mode frequencies and temperature.Source: §1 · p. 28
  • Repeated samples are converted into transition energies and assembled into a histogram that statistically reconstructs the Franck-Condon profile.At zero temperature, the input is vacuum and the circuit simplifies to M modes by omitting two-mode squeezing and the first interferometer.Source: §1 · pp. 27–28

2. Using the GBS applications layer

The applications-layer example demonstrates a code workflow for generating and plotting a formic-acid vibronic spectrum. The outlook identifies unresolved questions about industrial relevance, classical scaling, and imperfections, while presenting the software as an evolving open-source platform.

2. Using the GBS applications layer

  • For formic acid, the vibronic module accepts molecular parameters and temperature, then computes the GBS parameters with gbs_params().The example loads the frequencies, Duschinsky matrix, displacement vector, and temperature from the data module.Source: §2 · p. 29
  • The sample and vibronic modules generate samples and compute their energies, while the plot module builds the spectrum from those energies.The example uses sample.vibronic(), energies(), and plot.spectrum().Source: §2 · p. 29
  • The formic-acid spectrum plot shows sample counts against relative wavenumber, with a Lorentzian-broadened curve intended to resemble experimental spectra.The 0-0 transition is set to zero relative wavenumber.Source: Figure 14 · p. 30

V. OUTLOOK

  • Only vibronic spectra and molecular docking are identified as GBS examples tied to specific industrially relevant problems, and further work is needed to assess advantage over classical methods as problem size grows.The outlook calls for connecting known techniques to more specific industrial problems and understanding scaling with problem size.Source: §V · p. 30
  • Experimental implementations remain early, and imperfections including photon loss and decoherence can affect device performance, motivating noise-resilient algorithms and error-mitigation methods.The outlook calls for better understanding of imperfections’ impact.Source: §V · p. 30
  • The open-source applications layer is presented as an evolving platform: quantum software supports research, which in turn can inform better software.The authors say it is designed to grow and adapt as new discoveries are made.Source: §V · pp. 30–31
Loading 1912.07634v1…