Gaussian Boson Sampling for perfect matchings of arbitrary graphs
arXiv:1712.06729 · doi:10.1103/PhysRevA.98.032310
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. 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.
17 pages, 10 figures
References in corpus (5)
- Detection of 15 dB Squeezed States of Light and their Application for the Absolute Calibration of Photoelectric Quantum Efficiency
- Quantum Computational Supremacy
- Environment-Assisted Quantum Transport
- Gaussian states in continuous variable quantum information
- Sampling arbitrary photon-added or photon-subtracted squeezed states is in the same complexity class as boson sampling
Cited by in corpus (56)
- Quantum circuits with many photons on a programmable nanophotonic chip
- Strawberry Fields: A Software Platform for Photonic Quantum Computing
- Non-Gaussian Quantum States and Where to Find Them
- Phase-dependent chiral transport and effective non-Hermitian dynamics in a bosonic Kitaev-Majorana chain
- Broadband quadrature-squeezed vacuum and nonclassical photon number correlations from a nanophotonic device
- Molecular Docking with Gaussian Boson Sampling
- Computational advantage of quantum random sampling
- Gaussian Boson Sampling using threshold detectors
- Applications of Near-Term Photonic Quantum Computers: Software and Algorithms
- Quantum Indistinguishability by Path Identity: The awakening of a sleeping beauty
- A quantum hardware-induced graph kernel based on Gaussian Boson Sampling
- Regimes of classical simulability for noisy Gaussian boson sampling
- Experimental Gaussian Boson Sampling
- Scalable squeezed light source for continuous variable quantum sampling
- Quantum Experiments and Graphs II: Quantum Interference, Computation and State Generation
- Solving Graph Problems Using Gaussian Boson Sampling
- A universal programmable Gaussian Boson Sampler for drug discovery
- Graph isomorphism and Gaussian boson sampling
- Point Processes with Gaussian Boson Sampling
- ON states as resource units for universal quantum computation with photonic architectures
- Quantum Algorithm for Simulating Molecular Vibrational Excitations
- Conditional non-Gaussian quantum state preparation
- Training Gaussian Boson Sampling Distributions
- Quantum Experiments and Hypergraphs: Multi-Photon Sources for Quantum Interference, Quantum Computation and Quantum Entanglement
- Simulability of Imperfect Gaussian and Superposition Boson Sampling
- Classical benchmarking of Gaussian Boson Sampling on the Titan supercomputer
- Non-linear Boson Sampling
- Microring resonator-coupled photoluminescence from silicon W~centers
- Implementing quantum algorithms on temporal photonic cluster states
- Experimental demonstration of Gaussian boson sampling with displacement
- Error mitigation on a near-term quantum photonic device
- Signatures of Many-Particle Interference
- Correcting finite squeezing errors in continuous-variable cluster states
- Graph Picture of Linear Quantum Networks and Entanglement
- Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
- Multimode Bogoliubov transformation and Husimi's Q-function
- Noise thresholds for classical simulability of non-linear Boson sampling
- Higher-order topological phase of interacting photon pairs
- Distinguishability in quantum interference with the squeezed states
- Unsupervised Event Classification with Graphs on Classical and Photonic Quantum Computers
- A Quadratic Speedup in the Optimization of Noisy Quantum Optical Circuits
- Linear multiport photonic interferometers: loss analysis of temporally-encoded architectures
- Holographic Gaussian Boson Sampling with Matrix Product States on 3D cQED Processors
- Sample efficient graph classification using binary Gaussian boson sampling
- Gaussian boson sampling at finite temperature
- Gaussian boson sampling with click-counting detectors
- A duality at the heart of Gaussian boson sampling
- Speedup in Classical Simulation of Gaussian Boson Sampling
- Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
- Nonnegativity for hafnians of certain matrices
- Quantum interference with time-frequency modes and multiple-photons generated by a silicon nitride microresonator
- Circumventing defective components in linear optical interferometers
- Classical modelling of a bosonic sampler with photon collisions
- Realistic photon-number resolution in Gaussian boson sampling
- Quantum Advantage with Timestamp Membosonsampling
- Computational indistinguishability and boson sampling