Quantum Approximate Counting for Markov Chains and Application to Collision Counting

Grover’s search [9] is the most basic version of quantum search. This quantum algorithm considers the following problem called unstructured search: for a function $f\colon\{1,\ldots,N\}\to\{0,1\}$ given as a black-box, find one element $x\in\{1,\ldots,N\}$ such that $f(x)=1$ (we call such an element a solution and assume that there exists at least one). Let $M=|f^{-1}(1)|$ denote the number of solutions. Grover’s algorithm outputs with high probability a solution using $O(\sqrt{N/M})$ calls to the function $f$. This is a quadratic improvement over the classical (i.e., non-quantum) strategy, which is based on random sampling and requires $\Theta(N/M)$ calls to $f$ to find a solution with high probability.

Another fundamental, but more sophisticated, quantum search technique is quantum walk based search [2, 16, 21]. The problem considered here is a generalization of unstructured search. As for unstructured search, this problem accesses the data via a black-box. It can be defined in an abstract way for any Markov chain (Markov chains are generalizations of the concept of random walks over a graphs — see Section 2.2 for details). Some states of the Markov chains corresponding to “solutions” are called the marked states. The goal of the problem is to find one marked state (here we assume again that there is at least one marked state). Let $\lambda>0$ be a lower bound on the fraction of marked states. Magniez, Nayak, Roland and Santha [16] have shown that this problem can be solved with high probability by a quantum algorithm that makes

queries to the black-box, were $\delta$ denotes the spectral gap of the Markov chain and $\mathsf{S}$, $\mathsf{U}$ and $\mathsf{C}$ represent the number of queries needed to implement the three basic quantum operations corresponding to search: the setup operation, the update operation and the checking operation. Unstructured search simply corresponds to the Markov chain representing a random walk on a complete graph of $N$ vertices, which has spectral gap $\delta=1$, with $\lambda=M/N$, $\mathsf{S}=1$, $\mathsf{U}=2$ and $\mathsf{C}=0$. The complexity becomes $O(\sqrt{\lambda})=O(\sqrt{N/M})$, as for Grover’s search.³³3Grover’s search can also be derived in another (more direct) way, with costs $\mathsf{S}=0$, $\mathsf{U}=0$ and $\mathsf{C}=1$.   A striking illustration of the power of quantum walk based search is the problem called element distinctness: for two functions $f,g\colon\{1,\ldots,N\}\longrightarrow\{1,\ldots,K\}$ accessible as black boxes, find a pair $(i,j)\in\{1,\ldots,N\}^{2}$ satisfying $f(i)=g(j)$ if such a pair exists (such a pair is called a collision). Ambainis [2] showed how to solve this problem with $O(N^{2/3})$ queries using quantum walk based search.⁴⁴4While the version of element distinctness considered in [2] uses only one function, the version we present here is essentially equivalent (see [13] for details).   Besides element distinctness, quantum walk based search has been used to design quantum algorithms for many other problems, such as matrix multiplication [6], triangle finding [10, 12, 15] or associativity testing [14].

Quantum approximate counting is another very useful quantum primitive designed by Brassard, Høyer and Tapp [5]. It solves the (approximate) counting version of unstructured search: for any given $\epsilon>0$ and a function $f\colon\{1,\ldots,N\}\to\{0,1\}$ given as a black-box, output an $\epsilon$-approximation of the number of solution $M=|f^{-1}(1)|$, i.e., output an integer $\hat{M}$ such that $|M-\hat{M}|\leq\epsilon M$. The quantum approximate counting algorithm from [5] solves this problem using $O(\frac{1}{\epsilon}\sqrt{N/M})$ calls to $f$. This is again a quadratic improvement over the classical strategy, which is based on random sampling and requires $\Theta(\frac{1}{\epsilon^{2}}N/M)$ calls to $f$ [18]. Very recently, several variants of quantum approximate counting have been proposed [1, 20, 23, 24]. These variants have the same asymptotic complexity as the original algorithm but may be easier to implement in practice, especially on near-future quantum computers.

