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
arXiv:1402.0531 · doi:10.1103/PhysRevA.91.022334
Abstract
Boson sampling is a specific quantum computation, which is likely hard to implement efficiently on a classical computer. The task is to sample the output photon number distribution of a linear optical interferometric network, which is fed with single-photon Fock state inputs. A question that has been asked is if the sampling problems associated with any other input quantum states of light (other than the Fock states) to a linear optical network and suitable output detection strategies are also of similar computational complexity as boson sampling. We consider the states that differ from the Fock states by a displacement operation, namely the displaced Fock states and the photon-added coherent states. It is easy to show that the sampling problem associated with displaced single-photon Fock states and a displaced photon number detection scheme is in the same complexity class as boson sampling for all values of displacement. On the other hand, we show that the sampling problem associated with single-photon-added coherent states and the same displaced photon number detection scheme demonstrates a computational complexity transition. It transitions from being just as hard as boson sampling when the input coherent amplitudes are sufficiently small, to a classically simulatable problem in the limit of large coherent amplitudes.
arXiv comment7 pages, 3 figures; published version
References in corpus (22)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Boson Sampling on a Photonic Chip
- Experimental Boson Sampling
- Experimental boson sampling in arbitrary integrated photonic circuits
- Photonic Boson Sampling in a Tunable Circuit
- Quantum Nonlocality in Phase Space
- Efficient experimental validation of photonic boson sampling against the uniform distribution
- Boson Sampling from Gaussian States
- On the experimental verification of quantum complexity in linear optics
- Single-photon excitation of a coherent state: catching the elementary step of stimulated light emission
- Scalable boson-sampling with time-bin encoding using a loop-based architecture
- Stringent and efficient assessment of Boson-Sampling devices
- Partial indistinguishability theory for multi-photon experiments in multiport devices
- Scalable Implementation of Boson Sampling with Trapped Ions
- Photon-added state preparation via conditional measurement on a beam splitter
- Sufficient bound on the mode mismatch of single photons for scalability of the boson sampling computer
- Strong Violations of Bell-type Inequalities for Path-Entangled Number States
- Mixing nonclassical pure states in a linear-optical network almost always generates modal entanglement
- Spontaneous parametric down-conversion photon sources are scalable in the asymptotic limit for boson-sampling
- Boson-sampling with photons of arbitrary spectral structure
- Sampling generalized cat states with linear optics is probably hard
- Inefficiency of classically simulating linear optical quantum computing with Fock-state inputs
Cited by in corpus (26)
- Quantum Chemistry in the Age of Quantum Computing
- Gaussian Boson Sampling
- Experimental Scattershot Boson Sampling
- A detailed study of Gaussian Boson Sampling
- Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
- Vibronic Boson Sampling: Generalized Gaussian Boson Sampling for Molecular Vibronic Spectra at Finite Temperature
- Continuous-Variable Instantaneous Quantum Computing is hard to sample
- A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer
- Microwave Boson Sampling
- Dynamical phase transitions in sampling complexity
- Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
- Experimental generalized quantum suppression law in Sylvester interferometers
- Impact of photon addition and subtraction on nonclassical and phase properties of a displaced Fock state
- Implementing Scalable Boson Sampling with Time-Bin Encoding: Analysis of Loss, Mode Mismatch, and Time Jitter
- Generating photon-added states without adding a photon
- Experimental demonstration of Gaussian boson sampling with displacement
- Boson sampling with non-identical single photons
- Proof-of-work consensus by quantum sampling
- Exact sampling hardness of Ising spin models
- Noise thresholds for classical simulability of non-linear Boson sampling
- Nonclassicalities of hybrid coherent states
- Decoherence and Interferometric Sensitivity of BosonSampling in Superconducting Networks
- Sample caching Markov chain Monte Carlo approach to boson sampling simulation
- Distinguishability Transitions in Non-Unitary Boson Sampling Dynamics
- Gaussian boson sampling with click-counting detectors
- An investigation on the nonclassical and quantum phase properties of a family of engineered quantum states