Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1304.4206 · Physical Review A

Inefficiency of classically simulating linear optical quantum computing with Fock-state inputs

Bryan Gard, Jonathan P. Olson, Robert M. Cross, Moochan B. Kim, Hwang Lee, Jonathan P. Dowling

Published Feb 18, 2014• 25 citations
arXivHTMLPDF

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\"odinger 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.

DOI
10.1103/physreva.89.022328

Related papers

Quantum computation with identical bosons

A. A. Архипов

We investigate the computational complexity of quantum computing with identical noninteracting bosons, such as that in a linear optical system.We explore the challenges in building devices that implement this model and in certifying their correctness.In work done with Scott Aaronson, we introduce BOSONSAMPLING, a computational model of quantum linear optics [1].We argue that the statistical distribution of outcomes cannot be reproduced by any classical device in a reasonable time span.This gives hands-on evidence of quantum advantage, that there are quantum phenomena are prohibitive to simulate in the classical world.Moreover, this quantum advantage is already present in limited optical systems, suggesting a lower bar to building devices that exhibit super-classical computation.We lay out the computational complexity argument for the classical difficulty of simulating BOSONSAM-PLING.An efficient classical simulation would have unlikely complexity consequences for the polynomial hierarchy PH.We look into the difficulties in proving an analogous approximate result, including the conjectures that seem to be needed to push it through.We then discuss experimental implementations of BOSONSAMPLING.The scalability of current implementations is limited by various sources of noise that accumulate as the problem size grows.We prove a result [51 that pertains to the inexactnesses of components that comprise the linear optical network, giving bounds on the tolerances that suffice to obtain an output distribution close to the ideal one.Finally, we look at the challenge of certifying a BOSONSAMPLING device.We show the impossibility of one technique, to use a submatrix whose permanent is so large that its corresponding outcome appears very frequently.Joint work with Aaronson [21 argues that the outputs of a BOSONSAMPLING device can be verified not to come from a uniform distribution.Results on the statistical bunching of bosons obtained with Kuperberg [61 are another approach to certification.We further present a novel certification technique based on classically estimating the distribution of integer combinations of the boson counts.

•Jan 1, 2017•0 citations

Simulation of quantum optics by coherent state decomposition

Jeffrey Marshall, Namit Anand

We introduce a framework for simulating quantum optics by decomposing the system into a finite rank (number of terms) superposition of coherent states. This allows us to define a resource theory, where linear optical operations are “free” (i.e., do not increase the rank), and the simulation complexity for an m -mode system scales quadratically in m , in stark contrast to the Hilbert space dimension. We outline this approach explicitly in the Fock basis, relevant in particular for Boson sampling, where the simulation time (space) complexity for computing output amplitudes, to arbitrary accuracy, scales as O ( m 2 2 n ) [ O ( m 2 n )] for n photons distributed among m modes. We additionally demonstrate that linear optical simulations with the n photons initially in the same mode scales efficiently, as O ( m 2 n ). This paradigm provides a practical notion of “non-classicality,” i.e., the classical resources required for simulation. Moreover, by making connections to the stellar rank formalism, we show this comes from two independent contributions, the number of single-photon additions and the amount of squeezing.

arXiv:2305.17099•Optica Quantum•Nov 27, 2023•23 citations

Classical Computers Very Likely Can Not Efficiently Simulate Multimode Linear Optical Interferometers with Arbitrary Fock-State Inputs-An Elementary Argument

Jonathan P. Dowling

Bulletin of the American Physical Society•Mar 6, 2014•1 citation

Error tolerance of the boson-sampling model for linear optics quantum computing

Peter P. Rohde, Timothy C. Ralph

Linear optics quantum computing is a promising approach to implementing scalable quantum computation. However, this approach has very demanding physical resource requirements. Recently, Aaronson and Arkhipov (e-print arXiv:1011.3245) showed that a simplified model, which avoids the requirement for fast feed-forward and postselection, while likely not capable of solving BQP-complete problems efficiently, can solve an interesting sampling problem believed to be classically hard. Loss and mode mismatch are the dominant sources of error in such systems. We provide evidence that even lossy systems or systems with mode mismatch are likely to be classically hard to solve. This is of practical interest to experimentalists wishing to demonstrate such systems since it suggests that, even with errors in their implementation, they are likely implementing an algorithm that is classically hard to solve. Our results also equivalently apply to the multiwalker quantum walk model.

arXiv:1111.2426•Physical Review A•Feb 23, 2012•81 citations

Classical Computers Can Not Efficiently Simulate Multimode Linear Optical Interferometers with Arbitrary Fock-State Inputs

Jonathan P. Dowling

Get PDF Email Share Share with Facebook Tweet This Post on reddit Share with LinkedIn Add to CiteULike Add to Mendeley Add to BibSonomy Get Citation Copy Citation Text J. P. Dowling, "Classical Computers Can Not Efficiently Simulate Multimode Linear Optical Interferometers with Arbitrary Fock-State Inputs," in The Rochester Conferences on Coherence and Quantum Optics and the Quantum Information and Measurement meeting, OSA Technical Digest (online) (Optica Publishing Group, 2013), paper W5B.1. Export Citation BibTex Endnote (RIS) HTML Plain Text Citation alert Save article

The Rochester Conferences on Coherence and Quantum Optics and the Quantum Information and Measurement meeting•Jan 1, 2013•0 citations

Evidence for the conjecture that sampling generalized cat states with linear optics is hard

Peter P. Rohde, Keith R. Motes, Paul Knott +3 more

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.

arXiv:1310.0297•Physical Review A•Jan 30, 2015•33 citations
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"odinger 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.
We investigate the computational complexity of quantum computing with identical noninteracting bosons, such as that in a linear optical system.We explore the challenges in building devices that implement this model and in certifying their correctness.In work done with Scott Aaronson, we introduce BOSONSAMPLING, a computational model of quantum linear optics [1].We argue that the statistical distribution of outcomes cannot be reproduced by any classical device in a reasonable time span.This gives hands-on evidence of quantum advantage, that there are quantum phenomena are prohibitive to simulate in the classical world.Moreover, this quantum advantage is already present in limited optical systems, suggesting a lower bar to building devices that exhibit super-classical computation.We lay out the computational complexity argument for the classical difficulty of simulating BOSONSAM-PLING.An efficient classical simulation would have unlikely complexity consequences for the polynomial hierarchy PH.We look into the difficulties in proving an analogous approximate result, including the conjectures that seem to be needed to push it through.We then discuss experimental implementations of BOSONSAMPLING.The scalability of current implementations is limited by various sources of noise that accumulate as the problem size grows.We prove a result [51 that pertains to the inexactnesses of components that comprise the linear optical network, giving bounds on the tolerances that suffice to obtain an output distribution close to the ideal one.Finally, we look at the challenge of certifying a BOSONSAMPLING device.We show the impossibility of one technique, to use a submatrix whose permanent is so large that its corresponding outcome appears very frequently.Joint work with Aaronson [21 argues that the outputs of a BOSONSAMPLING device can be verified not to come from a uniform distribution.Results on the statistical bunching of bosons obtained with Kuperberg [61 are another approach to certification.We further present a novel certification technique based on classically estimating the distribution of integer combinations of the boson counts.
We introduce a framework for simulating quantum optics by decomposing the system into a finite rank (number of terms) superposition of coherent states. This allows us to define a resource theory, where linear optical operations are “free” (i.e., do not increase the rank), and the simulation complexity for an m -mode system scales quadratically in m , in stark contrast to the Hilbert space dimension. We outline this approach explicitly in the Fock basis, relevant in particular for Boson sampling, where the simulation time (space) complexity for computing output amplitudes, to arbitrary accuracy, scales as O ( m 2 2 n ) [ O ( m 2 n )] for n photons distributed among m modes. We additionally demonstrate that linear optical simulations with the n photons initially in the same mode scales efficiently, as O ( m 2 n ). This paradigm provides a practical notion of “non-classicality,” i.e., the classical resources required for simulation. Moreover, by making connections to the stellar rank formalism, we show this comes from two independent contributions, the number of single-photon additions and the amount of squeezing.
Linear optics quantum computing is a promising approach to implementing scalable quantum computation. However, this approach has very demanding physical resource requirements. Recently, Aaronson and Arkhipov (e-print arXiv:1011.3245) showed that a simplified model, which avoids the requirement for fast feed-forward and postselection, while likely not capable of solving BQP-complete problems efficiently, can solve an interesting sampling problem believed to be classically hard. Loss and mode mismatch are the dominant sources of error in such systems. We provide evidence that even lossy systems or systems with mode mismatch are likely to be classically hard to solve. This is of practical interest to experimentalists wishing to demonstrate such systems since it suggests that, even with errors in their implementation, they are likely implementing an algorithm that is classically hard to solve. Our results also equivalently apply to the multiwalker quantum walk model.
Get PDF Email Share Share with Facebook Tweet This Post on reddit Share with LinkedIn Add to CiteULike Add to Mendeley Add to BibSonomy Get Citation Copy Citation Text J. P. Dowling, "Classical Computers Can Not Efficiently Simulate Multimode Linear Optical Interferometers with Arbitrary Fock-State Inputs," in The Rochester Conferences on Coherence and Quantum Optics and the Quantum Information and Measurement meeting, OSA Technical Digest (online) (Optica Publishing Group, 2013), paper W5B.1. Export Citation BibTex Endnote (RIS) HTML Plain Text Citation alert Save article
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.