Polynomial speedup in Torontonian calculation by a scalable recursive algorithm

Abstract

Evaluating the Torontonian function is a central computational challenge in the simulation of Gaussian Boson Sampling (GBS) with threshold detection. In this work, we propose a recursive algorithm providing a polynomial speedup in the exact calculation of the Torontonian compared to state-of-the-art algorithms. According to our numerical analysis the complexity of the algorithm is proportional to $N^{1.0691}{2}^{N/2}$ with $N$ being the size of the problem. We also show that the recursive algorithm can be scaled up to HPC use cases making feasible the simulation of threshold GBS up to $35-40$ photon clicks without the needs of large-scale computational capacities.

arXiv comment13 pages, 7 pages

References in corpus (33)

• Characterizing Quantum Supremacy in Near-Term Devices
• Boson Sampling on a Photonic Chip
• Quantum Computational Supremacy
• Experimental Boson Sampling
• Experimental boson sampling in arbitrary integrated photonic circuits
• Photonic Boson Sampling in a Tunable Circuit
• Gaussian Boson Sampling
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Strawberry Fields: A Software Platform for Photonic Quantum Computing
• Efficient experimental validation of photonic boson sampling against the uniform distribution
• Boson Sampling from Gaussian States
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Experimental Scattershot Boson Sampling
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• A detailed study of Gaussian Boson Sampling
• Quantum computing and the entanglement frontier
• Scalable boson-sampling with time-bin encoding using a loop-based architecture
• Gaussian Boson Sampling using threshold detectors
• A 12-mode Universal Photonic Processor for Quantum Information Processing
• A chip-based array of near-identical, pure, heralded single photon sources
• Simulating boson sampling in lossy architectures
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Scalable Implementation of Boson Sampling with Trapped Ions
• Microwave Boson Sampling
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Classical simulation of linear optics subject to nonuniform losses
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Simulability of Imperfect Gaussian and Superposition Boson Sampling
• Driven Boson Sampling
• High Dimensional Unitary Transformations and Boson Sampling on Temporal Modes using Dispersive Optics
• Benchmarking 50-Photon Gaussian Boson Sampling on the Sunway TaihuLight
• Marginal probabilities in boson samplers with arbitrary input states