Deterministic Search on Complete Bipartite Graphs by Continuous-Time Quantum Walk

Quantum walk is a fundamental and powerful tool for designing quantum algorithms that outperform the classical counterparts, such as searching [1,2], element distinctness [3], and graph isomorphism [4]. Various models have been put forward for undirected graphs [5] or directed graphs [6,7]. It has been demonstrated that they are universal for quantum computing [8,9] and can be implemented in a variety of physical systems [10,11,12].

Quantum walk serves as a natural algorithmic framework for spatial search, that is, finding marked vertices on a given graph. Search problem is one of the most important problems in computer science. Many of the computation tasks can be reduced to search problems or invoke search algorithms as a subroutine. One early milestone in quantum computation is Grover's celebrated algorithm for search in an unstructured database [13]. Since then, extensive research has been conducted to enhance and generalize Grover's algorithm. There are two avenues of investigation. One is to de-randomize the original algorithm, making the search exact [14,15]. Since error probability becomes negligible only when the database becomes sufficiently large, determinacy is vital in problems where the search space is relatively small. It also simplifies error analysis when the algorithm is used as a subroutine. Moreover, derandomization holds inherent value in itself. For example, deterministic quantum algorithms indicate that quantum computation is not essentially probabilistic. On the other hand, Grover's unstructured search can be formulated as quantum walk search on a complete graph [16,17], another research field is devising algorithms for search on other classes of graphs, such as hypercubes [18], lattices [18,19], and even general graphs [1,2,20].

We pursue both of these two directions here, searching on graphs and searching with certainty. Marsh and Wang [21] gave the first nontrivial deterministic spatial search algorithm, called alternating quantum walk, which is to search on 2 × n Rook graphs. Employing the same alternating quantum walk framework, Qu et al. [22] proposed a deterministic search algorithm on star graphs and gave the first experimental demonstration. Utilizing the parity of integers, Wang et al. [23] reported a universal algorithm via alternating quantum walk that works for graphs with integer Laplacian spectra. Recently, Peng et al. [24] presented a spatial search algorithm on complete bipartite graphs by the coined quantum walk model. See Table 1 for a summary.

Table 1.

Comparison of previous results and our work on deterministic spatial search.

Algorithms	Graph	Model	Number of marked vertices
Marsh and Wang [21]	2 × n Rook graph	Alternating CTQW	Single
Qu et al. [22]	Star graph	Alternating CTQW	Single
Wang et al. [23]	Integer Laplacian spectra	Alternating CTQW	Multiple
Peng et al. [24]	Complete bipartite graph	Coined DTQW	Multiple
Our work	Complete bipartite graph	CTQW	Multiple

In this paper, we employ continuous-time quantum walk to construct a deterministic search algorithm on complete bipartite graphs. This class of graphs has been broadly studied due to its special structure and rich properties, such as biclique cryptanalysis [25] and state transfer [26,27]. Search on complete bipartite graphs has been explored in different cases. Wong et al. [28] studied the distinction between Laplacian and adjacency matrix as the Hamiltonian operator in continuous-time quantum walk search by analyzing searches on the complete partite graphs, while Rhodes and Wong [29] investigated how discrete-time quantum walk searches the complete bipartite graphs with different initial states. The calculation of the algorithmic parameter (runtime) of these two works varies according to the size of the two partite sets and the arrangement of the marked vertices. As shown in Section 3 (Theorem 1), our algorithm does not depend on a case-by-case analysis. Besides, the success probabilities of these algorithms are strictly less than 1 or only reach 1 asymptotically. See Table 2 for a comparison.

Table 2.

Comparison of previous results and our work on spatial search on complete bipartite graphs.

Algorithms	Model	Initial state	Success probability
Wong et al. [28]	CG framework for Laplacian walk	$\sum_{i = 0}^{m + n - 1} \| i 〉$ \sum\nolimits_{i = 0}^{m + n - 1} \|i\rangle	1 (m, n → ∞)
Wong et al. [28]	CG framework for adjacency walk	$\frac{1}{\sqrt{2 m}} \sum_{i \in V_{1}} \| i 〉 + \frac{1}{\sqrt{2 n}} \sum_{i \in V_{2}} \| i 〉$ {1 \over {\sqrt {2m}}}\sum\nolimits_{i \in {V_1}} \|i\rangle + {1 \over {\sqrt {2n}}}\sum\nolimits_{i \in {V_2}} \|i\rangle	1 (m, n → ∞)
Rhodes and Wong [29]	Coined DTQW	$\frac{1}{\sqrt{m + n}} (\sum_{i \in V_{1}} \| i 〉 \otimes \frac{1}{\sqrt{n}} \sum_{j \in V_{2}} \| j 〉 + \sum_{i \in V_{2}} \| i 〉 \otimes \frac{1}{\sqrt{m}} \sum_{j \in V_{1}} \| j 〉)$ {1 \over {\sqrt {m + n}}}\left({\sum\nolimits_{i \in {V_1}} \|i\rangle \otimes {1 \over {\sqrt n}}\sum\nolimits_{j \in {V_2}} \|j\rangle +} \right.\left. {\sum\nolimits_{i \in {V_2}} \|i\rangle \otimes {1 \over {\sqrt m}}\sum\nolimits_{j \in {V_1}} \|j\rangle} \right)	$\frac{m}{m + n}$ {m \over {m + n}} or $\frac{n}{m + n}$ {n \over {m + n}} (and 1 for a special case)
Rhodes and Wong [29]	Coined DTQW	$\frac{1}{\sqrt{2 mn}} (\sum_{i = 0}^{m + n - 1} \| i 〉 \otimes \sum_{j \sim i} \| j 〉)$ {1 \over {\sqrt {2mn}}}\left({\sum\nolimits_{i = 0}^{m + n - 1} \|i\rangle \otimes \sum\nolimits_{j \sim i} \|j\rangle} \right)	$\frac{1}{2}$ {1 \over 2} (and 1 for a special case)
Xu et al. [30]	Coined DTQW	$\frac{1}{\sqrt{2 mn}} (\sum_{i = 0}^{m + n - 1} \| i 〉 \otimes \sum_{j \sim i} \| j 〉)$ {1 \over {\sqrt {2mn}}}\left({\sum\nolimits_{i = 0}^{m + n - 1} \|i\rangle \otimes \sum\nolimits_{j \sim i} \|j\rangle} \right)	≥ 1 − ɛ for any adjustable parameter ɛ
Our work	CTQW	$\frac{1}{\sqrt{m}} \sum_{i \in V_{1}} \| i 〉$ {1 \over {\sqrt m}}\sum\nolimits_{i \in {V_1}} \|i\rangle or $\frac{1}{\sqrt{n}} \sum_{i \in V_{2}} \| i 〉$ {1 \over {\sqrt n}}\sum\nolimits_{i \in {V_2}} \|i\rangle	1

We consider the general case of multiple marked vertices. As pointed out in [31], knowing the number of solutions is necessary to deterministically find a marked vertex with quadratic speedup. Therefore, we assume the knowledge of the number of marked vertices. For the case of this quantity being unknown, there comes the Soufflé problem, that is, one might iterate too little or too much, rendering the algorithm unsuccessful. There are two strategies to deal with this issue. One is constructing a robust (also called fixed-point) quantum search algorithm [30], which can find a marked vertex with probability at least 1 − ɛ for any adjustable parameter ɛ whenever the number of search steps is larger than some threshold value. Another strategy is devising a quantum counting algorithm to estimate the number of marked vertices first and then employ the search algorithm. In this work, we utilize our search operator to design a quantum counting algorithm.

