84 citations · 141 across the 3 of their papers we have counts for
4 papers
On the hitting times of quantum versus random walks
Frederic Magniez, Ashwin Nayak, Peter C. Richter +1
In this paper we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions…
Two remarks on the local Hamiltonian problem
Peter C. Richter
In this note we present two natural restrictions of the local Hamiltonian problem which are BQP-complete under Karp reduction. Restrictions complete for QCMA, QMA_1, and MA were de…
Quantum speedup of classical mixing processes
Peter C. Richter
Most approximation algorithms for #P-complete problems (e.g., evaluating the permanent of a matrix or the volume of a polytope) work by reduction to the problem of approximate samp…
Almost uniform sampling via quantum walks
Peter C. Richter
Many classical randomized algorithms (e.g., approximation algorithms for #P-complete problems) utilize the following random walk algorithm for {\em almost uniform sampling} from a…