Quantum energetic advantage before computational advantage in Boson Sampling

Ariane Soret, Nessim Dridi, Stephen C. Wein +3 more

Understanding the energetic efficiency of quantum computers is essential for assessing their scalability and for determining whether quantum technologies can outperform classical computation beyond runtime alone. In this work, we analyze the energy required to solve the Boson Sampling problem, a paradigmatic task for quantum advantage, using a realistic photonic quantum computing architecture. Using the Metric-Noise-Resource methodology, we establish a quantitative connection between experimental control parameters, dominant noise processes, and energetic resources through a performance metric tailored to Boson Sampling. We estimate the energy cost per sample and identify operating regimes that optimize energetic efficiency. By comparing the energy consumption of quantum and state-of-the-art classical implementations, we demonstrate the existence of a quantum energetic advantage -- defined as a lower energy cost per sample compared to the best-known classical implementation -- that emerges before the onset of computational advantage, even in regimes where classical algorithms remain faster. Finally, we propose an experimentally feasible Boson Sampling architecture, including a complete noise and loss budget, that enables a near-term observation of quantum energetic advantage.

Alex Neville, Chris Sparrow

Anonymous

Byeongseon Go, Changhun Oh, Hyunseok Jeong

Boson sampling stands out as a promising approach toward experimental demonstration of quantum computational advantage. However, the presence of physical noise in near-term experiments hinders the realization of quantum computational advantage with boson sampling. Since physical noise in near-term boson-sampling devices is inevitable, precise characterization of the boundary of noise rates where the classical intractability of boson sampling is maintained is crucial for quantum computational advantage using near-term devices. In this work, we identify the level of partial-distinguishability noise that upholds the classical intractability of boson sampling. We find that boson sampling with on average O ( log  N ) distinguishable photons out of N input photons maintains the equivalent complexity to the ideal boson-sampling case. By providing strong complexity-theoretical evidence for the classical intractability of noisy boson sampling, we expect that our findings will ultimately facilitate the demonstration of quantum computational advantage with noisy boson-sampling experiments in the near future.

Alex Neville, Chris Sparrow, Raphaël Clifford A +4 more

Byeongseon Go, Changhun Oh, Hyunseok Jeong

Boson Sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage using near-term quantum devices. However, noise in experimental implementations poses a significant challenge, potentially rendering Boson Sampling classically simulable and compromising its classical intractability. Numerous studies have proposed classical algorithms that can efficiently simulate Boson Sampling under various noise models, particularly as noise rates increase with circuit depth. To address this challenge, we investigate the viability of achieving quantum computational advantage through Boson Sampling implemented with shallow-depth linear optical circuits. In particular, as the average-case hardness of estimating output probabilities of Boson Sampling is a crucial ingredient in demonstrating its classical intractability, we make progress on establishing the average-case hardness of Boson Sampling confined to logarithmic-depth regimes. We also obtain the average-case hardness for logarithmic-depth Fock-state Boson Sampling subject to lossy environments and for the logarithmic-depth Gaussian Boson Sampling. By providing complexity-theoretical backgrounds for the classical simulation hardness of logarithmic-depth Boson Sampling, we expect that our findings will mark a crucial step towards a more noise-tolerant demonstration of quantum advantage with shallow-depth Boson Sampling.