Approximate counting is one of the most fundamental problems in computer science. It has applications, for example, to the solution of NP-complete problems, which may be phrased in terms of the existence of a solution to a search problem [32]. Recently, Bezerra et al. [33] presented a quantum counting algorithm on complete bipartite graphs based on discrete-time quantum walk. The quantum walk dynamics has an eight-dimensional invariant subspace and the eigenvalues of the reduced operator separate into two nonequivalent classes. Our search operator has a simpler spectrum structure, consisting of −1 and a conjugate pair. Since the conjugate eigenvalues encode the information of the number of marked vertices, we employ quantum phase estimation to estimate the number of marked vertices, which is a nontrivial generalization of the quantum counting algorithm for Grover's unstructured search.

The rest of the paper is organized as follows. In Section 2, we introduce the concept of continuous-time quantum walk and the search oracle used in our algorithm. We present our main result, the deterministic search algorithm on complete bipartite graphs in Section 2, and give the quantum counting algorithm on complete the bipartite graphs based on our search operator in Section 4. In Section 5, we implement the search algorithm in the quantum circuit model and simulate it on the IBM quantum computing platform qiskit. We discuss some related issues in Section 6 and conclude our result in Section 7.

2.

Preliminary

2.1.

Continuous-Time Quantum Walk

There are two types of quantum walks: discrete- and continuous-time. In this work we focus on the continuous-time quantum walk, which is a natural analog of the classical continuous-time random walk. Given a graph G = (V, E) with |V| = n, let p_j(t) be the probability associated with vertex j at time t and P(t) = (p₁(t),…,p_n(t))^T. A continuous-time random walk over G is a stochastic Markovian process that evolves as per the master equation (1) $\frac{d}{d t} P (t) = LP (t),$ {{\rm{d}} \over {{\rm{d}}t}}P(t) = LP(t), which can be seen as a discrete analog of the diffusion equation $\frac{1}{k} \frac{\partial u}{\partial t} = Δ u$ {1 \over k}{{\partial u} \over {\partial t}} = \Delta u . Here L is the discrete Laplacian of the graph (a discrete approximation of the Laplacian operator Δ in the continuum). The solution of this differential equation can be given in closed form as (2) $P (t) = e^{Lt} P (0) .$ P(t) = {e^{Lt}}P(0). Note that equation (1) closely resembles the Schrödinger equation (3) $i \frac{d}{d t} | ψ 〉 = H | ψ 〉,$ i{{\rm{d}} \over {{\rm{d}}t}}|\psi \rangle = H|\psi \rangle, except that equation (1) lacks the factor of i. A continuous-time quantum walk is then defined as the unitary process that evolves as per the Schrödinger equation (3) under any Hermitian Hamiltonian that respects the structure of G. We choose H to be the adjacency matrix of the graph in this paper, and the solution of equation (3) can be given in closed form as (4) $| ψ (t) 〉 = e^{- iAt} | ψ (0) 〉 .$ |\psi (t)\rangle = {{\rm{e}}^{- iAt}}|\psi (0)\rangle.

2.2.

Graph Notation and Search Oracle

