From the Physics to the Computational Complexity of Multiboson Correlation Interference
arXiv:1507.01541 · doi:10.1103/PhysRevLett.115.243605
Abstract
We demonstrate how the physics of multiboson correlation interference leads to the computational complexity of linear optical interferometers based on correlation measurements in the degrees of freedom of the input bosons. In particular, we address the task of MultiBoson Correlation Sampling (MBCS) from the probability distribution associated with polarization- and time-resolved detections at the output of random linear optical networks. We show that the MBCS problem is fundamentally hard to solve classically even for nonidentical input photons, regardless of the color of the photons, making it also very appealing from an experimental point of view. These results fully manifest the quantum computational supremacy inherent to the fundamental nature of quantum interference.
arXiv commentv6: fixed missing equation numbers
References in corpus (37)
- Multi-photon entanglement and interferometry
- Observation of three-photon Greenberger-Horne-Zeilinger entanglement
- Boson Sampling on a Photonic Chip
- Experimental Boson Sampling
- Experimental boson sampling in arbitrary integrated photonic circuits
- Photonic Boson Sampling in a Tunable Circuit
- Experimental demonstration of a BDCZ quantum repeater node
- Observation of eight-photon entanglement
- Efficient experimental validation of photonic boson sampling against the uniform distribution
- Boson Sampling from Gaussian States
- Quantum Beat of Two Single Photons
- Experimental Scattershot Boson Sampling
- Efficient and long-lived quantum memory with cold atoms inside a ring cavity
- Hong-Ou-Mandel atom interferometry in tunnel-coupled optical tweezers
- On the experimental verification of quantum complexity in linear optics
- Electro-Optic Modulation of Single Photons
- An atomic Hong-Ou-Mandel experiment
- Multi-photon quantum interference in a multi-port integrated photonic device
- Linear Optical Quantum Metrology with Single Photons: Exploiting Spontaneously Generated Entanglement to Beat the Shot-Noise Limit
- Generalized multi-photon quantum interference
- Scalable Implementation of Boson Sampling with Trapped Ions
- Multiboson Correlation Interferometry with arbitrary single-photon pure states
- Photonic qubits, qutrits and ququads accurately prepared and delivered on demand
- Entangling Color-Different Photons via Time-Resolved Measurement and Active Feed-Forward
- Synchronized Independent Narrow-band Single Photons and Efficient Generation of Photonic Entanglement
- Sampling arbitrary photon-added or photon-subtracted squeezed states is in the same complexity class as boson sampling
- Observation of detection-dependent multi-photon coherence times
- Multi-Boson Correlation Sampling with Multi-mode Thermal Sources
- Multiparticle correlations in mesoscopic scattering: boson sampling, birthday paradox, and Hong-Ou-Mandel profiles
- Factoring numbers with a single interferogram
- Multi-Boson Correlation Sampling
- Multipath Correlation Interference and Controlled-NOT Gate Simulation with a Thermal Source
- Sampling of bosonic qubits
- New factorization algorithm based on a continuous representation of truncated Gauss sums
- Boson sampling with non-identical single photons
- Analogue algorithm for parallel factorization of an exponential number of large integers II. Optical implementation
- Analogue algorithm for parallel factorization of an exponential number of large integers I. Theoretical description
Cited by in corpus (30)
- Quantum Sampling Problems, BosonSampling and Quantum Supremacy
- A detailed study of Gaussian Boson Sampling
- A Statistical Benchmark for BosonSampling
- Interference of Temporally Distinguishable Photons Using Frequency-Resolved Detection
- Interfering distinguishable photons
- Time-resolved boson sampling with photons of different colors
- Classically simulating near-term partially-distinguishable and lossy boson sampling
- Ultimate quantum sensitivity in the estimation of the delay between two interfering photons through frequency-resolving sampling
- Multi-Boson Correlation Sampling
- Wave-particle duality of many-body quantum states
- NonClassicality Criteria in Multiport Interferometry
- Multipath Correlation Interference and Controlled-NOT Gate Simulation with a Thermal Source
- Symmetries and entanglement features of inner-mode resolved correlations of interfering nonidentical photons
- Spatial interference between pairs of disjoint optical paths with a single chaotic source
- Characterization of two distant double-slits by chaotic light second-order interference
- From Many-Particle Interference to Correlation Spectroscopy
- Estimation with ultimate quantum precision of the transverse displacement between two photons via two-photon interference sampling measurements
- Hectometer Revivals of Quantum Interference
- Scattershot multiboson correlation sampling with random photonic inner-mode multiplexing
- Distance sensing emerging from second-order interference of thermal light
- Analogue algorithm for parallel factorization of an exponential number of large integers I. Theoretical description
- Multi-photon interference in the spectral domain by direct heralding of superposition states
- Multi-parameter estimation of the state of two interfering photonic qubits
- Experimental linear optical computing of the matrix permanent
- The physics of thermal light second-order interference beyond coherence
- All-order momentum correlations of three ultracold bosonic atoms confined in triple-well traps: Signatures of emergent many-body quantum phase transitions and analogies with three-photon quantum-optics interference
- Boson sampling with random numbers of photons
- Which role does multiphoton interference play in small phase estimation in quantum Fourier transform interferometers?
- Quantum De Moivre-Laplace theorem for noninteracting indistinguishable particles
- Optical nonclassicality test based on third-order intensity correlations