Since quantum walk based search is a generalization of Grover search, a natural question is whether a version of quantum approximate counting can be obtained for quantum walk based search as well, i.e., whether there exists an efficient quantum algorithm to estimate the number of marked states of a Markov chain. To our knowledge, this problem has never been studied in the literature. This problem is especially motivated by the task of approximate collision counting: for two functions $f,g\colon\{1,\ldots,N\}\longrightarrow\{1,\ldots,K\}$ accessible as black boxes, output an approximation of the number of collisions. While not stated explicitly, this task is at the heart of most algorithms for estimating the edit distance between two non-repetitive strings [3, 13, 17], and is also used for estimating the $\ell_{1}$-distance between two probability distributions [4, 22].

Our main technical result is the following general approximate counting version for reversible Markov chains.

As an application of Theorem 1.1, we show how to construct a quantum algorithm to approximate the number of collisions. More precisely, the version of approximate collision counting we consider is as follows: for $\epsilon>0$ and for two injective functions $f,g\colon\{1,\ldots,N\}\longrightarrow\{1,\ldots,K\}$, where $K>N$, output an $\epsilon$-approximation of the number of collisions $m$, i.e., an estimate $\hat{m}$ such that $|m-\hat{m}|<\epsilon m$. (We restrict our attention to the case of injective functions since this simplifies the exposition of our result. Note that this version with injective functions is still interesting since it is precisely the version needed for estimating the edit distance between two non-repetitive strings [3, 13, 17].)

In order to derive worst-case complexity upper bounds that explicitly depend on the number of collisions, we assume that we know a lower bound $\bar{m}\leq m$, and state the complexities using $\bar{m}$. There is an easy randomized algorithm based on sampling (which has been, for instance, used implicitly in [3, 17]) that outputs with high probability an $\epsilon$-approximation of $m$ using $O\big{(}\frac{1}{\epsilon}\frac{N}{\sqrt{m}}+\frac{N}{\sqrt{\bar{m}}}\big{)}$ evaluations of $f$ and $g$, which is essentially tight (see Appendix A for details). Based on the technique of Theorem 1.1, we design a fast quantum algorithm for this problem:

Let us start by giving an overview of the quantum approximate counting by Brassard, Høyer and Tapp [5]. Roughly speaking, the quantum approximate counting algorithm from [5] applies the technique called quantum phase estimation [7, 11], which is based on the quantum Fourier transform, in order to estimate the eigenvalues of the unitary operator used as the main subroutine of Grover’s algorithm. This operator, when restricted to the appropriate subspace, is a rotation whose angle is closely related to the number of solutions. The eigenvalues of this operator are thus closely related to the number of solutions as well. A good approximation of the eigenvalues, which can be obtained using quantum phase estimation, then gives a good approximation of the number of solutions.

The main insight is that the main operator $U$ of quantum walk based search by Magniez, Nayak, Roland and Santha [16] approximately corresponds to a rotation $\overline{U}$ (see Corollary 2.3 in Section 2.2). To prove Theorem 1.1, we observe that the eigenvalues of this rotation $\overline{U}$ are closely related to the fraction of marked states with respect to the stationary distribution of the Markov chain, and then shows that quantum phase estimation applied on $U$ (instead of $\overline{U}$) with good enough precision gives a good estimation of these eigenvalues and thus a good approximation of the number of marked states if the stationary distribution is uniform (Section 3). To prove Theorem 1.2, we additionally establish the relation between the number of collisions and the number of marked states in the Markov chain corresponding to a random walk over the Johnson graph (which is the same Markov chain as the one used in Ambainis’ element distinctness algorithm [2]), and show that a good approximation for the latter gives a good enough approximation of the former (Section 4).

From Theorem 2.1 we know that when choosing parameters $t_{1}=\left\lceil\log_{2}\left(\frac{5\pi}{\epsilon\sqrt{\lambda}}\right)-1\right\rceil$, $\xi=0.01$, $t=t_{1}+\lceil\log_{2}(2+\frac{1}{2\xi})\rceil$, the algorithm Est($\overline{U}$, $|\Psi_{\pm}\rangle|0^{\tau}\rangle$, $t$) would output a value $z$ such that $|z-(\pm\varphi/\pi)|<2^{-t_{1}}$ with probability at least $0.99$.