A complete bipartite graph K_{m, n} is one whose vertex set V can be divided into two subsets V = V₁ ∪ V₂ and V₁ ∩ V₂ = ∅ with |V₁| = m and |V₂| = n, and whose edge set E = {{u, v} : u ∈ V₁, v ∈ V₂}. For quantum search on graphs, the corresponding Hilbert space is span{|0〉, |1〉, … , |m + n − 1〉}. We assume the marked vertices only occur in, say, the order-n part V₂ of the graph and denote the uniform superposition of the k marked vertices as $| w 〉 = \frac{1}{\sqrt{k}} \sum_{i = m}^{m + k - 1} | i 〉$ |w\rangle = {1 \over {\sqrt k}}\sum\nolimits_{i = m}^{m + k - 1} |i\rangle . This assumption is equivalent to saying that the oracle is local, acting on the subspace corresponding to the order-n part: (5) $O = {\begin{array}{l} I, in span {| 0 〉, \dots, | m - 1 〉}, \\ 2 | w 〉〈 w | - I, in span {| m 〉, \dots, | m + n - 1 〉} . \end{array}$ O = \left\{{\matrix{{I,\,{\kern 1pt} {\rm{in}}\,{\rm{span}}\{|0\rangle, \ldots,|m - 1\rangle \},} \hfill \cr {2|w\rangle \langle w| - I,\,{\rm{in}}\,{\rm{span}}\{|m\rangle, \ldots,|m + n - 1\rangle \}.} \hfill \cr}} \right. (Note that the definition differs from the standard definition by a phase −1.) In fact, such an oracle can be simulated by a standard global oracle. The standard oracle Õ is defined by making use of an oracle qubit |q〉: (6) $| i 〉 | q 〉 \overset{\tilde{O}}{\to} | i 〉 | q \oplus f (i) 〉,$ |i\rangle |q\rangle \mathop \to \limits^{\widetilde O} |i\rangle |q \oplus f(i)\rangle, f(i) equals 1 if vertex i is marked and equals 0 otherwise. If the oracle qubit is initially in the state $| - 〉 = \frac{| 0 〉 - | 1 〉}{\sqrt{2}}$ | - \rangle = {{|0\rangle - |1\rangle} \over {\sqrt 2}} , then the action of the oracle is (7) $| i 〉 | - 〉 \overset{\tilde{O}}{\to} {(- 1)}^{f (x)} | i 〉 | - 〉,$ |i\rangle | - \rangle \mathop \to \limits^{\widetilde O} {(- 1)^{f(x)}}|i\rangle | - \rangle, leaving the oracle qubit unchanged. We append an ancillary qubit |b〉 to indicate which part a state belongs to: |b = 0〉|v〉 means that |v〉 is in the order-m part and |b = 1〉|v〉 means that |v〉 is in the order-n part. This is possible since the underlying graph is assumed to be known. Let C_jZ be the Z gate controlled by the ancilla being in state |b = j〉 with target on the oracle qubit. The local oracles are implemented by (8) $O_{j} = - C_{j} Z \cdot \tilde{O} \cdot C_{j} Z$ {O_j} = - {C_j}Z \cdot \widetilde O \cdot {C_j}Z with the oracle qubit initiated in $| + 〉 = \frac{| 0 〉 + | 1 〉}{\sqrt{2}}$ | + \rangle = {{|0\rangle + |1\rangle} \over {\sqrt 2}} state [33]. O₁ is then the oracle in equation (5) and the corresponding circuit is shown in Figure 1.

In the general case of marked vertices distributing in both partite sets, one can search in two steps, first for the marked vertices in one part (with the corresponding local oracle) and then for the other part. Our quantum walk search operator is (9) $U (t) = e^{- iAt} O,$ U(t) = {e^{- iAt}}O, where A is the adjacency matrix of the complete bipartite graph.

3.

Deterministic Spatial Search Algorithm

Grover's original search algorithm is the iteration of the operator G = (I − 2|ψ〉〈ψ|)O, where O denotes the oracle and |ψ〉 is the uniform superposition of all states. One of the deterministic versions of Grover's search is to introduce an arbitrary phase to the reflection (I − 2|ψ〉〈ψ|), obtaining a generalized search operator G(α) = (I − (1 − e^iα)|ψ〉〈ψ|)O [34]. By choosing an appropriate phase α and iteration number, one can obtain a final state that is the superposition of all marked vertices. Our search operator is a further generalization, replacing the Grover diffusion operator (I − 2|ψ〉〈ψ|) with a quantum walk operator on complete bipartite graphs. By setting an appropriate walk time and iteration number, the system will reach a final state of superposition of all marked states.

Let $| s 〉 = \frac{1}{\sqrt{m}} \sum_{i = 0}^{m - 1} | i 〉$ |s\rangle = {1 \over {\sqrt m}}\sum\nolimits_{i = 0}^{m - 1} |i\rangle be the uniform superposition of states corresponding to the order-m part, and $| \bar{w} 〉 = \frac{1}{\sqrt{n - k}} \sum_{i = m + k}^{m + n - 1} | i 〉$ |\overline w \rangle = {1 \over {\sqrt {n - k}}}\sum\nolimits_{i = m + k}^{m + n - 1} |i\rangle be the complement of |w〉 in the order-n part. These three states group together vertices that evolve identically by symmetry, thus span{|s〉, |w, |w̄〉} is an invariant subspace of A, with the reduced adjacency matrix in this subspace being (10) $A = (\begin{matrix} 0 & \sqrt{mk} & \sqrt{m (n - k)} \\ \sqrt{mk} & 0 & 0 \\ \sqrt{m (n - k)} & 0 & 0 \end{matrix}) .$ A = \left({\matrix{0 & {\sqrt {mk}} & {\sqrt {m(n - k)}} \cr {\sqrt {mk}} & 0 & 0 \cr {\sqrt {m(n - k)}} & 0 & 0 \cr}} \right). This matrix has eigenvalues 0, $\pm \sqrt{mn}$ \pm \sqrt {mn} with eigenvectors (11) $\begin{array}{l} | v_{0} 〉 = \sqrt{\frac{n - k}{n}} | w 〉 - \sqrt{\frac{k}{n}} | \bar{w} 〉, \\ | v_{\pm \sqrt{mn}} 〉 = \frac{1}{\sqrt{2}} | s 〉 \pm \sqrt{\frac{k}{2 n}} | w 〉 \pm \sqrt{\frac{n - k}{2 n}} | \bar{w} 〉, \end{array}$ \matrix{{|{v_0}\rangle = \sqrt {{{n - k} \over n}} |w\rangle - \sqrt {{k \over n}} |\overline w \rangle,} \hfill \cr {|{v_{\pm \sqrt {mn}}}\rangle = {1 \over {\sqrt 2}}|s\rangle \pm \sqrt {{k \over {2n}}} |w\rangle \pm \sqrt {{{n - k} \over {2n}}} |\overline w \rangle,} \hfill \cr} where the subscripts are the corresponding eigenvalues.

From this spectrum decomposition, we have (12) $\begin{array}{l} e^{- iAt} & = | v_{0} 〉〈 v_{0} | + e^{- it \sqrt{mn}} | v_{\sqrt{mn}} 〉〈 v_{\sqrt{mn}} | + e^{it \sqrt{mn}} | v_{- \sqrt{mn}} 〉〈 v_{- \sqrt{mn}} | \\ = (\begin{matrix} cos (\sqrt{mn} t) & - i \sqrt{\frac{k}{n}} sin (\sqrt{mn} t) & - i \sqrt{\frac{n - k}{n}} sin (\sqrt{mn} t) \\ - i \sqrt{\frac{k}{n}} sin (\sqrt{mn} t) & \frac{n - k}{n} + \frac{k}{n} cos (\sqrt{mn} t) & - \frac{\sqrt{k (n - k)}}{n} (1 - cos (\sqrt{mn} t)) \\ - i \sqrt{\frac{n - k}{n}} sin (\sqrt{mn} t) & - \frac{\sqrt{k (n - k)}}{n} (1 - cos (\sqrt{mn} t)) & \frac{k}{n} + \frac{n - k}{n} cos (\sqrt{mn} t) \end{matrix}) . \end{array}$ \matrix{{{e^{- iAt}}} \hfill & {= |{v_0}\rangle \langle {v_0}| + {e^{- it\sqrt {mn}}}|{v_{\sqrt {mn}}}\rangle \langle {v_{\sqrt {mn}}}| + {e^{it\sqrt {mn}}}|{v_{- \sqrt {mn}}}\rangle \langle {v_{- \sqrt {mn}}}|} \hfill \cr {} \hfill & {= \left({\matrix{{\cos (\sqrt {mn} t)} & {- i\sqrt {{k \over n}} \sin (\sqrt {mn} t)} & {- i\sqrt {{{n - k} \over n}} \sin (\sqrt {mn} t)} \cr {- i\sqrt {{k \over n}} \sin (\sqrt {mn} t)} & {{{n - k} \over n} + {k \over n}\cos (\sqrt {mn} t)} & {- {{\sqrt {k(n - k)}} \over n}(1 - \cos (\sqrt {mn} t))} \cr {- i\sqrt {{{n - k} \over n}} \sin (\sqrt {mn} t)} & {- {{\sqrt {k(n - k)}} \over n}(1 - \cos (\sqrt {mn} t))} & {{k \over n} + {{n - k} \over n}\cos (\sqrt {mn} t)} \cr}} \right).} \hfill \cr} It follows that (13) $U (t) = (\begin{matrix} cos (\sqrt{mn} t) & - i \sqrt{\frac{k}{n}} sin (\sqrt{mn} t) & i \sqrt{\frac{n - k}{n}} sin (\sqrt{mn} t) \\ - i \sqrt{\frac{k}{n}} sin (\sqrt{mn} t) & \frac{n - k}{n} + \frac{k}{n} cos (\sqrt{mn} t) & \frac{\sqrt{k (n - k)}}{n} (1 - cos (\sqrt{mn} t)) \\ - i \sqrt{\frac{n - k}{n}} sin (\sqrt{mn} t) & - \frac{\sqrt{k (n - k)}}{n} (1 - cos (\sqrt{mn} t)) & - \frac{k}{n} - \frac{n - k}{n} cos (\sqrt{mn} t) \end{matrix}) .$ U(t) = \left({\matrix{{\cos (\sqrt {mn} t)} & {- i\sqrt {{k \over n}} \sin (\sqrt {mn} t)} & {i\sqrt {{{n - k} \over n}} \sin (\sqrt {mn} t)} \cr {- i\sqrt {{k \over n}} \sin (\sqrt {mn} t)} & {{{n - k} \over n} + {k \over n}\cos (\sqrt {mn} t)} & {{{\sqrt {k(n - k)}} \over n}(1 - \cos (\sqrt {mn} t))} \cr {- i\sqrt {{{n - k} \over n}} \sin (\sqrt {mn} t)} & {- {{\sqrt {k(n - k)}} \over n}(1 - \cos (\sqrt {mn} t))} & {- {k \over n} - {{n - k} \over n}\cos (\sqrt {mn} t)} \cr}} \right).

Solving the characteristic polynomial $det (λ I - U) = (λ + 1) (λ^{2} - [\frac{2 n - 2 k}{n} + \frac{2 k}{n} cos (\sqrt{mn} t)] λ + 1)$ \det (\lambda I - U) = (\lambda + 1)({\lambda^2} - [{{2n - 2k} \over n} + {{2k} \over n}\cos (\sqrt {mn} t)]\lambda + 1) , we obtain the eigenphases (14) $π, θ_{\pm} = \pm 2 arcsin (\sqrt{\frac{k}{n}} sin (\frac{\sqrt{mn} t}{2})) .$ \pi,{\kern 1pt} {\theta_ \pm} = \pm 2\arcsin \left({\sqrt {{k \over n}} \sin ({{\sqrt {mn} t} \over 2})} \right). The corresponding eigenvectors are (15) $\begin{array}{l} | v_{- 1} 〉 = \frac{1}{N} (- i \sqrt{\frac{n - k}{n}} sin (\frac{\sqrt{mn} t}{2}) | s 〉 + cos (\frac{\sqrt{mn} t}{2}) | \bar{w} 〉), \\ | v_{\pm} 〉 = \frac{1}{N} (\frac{1}{\sqrt{2}} cos (\frac{\sqrt{mn} t}{2}) | s 〉 \mp \frac{1}{\sqrt{2}} \sqrt{1 - \frac{k}{n} {sin}^{2} (\frac{\sqrt{mn} t}{2})} | w 〉 - i \frac{1}{\sqrt{2}} \sqrt{\frac{n - k}{n}} sin (\frac{\sqrt{mn} t}{2}) | \bar{w} 〉), \end{array}$ \matrix{{} \hfill & {|{v_{- 1}}\rangle = {1 \over N}(- i\sqrt {{{n - k} \over n}} \sin ({{\sqrt {mn} t} \over 2})|s\rangle + \cos ({{\sqrt {mn} t} \over 2})|\overline w \rangle),} \hfill \cr {} \hfill & {|{v_ \pm}\rangle = {1 \over N}({1 \over {\sqrt 2}}\cos ({{\sqrt {mn} t} \over 2})|s\rangle \mp {1 \over {\sqrt 2}}\sqrt {1 - {k \over n}\mathop {\sin}\nolimits^2 ({{\sqrt {mn} t} \over 2})} |w\rangle - i{1 \over {\sqrt 2}}\sqrt {{{n - k} \over n}} \sin ({{\sqrt {mn} t} \over 2})|\overline w \rangle),} \hfill \cr} where $N = \sqrt{1 - \frac{k}{n} {sin}^{2} (\frac{\sqrt{mn} t}{2})}$ N = \sqrt {1 - {k \over n}\mathop {\sin}\nolimits^2 ({{\sqrt {mn} t} \over 2})} is the normalization factor. Define matrices V = (|v₋₁〉 |v₊〉 |v₋〉) and D = diag{e^iπ, e^iθ₊, e^iθ₋}, then $U^{l} = V D^{l} V^{†} .$ {U^l} = V{D^l}{V^\dagger}.

Since |s〉 is not the superposition of all states, we perform a preprocessing step, evolving |s〉 through the walk operator for time $\frac{t}{2}$ {t \over 2} (the $\frac{1}{2}$ {1 \over 2} factor is chosen to facilitate the computation below): (16) $\begin{array}{l} e^{- iA \frac{t}{2}} | s 〉 = & cos (\frac{\sqrt{mn} t}{2}) | s 〉 - i \sqrt{\frac{k}{n}} sin (\frac{\sqrt{mn} t}{2}) | w 〉 - i \sqrt{\frac{n - k}{n}} sin (\frac{\sqrt{mn} t}{2}) | \bar{w} 〉 . \end{array}$ \matrix{{{e^{- iA{t \over 2}}}|s\rangle =} \hfill & {\cos ({{\sqrt {mn} t} \over 2})|s\rangle - i\sqrt {{k \over n}} \sin ({{\sqrt {mn} t} \over 2})|w\rangle - i\sqrt {{{n - k} \over n}} \sin ({{\sqrt {mn} t} \over 2})|\overline w \rangle.} \hfill \cr} Using this state as the initial state, we evolve it through the unitary U(t), and then by an appropriate choice of the time t and the iteration number l, we hope that the final state $U^{l} e^{- iA \frac{t}{2}} | s 〉$ {U^l}{e^{- iA{t \over 2}}}|s\rangle have a unit overlap with |w〉.

We evaluate the value of $〈 w | U^{l} e^{- iA \frac{t}{2}} | s 〉$ \langle w|{U^l}{e^{- iA{t \over 2}}}|s\rangle by using the matrix representation of the states and operators in the subspace: (17) $\begin{array}{l} 〈 w | U^{l} e^{- iA \frac{t}{2}} | s 〉 & = (0, 1, 0) V D^{l} V^{†} e^{- iA \frac{t}{2}} | s 〉 \\ = (0, - \frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}) D^{l} V^{†} e^{- iA \frac{t}{2}} | s 〉 \\ = (0, - \frac{1}{\sqrt{2}} e^{il θ}, \frac{1}{\sqrt{2}} e^{- il θ}) V^{†} e^{- iA \frac{t}{2}} | s 〉 \\ = (- i \frac{1}{N} cos (\frac{\sqrt{mn} t}{2}) sin (l θ), cos (l θ), \frac{1}{N} \sqrt{\frac{n - k}{n}} sin (\frac{\sqrt{mn} t}{2}) sin (l θ)) e^{- iA \frac{t}{2}} | s 〉 \\ = - i [\sqrt{1 - \frac{k}{n} {sin}^{2} (\frac{\sqrt{mn} t}{2})} sin (l θ) + \sqrt{\frac{k}{n}} sin (\frac{\sqrt{mn} t}{2}) cos (l θ)] . \end{array}$ \matrix{{\langle w|{U^l}{e^{- iA{t \over 2}}}|s\rangle} \hfill & {= (0,1,0)V{D^l}{V^\dagger}{e^{- iA{t \over 2}}}|s\rangle} \hfill \cr {} \hfill & {= \left({0, - {1 \over {\sqrt 2}},{1 \over {\sqrt 2}}} \right){D^l}{V^\dagger}{e^{- iA{t \over 2}}}|s\rangle} \hfill \cr {} \hfill & {= \left({0, - {1 \over {\sqrt 2}}{e^{il\theta}},{1 \over {\sqrt 2}}{e^{- il\theta}}} \right){V^\dagger}{e^{- iA{t \over 2}}}|s\rangle} \hfill \cr {} \hfill & {= \left({- i{1 \over N}\cos ({{\sqrt {mn} t} \over 2})\sin (l\theta),\cos (l\theta),{1 \over N}\sqrt {{{n - k} \over n}} \sin ({{\sqrt {mn} t} \over 2})\sin (l\theta)} \right){e^{- iA{t \over 2}}}|s\rangle} \hfill \cr {} \hfill & {= - i\left[ {\sqrt {1 - {k \over n}\mathop {\sin}\nolimits^2 ({{\sqrt {mn} t} \over 2})} \sin (l\theta) + \sqrt {{k \over n}} \sin ({{\sqrt {mn} t} \over 2})\cos (l\theta)} \right].} \hfill \cr}

Here we make a variable substitution (18) $sin (\frac{\sqrt{mn} t}{2}) = \sqrt{\frac{n}{k}} sin (\frac{π}{2} x) .$ \sin ({{\sqrt {mn} t} \over 2}) = \sqrt {{n \over k}} \sin \left({{\pi \over 2}x} \right). It follows that $\sqrt{1 - \frac{k}{n} {sin}^{2} (\frac{\sqrt{mn} t}{2})} = cos (\frac{π}{2} x)$ \sqrt {1 - {k \over n}\mathop {\sin}\nolimits^2 ({{\sqrt {mn} t} \over 2})} = \cos ({\pi \over 2}x) and (19) $θ = 2 arcsin (\sqrt{\frac{k}{n}} sin (\frac{\sqrt{mn} t}{2})) = π x .$ \theta = 2\arcsin \left({\sqrt {{k \over n}} \sin ({{\sqrt {mn} t} \over 2})} \right) = \pi x. The overlap now is (20) $\begin{array}{l} i 〈 w | U^{l} e^{- iA \frac{t}{2}} | s 〉 & = sin (l θ) cos (\frac{π}{2} x) + cos (l θ) sin (\frac{π}{2} x) \\ = sin (l θ + \frac{π}{2} x) \\ = sin [(2 l + 1) \frac{π}{2} x] . \end{array}$ \matrix{{i\langle w|{U^l}{e^{- iA{t \over 2}}}|s\rangle} \hfill & {= \sin (l\theta)\cos ({\pi \over 2}x) + \cos (l\theta)\sin ({\pi \over 2}x)} \hfill \cr {} \hfill & {= \sin (l\theta + {\pi \over 2}x)} \hfill \cr {} \hfill & {= \sin [(2l + 1){\pi \over 2}x].} \hfill \cr} Therefore, setting $x = \frac{1}{2 l + 1}$ x = {1 \over {2l + 1}} , or equivalently, (21) $\begin{array}{l} t = & \frac{2}{\sqrt{mn}} arcsin [\sqrt{\frac{n}{k}} sin (\frac{π}{2} x)] \\ = & \frac{2}{\sqrt{mn}} arcsin [\sqrt{\frac{n}{k}} sin (\frac{π}{2 (2 l + 1)})], \end{array}$ \matrix{{t =} \hfill & {{2 \over {\sqrt {mn}}}\arcsin [\sqrt {{n \over k}} \sin ({\pi \over 2}x)]} \hfill \cr = \hfill & {{2 \over {\sqrt {mn}}}\arcsin [\sqrt {{n \over k}} \sin ({\pi \over {2(2l + 1)}})],} \hfill \cr} we have $| 〈 w | U^{l} e^{- iA \frac{t}{2}} | s 〉 | = 1$ |\langle w|{U^l}{e^{- iA{t \over 2}}}|s\rangle | = 1 . Note that $\sqrt{\frac{n}{k}} sin (\frac{π}{2 (2 l + 1)}) \leq 1$ \sqrt {{n \over k}} \sin ({\pi \over {2(2l + 1)}}) \le 1 from equation (21), that is, (22) $\frac{π}{2 (2 l + 1)} \leq arcsin \sqrt{\frac{k}{n}},$ {\pi \over {2(2l + 1)}} \le \arcsin \sqrt {{k \over n}}, let $\frac{π}{2 (2 l + 1)} \leq \sqrt{\frac{k}{n}}$ {\pi \over {2(2l + 1)}} \le \sqrt {{k \over n}} , that is, the requirement on l is (23) $l \geq \frac{π}{4} \sqrt{\frac{n}{k}} - \frac{1}{2},$ l \ge {\pi \over 4}\sqrt {{n \over k}} - {1 \over 2}, then since x < arcsin x for 0 < x < 1, equation (22) is satisfied.

We formalize the above result into a theorem and thus obtain our deterministic spatial search algorithm (see Algorithm 1).

Algorithm 1 : Deterministic search algorithm on complete bipartite graphs.
Input: A complete bipartite graph K_m,n with k marked vertices on the order-n part whose adjacency matrix is A, an oracle O that satisfies equation (5).
Output: A marked vertex.
1: Calculate parameters $l = ⌈ \frac{π}{4} \sqrt{\frac{n}{k}} - \frac{1}{2} ⌉$ l = \left\lceil {{\pi \over 4}\sqrt {{n \over k}} - {1 \over 2}} \right\rceil and $t = \frac{2}{\sqrt{mn}} arcsin [\sqrt{\frac{n}{k}} sin (\frac{π}{2 (2 l + 1)})]$ t = {2 \over {\sqrt {mn}}}\arcsin \left[ {\sqrt {{n \over k}} \sin ({\pi \over {2(2l + 1)}})} \right] .
2: Construct the initial state $\| s 〉 = \frac{1}{\sqrt{m}} \sum_{i = 0}^{m - 1} \| i 〉$ \|s\rangle = {1 \over {\sqrt m}}\sum\nolimits_{i = 0}^{m - 1} \|i\rangle .
3: Perform quantum walk search $U^{l} (t) e^{- iA \frac{t}{2}} \| s 〉 = {(e^{- iAt} O)}^{l} e^{- iA \frac{t}{2}} \| s 〉$ {U^l}(t){e^{- iA{t \over 2}}}\|s\rangle = {({{\rm{e}}^{- iAt}}O)^l}{{\rm{e}}^{- iA{t \over 2}}}\|s\rangle .
4: Measure the final state and get \|i〉.
5: Return vertex i.

Theorem 1

Let K_m,n be a complete bipartite graph with k marked vertices on the order-n part and A be its adjacency matrix. For any $l \geq \frac{π}{4} \sqrt{\frac{n}{k}} - \frac{1}{2}$ l \ge {\pi \over 4}\sqrt {{n \over k}} - {1 \over 2} and $t = \frac{2}{\sqrt{mn}} arcsin [\sqrt{\frac{n}{k}} sin (\frac{π}{2 (2 l + 1)})]$ t = {2 \over {\sqrt {mn}}}\arcsin [\sqrt {{n \over k}} \sin ({\pi \over {2(2l + 1)}})] , starting from the state $| s 〉 = \frac{1}{\sqrt{m}} \sum_{i = 0}^{m - 1} | i 〉$ |s\rangle = {1 \over {\sqrt m}}\sum\nolimits_{i = 0}^{m - 1} |i\rangle , algorithm $U^{l} (t) e^{- iA \frac{t}{2}}$ {U^l}(t){e^{- iA{t \over 2}}} returns a final state of uniform superposition of all marked vertices with certainty.

4.

Quantum Counting for Spatial Search

The algorithmic parameters l and t depend on the number of marked vertices k, as indicated by equations (23) and (21). Therefore, when the number of marked vertices is unknown, it is necessary to estimate k before applying the algorithm. We first review the quantum counting algorithm in the context of unstructured search, and then show how a similar idea can be applied to spatial search via our search operator.

We adopt the notation in [34] and give the following definition:

Definition 1

For any integer M > 0 and real number 0 ≤ ω < 1, let $| S_{M} (ω) 〉 = \frac{1}{\sqrt{M}} \sum_{y = 0}^{M - 1} e^{2 π i ω y} | y 〉 .$ |{S_M}(\omega)\rangle = {1 \over {\sqrt M}}\sum\limits_{y = 0}^{M - 1} {{\rm{e}}^{2\pi i\omega y}}|y\rangle. We then have, for integers 0 ≤ j ≤ M − 1, the Fourier basis $F_{M} | j 〉 = | S_{M} (\frac{j}{M}) 〉$ {F_M}|j\rangle = |{S_M}({j \over M})\rangle for the space span{|j〉, 0 ≤ j ≤ M − 1}.

We expand |ϕ₀〉 = ∑α_j|θ_j〉 in the eigenphases of U, and thus with probability |α_j|², the state of the second register would be |θ_j〉. After step 2 of the algorithm, the state of the first register will be (24) $\frac{1}{\sqrt{M}} \sum_{l = 0}^{M - 1} e^{il θ_{j}} | l 〉 = | S_{M} (\frac{θ_{j}}{2 π}) 〉$ {1 \over {\sqrt M}}\sum\limits_{l = 0}^{M - 1} {e^{il{\theta_j}}}|l\rangle = |{S_M}({{{\theta_j}} \over {2\pi}})\rangle (25) $= \sum_{l = 0}^{M - 1} f_{l} F_{M} | l 〉,$ = \sum\limits_{l = 0}^{M - 1} {f_l}{F_M}|l\rangle, provided that the state in the second register is |θ_j〉 (with probability |α_j|²). We expand the state in Fourier basis in equation (25). Step 3 performs the inverse Fourier transform, hence with probability |f_l|², step 4 will measure the result l. If |ϕ₀〉 is one of the eigenvectors |θ_j〉 of the unitary U, the following theorem from [34] ensures that $\tilde{θ} = 2 π \frac{l}{M}$ \tilde \theta = 2\pi {l \over M} is an estimation of θ_j with error at most $\frac{2 π}{M}$ {{2\pi} \over M} with probability at least $\frac{8}{π^{2}}$ {8 \over {{\pi^2}}} (≈0.81).

Theorem 2

Let M = 2^p, p is the number of ancillary qubits in Algorithm 2. If $\frac{θ}{2 π}$ {\theta \over {2\pi}} M is an integer, then Algorithm 2 returns the exact value of the phase θ with certainty: (26) $Prob (l = \frac{θ}{2 π} M) = 1 .$ {\rm{Prob}}(l = {\theta \over {2\pi}}M) = 1. Otherwise, the algorithm returns an estimation of the phase θ with error $\frac{2 π}{M}$ {{2\pi} \over M} with probability (27) $\begin{array}{l} Prob (l = ⌊ \frac{θ}{2 π} M ⌋) + Prob (l = ⌈ \frac{θ}{2 π} M ⌉) \\ = & \frac{{sin}^{2} [M Δ_{1} π]}{M^{2} {sin}^{2} [Δ_{1} π]} + \frac{{sin}^{2} [M Δ_{2} π]}{M^{2} {sin}^{2} [Δ_{2} π]} \geq \frac{8}{π^{2}}, \end{array}$ \matrix{{} \hfill & {{\rm{Prob}}(l = \left\lfloor {{\theta \over {2\pi}}M} \right\rfloor) + {\rm{Prob}}(l = \left\lceil {{\theta \over {2\pi}}M} \right\rceil)} \hfill \cr = \hfill & {{{\mathop {\sin}\nolimits^2 [M{\Delta_1}\pi ]} \over {{M^2}\mathop {\sin}\nolimits^2 [{\Delta_1}\pi ]}} + {{\mathop {\sin}\nolimits^2 [M{\Delta_2}\pi ]} \over {{M^2}\mathop {\sin}\nolimits^2 [{\Delta_2}\pi ]}} \ge {8 \over {{\pi^2}}},} \hfill \cr} where $Δ_{1} = \frac{1}{M} (\frac{θ_{j}}{2 π} M - ⌊ \frac{θ}{2 π} M ⌋)$ {\Delta_1} = {1 \over M}({{{\theta_j}} \over {2\pi}}M - \left\lfloor {{\theta \over {2\pi}}M} \right\rfloor) , $Δ_{2} = \frac{1}{M} (⌈ \frac{θ}{2 π} M ⌉ - \frac{θ_{j}}{2 π} M)$ {\Delta_2} = {1 \over M}(\left\lceil {{\theta \over {2\pi}}M} \right\rceil - {{{\theta_j}} \over {2\pi}}M) .

Algorithm 2 : Quantum Phase Estimation (QPE).
Input: A unitary U, initial state \|0〉^⊗p\|ϕ₀ (p is the number of qubits in the first register and \|ϕ₀〉 is an arbitrary state of the second register).
Output: An estimate θ̃ of one of the eigenphases of U.
1: Apply Hadamard gate H to each qubit in the first register.
2: Apply U^{2^j} on the second register controlled by qubit j, 1 ≤ j ≤ p in the first register.
3: Apply inverse quantum Fourier transform to the first register.
4: Measure the first register in the computational basis and get the result l.
5: Return $\tilde{θ} = 2 π \frac{l}{M} (M = 2^{p})$ \tilde \theta = 2\pi {l \over M}(M = {2^p}) .

Intuitively, quantum phase estimation works as follows. The eigenvalues of a unitary lie on a unit circle. Divide the circle into M parts. QPE can only obtain an estimation of the eigenphases from the set $Ω_{M} = {\frac{j}{M} 2 π, 0 \leq j \leq M - 1}$ {\Omega_M} = \{{j \over M}2\pi,0 \le j \le M - 1\} . Hence, for eigenphase θ in Figure 2, the best estimation is θ⁻ or θ⁺ (with error at most $\frac{2 π}{M}$ {{2\pi} \over M} ) as depicted in Figure 2, which corresponds to the measured result of $⌊ \frac{θ}{2 π} M ⌋$ \left\lfloor {{\theta \over {2\pi}}M} \right\rfloor or $⌈ \frac{θ}{2 π} M ⌉$ \left\lceil {{\theta \over {2\pi}}M} \right\rceil . Theorem 2 then states that the probability of obtaining this best estimation is at least $\frac{8}{π^{2}}$ {8 \over {{\pi^2}}} . Specially, in the case of θ ∈ Ω_M, one obtain the result θ with certainty.

For unstructured search with k marked vertices, the initial state (i.e., the uniform superposition state of all vertices) may be re-expressed as (28) $| ψ 〉 = \sqrt{\frac{N - k}{N}} | α 〉 + \sqrt{\frac{k}{N}} | β 〉,$ |\psi \rangle = \sqrt {{{N - k} \over N}} |\alpha \rangle + \sqrt {{k \over N}} |\beta \rangle, where $| α 〉 = \frac{1}{\sqrt{N - k}} \sum_{i unmarked} | i 〉$ |\alpha \rangle = {1 \over {\sqrt {N - k}}}\sum\nolimits_{i{\kern 1pt} {\rm{unmarked}}} |i\rangle and $| β 〉 = \frac{1}{\sqrt{k}} \sum_{i marked} | i 〉$ |\beta \rangle = {1 \over {\sqrt k}}\sum\nolimits_{i{\kern 1pt} {\rm{marked}}} |i\rangle . In the two-dimensional subspace span{|α〉, |β〉}, the Grover operator G = (I − 2|ψ〉〈ψ|)O is a rotation operator of angle θ with eigenvalues e^iθ and e^i(2π−θ) [32]. The quantum counting algorithm for Grover's search is based on the observation that (29) ${sin}^{2} (\frac{θ}{2}) = {sin}^{2} (\frac{2 π - θ}{2}) = \frac{k}{N} .$ \mathop {\sin}\nolimits^2 \left({{\theta \over 2}} \right) = \mathop {\sin}\nolimits^2 \left({{{2\pi - \theta} \over 2}} \right) = {k \over N}. Hence utilizing the phase estimation algorithm (see Algorithm 2) which outputs (an estimation of) the eigenphases of unitary operators, one can estimate the number of marked vertices through equation (29).

Apparently, this counting algorithm cannot be directly applied to complete bipartite graphs. Fortunately, the special spectrum structure of the algorithmic operator U(t) allows us to construct a simple quantum counting algorithm by employing quantum phase estimation in a similar fashion. The problem concerning QPE is that the input state |ϕ₀〉 is not an eigenvector in general and one would not be able to determine which eigenvalue corresponds to the estimation result. Fortunately, we can circumvent this difficulty as equation (29) does in the context of unstructured search. The key is that the spectrum of our evolutionary operator consists of a conjugate pair and −1. We evaluate k by rewriting equation (14) for θ_±: (30) $k = {(\frac{sin \frac{θ_{\pm}}{2}}{sin (\frac{\sqrt{mn}}{2} t)})}^{2} n .$ k = {({{\sin {{{\theta_ \pm}} \over 2}} \over {\sin ({{\sqrt {mn}} \over 2}t)}})^2}n. If we take $t = t_{0} = \frac{π}{\sqrt{mn}}$ t = {t_0} = {\pi \over {\sqrt {mn}}} , then $θ_{\pm} = 2 arcsin \sqrt{\frac{k}{n}} \leq 2 arcsin \frac{1}{\sqrt{2}} = \frac{π}{2}$ {\theta_ \pm} = 2\arcsin \sqrt {{k \over n}} \le 2\arcsin {1 \over {\sqrt 2}} = {\pi \over 2} provided that $k < \frac{n}{2}$ k < {n \over 2} , and (31) $k = {(sin \frac{θ_{\pm}}{2})}^{2} n .$ k = {(\sin {{{\theta _ \pm }} \over 2})^2}n. Note that equation (31) is the counterpart of equation (29) in the setting of spatial search. The eigenphase distribution of U(t₀) on the unit circle is shown in Figure 3. The eigenvectors in (15) now become (32) $\begin{array}{l} | v_{- 1} 〉 = - i | s 〉, \\ | v_{\pm} 〉 = \frac{\mp | w 〉 - i | \bar{w} 〉}{\sqrt{2}} . \end{array}$ \matrix{{} \hfill & {|{v_{- 1}}\rangle = - i|s\rangle,} \hfill \cr {} \hfill & {|{v_ \pm}\rangle = {{\mp |w\rangle - i|\bar w\rangle} \over {\sqrt 2}}.} \hfill \cr} Note that we can expend the uniform superposition state in this basis {|v₋₁〉, |v₊〉, |v₋〉} as follows: (33) $| ψ 〉 = \frac{1}{\sqrt{m + n}} (i \sqrt{m} | v_{- 1} 〉 + (i \sqrt{n - k} - \sqrt{k}) \frac{| v_{+} 〉 - | v_{-} 〉}{\sqrt{2}}) .$ |\psi \rangle = {1 \over {\sqrt {m + n}}}(i\sqrt m |{v_{- 1}}\rangle + (i\sqrt {n - k} - \sqrt k){{|{v_ +}\rangle - |{v_ -}\rangle} \over {\sqrt 2}}). Our quantum counting algorithm for complete bipartite graphs is to apply QPE to the operator U(t₀) starting with the state |0〉^⊗p|ψ〉. |ψ〉 will be in the state |v₋₁〉 with probability $\frac{m}{m + n}$ {m \over {m + n}} . In this case, we would measure −1 with certainty, which we discard. We then assume that |ψ〉 be in either |v₊〉 or |v₋〉. Theorem 2 then guarantees that we can obtain an estimate of the eigenphases θ_± with error $\frac{2 π}{M}$ {{2\pi} \over M} with probability at least $\frac{8}{π^{2}}$ {8 \over {{\pi^2}}} , from which we can evaluate k.

Theorem 3 (Quantum Counting on Complete Bipartite Graphs)

Algorithm 3 output an estimation k̃ of the number of marked vertices k with precision δ with success probability at least $\frac{8}{π^{2}}$ {8 \over {{\pi^2}}} .

Proof

Followed from Theorem 2, $| \tilde{θ} - θ | \leq ε = \frac{2 π}{M}$ |\tilde \theta - \theta | \le \varepsilon = {{2\pi} \over M} with probability $\frac{8}{π^{2}}$ {8 \over {{\pi^2}}} . Then $| \tilde{k} - k | = | {(sin \frac{\tilde{θ}}{2})}^{2} - {(sin \frac{θ}{2})}^{2} | n$ |\tilde k - k| = |{(\sin {{\tilde \theta} \over 2})^2} - {(\sin {\theta \over 2})^2}|n by (31). Using trigonometric identities, we obtain (34) $\begin{array}{l} {sin}^{2} (\frac{θ}{2} + \frac{ε}{2}) - {sin}^{2} (\frac{θ}{2}) = & cos \frac{θ}{2} sin \frac{θ}{2} sin ε + cos θ {sin}^{2} \frac{ε}{2}, \\ {sin}^{2} (\frac{θ}{2}) - {sin}^{2} (\frac{θ}{2} - \frac{ε}{2}) = & cos \frac{θ}{2} sin \frac{θ}{2} sin ε - cos θ {sin}^{2} \frac{ε}{2} . \end{array}$ \matrix{{\mathop {\sin}\nolimits^2 ({\theta \over 2} + {\varepsilon \over 2}) - \mathop {\sin}\nolimits^2 ({\theta \over 2}) =} \hfill & {\cos {\theta \over 2}\sin {\theta \over 2}\sin \varepsilon + \cos \theta \mathop {\sin}\nolimits^2 {\varepsilon \over 2},} \hfill \cr {\mathop {\sin}\nolimits^2 ({\theta \over 2}) - \mathop {\sin}\nolimits^2 ({\theta \over 2} - {\varepsilon \over 2}) =} \hfill & {\cos {\theta \over 2}\sin {\theta \over 2}\sin \varepsilon - \cos \theta \mathop {\sin}\nolimits^2 {\varepsilon \over 2}.} \hfill \cr} It follows that (35) $\begin{array}{l} | \tilde{k} - k | \leq n (\sqrt{1 - \frac{k}{n}} \sqrt{\frac{k}{n}} ε + \frac{ε^{2}}{4}) & = \frac{2 π}{M} \sqrt{k (n - k)} + \frac{π^{2}}{M^{2}} n \\ = \sqrt{k (n - k)} ε + \frac{n}{4} ε^{2} \\ = \frac{5 n}{4} ε = \frac{5 n π}{2 M} \\ \leq δ . \end{array}$ \matrix{{|\tilde k - k| \le n(\sqrt {1 - {k \over n}} \sqrt {{k \over n}} \varepsilon + {{{\varepsilon^2}} \over 4})} \hfill & {= {{2\pi} \over M}\sqrt {k(n - k)} + {{{\pi^2}} \over {{M^2}}}n} \hfill \cr {} \hfill & {= \sqrt {k(n - k)} \varepsilon + {n \over 4}{\varepsilon^2}} \hfill \cr {} \hfill & {= {{5n} \over 4}\varepsilon = {{5n\pi} \over {2M}}} \hfill \cr {} \hfill & {\le \delta.} \hfill \cr}

Algorithm 3 : Quantum counting for search on complete bipartite graphs.
Input: Unitary U(t₀), initial state\|0〉^⊗p\|ψ〉 ( $p = ⌈ {log}_{2} \frac{5 n π}{2 δ} ⌉$ p = \left\lceil {{{\log}_2}\,{{5n\pi} \over {2\delta}}} \right\rceil is the number of qubits in the first register and δ is the desired precision).
Output: Estimation k̃ of the number of marked vertices k with precision δ.
1: Call Algorithm 2 and get the result θ̃.
2: if θ̃ = π
then discard;
else
$\tilde{k} = {(sin \frac{\tilde{θ}}{2})}^{2} n$ \tilde k = {\left({\sin {{\tilde \theta} \over 2}} \right)^2}n .
3: Return k̃.

5.

Circuit Implementation and Simulation

The heart of the circuit implementation of our algorithm lies in the implementation of operator e^−iAt. We follow the method of diagonalization in [35] to address the case where m = 2^l₁ and n = 2^l₂.

We first diagonalize A = QΛQ^† using its eigenphases, with $Λ = diag (\sqrt{mn}, 0^{m - 1}, - \sqrt{mn}, 0^{n - 1})$ \Lambda = {\rm{diag}}(\sqrt {mn},{0^{m - 1}}, - \sqrt {mn},{0^{n - 1}}) and where H is the Hadamard gate.

Here we expand the Hilbert space by d dimensions so that m = n + d. Define $\tilde{Λ} = diag (\sqrt{mn}, 0^{m - 1}, - \sqrt{mn}, 0^{m - 1})$ \widetilde \Lambda = {\rm{diag}}(\sqrt {mn},{0^{m - 1}}, - \sqrt {mn},{0^{m - 1}}) and (36) Then for (37) $\tilde{A} = \tilde{Q} \tilde{Λ} {\tilde{Q}}^{†},$ \widetilde A = \widetilde Q\widetilde \Lambda {\widetilde Q^\dagger}, it is easily seen that (38) $e^{- i \tilde{A} t} = \tilde{Q} e^{- i \tilde{Λ} t} {\tilde{Q}}^{†}$ {e^{- i\widetilde At}} = \widetilde Q{e^{- i\widetilde \Lambda t}}{\widetilde Q^\dagger} acts as e^−iAt in the original space and as identity in the expended subspace. Equations (39–41) show how to implement these operators by elementary gates with P₀ = |0〉〈0| and P₁ = |1〉〈1| being the two-dimensional projection operators. (39) (40) (41)

The circuit for e^−iÃt is given in Figure 4. As pointed out in [35], the diagonalization approach confines the time-dependence of e^−iÃt to the diagonal matrix e^−iΛ̃t, which can be implemented by a controlled phase gate. This means that the walk operator can be simulated efficiently in constant time, that is, the complexity of the quantum circuit does not scale with the parameter t.

For m, n that are not a power of 2, we can simply add vertices to the search space, none of which are marked, such that the sizes of the two partite sets are a power of 2. Alternatively, one can employ the oracle Hamiltonian simulation algorithm. Assuming access to a unitary oracle that implements the adjacency matrix, the implementation of the quantum walk operator can be achieved through sparse Hamiltonian simulation algorithm [36].

To verify the correctness of the spatial search algorithm, we implement the circuit on the well-known quantum computing platform Qiskit for a specific example for demonstration. Consider graph K_8,4 (Figure 5). Such a graph requires 4 qubits to encode the vertices, with the corresponding state space being span{|0〉, |1〉, … , |15〉}. Suppose that vertex |8〉 is marked. The circuit in Figure 6 simulates the oracle of equation (5). We adopt the qiskit primitive Sampler [37], which estimates the entire quasi-probability distribution at the output of a quantum circuit by sampling from its output. The simulation works perfectly and returns the marked vertex with certainty. We also use the simulator Qiskit Aer [38] and get counts on the result (Figure 7, [39]), which shows that all the measurement results are the marked vertex.

6.

Discussion

Our spatial search algorithm takes the simple form of iterations of an oracle followed by a walk operator. We point out that the calculation in Section 3 only works for adjacency walk, not for Laplacian walk. As for the oracle, we adopt the specific form of equation (5), whose matrix representation in the invariant subspace span{|s〉, |w〉, |w̄〉} is (42) $(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & - 1 \end{matrix}),$ \left({\matrix{1 & 0 & 0 \cr 0 & 1 & 0 \cr 0 & 0 & {- 1} \cr}} \right), while for a standard oracle O^′, the corresponding matrix is (43) $(\begin{matrix} 1 & 0 & 0 \\ 0 & - 1 & 0 \\ 0 & 0 & 1 \end{matrix}) .$ \left({\matrix{1 & 0 & 0 \cr 0 & {- 1} & 0 \cr 0 & 0 & 1 \cr}} \right). In fact, direct calculation shows that in the subspace span{|s〉, |w〉, |w̄〉}, (44) $O e^{- iAt} O = O^{'} e^{iAt} O^{'} .$ O{e^{- iAt}}O = O'{e^{iAt}}O'. Therefore, the two oracles are equivalent in the sense that (45) ${(e^{- iAt} O)}^{2 l} = {(e^{- iAt} O^{'} e^{iAt} O^{'})}^{l}$ {({e^{- iAt}}O)^{2l}} = {({e^{- iAt}}O'{e^{iAt}}O')^l} for some integer l.

Although our algorithm is within the framework of alternating walk, we do not assume a generalized phase oracle (i.e., an oracle that does not flip the marked vertices but rotates it by a specified angle) as most of the algorithms in Table 1 did, making our algorithm easier to implement.

We and reference [24] both exploit the specific structure of complete bipartite graphs to simplify the calculation and analysis. However, we adopt the different quantum walk framework (CTQW vs. DTQW): They [24] reduced the calculation to a single-qubit quantum system and used Bloch sphere representation as an analysis tool, while we reduce the calculation to a three-dimensional invariant subspace and further make use of the spectrum structure in the subsequent calculation. More importantly, the symmetry of the spectrum of our search operator makes it possible to design a simple algorithm to estimate the number of marked vertices.

Quantum counting is another difficulty one might encounter in constructing deterministic search algorithms on graphs. Typically the algorithmic parameters such as iteration number or evolution time are functions of the number of marked vertices. However, the eigenphases of the evolution operator usually do not have sufficient symmetries, such that QPE cannot be used to extract the information of the number of marked vertices from the operator eigenphases. In recent years, there have been research works that have constructed quantum counting (and the closely related problem of amplitude estimation) algorithms without QPE [40,41,43]. It is an interesting research line to construct quantum counting algorithms without QPE on graphs.

7.

Conclusions

In this work, we propose a deterministic search algorithm on complete bipartite graphs via continuous-time quantum walk. Our algorithm takes a simple form of iterations of an oracle followed by a walk operator, which can be seen as a generalization of Grover's search, replacing the Grover diffusion operator with a quantum walk operator. We exploit the symmetries of complete bipartite graphs and reduce the calculation to a three-dimensional invariant subspace. By choosing appropriate evolution time and iteration number, the system outputs a marked vertex with certainty. Making use of the symmetry of the search operator spectrum, we develop a quantum counting algorithm for spatial search. This is another advantage of our search scheme since previous works on deterministic spatial search assume the number of marked vertices is known. We also provide quantum circuit implementation for our search algorithm and simulate it on the IBM quantum computing platform Qiskit.

Potential application would be for any search task whenever the search structure is the complete bipartite graph, such as database search with specific physical arrangement of data and solution space search (as Ambainis's celebrated algorithm [3] for element distinctness did). Future work would be to construct deterministic search algorithms on other types of graphs. As the calculation in the text shows, our algorithm strongly depends on the specific structure of the graph. Deterministic algorithm for more general graphs might require a more sophisticated search scheme.

Language:: English

Publication timeframe:: 1 times per year
Journal Subjects:: Physics, Quantum Physics

Journal RSS Feed

Deterministic Search on Complete Bipartite Graphs by Continuous-Time Quantum Walk

Honghong Lin

Yun Shang

Article Category: Article

Published Online: Oct 14, 2024

Page range: 1 - 15

Received: Jun 21, 2024

Accepted: Sep 10, 2024

DOI: https://doi.org/10.2478/qic-2024-0001

Keywordsspatial search, deterministic quantum algorithm, quantum counting, continuous-time quantum walk, complete bipartite graph

© 2024 Honghong Lin et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Keywords
spatial search, deterministic quantum algorithm, quantum counting, continuous-time quantum walk, complete bipartite graph