Using Gaussian Boson Sampling to Find Dense Subgraphs
arXiv:1803.10730 · doi:10.1103/PhysRevLett.121.030503
Abstract
Boson sampling devices are a prime candidate for exhibiting quantum supremacy, yet their application for solving problems of practical interest is less well understood. Here we show that Gaussian boson sampling (GBS) can be used for dense subgraph identification. Focusing on the NP-hard densest k-subgraph problem, we find that stochastic algorithms are enhanced through GBS, which selects dense subgraphs with high probability. These findings rely on a link between graph density and the number of perfect matchings -- enumerated by the Hafnian -- which is the relevant quantity determining sampling probabilities in GBS. We test our findings by constructing GBS-enhanced versions of the random search and simulated annealing algorithms and apply them through numerical simulations of GBS to identify the densest subgraph of a 30 vertex graph.
6 pages, 4 figures
References in corpus (11)
- Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
- Probing many-body dynamics on a 51-atom quantum simulator
- Observation of a Many-Body Dynamical Phase Transition with a 53-Qubit Quantum Simulator
- Photonic Boson Sampling in a Tunable Circuit
- Gaussian Boson Sampling
- Experimental Realization of Quantum Artificial Intelligence
- Experimental Scattershot Boson Sampling
- Unsupervised Machine Learning on a Hybrid Quantum Computer
- No imminent quantum supremacy by boson sampling
- Quantum approximate optimization with Gaussian boson sampling
- Towards Quantum Supremacy with Lossy Scattershot Boson Sampling
Cited by in corpus (70)
- Quantum computational advantage using photons
- Noisy intermediate-scale quantum (NISQ) algorithms
- Quantum circuits with many photons on a programmable nanophotonic chip
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- Intelligent Computing: The Latest Advances, Challenges and Future
- Generation and sampling of quantum states of light in a silicon chip
- 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
- Squeezed light from a nanophotonic molecule
- Noisy intermediate-scale quantum computers
- 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
- Regimes of classical simulability for noisy Gaussian boson sampling
- Experimental Gaussian Boson Sampling
- Simulating realistic non-Gaussian state preparation
- NISQ Computers: A Path to Quantum Supremacy
- Scalable squeezed light source for continuous variable quantum sampling
- Quantum approximate optimization with Gaussian boson sampling
- Solving Graph Problems Using Gaussian Boson Sampling
- Exact simulation of Gaussian Boson Sampling in polynomial space and exponential time
- Scalable and Programmable Phononic Network with Trapped Ions
- Building a large-scale quantum computer with continuous-variable optical technologies
- A universal programmable Gaussian Boson Sampler for drug discovery
- Reconfigurable continuously-coupled 3D photonic circuit for Boson Sampling experiments
- Point Processes with Gaussian Boson Sampling
- The Complexity of Bipartite Gaussian Boson Sampling
- Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
- A Survey on the Densest Subgraph Problem and Its Variants
- Quantum Algorithm for Simulating Molecular Vibrational Excitations
- Benchmarking of Gaussian boson sampling using two-point correlators
- Training Gaussian Boson Sampling Distributions
- Quantum machine learning with Adaptive Boson Sampling via post-selection
- Degenerate Squeezing in Waveguides: A Unified Theoretical Approach
- Non-linear Boson Sampling
- Classical benchmarking of Gaussian Boson Sampling on the Titan supercomputer
- Information processing at the speed of light
- Experimental demonstration of Gaussian boson sampling with displacement
- Error mitigation on a near-term quantum photonic device
- Signatures of Many-Particle Interference
- Continuous-variable quantum approximate optimization on a programmable photonic quantum processor
- Graph Picture of Linear Quantum Networks and Entanglement
- Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
- Certification of Gaussian Boson Sampling via graph theory
- Distinguishability in quantum interference with the squeezed states
- Gaussian boson sampling with partial distinguishability
- Sample caching Markov chain Monte Carlo approach to boson sampling simulation
- A Quadratic Speedup in the Optimization of Noisy Quantum Optical Circuits
- Linear multiport photonic interferometers: loss analysis of temporally-encoded architectures
- The First Hardware Demonstration of a Universal Programmable RRAM-based Probabilistic Computer for Molecular Docking
- Sample efficient graph classification using binary Gaussian boson sampling
- Boson sampling enhanced quantum chemistry
- Extending the Q-score to an Application-level Quantum Metric Framework
- Gaussian boson sampling at finite temperature
- Gaussian boson sampling with click-counting detectors
- Validation of a noisy Gaussian boson sampler via graph theory
- A duality at the heart of Gaussian boson sampling
- Quantum interference with time-frequency modes and multiple-photons generated by a silicon nitride microresonator
- Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
- Unified boson sampling
- Speedup in Classical Simulation of Gaussian Boson Sampling
- Circumventing defective components in linear optical interferometers
- Entropy density benchmarking of near-term quantum circuits
- Computational indistinguishability and boson sampling
- Quantum community detection via deterministic elimination
- Quantum Advantage with Timestamp Membosonsampling
- Efficient Quantum Circuit Simulation by Tensor Network Methods on Modern GPUs
- Realistic photon-number resolution in Gaussian boson sampling
- Optical Quantum Computing