Strong Simulation of Linear Optical Processes
Preprint
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\binom{n+m-1}{m-1}}\right)$, linear in the number of output states $\binom{n+m-1}{m-1}$. 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.
Keywords
All Related Versions
This publication has 35 references indexed in Scilit:
- Quantum cryptography: Public key distribution and coin tossingTheoretical Computer Science, 2014
- The permanent of a square matrixEuropean Journal of Combinatorics, 2010
- Introduction to Optical Quantum Information Processing2010
- Quantum Communication ComplexityFoundations of Physics, 2003
- A scheme for efficient quantum computation with linear opticsNature, 2001
- Practical Methods of Optimization2000
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Combinatorial Algorithms1978
- An Introduction to Probability Theory and its Applications. By William Feller [2nd edn. Pp. xv+461. New York: John Wiley and Sons; London: Chapman and Hall. 1957. 86s.]Journal of the Institute of Actuaries, 1958
- On quantum field theory — I: explicit solution of Dyson’s equation in electrodynamics without use of feynman graphsIl Nuovo Cimento (1869-1876), 1953