2023/11/09 by Tian-Yu Yang, Yang, Tian-Yu, Xiang‐Bin Wang +1 · 1 citation
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Spectroscopy and Quantum Chemical Studies
paper · pdf · doi:10.48550/arxiv.2311.05355
openalex publication_date 2023/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Gaussian Boson sampling (GBS) plays a crucially important role in demonstrating quantum advantage. As a major imperfection, the limited connectivity of the linear optical network weakens the quantum advantage result in recent experiments. Here we present a faster classical algorithm to simulate the GBS process with limited connectivity. In this work, we introduce an enhanced classical algorithm for simulating GBS processes with limited connectivity. It computes the loop Hafnian of an n × n symmetric matrix with bandwidth w in O(nw2w) time which is better than the previous fastest algorithm which runs in O(nw2 2w) time. This classical algorithm is helpful on clarifying how limited connectivity affects the computational complexity of GBS and tightening the boundary of quantum advantage in the GBS problem.