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

IEEE International Conference on Quantum Computing and Engineering (QCE)

Simulation of Linear Optical Interferometers (Extended Abstract)

Nicolas Heurtel, Shane Mansfield, Jean Sénellart, Benoît Valiron

Published Sep 1, 2022• 1 citation
Publisher

Abstract

We propose an algorithm to compute the full output distribution of photons passing through linear optical interferometers. More precisely, given n photons at the input of an m-mode interferometer, the proposed algorithm computes the probabilities of all the $\binom{n + m - 1}{m - 1}$ possible output states in a linear time complexity of $O\left( {n\binom{n + m - 1}{m - 1}} \right)$, outperforming the naive method – computing one permanent for each state – by an exponential factor. The benchmarking has been carried out on a quantum machine learning use-case, to both illustrate the gain and give one possible application. Finally, as storing all the probabilities requires a memory space that is exponential in n and m, we discuss and give strong evidence that memory is far more limiting than the time for the computation of the full distribution.

DOI
10.1109/qce53715.2022.00080

Related papers

On the estimation of linear-optical amplitudes and probabilities with entangled input state

Jean Sénellart, Pierre-Emmanuel Emeriau

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+nL^3+mn)$ operations after $O(nLχ^3)$ preprocessing, and an additive error $\varepsilon$ with probability at least $1-δ$ requires $O(\|ψ\|^2\varepsilon^{-2}\log(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 $χ\le2^k$, so the cost stays polynomial as long as $k=O(\log n)$. 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.

arXiv:2611.10500•Nov 7, 2026•1 citation

The Computational Complexity of Linear Optics

Scott Aaronson, Arkhipov, Alex

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.

arXiv:1011.3245•Electronic colloquium on computational complexity•Jan 25, 2010•191 citations

Fast reconstruction of programmable interferometers with intensity-only measurements

B. I. Bantysh, Andrey Yu. Chernyavskiy, Suren A. Fldzhyan +1 more

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.

arXiv:2401.06093•Laser Physics Letters•Dec 12, 2023•6 citations

Characterization of multimode linear optical networks

Francesco Hoch, Taira Giordani, Nicolò Spagnolo +3 more

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.

arXiv:2304.06486•Advanced Photonics Nexus•Jan 3, 2023•17 citations

Correlation functions and matrix permanents

Vincenzo Tamma, Florian Nägele

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.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Sep 26, 2013•4 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
We propose an algorithm to compute the full output distribution of photons passing through linear optical interferometers. More precisely, given n photons at the input of an m-mode interferometer, the proposed algorithm computes the probabilities of all the (n+m−1m−1)\binom{n + m - 1}{m - 1}(m−1n+m−1​) possible output states in a linear time complexity of O(n(n+m−1m−1))O\left( {n\binom{n + m - 1}{m - 1}} \right)O(n(m−1n+m−1​)), outperforming the naive method – computing one permanent for each state – by an exponential factor. The benchmarking has been carried out on a quantum machine learning use-case, to both illustrate the gain and give one possible application. Finally, as storing all the probabilities requires a memory space that is exponential in n and m, we discuss and give strong evidence that memory is far more limiting than the time for the computation of the full distribution.
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 nnn-photon input that is a matrix-product state of bond dimension χχχ, with one photon per site and LLL modes per site, we give an unbiased estimator of any output amplitude of an mmm-mode interferometer, whose mean-square error after NNN draws is at most ∥ψ∥2/N\|ψ\|^2/N∥ψ∥2/N whatever the interferometer, the output pattern and the entanglement of the state. Each draw costs O(nLχ2+nL3+mn)O(nLχ^2+nL^3+mn)O(nLχ2+nL3+mn) operations after O(nLχ3)O(nLχ^3)O(nLχ3) preprocessing, and an additive error ε\varepsilonε with probability at least 1−δ1-δ1−δ requires O(∥ψ∥2ε−2log⁡(1/δ))O(\|ψ\|^2\varepsilon^{-2}\log(1/δ))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χ=2χ=2 at any length, and a memory of kkk qubits, held in emitters or in photons stored in a delay line, gives χ≤2kχ\le2^kχ≤2k, so the cost stays polynomial as long as k=O(log⁡n)k=O(\log n)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