Inefficiency of classically simulating linear optical quantum computing with Fock-state inputs
arXiv:1304.4206 · doi:10.1103/PhysRevA.89.022328
Abstract
Aaronson and Arkhipov recently used computational complexity theory to argue that classical computers very likely cannot efficiently simulate linear, multimode, quantum-optical interferometers with arbitrary Fock-state inputs [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013)]. Here we present an elementary argument that utilizes only techniques from quantum optics. We explicitly construct the Hilbert space for such an interferometer and show that its dimension scales exponentially with all the physical resources. We also show in a simple example just how the Schrödinger and Heisenberg pictures of quantum theory, while mathematically equivalent, are not in general computationally equivalent. Finally, we conclude our argument by comparing the symmetry requirements of multiparticle bosonic to fermionic interferometers and, using simple physical reasoning, connect the nonsimulatability of the bosonic device to the complexity of computing the permanent of a large matrix.
arXiv comment7 pages, 1 figure Published in PRA Phys. Rev. A 89, 022328 (2014)
References in corpus (16)
- Engineered 2D Ising interactions on a trapped-ion quantum simulator with hundreds of spins
- Boson Sampling on a Photonic Chip
- Experimental Boson Sampling
- Experimental boson sampling in arbitrary integrated photonic circuits
- Photonic Boson Sampling in a Tunable Circuit
- Efficient Classical Simulation of Continuous Variable Quantum Information Processes
- Optical Simulation of Quantum Logic
- Entangled Fock states for Robust Quantum Optical Metrology, Imaging, and Sensing
- Quantum quincunx in cavity quantum electrodynamics
- Quantum interference and manipulation of entanglement in silicon wire waveguide quantum circuits
- Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation
- Counting Statistics of Many-Particle Quantum Walks
- Strong Violations of Bell-type Inequalities for Path-Entangled Number States
- Towards photostatistics from photon-number discriminating detectors
- Conditional linear-optical measurement schemes generate effective photon nonlinearities
- Nonexistence of Entanglement Sudden Death in High NOON States
Cited by in corpus (11)
- Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
- Linear Optical Quantum Metrology with Single Photons: Exploiting Spontaneously Generated Entanglement to Beat the Shot-Noise Limit
- Interference of Identical Particles from Entanglement to Boson-Sampling
- 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
- Linear optical quantum metrology with single photons --- Experimental errors, resource counting, and quantum Cramér-Rao bounds
- Sampling of bosonic qubits
- Artificial coherent states of light by multi-photon interference in a single-photon stream
- The scaling of boson sampling experiments
- A nonlocal ontology underlying the time-symmetric Heisenberg representation
- Boson sampling with ultracold atoms in a programmable optical lattice
- Encoding strongly-correlated many-boson wavefunctions on a photonic quantum computer: application to the attractive Bose-Hubbard model