Jun 20 – 21, 2022
Hotel Mercure Budapest Castle Hill
Europe/Budapest timezone

Polynomial speedup in exact Torontonian calculation by a scalable recursive algorithm

Jun 21, 2022, 11:20 AM
Hotel Mercure Budapest Castle Hill

Hotel Mercure Budapest Castle Hill

1013 Budapest, Krisztina Körút 41-43


Ágoston Kaposi


Evaluating the Torontonian function is a central computational challenge in the simulation of Gaussian Boson Sampling (GBS) with threshold detection.
During the calculation of this matrix function exponentially large number of determinants have to be computed.
We proposed a recursive algorithm providing a polynomial speedup in the exact calculation of the Torontonian compared to state-of-the-art algorithms.
Our algorithm recursively reuses the data used before to reach the computational advantage.
According to numerical analysis the complexity of the algorithm is ordo(n^1.06912 * 2^n).
With our algorithm, one can simulate threshold GBS up to 35-40 photon clicks without the needs of large-scale computational capacities.

Primary authors

Ágoston Kaposi Zoltán Kolarovszki Zoltan Zimboras (Wigner RCP) Peter Rakyta (Department of Physics of Complex Systems, Eötvös Loránd University)

Presentation materials