Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914122886545408 |
|---|---|
| author | Zhang, Yexin Zhou, Shuo Wang, Xinzhao Wang, Ziruo Yang, Ziyi Yang, Rui Xue, Yecheng Li, Tongyang |
| author_facet | Zhang, Yexin Zhou, Shuo Wang, Xinzhao Wang, Ziruo Yang, Ziyi Yang, Rui Xue, Yecheng Li, Tongyang |
| contents | Gaussian Boson Sampling (GBS) is a promising candidate for demonstrating quantum computational advantage and can be applied to solving graph-related problems. In this work, we propose Markov chain Monte Carlo-based algorithms to sample from GBS distributions on undirected, unweighted graphs. Our main contribution is a double-loop variant of Glauber dynamics, whose stationary distribution matches the GBS distribution. We further prove that it mixes in polynomial time for dense graphs using a refined canonical path argument. Numerically, we conduct experiments on unweighted graphs with 256 vertices, larger than the scales in former GBS experiments as well as classical simulations. In particular, we show that both the single-loop and double-loop Glauber dynamics improve the performance of original random search and simulated annealing algorithms for the max-Hafnian and densest $k$-subgraph problems up to 10$\times$. Overall, our approach offers both theoretical guarantees and practical advantages for efficient classical sampling from GBS distributions on unweighted graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_02445 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs Zhang, Yexin Zhou, Shuo Wang, Xinzhao Wang, Ziruo Yang, Ziyi Yang, Rui Xue, Yecheng Li, Tongyang Quantum Physics Data Structures and Algorithms Gaussian Boson Sampling (GBS) is a promising candidate for demonstrating quantum computational advantage and can be applied to solving graph-related problems. In this work, we propose Markov chain Monte Carlo-based algorithms to sample from GBS distributions on undirected, unweighted graphs. Our main contribution is a double-loop variant of Glauber dynamics, whose stationary distribution matches the GBS distribution. We further prove that it mixes in polynomial time for dense graphs using a refined canonical path argument. Numerically, we conduct experiments on unweighted graphs with 256 vertices, larger than the scales in former GBS experiments as well as classical simulations. In particular, we show that both the single-loop and double-loop Glauber dynamics improve the performance of original random search and simulated annealing algorithms for the max-Hafnian and densest $k$-subgraph problems up to 10$\times$. Overall, our approach offers both theoretical guarantees and practical advantages for efficient classical sampling from GBS distributions on unweighted graphs. |
| title | Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.02445 |