Most proposed applications of boson samplers, including photonic machine-learning models, do not use the samples themselves but estimates of output probabilities, marginals or overlaps, obtained to additive precision from a finite number of shots. For product inputs such as single photons, these quantities can already be estimated classically with Gurvits's algorithm and its generalisations. We ask whether entangled inputs change this picture. For any
n-photon input that is a matrix-product state of bond dimension
χ, with one photon per site and
L modes per site, we give an unbiased estimator of any output amplitude of an
m-mode interferometer, whose mean-square error after
N draws is at most
∥ψ∥2/N whatever the interferometer, the output pattern and the entanglement of the state. Each draw costs
O(nLχ2+nL3+mn) operations after
O(nLχ3) preprocessing, and an additive error
ε with probability at least
1−δ requires
O(∥ψ∥2ε−2log(1/δ)) draws, with memory of the order of the input size. The main application is to light emitted sequentially by quantum emitters, such as spin-based sources of photonic cluster states, for which
χ is bounded by the dimension of the source's retained quantum memory: one spin gives
χ=2 at any length, and a memory of
k qubits, held in emitters or in photons stored in a delay line, gives
χ≤2k, so the cost stays polynomial as long as
k=O(logn). The same sampler also estimates traced-memory probabilities, overlaps and individual marginal probabilities. All guarantees are additive: the estimator gives neither relative estimates of exponentially small probabilities nor a sampler of the output distribution.
We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum computation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions. Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then P^#P=BPP^NP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation. Our main result suggests that even an approximate or noisy classical simulation would already imply a collapse of the polynomial hierarchy. For this, we need two unproven conjectures: the "Permanent-of-Gaussians Conjecture", which says that it is #P-hard to approximate the permanent of a matrix A of independent N(0,1) Gaussian entries, with high probability over A; and the "Permanent Anti-Concentration Conjecture", which says that |Per(A)|>=sqrt(n!)/poly(n) with high probability over A. We present evidence for these conjectures, both of which seem interesting even apart from our application. This paper does not assume knowledge of quantum optics. Indeed, part of its goal is to develop the beautiful theory of noninteracting bosons underlying our model, and its connection to the permanent function, in a self-contained way accessible to theoretical computer scientists.
Abstract Programmable linear optical interferometers are promising for classical and quantum applications. Their integrated design makes it possible to create more scalable and stable devices. To use them in practice, one has to reconstruct the whole device model taking the manufacturing errors into account. The inability to address individual interferometer elements complicates the reconstruction problem. A naive approach is to train the model via some complex optimization procedure. A faster optimization-free algorithm has been recently proposed (Bantysh et al 2023 Opt. Express 31 16729–42). However, it requires the full transfer matrix tomography while a more practical setup measures only the fields intensities at the interferometer output. In this paper, we propose the modification of the fast algorithm, which uses additional set of interferometer configurations in order to reconstruct the model in the case of intensity-only measurements. We show that it performs slightly worse than the original fast algorithm but it is more practical and still does not require intensive numerical optimization.
Multimode optical interferometers represent the most viable platforms for the successful implementation of several quantum information schemes that take advantage of optical processing. Examples range from quantum communication and sensing, to computation, including optical neural networks, optical reservoir computing, or simulation of complex physical systems. The realization of such routines requires high levels of control and tunability of the parameters that define the operations carried out by the device. This requirement becomes particularly crucial in light of recent technological improvements in integrated photonic technologies, which enable the implementation of progressively larger circuits embedding a considerable amount of tunable parameters. We formulate efficient procedures for the characterization of optical circuits in the presence of imperfections that typically occur in physical experiments, such as unbalanced losses and phase instabilities in the input and output collection stages. The algorithm aims at reconstructing the transfer matrix that represents the optical interferometer without making any strong assumptions about its internal structure and encoding. We show the viability of this approach in an experimentally relevant scenario, defined by a tunable integrated photonic circuit, and we demonstrate the effectiveness and robustness of our method. Our findings can find application in a wide range of optical setups, based on both bulk and integrated configurations.
The connection between the boson sampling problem in a linear optical interferometer with single photon sources and the computation of matrix permanents has recently brought a strong interest for quantum computing applications. In this work we explore the physics of N-order interference in terms of N-order correlation functions in a generic linear optical interferometer with both Fock states sources and thermal sources. We will show how also in this case the connection of such a problem with matrix permanents play a fundamental role.
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