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.
v6: fixed missing equation numbers
References in corpus (21)
- Photonic Boson Sampling in a Tunable Circuit
- Experimental demonstration of a BDCZ quantum repeater node
- Quantum Beat of Two Single Photons
- Experimental Scattershot Boson Sampling
- Efficient and long-lived quantum memory with cold atoms inside a ring cavity
- 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
- Multiboson Correlation Interferometry with arbitrary single-photon pure states
- Entangling Color-Different Photons via Time-Resolved Measurement and Active Feed-Forward
- 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
- 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
- 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 (29)
- Quantum Sampling Problems, BosonSampling and Quantum Supremacy
- A detailed study of Gaussian Boson Sampling
- 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
- Multipath Correlation Interference and Controlled-NOT Gate Simulation with a Thermal Source
- NonClassicality Criteria in Multiport Interferometry
- Symmetries and entanglement features of inner-mode resolved correlations of interfering nonidentical photons
- Characterization of two distant double-slits by chaotic light second-order interference
- Spatial interference between pairs of disjoint optical paths with a single chaotic source
- Estimation with ultimate quantum precision of the transverse displacement between two photons via two-photon interference sampling measurements
- From Many-Particle Interference to Correlation Spectroscopy
- 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
- The physics of thermal light second-order interference beyond coherence
- Experimental linear optical computing of the matrix permanent
- Boson sampling with random numbers of photons
- 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
- 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