Quantum approximate optimization with Gaussian boson sampling
arXiv:1803.10731 · doi:10.1103/PhysRevA.98.012322
Abstract
Hard optimization problems are often approached by finding approximate solutions. Here, we highlight the concept of proportional sampling and discuss how it can be used to improve the performance of stochastic algorithms for optimization. We introduce an NP-Hard problem called Max-Haf and show that Gaussian boson sampling (GBS) can be used to enhance any stochastic algorithm for this problem. These results are applied by enhancing the random search, simulated annealing, and greedy algorithms. With numerical simulations, we confirm that all algorithms are improved when employing GBS, and that GBS-enhanced random search performs the best despite being the one with the simplest underlying classical routine.
12 pages, 6 figures
References in corpus (9)
- Quantum Computational Supremacy
- Photonic Boson Sampling in a Tunable Circuit
- Gaussian Boson Sampling
- Experimental Scattershot Boson Sampling
- Using Gaussian Boson Sampling to Find Dense Subgraphs
- Architectures for quantum simulation showing a quantum speedup
- Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
- Continuous-Variable Instantaneous Quantum Computing is hard to sample
- Towards Quantum Supremacy with Lossy Scattershot Boson Sampling
Cited by in corpus (33)
- Noisy intermediate-scale quantum (NISQ) algorithms
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- Molecular Docking with Gaussian Boson Sampling
- Computational advantage of quantum random sampling
- Using Gaussian Boson Sampling to Find Dense Subgraphs
- Gaussian Boson Sampling using threshold detectors
- Applications of Near-Term Photonic Quantum Computers: Software and Algorithms
- Experimental 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
- Reconfigurable continuously-coupled 3D photonic circuit for Boson Sampling experiments
- Point Processes with Gaussian Boson Sampling
- Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
- Benchmarking of Gaussian boson sampling using two-point correlators
- Training Gaussian Boson Sampling Distributions
- Simulating Chemistry on Bosonic Quantum Devices
- Degenerate Squeezing in Waveguides: A Unified Theoretical Approach
- Classical benchmarking of Gaussian Boson Sampling on the Titan supercomputer
- Non-linear Boson Sampling
- Signatures of Many-Particle Interference
- Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
- Certification of Gaussian Boson Sampling via graph theory
- 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
- Transition of Anticoncentration in Gaussian Boson Sampling
- Quantum interference with time-frequency modes and multiple-photons generated by a silicon nitride microresonator
- Circumventing defective components in linear optical interferometers
- Sampling and the complexity of nature
- Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
- Realistic photon-number resolution in Gaussian boson sampling
- Generalized Interference of Fermions and Bosons