Strong Simulation of Linear Optical Processes

Abstract

In this paper, we provide an algorithm and general framework for the simulation of photons passing through linear optical interferometers. Given $n$ photons at the input of an $m$-mode interferometer, our algorithm computes the probabilities of all possible output states with time complexity $O\left(n\left(\genfrac{}{}{0ex}{}{n+m-1}{m-1}\right)\right)$, linear in the number of output states $\left(\genfrac{}{}{0ex}{}{n+m-1}{m-1}\right)$. It outperforms the permanent-based method by an exponential factor, and for the restricted problem of computing the probability for one given output it improves the time complexity over the state-of-the-art for the permanent of matrices with multiple rows or columns, with a tradeoff in the memory usage. Our algorithm also has additional versatility by virtue of its use of memorisation -- the storing of intermediate results -- which is advantageous in situations where several input states may be of interest. Additionally it allows for hybrid simulations, in which outputs are sampled from output states whose probability exceeds a given threshold, or from a restricted set of states. We consider a concrete, optimised implementation, and we benchmark the efficiency of our approach compared to existing tools.

26 pages

References in corpus (5)

• Quantum computational advantage using photons
• Strong quantum computational advantage using a superconducting quantum processor
• Perceval: A Software Platform for Discrete Variable Photonic Quantum Computing
• Is quantum computing green? An estimate for an energy-efficiency quantum advantage
• Improved Heralded Schemes to Generate Entangled States From Single Photons

Cited by in corpus (10)

• Perceval: A Software Platform for Discrete Variable Photonic Quantum Computing
• Riemannian optimization of photonic quantum circuits in phase and Fock space
• Simulation of quantum optics by coherent state decomposition
• Simulating photonic devices with noisy optical elements
• Demonstration of quantum projective simulation on a single-photon-based quantum computer
• Multiphoton, multimode state classification for nonlinear optical circuits
• Bosonic randomized benchmarking with passive transformations
• Advancing Quantum Networking: Some Tools and Protocols for Ideal and Noisy Photonic Systems
• Boundaries for quantum advantage with single photons and loop-based time-bin interferometers
• Automated discovery of heralded ballistic graph state generators for fusion-based photonic quantum computation