Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha
the hitting times of quantum versus random walks ∗†
Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha
the hitting times of quantum versus random walks ∗
On the hitting times of quantum versus random walks (2008)
Magniez, Frederic, Nayak, Ashwin, Richter, Peter C., Santha, Miklos
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. In particular, we...
Lower Bounds, Graph Embeddings, Combinatorial Preconditioners, Gary L. Miller, Peter C. Richter
Given a general graph G, a fundamental problem is to find a spanning tree H that best approximates G by some measure. Often this measure is some combination of the congestion and dilation of an...
Two remarks on the local Hamiltonian problem (2007)
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 demonstrated...
Quantum speedup of classical mixing processes (2006)
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 sampling from a...
Almost uniform sampling via quantum walks (2006)
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 state space $S$ of...