Fetching the paper…
Reading the bibliography…
We present a classical algorithm that approximately samples from the output distribution of certain noisy Boson Sampling experiments.
Combinatorial mathematics
Herbert John Ryser · 1963
Earlier work this paper cites.
The complexity of computing the permanent
Leslie G Valiant · 1979
Earlier work this paper cites.
Quantum complexity theory
Ethan Bernstein and Umesh Vazirani · 1993
Earlier work this paper cites.
Limitations of noisy reversible computation
Dorit Aharonov, Michael Ben-Or, Russell Impagliazzo, and Noam Nisan · 1996
Earlier work this paper cites.
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
Mark Jerrum, Alistair Sinclair, and Eric Vigoda · 2004
Earlier work this paper cites.
Adaptive quantum computation, constant-depth quantum circuits and Arthur-Merlin games
Barbara M. Terhal and David P. DiVincenzo · 2004
Earlier work this paper cites.
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd · 2010
Earlier work this paper cites.
The computational complexity of linear optics
Scott Aaronson and Alex Arkhipov · 2011
Earlier work this paper cites.
Bosonsampling is far from uniform
Scott Aaronson and Alex Arkhipov · 2013
Earlier work this paper cites.
Gaussian noise sensitivity and bosonsampling
Gil Kalai and Guy Kindler · 2014
Earlier work this paper cites.
Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
Malte C Tichy · 2015
Earlier work this paper cites.
Bosonsampling with lost photons
Scott Aaronson and Daniel J Brod · 2016
Earlier work this paper cites.
Local random quantum circuits are approximate polynomial-designs
Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki · 2016
Earlier work this paper cites.
Complexity-theoretic foundations of quantum supremacy experiments
Scott Aaronson and Lijie Chen · 2017
Earlier work this paper cites.
Achieving quantum supremacy with sparse and noisy commuting quantum computations
Michael J Bremner, Ashley Montanaro, and Dan J Shepherd · 2017
Earlier work this paper cites.
Fourier analysis of sampling from noisy chaotic quantum circuits
Sergio Boixo, Vadim N Smelyanskiy, and Hartmut Neven · 2017
Earlier work this paper cites.
Gaussian boson sampling
Craig S Hamilton, Regina Kruse, Linda Sansoni, Sonja Barkhofen, Christine Silberhorn, and Igor Jex · 2017
Earlier work this paper cites.
Classical boson sampling algorithms with superior performance to near-term experiments
Alex Neville, Chris Sparrow, Raphaël Clifford, Eric Johnston, Patrick M Birchall, Ashley Montanaro, and Anthony Laing · 2017
Earlier work this paper cites.
Direct dialling of haar random unitary matrices
Nicholas J Russell, Levon Chakhmakhchyan, Jeremy L O’Brien, and Anthony Laing · 2017
Cited alongside, same era.
Architectures for quantum simulation showing a quantum speedup
Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert · 2018
Cited alongside, same era.
Efficient classical simulation of noisy quantum computation
Xun Gao and Luming Duan · 2018
Cited alongside, same era.
Anticoncentration theorems for schemes showing a quantum speedup
Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert · 2018
Cited alongside, same era.
Aram Harrow and Saeed Mehraban · 2018
Cited alongside, same era.
Spoofing linear cross-entropy benchmarking in shallow quantum circuits
Boaz Barak, Chi-Ning Chou, and Xun Gao · 2021
Later among the works it cites.
Noise and the frontier of quantum supremacy
Adam Bouland, Bill Fefferman, Zeph Landau, and Yunchao Liu · 2021
Later among the works it cites.
Quantum supremacy and hardness of estimating output probabilities of quantum circuits
Yasuhiro Kondo, Ryuhei Mori, and Ramis Movassagh · 2021
Later among the works it cites.
Sepehr Nezami · 2021
Later among the works it cites.
Classical simulation of lossy boson sampling using matrix product operators
Changhun Oh, Kyungjoo Noh, Bill Fefferman, and Liang Jiang · 2021
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Classical simulation of photonic linear optics with lost particles
Michał Oszmaniec and Daniel J Brod · 2018
Cited alongside, same era.
Efficient classical algorithm for boson sampling with partially distinguishable photons
Jelmer J Renema, Adrian Menssen, William R Clements, Gil Triginer, William S Kolthammer, and Ian A Walmsley · 2018
Cited alongside, same era.
Classical simulability of noisy boson sampling
Jelmer Renema, Valery Shchesnovich, and Raul Garcia-Patron · 2018
Cited alongside, same era.
Quantum supremacy using a programmable superconducting processor
Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al · 2019
Cited alongside, same era.
On the classical hardness of spoofing linear cross-entropy benchmarking
Scott Aaronson and Sam Gunn · 2019
Cited alongside, same era.
On the complexity and verification of quantum random circuit sampling
Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani · 2019
Cited alongside, same era.
Simulating boson sampling in lossy architectures
Raúl García-Patrón, Jelmer J Renema, and Valery Shchesnovich · 2019
Cited alongside, same era.
Yasuhiro Takahashi, Yuki Takeuchi, and Seiichiro Tani · 2021
Later among the works it cites.
Efficient approximation of experimental gaussian boson sampling
Benjamin Villalonga, Murphy Yuezhen Niu, Li Li, Hartmut Neven, John C Platt, Vadim N Smelyanskiy, and Sergio Boixo · 2021
Later among the works it cites.
Strong quantum computational advantage using a superconducting quantum processor
Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, et al · 2021
Later among the works it cites.
Phase-programmable Gaussian boson sampling using stimulated squeezed light
Han-Sen Zhong, Yu-Hao Deng, Jian Qin, Hui Wang, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Dian Wu, Si-Qiu Gong, Hao Su, et al · 2021
Later among the works it cites.
https://scottaaronson.blog/?p=6871 , 2022
Scott Aaronson · 2022
Later among the works it cites.
A polynomial-time classical algorithm for noisy random circuit sampling
Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani · 2022
Later among the works it cites.
Random quantum circuits anticoncentrate in log depth
Alexander M Dalzell, Nicholas Hunter-Jones, and Fernando GSL Brandão · 2022
Later among the works it cites.
Quantum computational advantage via high-dimensional Gaussian boson sampling
Abhinav Deshpande, Arthur Mehta, Trevor Vincent, Nicolás Quesada, Marcel Hinsche, Marios Ioannou, Lars Madsen, Jonathan Lavoie, Haoyu Qi, Jens Eisert, Dominik Hangleiter, Bill Fefferman, and Ish Dhand · 2022
Later among the works it cites.
Tight bounds on the convergence of noisy random circuits to the uniform distribution
Abhinav Deshpande, Pradeep Niroula, Oles Shtanko, Alexey V Gorshkov, Bill Fefferman, and Michael J Gullans · 2022
Later among the works it cites.
Computational advantage of quantum random sampling
Dominik Hangleiter and Jens Eisert · 2022
Later among the works it cites.
Quantum computational advantage with a programmable photonic processor
Lars S Madsen, Fabian Laudenbach, Mohsen Falamarzi Askarani, Fabien Rortais, Trevor Vincent, Jacob FF Bulmer, Filippo M Miatto, Leonhard Neuhaus, Lukas G Helt, Matthew J Collins, et al · 2022
Later among the works it cites.
Classical simulation of boson sampling based on graph structure
Changhun Oh, Youngrong Lim, Bill Fefferman, and Liang Jiang · 2022
Later among the works it cites.
Quantum-inspired classical algorithm for molecular vibronic spectra
Changhun Oh, Youngrong Lim, Yat Wong, Bill Fefferman, and Liang Jiang · 2022
Later among the works it cites.