Let us now interpret these probabilities in a more algebraic way. Let $M_{+}$ and $M_{-}$ be the projection over the subspaces $\operatorname{span}\left\{|\tilde{b}\rangle:\left|\frac{\tilde{b}}{2^{t}}-\frac{\varphi}{\pi}\right|<2^{-t_{1}}\right\}$ and $\operatorname{span}\left\{|\tilde{b}\rangle:\left|\frac{\tilde{b}}{2^{t}}+\frac{\varphi}{\pi}\right|<2^{-t_{1}}\right\}$, respectively, of the vector space $\mathbb{C}^{2^{t}}$. We thus have:

Let us now analyze the output of Est($\overline{U}$, $|\pi\rangle|0^{\tau}\rangle$, $t$). For conciseness, we write $|\overline{\Phi}\rangle=C_{t}(\overline{U})|0^{t}\rangle|\pi\rangle|0^{\tau}\rangle$. Remember the decomposition of Eq. (2) and observe that ${\big{\|}-\frac{i}{\sqrt{2}}e^{i2\varphi}\big{\|}^{2}}=\big{\|}\frac{i}{\sqrt{2}}e^{-i2\varphi}\big{\|}^{2}=\frac{1}{2}$. Thus we have:

which means that Est($\overline{U}$, $|\pi\rangle|0^{\tau}\rangle$, $t$) outputs a value $z$ such that $|z-\varphi/\pi|<2^{-t_{1}}$ with probability at least $0.99/2$ and $|z+\varphi/\pi|<2^{-t_{1}}$ with probability at least $0.99/2$.

We apply phase estimation on $U$ instead of $\overline{U}$, with the input state $|\pi\rangle|0^{\tau}\rangle$, where $U$ is the operator introduced in Section 2.2. Remember that $U$ is defined using a parameter $k$ (see the statement of Theorem 2.2). We set $k=2t+t_{1}+1$.

The algorithm for Theorem 1.1 is as follows.

We are going to show that $|M-\hat{M}|<\epsilon$, where $M=N\sin^{2}\varphi$ and $\hat{M}=N\sin^{2}(y\pi)$, by analyzing the quantity $\bigl{|}\varphi-|y|\pi\bigr{|}$.

Let us write $|\Phi\rangle=C_{t}(U)|0^{t}\rangle|\pi\rangle|0^{\tau}\rangle$. For any measurement operator $M_{m}\in\{M_{+},M_{-}\}$, we have

where we used Lemma 3.1 to derive the last inequality (remember that we are taking $k=2t+t_{1}+1$). Combined with (3), this implies that with probability at least $0.99/2-2^{-2t_{1}}$ the output of Est($U$, $|\pi\rangle|0^{\tau}\rangle$, $t$) satisfies the condition $|y-\varphi/\pi|\leq 2^{-t_{1}}$, and with probability at least $0.99/2-2^{-2t_{1}}$ it satisfies the condition $|y+\varphi/\pi|\leq 2^{-t_{1}}$. It follows from this condition that $\big{|}|y|-\varphi/\pi\big{|}\leq 2^{-t_{1}}$ holds with probability at least $0.99-2^{1-2t_{1}}$, since $\varphi\geq 0$. Assume that this inequality holds. Then $\bigl{|}\varphi-|y|\pi\bigr{|}=\pi\left|\frac{\varphi}{\pi}-|y|\right|\leq 2^{-t_{1}}\pi$. Notice that for any $\alpha,\beta\in\mathbb{R}$, $|\sin{\alpha}-\sin{\beta}|\leq|\alpha-\beta|$ by the mean value theorem. We thus have

and it follows that

Under the framework presented in Section 2.2, the quantum state $|\pi\rangle$ can be created using $\mathsf{S}$ queries, and the operator $U$ can be implemented using $\frac{k}{\sqrt{\delta}}\mathsf{U}+\mathsf{C}$ queries. The operator $U$ is applied for $O(2^{t})=O(\frac{1}{\epsilon}\frac{1}{\sqrt{\lambda}})$ times by the phase estimation algorithm. The overall complexity of Algorithm 2 is thus

queries, as claimed. ∎

From the argument above, we then obtain the following immediate corollary for any reversible ergodic Markov chain whose stationary distribution is not necessarily uniform.