Gaussian boson sampling for perfect matchings of arbitrary graphs

Kamil Brádler, Pierre-Luc Dallaire-Demers, Patrick Rebentrost, Daiqin Su, and Christian Weedbrook
Phys. Rev. A 98, 032310 – Published 10 September 2018

Abstract

A famously hard graph problem with a broad range of applications is computing the number of perfect matchings, that is, the number of unique and complete pairings of the vertices of a graph. We propose a method to estimate the number of perfect matchings of undirected graphs based on the relation between Gaussian boson sampling and graph theory. The probability of measuring zero or one photons in each output mode is directly related to the hafnian of the adjacency matrix, and thus to the number of perfect matchings of a graph. We present encodings of the adjacency matrix of a graph into a Gaussian state and show strategies to boost the sampling success probability for the studied graphs. With our method, a Gaussian boson sampling device can be used to estimate the number of perfect matchings significantly faster and with lower-energy consumption compared to a classical computer.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
3 More
  • Received 1 March 2018

DOI:https://doi.org/10.1103/PhysRevA.98.032310

©2018 American Physical Society

Physics Subject Headings (PhySH)

Quantum Information, Science & TechnologyAtomic, Molecular & OpticalNetworks

Authors & Affiliations

Kamil Brádler*, Pierre-Luc Dallaire-Demers, Patrick Rebentrost, Daiqin Su, and Christian Weedbrook

  • Xanadu, 372 Richmond Street West, Toronto, Ontario, Canada M5V 1X6

  • *kamil@xanadu.ai
  • daiqin@xanadu.ai

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 98, Iss. 3 — September 2018

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×