Sampling generalized cat states with linear optics is probably hard
arXiv:1310.0297 · doi:10.1103/PhysRevA.91.012342
Abstract
Boson-sampling has been presented as a simplified model for linear optical quantum computing. In the boson-sampling model, Fock states are passed through a linear optics network and sampled via number-resolved photodetection. It has been shown that this sampling problem likely cannot be efficiently classically simulated. This raises the question as to whether there are other quantum states of light for which the equivalent sampling problem is also computationally hard. We present evidence, without using a full complexity proof, that a very broad class of quantum states of light --- arbitrary superpositions of two or more coherent states --- when evolved via passive linear optics and sampled with number-resolved photodetection, likely implements a classically hard sampling problem.
8 pages, 2 figures
References in corpus (6)
- Photonic Boson Sampling in a Tunable Circuit
- Boson Sampling from Gaussian States
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Multi-photon quantum interference in a multi-port integrated photonic device
- On the hardness of classically simulating the one clean qubit model
- Mixing nonclassical pure states in a linear-optical network almost always generates modal entanglement
Cited by in corpus (20)
- Gaussian Boson Sampling
- Efficient experimental validation of photonic boson sampling against the uniform distribution
- Experimental Scattershot Boson Sampling
- A detailed study of Gaussian Boson Sampling
- Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
- Interference of Identical Particles from Entanglement to Boson-Sampling
- Vibronic Boson Sampling: Generalized Gaussian Boson Sampling for Molecular Vibronic Spectra at Finite Temperature
- A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer
- Sampling arbitrary photon-added or photon-subtracted squeezed states is in the same complexity class as boson sampling
- Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
- Experimental generalized quantum suppression law in Sylvester interferometers
- Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states---The quantum-classical divide and computational-complexity transitions in linear optics
- Multiparticle correlations in mesoscopic scattering: boson sampling, birthday paradox, and Hong-Ou-Mandel profiles
- Practical quantum somewhat-homomorphic encryption with coherent states
- Boson sampling with non-identical single photons
- Implementing Scalable Boson Sampling with Time-Bin Encoding: Analysis of Loss, Mode Mismatch, and Time Jitter
- Quantum-inspired permanent identities
- Classical verification of quantum circuits containing few basis changes
- Noise thresholds for classical simulability of non-linear Boson sampling
- Quantum suppression law in a 3-D photonic chip implementing the Fast Fourier Transform