652 citations · 1.1k across the 25 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
quant-ph2012
Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent
Scott Aaronson, Travis Hance
Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n*n matrix A. The algorithm runs in O(n^2/eps^2) time, and approximates Per(A) t…
quant-ph2012★ 652 cited
Photonic Boson Sampling in a Tunable Circuit
Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi-Keshari +4
Quantum computers are unnecessary for exponentially-efficient computation or simulation if the Extended Church-Turing thesis---a foundational tenet of computer science---is correct…