PRPeter C. Richter

Peter C. Richter

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Peter C. Richter has a total of 2 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Quantum Analogs of Markov Chains

    by ∎ AshwinNayak, Peter C.RIchter, ∎ MarioSzegedy


  • Quantum speedup of classical mixing processes

    by Peter C. Richter

    Most approximation algorithms for #P-complete problems (e.g., evaluating the partition function of a monomer-dimer or ferromagnetic Ising system) work by reduction to the problem of approximate sampling from a distribution π over a large set S. This problem is solved using the Markov chain Monte Carlo method: a sparse, reversible Markov chain P on S with stationary distribution π is run to near equilibrium. The running time of this random walk algorithm, the so-called mixing time of P, is O(δ−1 log 1∕π∗) as shown by Aldous, where δ is the spectral gap of P and π∗ is the minimum value of π. A natural question is whether a speedup of this classical method to O(δ−1 log 1∕π∗) is possible using quantum walks. We provide evidence for this possibility using quantum walks that decohere under repeated randomized measurements. We show that (i) decoherent quantum walks always mix, just like their classical counterparts, (ii) the mixing time is a robust quantity, essentially invariant under any smooth form of decoherence, and (iii) the mixing time of the decoherent quantum walk on a periodic lattice Znd is O(nd log d), which is indeed O(δ−1 log 1∕π∗) and is asymptotically no worse than the diameter of Znd (the obvious lower bound) up to at most a logarithmic factor.


  • Open Access

    Quantum speedup of classical mixing processes

    by 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 sampling from a distribution $\pi$ over a large set $\S$. This problem is solved using the {\em Markov chain Monte Carlo} method: a sparse, reversible Markov chain $P$ on $\S$ with stationary distribution $\pi$ is run to near equilibrium. The running time of this random walk algorithm, the so-called {\em mixing time} of $P$, is $O(\delta^{-1} \log 1/\pi_*)$ as shown by Aldous, where $\delta$ is the spectral gap of $P$ and $\pi_*$ is the minimum value of $\pi$. A natural question is whether a speedup of this classical method to $O(\sqrt{\delta^{-1}} \log 1/\pi_*)$, the diameter of the graph underlying $P$, is possible using {\em quantum walks}. We provide evidence for this possibility using quantum walks that {\em decohere} under repeated randomized measurements. We show: (a) decoherent quantum walks always mix, just like their classical counterparts, (b) the mixing time is a robust quantity, essentially invariant under any smooth form of decoherence, and (c) the mixing time of the decoherent quantum walk on a periodic lattice $\Z_n^d$ is $O(n d \log d)$, which is indeed $O(\sqrt{\delta^{-1}} \log 1/\pi_*)$ and is asymptotically no worse than the diameter of $\Z_n^d$ (the obvious lower bound) up to at most a logarithmic factor.

  • Open Access

    Almost uniform sampling via quantum walks

    by 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 state space $S$ of cardinality $N$: run a symmetric ergodic Markov chain $P$ on $S$ for long enough to obtain a random state from within $\epsilon$ total variation distance of the uniform distribution over $S$. The running time of this algorithm, the so-called {\em mixing time} of $P$, is $O(\delta^{-1} (\log N + \log \epsilon^{-1}))$, where $\delta$ is the spectral gap of $P$. We present a natural quantum version of this algorithm based on repeated measurements of the {\em quantum walk} $U_t = e^{-iPt}$. We show that it samples almost uniformly from $S$ with logarithmic dependence on $\epsilon^{-1}$ just as the classical walk $P$ does; previously, no such quantum walk algorithm was known. We then outline a framework for analyzing its running time and formulate two plausible conjectures which together would imply that it runs in time $O(\delta^{-1/2} \log N \log \epsilon^{-1})$ when $P$ is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs.