Open AccessEquivalence between spin Hamiltonians and boson sampling
Author(s) -
Borja Peropadre,
Alán AspuruGuzik,
Juan José GarcíaRipoll
Publication year - 2017
Publication title -
physical review. a/physical review, a
Language(s) - English
Resource type - Journals
eISSN - 2469-9934
pISSN - 2469-9926
DOI - 10.1103/physreva.95.032327
Subject(s) - spins , boson , physics , equivalence (formal languages) , quantum , quantum mechanics , spin (aerodynamics) , sampling (signal processing) , theoretical physics , statistical physics , mathematics , condensed matter physics , discrete mathematics , thermodynamics , detector , optics
8 pags., 3 figs., 3 apps.Aaronson and Arkhipov showed that predicting or reproducing the measurement statistics of a general linear optics circuit with a single Fock-state input is a classically hard problem. Here we show that this problem, known as boson sampling, is as hard as simulating the short time evolution of a large but simple spin model with long-range XY interactions. The conditions for this equivalence are the same for efficient boson sampling, namely, having a small number of photons (excitations) as compared to the number of modes (spins). This mapping allows efficient implementations of boson sampling in small quantum computers and simulators and sheds light on the complexity of time evolution with critical spin models.B.P. and A.A.-G. acknowledge the Air Force Office of Scientific\udResearch for support under Award No. FA9550-12-1-\ud0046. A.A.-G. acknowledges the Army Research Office under\udAward No. W911NF-15-1-0256 and the Vannevar Bush Faculty\udFellowship under Award No. N00014-16-1-2008. J.J.G.R.\udacknowledges support from the Spanish MINECO/FEDER\udProject No. FIS2012-33022 and CAM PRICYT Project No.\udQUITEMAD+S2013/ICE-2801.Peer Reviewe