Boson sampling with Gaussian measurements
arXiv:1705.05299 · doi:10.1103/PhysRevA.96.032326
Abstract
We develop an alternative boson sampling model operating on single-photon states followed by linear interferometry and Gaussian measurements. The hardness proof for simulating such continuous-variable measurements is established in two main steps, making use of the symmetry of quantum evolution under time reversal. Namely, we first construct a twofold version of scattershot boson sampling in which, as opposed to the original proposal, both legs of a collection of two-mode squeezed vacuum states undergo parallel linear-optical transformations. This twofold scattershot model yields, as a corollary, an instance of boson sampling from Gaussian states where photon counting is hard to simulate. Then, a time-reversed setup is used to exhibit a boson sampling model in which the simulation of Gaussian measurements -- namely the outcome of eight-port homodyne detection -- is proven to be computationally hard. These results illustrate how the symmetry of quantum evolution under time reversal may serve as a tool for analyzing the computational complexity of novel physically-motivated computational problems.
8 pages, 3 figures. Updated version for publication
References in corpus (10)
- Photonic Boson Sampling in a Tunable Circuit
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- What can quantum optics say about computational complexity theory?
- Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation
- Continuous-Variable Instantaneous Quantum Computing is hard to sample
- Polynomial approximation of non-Gaussian unitaries by counting one photon at a time
- Gaussian Noise Sensitivity and BosonSampling
- Characterizing Quantum Properties of a Measurement Apparatus: Insights from the Retrodictive Approach
- Exact Boson Sampling using Gaussian continuous variable measurements
- Reconfigurable Optical Quantum Networks Using Multimode Quantum Frequency Combs and Pulse Shaping
Cited by in corpus (38)
- Photonic quantum information processing: a review
- Strawberry Fields: A Software Platform for Photonic Quantum Computing
- Resource theory of quantum non-Gaussianity and Wigner negativity
- A detailed study of Gaussian Boson Sampling
- Computational advantage of quantum random sampling
- Simulating boson sampling in lossy architectures
- Universal Gate Set for Continuous-Variable Quantum Computation with Microwave Circuits
- Resources for bosonic quantum computational advantage
- Exact simulation of Gaussian Boson Sampling in polynomial space and exponential time
- Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
- The Complexity of Bipartite Gaussian Boson Sampling
- Quantum Entropy and Central Limit Theorem
- Proposal for Quantum Simulation via All-Optically Generated Tensor Network States
- Benchmarking of Gaussian boson sampling using two-point correlators
- Contextuality and Wigner negativity are equivalent for continuous-variable quantum measurements
- Classical simulation of Gaussian quantum circuits with non-Gaussian input states
- Efficient verification of Boson Sampling
- Simulability of Imperfect Gaussian and Superposition Boson Sampling
- Simulating lossy Gaussian boson sampling with matrix product operators
- Holomorphic representation of quantum computations
- Signatures of Many-Particle Interference
- Quantum state engineering by non-deterministic noiseless linear amplification
- Quantum-inspired permanent identities
- Complexity of Fermionic Dissipative Interactions and Applications to Quantum Computing
- Simulating arbitrary Gaussian circuits with linear optics
- From the Bloch sphere to phase space representations with the Gottesman-Kitaev-Preskill encoding
- Efficient validation of Boson Sampling from binned photon-number distributions
- Digital homodyne and heterodyne detection for stationary bosonic modes
- Multiphoton Correlations between Quantum Images
- Boson sampling enhanced quantum chemistry
- Continuous Variable Quantum Advantages and Applications in Quantum Optics
- Gaussian boson sampling with click-counting detectors
- Bosonic randomized benchmarking with passive transformations
- Sampling and the complexity of nature
- Complexity of Gaussian quantum optics with a limited number of non-linearities
- Resourcefulness of non-classical continuous-variable quantum gates
- Classical algorithms for measurement-adaptive Gaussian circuits
- The Interplay between Quantum Contextuality and Wigner Negativity