Distributed exact Grover’s algorithm

Abstract

Distributed quantum computation has gained extensive attention. In this paper, we consider a search problem that includes only one target item in the unordered database. After that, we propose a distributed exact Grover’s algorithm (DEGA), which decomposes the original search problem into $\lfloor n/2\rfloor$ parts. Specifically, (i) our algorithm is as exact as the modified version of Grover’s algorithm by Long, which means the theoretical probability of finding the objective state is 100%; (ii) the actual depth of our circuit is $8(n\text{mod}2)+9$, which is less than the circuit depths of the original and modified Grover’s algorithms, $1+8\lfloor \frac{\pi }{4}\sqrt{2^n}\rfloor$ and $9+8\lfloor \frac{\pi }{4}\sqrt{2^n}-\frac{1}{2}\rfloor$, respectively. It only depends on the parity of $n$, and it is not deepened as $n$ increases; (iii) we provide particular situations of the DEGA on MindQuantum (a quantum software) to demonstrate the practicality and validity of our method. Since our circuit is shallower, it will be more resistant to the depolarization channel noise.

Graphical abstract

Keywords

distributed quantum computation / search problem / distributed exact Grover’s algorithm (DEGA) / MindQuantum / the depolarization channel noise

1 Introduction

Quantum computation is a novel computing model based on quantum mechanics. It has gained considerable attention over the past few decades since Benioff [1,2] proposed the concept of the quantum Turing machine in 1980. Subsequently, rapid progress has been made in quantum computation, so that numerous impressive quantum algorithms have been presented, such as Deutsch’s algorithm [3], Deutsch−Jozsa (DJ) algorithm [4], Bernstein-Vazirani (BV) algorithm [5], Simon’s algorithm [6], Shor’s algorithm [7], Grover’s algorithm [8], HHL algorithm [9] and so on. For some specific problems, due to the unique properties of quantum superposition and quantum entanglement, quantum algorithms have shown incomparable advantages over classical algorithms.

Grover’s algorithm was proposed by Grover [8] in 1996, which is a quantum search algorithm that solves the search problem in an unordered database with $2^n$ elements. Specifically, let Boolean function $f:\{0,1{\}}^n\to \{0,1\}$. For the $m$ targets search problem, it aims to find out one target string $x_i\in \{0,1{\}}^n$ satisfying $f(x_i)=1$, where $i\in \{0,1,\cdots ,m-1\}$. Suppose we have a black box (Oracle) that can recognize the inputs, which means it will return $f(x)=1$ when $x$ is a target string, and output $f(x)=0$ otherwise. The classical algorithms have to query Oracle $\mathcal{O}\left(2^n/m\right)$ times, while Grover’s algorithm needs to query $\mathcal{O}\left(\sqrt{2^n/m}\right)$ times to figure out the target string with great probability, which has square acceleration compared with the classical algorithms.

Grover’s algorithm is widely regarded as one of the most prominent quantum algorithms. Furthermore, it is widely used in the minimum search problem [10], string matching problem [11], quantum dynamic programming [12] and computational geometry problem [13], etc. Subsequently, a generalization of Grover’s algorithm known as the quantum amplitude amplification and estimation algorithms [14] were presented.

However, Grover’s algorithm is unable to search for the target state accurately, except in the case of $1/4$ of the data in the database meet the search conditions, which has been strictly proved [15]. In 2001, Long [16] improved Grover’s algorithm and proposed the modified version, which will acquire the goal state with a probability of 100%. Its main idea is to extend Grover operator $G$ to operator $L$. The adjustment is carried out by three steps: (i) substitute phase rotation for phase inversion; (ii) let the phase rotation angles of two reflections in $L$ equal, which is called phase-matching condition; (iii) iterate $J+1$ times for operator $L$, where $J=\lfloor (\pi /2-\theta )/(2\theta )\rfloor$ and $\theta =\arcsin \left(\sqrt{m/2^n}\right)$. Actually, $J$ can be any integer equal to or greater than $\lfloor (\pi /2-\theta )/(2\theta )\rfloor$.

In 2017, Preskill [17] declared that quantum computation is entering the noisy intermediate-scale quantum (NISQ) era. To deploy quantum computers, various physical systems are taken into consideration, such as ions [18], photons [19], superconduction [20], and other quantum systems [21,22]. Currently, small-qubit quantum computers are much easier to implement than large-scale universal quantum computers. Hence, researchers are considering how several small-scale devices might collaborate to accomplish a task on a large scale.

Distributed quantum computation, combining distributed computing and quantum computation, has gained extensive attention. In order to process a huge issue efficiently, it attempts to break it up into many subproblems that are distributed across several quantum computers. In this way, each component needs fewer qubits and has a shallower quantum circuit.

This research field has seen a significant amount of theoretical and experimental work [23-26]. Avron et al. [27] proposed a distributed method for constructing Oracle and then illustrated the advantage in the case of a Grover research. In their Grover’s algorithm experiment, however, they only acquired $n-1$ qubits of the target state rather than the target state itself directly. The total number of qubits used in their scheme is $2(n-1)$.

Qiu et al. [28] proposed two distributed Grover’s algorithms (parallel and serial) and these algorithms require fewer qubits and have shallower depth of circuits. Notably, the distributed algorithms by Qiu et al. [28] can solve the search problem with multiple targets. They divided a Boolean function $f$ into $2^k$ subfunctions, where $2^k$ represents the number of computing nodes. By employing the quantum counting algorithm, the number of solutions in each subfunction can be determined, and then the solution for each subfunction can be obtained. Particularly, Qiu et al. [28] proposed an efficient algorithm of constructing quantum circuits for realizing the Oracle corresponding to any Boolean function with conjunctive normal form (CNF). The total number of qubits used in their parallel scheme is $2^k(n-k)$.

Tan et al. [29] presented an interesting and novel distributed Simon’s algorithm, which improves essentially the number of qubits for inputs and the depth of circuits compared to the famous Simon’s algorithm. Recently, Xiao et al. [30] proposed a distributed Shor’s algorithm, which can separately estimate patrial bits of $s/r$ for some $s\in \{0,1,\cdots ,r-1\}$ by two quantum computers during solving order-finding. Later, they extended this method to multiple nodes [31]. Zhou et al. [32] designed a distributed BV algorithm (DBVA) with $2\le t\le n$ nodes. Comparing with the original BV algorithms, their scheme is easier to verify in experiments. Li et al. [33] proposed a multi-node distributed exact quantum algorithm for solving the DJ problem with super-exponential speedup compared to distributed classical deterministic algorithms.

In this paper, we consider a search problem that includes only one target item in the unordered database (we still do not know how to solve it for the case of multiple targets). After that, we propose a distributed exact Grover’s algorithm (DEGA), which decomposes the original search problem into $\lfloor n/2\rfloor$ parts. Specifically, (i) our algorithm is as exact as the modified version of Grover’s algorithm by Long, which means the theoretical probability of finding the objective state is 100%; (ii) the actual depth of our circuit is $8(n\text{mod}2)+9$, which is less than the circuit depths of the original and modified Grover’s algorithms, $1+8\lfloor \frac{\pi }{4}\sqrt{2^n}\rfloor$ and $9+8\lfloor \frac{\pi }{4}\sqrt{2^n}-\frac{1}{2}\rfloor$, respectively. It only depends on the parity of $n$, and it is not deepened as $n$ increases.

MindQuantum (a quantum software) [34] is a general software library supporting the development of applications for quantum computation. Eventually, we provide particular situations of the DEGA on MindQuantum. These experiments will further demonstrate the correctness of the DEGA and explicate the specific steps of implement $n$-qubit DEGA, where $n\in \{2,3,4,5\}$. After that, we will simulate a 5-qubit DEGA running in the depolarization channel and compare with the original and modified Grover’s algorithms. Since our circuit is shallower, it will be more resistant to the depolarization channel noise.

The rest of the paper is organized as follows. We will briefly review the original and modified Grover’s algorithms in Section 2 and primarily describe the DEGA in Section 3. Next, the analysis of our the algorithm will be presented in Section 4. After that, we will provide particular situations of the DEGA on MindQuantum in Section 5. Finally, we will give a brief conclusion in Section 6.

2 Preliminaries

In this section, we briefly review the original [8] and modified [16] Grover’s algorithms.

2.1 Grover’s algorithm [8]

Suppose that the search task is carried out in an unordered set (or database) with $2^n$ elements. We establish a one-to-one correspondence between the elements in the database and the indexes (integers from 0 to $2^n-1$). We focus on searching the indexes of these elements.

Let Boolean function $f:\{0,1{\}}^n\to \{0,1\}$. Define a function for the search problem as follows:

(1)$f(x)=\{\begin{array}{ll}1,& x=\tau ,\\ 0,& x\ne \tau ,\end{array}$

where $x\in \{0,1{\}}^n$ and $\tau$ is the target index. In a quantum system, indexes are represented by quantum states $|0⟩,|1⟩,\cdots ,|2^n-1⟩$ (or $|00\cdots 0⟩,|00\cdots 1⟩,\cdots ,|11\cdots 1⟩$).

Without loss of generality, we consider a search problem that includes only one target item in the unordered database throughout this paper. Suppose we have a black box (Oracle $U_{f(x)}:|x⟩\to (-1{)}^{f(x)}|x⟩$, where $x\in \{0,1{\}}^n$) that can recognize the inputs. The purpose of Grover’s algorithm is to find out $|\tau ⟩$ with high probability.

Here, we briefly review Grover’s algorithm in Algorithm 1. The whole quantum circuit is shown in Fig.1.

Fig.1 Quantum circuit of Grover’s algorithm.

Full size|PPT slide

Full size|PPT slide

Next, we analyse Grover’s algorithm.

Denote

(2)$|\tilde{x}⟩\triangleq \sqrt{{\displaystyle \frac{1}{2^n-1}}}{\displaystyle \sum _{x\ne \tau }|x⟩,}$

(3)$|h⟩\triangleq H^{\otimes n}\left(|0{⟩}^{\otimes n}\right)=\sqrt{{\displaystyle \frac{1}{2^n}}}{\displaystyle \sum _{x\in \{0,1{\}}^n}|x⟩.}$

Then we can write

(4)$\begin{array}{rl}|h⟩=& \sqrt{\frac{2^n-1}{2^n}}|\tilde{x}⟩+\sqrt{\frac{1}{2^n}}|\tau ⟩\\ \triangleq & \cos \theta |\tilde{x}⟩+\sin \theta |\tau ⟩,\end{array}$

where

(5)$\theta =\arcsin \left(\sqrt{{\displaystyle \frac{1}{2^n}}}\right)\in \left(0,{\displaystyle \frac{\pi }{2}}\right).$

Since $U_0=I^{\otimes n}-2(|0⟩⟨0|{)}^{\otimes n}$ and $U_{f(x)}=I^{\otimes n}-2|\tau ⟩⟨\tau |$, we have

(6)$\begin{array}{rl}G=& -H^{\otimes n}{U}_0{H}^{\otimes n}{U}_{f(x)}\\ =& -H^{\otimes n}\left(I^{\otimes n}-2(|0⟩⟨0|{)}^{\otimes n}\right)H^{\otimes n}\left(I^{\otimes n}-2|\tau ⟩⟨\tau |\right)\\ =& -\left(I^{\otimes n}-2|h⟩⟨h|\right)\left(I^{\otimes n}-2|\tau ⟩⟨\tau |\right).\end{array}$

Therefore, the effect of one iteration of Grover operator $G$ is two successive reflections in the space spanned by $\{|\tilde{x}⟩,|\tau ⟩\}$, around $|\tilde{x}⟩$ and $|h⟩$, respectively. In other words, one iteration of $G$ causes a rotation by an angle $2\theta$ from the initial state $|h⟩$ to the target state $|\tau ⟩$ (see Fig.2).

Fig.2 Visualization of Grover’s algorithm. In the two-dimensional plane space spanned by $\{|\tilde{x}⟩,|\tau ⟩\}$, one iteration of $G$ causes a rotation by an angle $2\theta$ from the initial state $|h⟩$ to the target state $|\tau ⟩$.

Full size|PPT slide

After $k$ iterations of $G$, the state will be

(7)$G^k|h⟩=\cos ((2k+1)\theta )|\tilde{x}⟩+\sin ((2k+1)\theta )|\tau ⟩.$

The goal is to make

(8)$\sin ((2k+1)\theta )\approx 1,$

then

(9)$(2k+1)\theta \approx {\displaystyle \frac{\pi }{2}},$

will suffice, so we should choose

(10)$k\approx {\displaystyle \frac{\pi /2-\theta }{2\theta }}={\displaystyle \frac{\pi }{4\theta }}-{\displaystyle \frac{1}{2}}.$

Note that $k$ must be a positive integer.

Since we have assumed there is only one target item, then

(11)$\theta =\arcsin \left(\sqrt{{\displaystyle \frac{1}{2^n}}}\right)\approx \sqrt{{\displaystyle \frac{1}{2^n}}},$

so

(12)$k=\lfloor {\displaystyle \frac{\pi }{4}}\sqrt{2^n}\rfloor$

is a suitable choice for Grover’s algorithm. The success probability is

(13)${\sin }^2\left(\left(2\lfloor {\displaystyle \frac{\pi }{4}}\sqrt{2^n}\rfloor +1\right)\arcsin \left(\sqrt{{\displaystyle \frac{1}{2^n}}}\right)\right).$

2.2 The modified Grover’s algorithm by Long [16]

In 2001, Long improved Grover’s algorithm and proposed a modified version of Grover’s algorithm, which will acquire the goal state with a probability of 100%. Its main idea is to extend Grover operator $G$ to operator $L$. The adjustment is carried out by three steps: (1) substitute phase rotation for phase inversion; (2) let the phase rotation angles of two reflections in $L$ equal, which is called phase-matching condition; (3) iterate $J+1$ times for operator $L$, where $J=\lfloor (\pi /2-\theta )/(2\theta )\rfloor$ and $\theta =\arcsin \left(\sqrt{1/2^n}\right)$. Actually, $J$ can be any integer equal to or greater than $\lfloor (\pi /2-\theta )/(2\theta )\rfloor$.

Here, we briefly review the modified Grover’s algorithm by Long in Algorithm 2. The whole quantum circuit is shown in Fig.3.

Fig.3 Quantum circuit of the modified Grover’s algorithm.

Full size|PPT slide

Full size|PPT slide

Obviously, the modified Grover’s algorithm is a Grover’s algorithm when $\varphi =\pi$.

Next, we analyse the modified Grover’s algorithm.

In Grover’s algorithm, iterate

(14)$j_{op}=\lfloor (\pi /2-\theta )/(2\theta )\rfloor$

or $j_{op}+1$ times of the Grover operator $G$, so that $(2j_{op}+1)\theta$ and $[2(j_{op}+1)+1]\theta$ are close to $\pi /2$, where $\theta =\arcsin \left(\sqrt{1/2^n}\right)$. However, Grover’s algorithm is unable to search for the target state accurately, except in the case of $1/4$ of the data in the database meet the search conditions.

After substituting phase rotation $R_0=I^{\otimes n}+({\mathrm{e}}^{\mathrm{i}\varphi }-1)(|0⟩⟨0|{)}^{\otimes n}$ and $R_{f(x)}=I^{\otimes n}+({\mathrm{e}}^{\mathrm{i}\varphi }-1)|\tau ⟩⟨\tau |$ for phase inversion $U_0=I^{\otimes n}-2(|0⟩⟨0|{)}^{\otimes n}$ and $U_{f(x)}=I^{\otimes n}-2|\tau ⟩⟨\tau |$, we have

(15)$\begin{array}{rl}L=& -H^{\otimes n}{R}_0{H}^{\otimes n}{R}_{f(x)}\\ =& -H^{\otimes n}\left[I^{\otimes n}+({\mathrm{e}}^{\mathrm{i}\varphi }-1)(|0⟩⟨0|{)}^{\otimes n}\right]\\ & \cdot H^{\otimes n}\left[I^{\otimes n}+({\mathrm{e}}^{\mathrm{i}\varphi }-1)|\tau ⟩⟨\tau |)\right]\\ =& -\left[I^{\otimes n}+({\mathrm{e}}^{\mathrm{i}\varphi }-1)|h⟩⟨h|\right]\left[I^{\otimes n}+({\mathrm{e}}^{\mathrm{i}\varphi }-1)|\tau ⟩⟨\tau |\right]\\ =& \left(\begin{array}{cc}-{\mathrm{e}}^{\mathrm{i}\varphi }(1+({\mathrm{e}}^{\mathrm{i}\varphi }-1){\sin }^2\theta )& -{\mathrm{e}}^{\mathrm{i}\varphi }(1-{\mathrm{e}}^{-\mathrm{i}\varphi })\sin \theta \cos \theta \\ -{\mathrm{e}}^{\mathrm{i}\varphi }({\mathrm{e}}^{\mathrm{i}\varphi }-1)\sin \theta \cos \theta & -{\mathrm{e}}^{\mathrm{i}\varphi }(1-(1-{\mathrm{e}}^{-\mathrm{i}\varphi }){\sin }^2\theta )\end{array}\right)\end{array}$

(16)$=-{\mathrm{e}}^{\mathrm{i}\varphi }\left[\cos \left({\displaystyle \frac{\alpha }{2}}\right)I+\mathrm{i}\sin \left({\displaystyle \frac{\alpha }{2}}\right)(n_{x}X+n_{y}Y+n_{z}Z)\right],$

where

(17)$\alpha =4\beta ,\sin \beta =\sin \left({\displaystyle \frac{\varphi }{2}}\right)\sin \theta ,\theta =\arcsin \left(\sqrt{1/2^n}\right),$

and

(18)$\begin{array}{rl}& n_x=\frac{\cos \theta }{\cos \beta }\cos \left(\frac{\varphi }{2}\right),n_y=\frac{\cos \theta }{\cos \beta }\sin \left(\frac{\varphi }{2}\right),\\ & n_z=\frac{\cos \theta }{\cos \beta }\cos \left(\frac{\varphi }{2}\right)\tan \theta ,\end{array}$

and $I$, $X$, $Y$, $Z$ represent the Pauli gates,

(19)$\begin{array}{rl}& I=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),X=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),\\ & Y=\left(\begin{array}{cc}0& -\mathrm{i}\\ \mathrm{i}& 0\end{array}\right),Z=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right).\end{array}$

The equivalence of Eq. (15) and Eq. (16) will be detailed in Appendix A. It can be seen that the phase rotation angles of two reflections in $L$ are equal, which is called phase-matching condition. Furthermore, $L$ can be regarded as the three-dimensional rotation about the axis $\mathit{l}$ in the Bloch sphere spanned by $\{|\tilde{x}⟩,|\tau ⟩\}$ and the rotation angel is $\alpha$, where

(20)$\begin{array}{rl}\mathit{l}=& {\left[n_x,n_y,n_z\right]}^{\mathrm{T}}\\ =& \frac{\cos \theta }{\cos \beta }{\left[\cos \left(\frac{\varphi }{2}\right),\sin \left(\frac{\varphi }{2}\right),\cos \left(\frac{\varphi }{2}\right)\tan \theta \right]}^{\mathrm{T}}.\end{array}$

The initial state $|h⟩$ and the target state $|\tau ⟩$ in the three-dimensional Bloch sphere can represent by the following vectors

(21)${\mathit{r}}_i={\left[\sin \left(2\theta \right),0,-\cos \left(2\theta \right)\right]}^{\mathrm{T}},$

(22)${\mathit{r}}_f={\left[0,0,1\right]}^{\mathrm{T}}.$

Denote ${\mathit{r}}_0$ as the projections of ${\mathit{r}}_i$ and ${\mathit{r}}_f$ on axis $\mathit{l}$,

(23)$\begin{array}{rl}{\mathit{r}}_0=& c[{\cos }^2\left(\frac{\varphi }{2}\right)\tan \theta ,\sin \left(\frac{\varphi }{2}\right)\cos \left(\frac{\varphi }{2}\right)\tan \theta ,\\ & {{\cos }^2\left(\frac{\varphi }{2}\right){\tan }^2\theta ]}^{\mathrm{T}},\end{array}$

where

(24)$c={\displaystyle \frac{1}{1+\left({\cos }^2\left({\displaystyle \frac{\varphi }{2}}\right)/{\tan }^2\theta \right)}}.$

As shown in Fig.4, the desired rotation angle $\omega$ between ${\mathit{r}}_i-{\mathit{r}}_0$ and ${\mathit{r}}_f-{\mathit{r}}_0$ satisfies

Fig.4 Visualization of the modified Grover’s algorithm. In the three-dimensional Bloch sphere spanned by $\{|\tilde{x}⟩,|\tau ⟩\}$, the initial state ${\mathit{r}}_i$ rotate $\omega$ around axis $\mathit{l}$, and then ${\mathit{r}}_f$ is obtained, where $\omega$ is the desired rotation angle.

Full size|PPT slide

(25)$\begin{array}{rl}\cos \omega =& {\displaystyle \frac{({\mathit{r}}_i-{\mathit{r}}_0)\cdot ({\mathit{r}}_f-{\mathit{r}}_0)}{|{\mathit{r}}_i-{\mathit{r}}_0||{\mathit{r}}_f-{\mathit{r}}_0|}}\\ =& \cos \left(2\arccos \left(\sin \left({\displaystyle \frac{\varphi }{2}}\right)\sin \theta \right)\right),\end{array}$

then we will have

(26)$\omega =2\arccos \left(\sin \left({\displaystyle \frac{\varphi }{2}}\right)\sin \theta \right)=2\left[{\displaystyle \frac{\pi }{2}}-\arcsin \left(\sin \left({\displaystyle \frac{\varphi }{2}}\right)\sin \theta \right)\right].$

Besides, in order to obtain the target state with certainty, angle $\omega$ ought to satisfy

(27)$\omega =(J+1)\alpha =4(J+1)\arcsin \left(\sin \left({\displaystyle \frac{\varphi }{2}}\right)\sin \theta \right)$

after $J+1$ times iteration of operator $L$. Combining Eq. (25) and Eq. (27), we can get

(28)$\sin \left({\displaystyle \frac{\pi }{4J+6}}\right)=\sin \left({\displaystyle \frac{\varphi }{2}}\right)\sin \theta .$

In other words, we have

(29)$\varphi =2\arcsin \left(\sin \left({\displaystyle \frac{\pi }{4J+6}}\right)/\sin \theta \right).$

3 Distributed exact Grover’s algorithm

In this section, we mainly describe the distributed exact Grover’s algorithm (DEGA), which decomposes the original search problem into $\lfloor n/2\rfloor$ parts.

3.1 Subfunctions

As mentioned in [27], an $n$-qubit Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ can be split into two subfunctions $f_{\text{even}/\text{odd}}:\{0,1{\}}^{n-1}\to \{0,1\}$,

(30)$f_{\text{even}}(x)=f(x_0{x}_1\cdots x_{i-1}0x_{i+1}\cdots x_{n-2}{x}_{n-1}),$

(31)$f_{\text{odd}}(x)=f(x_0{x}_1\cdots x_{i-1}1x_{i+1}\cdots x_{n-2}{x}_{n-1}),$

where $x=x_0{x}_1\cdots x_{i-1}{x}_{i+1}\cdots x_{n-2}{x}_{n-1}\in \{0,1{\}}^{n-1}$.

Furthermore, we can divide the original function into $2^k$ subfunctions $f_p:\{0,1{\}}^{n-k}\to \{0,1\}$:

(32)$f_p(x)=f(\underset{n-k}{\underbrace{x_0{x}_1\cdots x_{n-k-1}}}\underset{k}{\underbrace{y_{p_0}{y}_{p_1}\cdots y_{p_{k-1}}}}),$

where $k\in \{1,2,\cdots ,n-1\}$, $x=x_0{x}_1\cdots x_{n-k-1}\in \{0,1{\}}^{n-k}$, and $y_{p_0}{y}_{p_1}\cdots y_{p_{k-1}}\in \{0,1{\}}^k$ is the binary representation of $p\in \{0,1,\cdots ,2^k-1\}$.

More generally, $y_{p_0}{y}_{p_1}\cdots y_{p_{k-1}}$ can be at any $k$ positions in $x$ of the original function $f$. For instance, we can also obtain another $2^k$ subfunctions $f_q:\{0,1{\}}^{n-k}\to \{0,1\}$:

(33)$f_q(x)=f(\underset{k}{\underbrace{y_{q_0}{y}_{q_1}\cdots y_{q_{k-1}}}}\underset{n-k}{\underbrace{x_k{x}_{k+1}\cdots x_{n-1}}}),$

where $k\in \{1,2,\cdots ,n-1\}$, $x=x_k{x}_{k+1}\cdots x_{n-1}\in \{0,1{\}}^{n-k}$, and $y_{q_0}{y}_{q_1}\cdots y_{q_{k-1}}\in \{0,1{\}}^k$ is the binary representation of $q\in \{0,1,\cdots ,2^k-1\}$.

Next, we need to describe our partitioning strategy for the original function before providing our algorithm. We will generate a total of $\lfloor n/2\rfloor$ subfunctions $g_i(m_i)$ for our algorithm, where $i\in \{0,1,\cdots ,\lfloor n/2\rfloor -1\}$. The specific generation method is as follows.

When $i\in \{0,1,\cdots ,\lfloor n/2\rfloor -2\}$, we choose first $2i$ and last $n-2(i+1)$ bits in $x$ to divide $f$, then we can get $2^{n-2}$ subfunctions $f_{i,j}:\{0,1{\}}^2\to \{0,1\}$:

(34)$f_{i,j}(m_i)=f(\underset{2i}{\underbrace{y_{j_0}{y}_{j_1}\cdots y_{j_{2i-1}}}}{m}_i\underset{n-2(i+1)}{\underbrace{y_{j_{2i}}{y}_{j_{2i+1}}\cdots y_{j_{n-3}}}}),$

where $m_i\in \{0,1{\}}^2$ and $y_{j_0}{y}_{j_1}\cdots y_{j_{2i-1}}{y}_{j_{2i}}{y}_{j_{2i+1}}\cdots y_{j_{n-3}}\in \{0,1{\}}^{n-2}$ is the binary representation of $j\in \{0,1,\cdots ,$ $2^{n-2}-1\}$. Afterwards, we generate a new function $g_i:\{0,1{\}}^2\to \{0,1\}$ through these subfunctions,

(35)$g_i(m_i)=\text{OR}(f_{i,0}(m_i),f_{i,1}(m_i),\cdots ,f_{i,2^{n-2}-1}(m_i)),$

where $m_i\in \{0,1{\}}^2$. Besides,

(36)$\text{OR}(x)=\{\begin{array}{ll}1,& |x|\ge 1,\\ 0,& |x|=0,\end{array}$

where $|x|$ is the Hamming weight of $x\in \{0,1{\}}^n$ (its number of 1’s). It means we have acquired $\lfloor n/2\rfloor -1$ subfunctions $g_i:\{0,1{\}}^2\to \{0,1\}$, where $i\in \{0,1,\cdots ,\lfloor n/2\rfloor -2\}$.

When $i=\lfloor n/2\rfloor -1$, we choose first $2i$ bits in $x$ to divide $f$, then we can get $2^{2i}$ subfunctions $f_{i,j}:\{0,1{\}}^{n-2i}\to \{0,1\}$:

(37)$f_{i,j}(m_i)=f(\underset{2i}{\underbrace{y_{j_0}{y}_{j_1}\cdots y_{j_{2i-1}}}}\underset{n-2i}{\underbrace{m_i}}),$

where $m_i\in \{0,1{\}}^{n-2i}$ and $y_{j_0}{y}_{j_1}\cdots y_{j_{2i-1}}\in \{0,1{\}}^{2i}$ is the binary representation of $j\in \{0,1,\cdots ,$ $2^{2i}-1\}$. Afterwards, we also generate a new function $g_i:\{0,1{\}}^{n-2i}\to \{0,1\}$ by these subfunctions,

(38)$g_i(m_i)=\text{OR}(f_{i,0}(m_i),f_{i,1}(m_i),\cdots ,f_{i,2^{2i}-1}(m_i)),$

where $m_i\in \{0,1{\}}^{n-2i}$. Specifically, when $n$ is an even number, we have

(39)$n-2i=n-2(\lfloor n/2\rfloor -1)=n-2\left({\displaystyle \frac{n}{2}}-1\right)=2.$

When $n$ is an odd number, we have

(40)$n-2i=n-2(\lfloor n/2\rfloor -1)=n-2\left({\displaystyle \frac{n-1}{2}}-1\right)=3.$

It means we have acquired the last subfunction $g_i:\{0,1{\}}^{n-2i}\to \{0,1\}$, where $i=\lfloor n/2\rfloor -1$.

3.2 Distributed exact Grover’s algorithm

So far, we have successfully generated a total of $\lfloor n/2\rfloor$ subfunctions $g_i(m_i)$ according to the original function $f(x)$ and $n$, where $i\in \{0,1,\cdots ,$ $\lfloor n/2\rfloor -1\}$. Additionally, we assume that obtaining the Oracle for each subfunction is simple. In other words, we can have $\lfloor n/2\rfloor -1$ Oracles

(41)$U_{g_i(x)}:|x⟩\to (-1{)}^{g_i(x)}|x⟩,$

where $x\in \{0,1{\}}^2$, $i\in \{0,1,\cdots ,$ $\lfloor n/2\rfloor -2\}$, and ${\tau }_i$ is the target string of $g_i(x)$ such that $g_i({\tau }_i)=1$.

For the last subfunctions $g_i:\{0,1{\}}^{n-2i}\to \{0,1\}$, we first need to determine the parity of $n$. If $n$ is an even number, we can also have the Oracle as in Eq. (41), where $i=\lfloor n/2\rfloor -1$. Otherwise, we can have another Oracle

(42)$R_{g_i(x)}:|x⟩\to {\mathrm{e}}^{\mathrm{i}\varphi \cdot g_i(x)}|x⟩,$

where $x\in \{0,1{\}}^3$, $i=\lfloor n/2\rfloor -1$, ${\tau }_i$ is the target string of $g_i(x)$ such that $g_i({\tau }_i)=1$, $\varphi =2\arcsin \left(\sin \left(\frac{\pi }{4J+6}\right)/\sin \theta \right)$, $J=\lfloor (\pi /2-\theta )/(2\theta )\rfloor$, and $\theta =\arcsin \left(\sqrt{1/2^3}\right)$.

Next, we provide a detailed introduction to the DEGA in Algorithm 3. The whole quantum circuit is shown in Fig.5.

Fig.5 Quantum circuit of the distributed exact Grover’s algorithm (DEGA).

Full size|PPT slide

Full size|PPT slide

The target index string $\tau ={\tau }_0{\tau }_1\cdots {\tau }_{\lfloor n/2\rfloor -1}\in \{0,1{\}}^n$ will be successfully searched exactly after following the above algorithm steps. Therefore, the entire process of the DEGA is accomplished.

4 Analysis

In this section, we will first demonstrate the correctness of the DEGA. The original and modified Grover’s algorithms, and existing distributed Grover’s algorithms will next be compared to the approach.

4.1 Correctness

To verify the correctness of the DEGA, it is equivalent to proving that we can obtain the target index string $\tau \in \{0,1{\}}^n$ by Algorithm 3 exactly. Firstly, we give the following theorem.

Theorem 1. Each subfunction $g_i(x)$ [as in Eq. (35) and Eq. (38)] has its corresponding target string ${\tau }_i$ such that $g_i({\tau }_i)=1$, which satisfies

(43)$\tau ={\tau }_0{\tau }_1\cdots {\tau }_{\lfloor n/2\rfloor -1},$

where $i\in \{0,1,\cdots ,\lfloor n/2\rfloor -1\}$ and $\tau \in \{0,1{\}}^n$ is the target string of the original function $f(x)$.

Proof. Without losing generality, suppose the target string can be expressed as $\tau =x_0{x}_1\cdots x_{n-1}\in \{0,1{\}}^n$.

The proof is divided into two parts.

Part 1: For $i\in \{0,1,\cdots ,$ $\lfloor n/2\rfloor -2\}$, we first prove ${\tau }_i=x_{2i}{x}_{2i+1}\in \{0,1{\}}^2$.

As can be seen from Eq. (34), we can get $2^{n-2}$ subfunctions $f_{i,j}:\{0,1{\}}^2\to \{0,1\}$:

(44)$f_{i,j}(m_i)=f(\underset{2i}{\underbrace{y_{j_0}{y}_{j_1}\cdots y_{j_{2i-1}}}}{m}_i\underset{n-2(i+1)}{\underbrace{y_{j_{2i}}{y}_{j_{2i+1}}\cdots y_{j_{n-3}}}}),$

where $m_i\in \{0,1{\}}^2$ and $y_{j_0}{y}_{j_1}\cdots y_{j_{2i-1}}{y}_{j_{2i}}{y}_{j_{2i+1}}\cdots y_{j_{n-3}}\in \{0,1{\}}^{n-2}$ is the binary representation of $j\in \{0,1,\cdots ,$ $2^{n-2}-1\}$. Thus, there exists $j^{\prime }=y_{j_0^{\prime }}{y}_{j_1^{\prime }}\cdots y_{j_{2i-1}^{\prime }}{y}_{j_{2i}^{\prime }}{y}_{j_{2i+1}^{\prime }}\cdots y_{j_{n-3}^{\prime }}\in \{0,1{\}}^{n-2}$, such that

(45)$\begin{array}{rl}& \underset{2i}{\underbrace{y_{j_0^{\prime }}{y}_{j_1^{\prime }}\cdots y_{j_{2i-1}^{\prime }}}}\underset{n-2(i+1)}{\underbrace{y_{j_{2i}^{\prime }}{y}_{j_{2i+1}^{\prime }}\cdots y_{j_{n-3}^{\prime }}}}\\ & =x_0{x}_1\cdots x_{2i-1}{x}_{2i+2}\cdots x_{n-1},\end{array}$

where $x_0{x}_1\cdots x_{2i-1}{x}_{2i+2}\cdots x_{n-1}\in \{0,1{\}}^{n-2}$ represents $\tau =x_0{x}_1\cdots x_{2i-1}{x}_{2i}{x}_{2i+1}{x}_{2i+2}\cdots x_{n-1}\in \{0,1{\}}^n$ removes $x_{2i}{x}_{2i+1}\in \{0,1{\}}^2$.

In other words, we have a subfunction $f_{i,j^{\prime }}:\{0,1{\}}^2\to \{0,1\}$:

(46)$f_{i,j^{\prime }}(m_i)=\{\begin{array}{ll}1,& m_i=x_{2i}{x}_{2i+1},\\ 0,& \text{otherwise},\end{array}$

where $m_i\in \{0,1{\}}^2$. For the remaining subfunctions $f_{i,j\ne j^{\prime }}:\{0,1{\}}^2\to \{0,1\}$:

(47)$f_{i,j\ne j^{\prime }}(m_i)\equiv 0,$

where $m_i\in \{0,1{\}}^2$.

Afterwards, we generate a new function $g_i:\{0,1{\}}^2\to \{0,1\}$ by these subfunctions,

(48)$g_i(m_i)=\text{OR}(f_{i,0}(m_i),f_{i,1}(m_i),\cdots ,f_{i,2^{n-2}-1}(m_i))$

(49)$=\{\begin{array}{ll}1,& m_i=x_{2i}{x}_{2i+1},\\ 0,& \text{otherwise},\end{array}$

where $m_i\in \{0,1{\}}^2$. Therefore, let ${\tau }_i=x_{2i}{x}_{2i+1}$. It is the target string of $g_i(m_i)$ such that $g_i({\tau }_i)=1$.

Part 1 has been proved.

Part 2: For $i=\lfloor n/2\rfloor -1$, we prove that

(50)$\begin{array}{rl}{\tau }_i=& x_{2i}{x}_{2i+1}\cdots x_{n-1}\\ =& \{\begin{array}{ll}{x}_{2i}{x}_{2i+1}=x_{n-2}{x}_{n-1}\in \{0,1{\}}^2,& n\text{is even},\\ x_{2i}{x}_{2i+1}{x}_{2i+2}=x_{n-3}{x}_{n-2}{x}_{n-1}\in \{0,1{\}}^3,& n\text{is odd}.\end{array}\end{array}$

The proof of Part 2 is similar to Part 1. As can be seen from Eq. (37), we can get $2^{2i}$ subfunctions $f_{i,j}:\{0,1{\}}^{n-2i}\to \{0,1\}$:

(51)$f_{i,j}(m_i)=f(\underset{2i}{\underbrace{y_{j_0}{y}_{j_1}\cdots y_{j_{2i-1}}}}\underset{n-2i}{\underbrace{m_i}}),$

where $m_i\in \{0,1{\}}^{n-2i}$ and $y_{j_0}{y}_{j_1}\cdots y_{j_{2i-1}}\in \{0,1{\}}^{2i}$ is the binary representation of $j\in \{0,1,\cdots ,$ $2^{2i}-1\}$.

Thus, there exists $j^{″}=y_{j_0^{″}}{y}_{j_1^{″}}\cdots y_{j_{2i-1}^{″}}\in \{0,1{\}}^{2i}$, such that

(52)$\underset{2i}{\underbrace{y_{j_0^{″}}{y}_{j_1^{″}}\cdots y_{j_{2i-1}^{″}}}}=x_0{x}_1\cdots x_{2i-1},$

where $x_0{x}_1\cdots x_{2i-1}\in \{0,1{\}}^{2i}$ represents $\tau =x_0{x}_1\cdots x_{2i-1}{x}_{2i}{x}_{2i+1}\cdots x_{n-1}\in \{0,1{\}}^n$ removes $x_{2i}{x}_{2i+1}\cdots$ $x_{n-1}\in \{0,1{\}}^{n-2i}$.

In other words, we have a subfunction $f_{i,j^{″}}:\{0,1{\}}^{n-2i}\to \{0,1\}$:

(53)$f_{i,j^{″}}(m_i)=\{\begin{array}{ll}1,& m_i=x_{2i}{x}_{2i+1}\cdots x_{n-1},\\ 0,& \text{otherwise},\end{array}$

where $m_i\in \{0,1{\}}^{n-2i}$. For the remaining subfunctions $f_{i,j\ne j^{″}}:\{0,1{\}}^{n-2i}\to \{0,1\}$:

(54)$f_{i,j\ne j^{″}}(m_i)\equiv 0,$

where $m_i\in \{0,1{\}}^{n-2i}$.

Afterwards, we also generate a new function $g_i:\{0,1{\}}^{n-2i}\to \{0,1\}$ by these subfunctions,

(55)$g_i(m_i)=\text{OR}(f_{i,0}(m_i),f_{i,1}(m_i),\cdots ,f_{i,2^{2i}-1}(m_i))$

(56)$=\{\begin{array}{ll}1,& m_i=x_{2i}{x}_{2i+1}\cdots x_{n-1},\\ 0,& \text{otherwise},\end{array}$

where $m_i\in \{0,1{\}}^{n-2i}$. Specifically, when $n$ is an even number, we have

(57)$n-2i=n-2(\lfloor n/2\rfloor -1)=n-2\left({\displaystyle \frac{n}{2}}-1\right)=2.$

When $n$ is an odd number, we have

(58)$n-2i=n-2(\lfloor n/2\rfloor -1)=n-2\left({\displaystyle \frac{n-1}{2}}-1\right)=3.$

Therefore, let

(59)$\begin{array}{rl}{\tau }_i=& x_{2i}{x}_{2i+1}\cdots x_{n-1}\\ =& \{\begin{array}{ll}{x}_{2i}{x}_{2i+1}=x_{n-2}{x}_{n-1}\in \{0,1{\}}^2,& n\text{is even},\\ x_{2i}{x}_{2i+1}{x}_{2i+2}=x_{n-3}{x}_{n-2}{x}_{n-1}\in \{0,1{\}}^3,& n\text{is odd}.\end{array}\end{array}$

It is the target string of $g_i(m_i)$ such that $g_i({\tau }_i)=1$.

Part 2 has been proved.

Gather all subfunction target strings, then the target string of the original function $f(x)$ is

(60)$\tau ={\tau }_0{\tau }_1\cdots {\tau }_{\lfloor n/2\rfloor -1}=x_0{x}_1\cdots x_{n-1}\in \{0,1{\}}^n.$

□

So far, we have proved that the target string corresponding to each subfunction $g_i(m_i)$ is ${\tau }_i$, which satisfies $\tau ={\tau }_0{\tau }_1\cdots {\tau }_{\lfloor n/2\rfloor -1}$, where $i\in \{0,1,\cdots ,$ $\lfloor n/2\rfloor -1\}$.

In addition, only when $1/4$ of the data in the database meet the search conditions, the success probability of Grover’s algorithm is 1, which has been strictly proved mathematically [15]. In other words, a 2-qubit Grover’s algorithm of finding one in four is exact. The modified version of Grover’s algorithm [16] searches a target state with full successful rate. In particular, a 3-qubit modified Grover’s algorithm is also exact when $n=3$.

Next, we demonstrate the correctness of Algorithm 3 by the following Theorem 2.

Theorem 2. (Correctness of DEGA) For an $n$-qubit search problem that includes only one target index string, suppose that the goal can be expressed as $\tau =x_0{x}_1\cdots x_{n-1}\in \{0,1{\}}^n$ of the original function $f(x)$. Then we can obtain $\tau ={\tau }_0{\tau }_1\cdots {\tau }_{\lfloor n/2\rfloor -1}$ by Algorithm 3 exactly, where ${\tau }_i$ is the target string of $g_i(x)$ and satisfies

(61)${\tau }_i=\{\begin{array}{ll}{x}_{2i}{x}_{2i+1},& i\in \{0,1,\cdots ,\lfloor n/2\rfloor -2\},\\ x_{2i}{x}_{2i+1}\cdots x_{n-1},& i=\lfloor n/2\rfloor -1,\end{array}$

where

(62)$\begin{array}{rl}& x_{2i}{x}_{2i+1}\cdots x_{n-1}\\ & =\{\begin{array}{ll}{x}_{2i}{x}_{2i+1}=x_{n-2}{x}_{n-1},& n\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n},\\ x_{2i}{x}_{2i+1}{x}_{2i+2}=x_{n-3}{x}_{n-2}{x}_{n-1},& n\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}.\end{array}\end{array}$

Proof. From Section 3.1, we have declared how to generate $\lfloor n/2\rfloor$ subfunctions $g_i(x)$ as in Eq. (35) and Eq. (38) according to $f(x)$ and $n$, which decomposes the original search problem into $\lfloor n/2\rfloor$ parts, where $i\in \{0,1,\cdots ,$ $\lfloor n/2\rfloor -1\}$.

Furthermore, suppose that the goal can be expressed as $\tau =x_0{x}_1\cdots x_{n-1}\in \{0,1{\}}^n$ of the original function $f(x)$. Theorem 1 has already explained each subfunction $g_i(x)$ has its corresponding target string ${\tau }_i$ such that $g_i({\tau }_i)=1$, which satisfies

(63)$\tau ={\tau }_0{\tau }_1\cdots {\tau }_{\lfloor n/2\rfloor -1}.$

Last but not least, we will accurately obtain the solution of each part. For $i\in \{0,1,\cdots ,$ $\lfloor n/2\rfloor -2\}$, by running the 2-qubit Grover’s algorithm, we can precisely determine ${\tau }_i=x_{2i}{x}_{2i+1}\in \{0,1{\}}^2$. For $i=\lfloor n/2\rfloor -1$, by running the 2-qubit Grover’s algorithm when $n$ is even or the 3-qubit modified Grover’s algorithm when $n$ is odd, we can exactly obtain

(64)$\begin{array}{rl}{\tau }_i=& x_{2i}{x}_{2i+1}\cdots x_{n-1}\\ =& \{\begin{array}{ll}{x}_{2i}{x}_{2i+1}=x_{n-2}{x}_{n-1}\in \{0,1{\}}^2,& n\text{is even},\\ x_{2i}{x}_{2i+1}{x}_{2i+2}=x_{n-3}{x}_{n-2}{x}_{n-1}\in \{0,1{\}}^3,& n\text{is odd}.\end{array}\end{array}$

In conclusion, we can obtain $\tau ={\tau }_0{\tau }_1\cdots {\tau }_{\lfloor n/2\rfloor -1}$ through Algorithm 3 with a probability of 100%, where ${\tau }_i$ is the target string of $g_i(x)$, where $i\in \{0,1,\cdots ,$ $\lfloor n/2\rfloor -1\}$.□

4.2 Comparison

In this subsection, the original and modified Grover’s algorithms, and existing distributed Grover’s algorithms will be compared to our approach.

Compared with the original Grover’s algorithm, the DEGA is as exact as the modified version of Grover’s algorithm by Long, which means the theoretical probability of finding the objective state is 100%.

In order to compare the circuit depth, we give the following definition.

Definition 1. (Depth of circuit) The depth of circuit is defined as the longest path from the input to the output, moving forward in time along qubit wires.

The depth of the circuit on the left, for example, is 1, whereas the right is 11 (see Fig.6).

Fig.6 Equivalent quantum circuit of Toffoli gate (or $C^{2}Z$ gate), where $T$ represent $\pi /8$ gate and $T^{†}$ represents the conjugate transpose of $T$.

Full size|PPT slide

Furthermore, the depth of the quantum circuit depends on the circuit composed of specific quantum gates. Then we need to clarify the construction circuit of the Oracle in the quantum search algorithms. Due to the method by Qiu et al. [28], we will introduce a construction for the Oracle in the original and modified Grover’s algorithms.

$U_{f(x)}=I^{\otimes n}-2|\tau ⟩⟨\tau |$ is employed in the Grover operator $G=-H^{\otimes n}{U}_0{H}^{\otimes n}{U}_{f(x)}$ to flip the phase of the target state $|\tau ⟩=|x_0{x}_1\cdots x_{n-1}⟩$, where $\tau =x_0{x}_1\cdots x_{n-1}\in \{0,1{\}}^n$. Thus, the specific construction circuit of $U_{f(x)}$ (see Fig.7) is as follows:

Fig.7 The quantum circuit corresponding to the Oracle $U_{f(x)}$.

Full size|PPT slide

(65)$U_{f(x)}=\left(\underset{i=0}{\overset{n-1}{⨂}}{X}^{1-x_i}\right)\left(C^{n-1}Z\right)\left(\underset{i=0}{\overset{n-1}{⨂}}{X}^{1-x_i}\right),$

where $C^{n-1}Z$ will only flip the phase of $|1{⟩}^{\otimes n}$,

(66)$\left(C^{n-1}Z\right)|x⟩=\{\begin{array}{ll}-|x⟩,& |x⟩=|1{⟩}^{\otimes n},\\ |x⟩,& \text{otherwise},\end{array}$

where $x=x_0{x}_1\cdots x_{n-1}\in \{0,1{\}}^n$. Besides, it should be noted that

(67)$X^{1-x_i}=\{\begin{array}{ll}X,& x_i=0,\\ I,& x_i=1,\end{array}$

where $i\in \{0,1,\cdots ,n-1\}$. In particular, the construction circuit of $U_0=I^{\otimes n}-2(|0⟩⟨0|{)}^{\otimes n}$ (see Fig.8) is

Fig.8 The quantum circuit corresponding to the Oracle $U_0$.

Full size|PPT slide

(68)$U_0=\left(X^{\otimes n}\right)\left(C^{n-1}Z\right)\left(X^{\otimes n}\right).$

It can be found that the quantum circuit in Fig.7 or Fig.8 has a circuit depth of 3.

Similarly, we can also give the specific construction circuit of $R_{f(x)}=I^{\otimes n}+({\mathrm{e}}^{\mathrm{i}\varphi }-1)|\tau ⟩⟨\tau |$ in the operator $L=-H^{\otimes n}{R}_0{H}^{\otimes n}{R}_{f(x)}$ (see Fig.9) as follows:

Fig.9 The quantum circuit corresponding to the Oracle $R_{f(x)}$.

Full size|PPT slide

(69)$R_{f(x)}=\left(\underset{i=0}{\overset{n-1}{⨂}}{X}^{1-x_i}\right)\left(C^{n-1}R(\varphi )\right)\left(\underset{i=0}{\overset{n-1}{⨂}}{X}^{1-x_i}\right),$

where $R(\varphi )$ represents the rotation gate,

(70)$R(\varphi )=\left(\begin{array}{cc}1& 0\\ 0& {\mathrm{e}}^{\mathrm{i}\varphi }\end{array}\right),$

and $C^{n-1}R(\varphi )$ will only rotate the phase of $|1{⟩}^{\otimes n}$,

(71)$\left(C^{n-1}R(\varphi )\right)|x⟩=\{\begin{array}{ll}{\mathrm{e}}^{\mathrm{i}\varphi }|x⟩,& |x⟩=|1{⟩}^{\otimes n},\\ |x⟩,& \text{otherwise},\end{array}$

where $x=x_0{x}_1\cdots x_{n-1}\in \{0,1{\}}^n$. In particular, the construction circuit of $R_0=I^{\otimes n}+({\mathrm{e}}^{\mathrm{i}\varphi }-1)(|0⟩⟨0|{)}^{\otimes n}$ in operator $L$ (see Fig.10) is

Fig.10 The quantum circuit corresponding to the Oracle $R_0$.

Full size|PPT slide

(72)$R_0=\left(X^{\otimes n}\right)\left(C^{n-1}R(\varphi )\right)\left(X^{\otimes n}\right).$

Quantum circuit in Fig.9 or Fig.10 also has a circuit depth of 3.

If the target state is $|1{⟩}^{\otimes n}$, then the depth of circuit is only 1. We ignore this special case. By the way, perhaps there are other better methods to construct the quantum circuits of Oracle, but we will not cover it here. Throughout this paper, we use the same methods described above to construct the Oracle circuits in the Grover operator $G$ and operator $L$.

After identifying the specific quantum gates in the original and modified Grover’s algorithms, we might calculate the circuit depth of these two methods.

Theorem 3. The circuit depths for the original and modified Grover’s algorithms are $1+8\lfloor \frac{\pi }{4}\sqrt{2^n}\rfloor$ and $9+8\lfloor \frac{\pi }{4}\sqrt{2^n}-\frac{1}{2}\rfloor$, respectively.

Proof. In Grover’s algorithm, Grover operator $G=-H^{\otimes n}{U}_0{H}^{\otimes n}{U}_{f(x)}$ is executed with $\lfloor \frac{\pi }{4}\sqrt{2^n}\rfloor$ times, where $dep(U_f)=dep(U_0)=3$ and $dep(H^{\otimes n})=1$. Thus, the circuit depth of Grover’s algorithm is

(73)$\begin{array}{rl}dep(\text{Grover})=& 1+\lfloor \frac{\pi }{4}\sqrt{2^n}\rfloor \cdot (3+1+3+1)\\ =& 1+8\lfloor \frac{\pi }{4}\sqrt{2^n}\rfloor .\end{array}$

Similarly, since operator $L=-H^{\otimes n}{R}_0{H}^{\otimes n}{R}_{f(x)}$ is executed with $J+1$ times, where $J=\lfloor (\pi /2-\theta )/(2\theta )\rfloor$, $\theta =\arcsin \left(\sqrt{1/2^n}\right)$, and $dep(R_f)=dep(R_0)=3$, the circuit depth of the modified Grover’s algorithm is

(74)$\begin{array}{rl}dep(\text{modified Grover})=& 1+\left(\lfloor \frac{\pi }{4}\sqrt{2^n}-\frac{1}{2}\rfloor +1\right)\\ & \cdot (3+1+3+1)\\ =& 9+8\lfloor \frac{\pi }{4}\sqrt{2^n}-\frac{1}{2}\rfloor .\end{array}$

□

It has been discovered that the circuit depths of the original and modified Grover’s algorithms deepen as $n$ increases.

Next, we give the circuit depth of the DEGA by the following theorem.

Theorem 4. The circuit depth of Algorithm 3 is $8(nmod2)+9$.

Proof. When $n$ is an even number, the DEGA will run $\lfloor n/2\rfloor$ parts 2-qubit Grover’s algorithm, and each part only needs to iterate the Grover operator $G$ once, so the circuit depth is

(75)$dep(\text{DEGA},n\text{is even})=1+1\cdot (3+1+3+1)=9.$

When $n$ is an odd number, the DEGA will run $\lfloor n/2\rfloor -1$ parts 2-qubit Grover’s algorithm and 1 part 3-qubit modified Grover’s algorithm, and the last part needs to iterate the operator $L$ twice, so the circuit depth is

(76)$dep(\text{DEGA},n\text{is odd})=1+2\cdot (3+1+3+1)=17.$

In other words, the actual depth of our circuit is

(77)$dep(\text{DEGA})=8(n\text{mod}2)+9=\{\begin{array}{ll}9,& n\text{is even},\\ 17,& n\text{is odd}.\end{array}$

□

Besides, each portion of the DEGA only comprises two or three qubits, making physical experiment verification trivial.

Therefore, the actual circuit depth will be shallower comparing with the original and modified Grover’s algorithms. The circuit depth of the DEGA only depends on the parity of $n$, and it is not deepened as $n$ increases.

Next, we will contrast the DEGA with the existing distributed Grover’s algorithms.

In Ref. [27], they split the original $n$-qubit Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ two subfunctions $f_{\text{even}/\text{odd}}:\{0,1{\}}^{n-1}\to \{0,1\}$ as in Eq. (30) and Eq. (31), and then executed $(n-1)$-qubit Grover’s algorithm for each subfunction. After that, they will decide whether 0 or 1 to add to the $i$-th bit based on which subfunction can correctly run the result (0 for $f_{\text{even}}$ and 1 for $f_{\text{odd}}$). That is to say, they only acquired $n-1$ qubits of the target state rather than the target state itself directly. The total number of qubits used in their scheme is $2(n-1)$.

In Ref. [28], they have solved the case of multiple targets, and presented the serial and parallel distributed Grover’s algorithms and divided the original function $f$ into $2^k$ subfunctions $f_p:\{0,1{\}}^{n-k}\to \{0,1\}$ as in Eq. (32), where $2^k$ represents the number of computing nodes. The total number of qubits used in their parallel scheme is $2^k(n-k)$.

Finally, we will analyse why DEGA is not suitable for solving multiple target strings. To begin with, when the target string is a single string, the final state is a direct product state, which may be thought of as the direct product of several quantum states. At this stage, each node can accurately search for some information of the initial target string, yielding the original target string. However, when the target string consists of multiple strings, the final state may be an entangled state, which cannot be decomposed into a direct product of multiple quantum states at this point. In other words, DEGA is not applicable when the target string includes several strings and its related quantum state is an entangled state. Therefore, how to design a distributed quantum algorithm to solve the exact search problem with the case of multiple targets is still an open problem. Perhaps additional quantum operations, such as performing quantum gates between nodes, are needed to enable entanglement of the final state.

5 Experiment

In this section, we will provide particular situations of the DEGA on MindQuantum (a quantum software). These experiments will further demonstrate the correctness of the DEGA and explicate the specific steps of implement $n$-qubit DEGA, where $n\in \{2,3,4,5\}$. After that, we will simulate the 5-qubit DEGA running in the depolarization channel and compare with the original and modified Grover’s algorithms. Since our circuit is shallower, it will be more resistant to the depolarization channel noise.

5.1 The 2-qubit DEGA, the target string τ = 01

Let Boolean function $f:\{0,1{\}}^2\to \{0,1\}$. Suppose

(78)$f(x)=\{\begin{array}{ll}1,& x=01,\\ 0,& x\ne 01,\end{array}$

where $x\in \{0,1{\}}^2$ and $\tau =01$ is the target string. When $n=2$, the DEGA is a 2-qubit Grover’s algorithm. Thus, we can build its circuit (see Fig.11).

Fig.11 Quantum circuit of the 2-qubit DEGA (target string $\tau =01$).

Full size|PPT slide

By sampling the circuit in Fig.11 10 000 times, the sampling results can be found in Fig.12.

Fig.12 The sampling results of the 2-qubit DEGA (target string $\tau =01$).

Full size|PPT slide

The sampling results demonstrate that $\tau =01$ is obtained exactly after measurement. Besides, the total number of quantum gates is 14 and the circuit depth is 9.

5.2 The 3-qubit DEGA, the target string τ = 101

Let Boolean function $f:\{0,1{\}}^3\to \{0,1\}$. Suppose

(79)$f(x)=\{\begin{array}{ll}1,& x=101,\\ 0,& x\ne 101,\end{array}$

where $x\in \{0,1{\}}^3$ and $\tau =101$ is the target string. When $n=3$, the DEGA is a 3-qubit modified Grover’s algorithm. Thus, we can build its circuit (see Fig.13). Note that PhaseShift (called the PS gate) is a single-qubit gate, whose matric is as follows:

Fig.13 Quantum circuit of the 3-qubit DEGA (target string $\tau =101$). The parameter in the circuit is $\varphi =2\arcsin \left(\sin \left(\frac{\pi }{4J+6}\right)/\sin \theta \right)=2.1268800471555034\approx 2.1269$, where $J=\lfloor (\pi /2-\theta )/(2\theta )\rfloor$ and $\theta =\arcsin \left(\sqrt{1/2^3}\right)$.

Full size|PPT slide

(80)$\text{PS}(\varphi )=\left(\begin{array}{cc}1& 0\\ 0& {\mathrm{e}}^{\mathrm{i}\varphi }\end{array}\right).$

By sampling the circuit in Fig.13 10 000 times, the sampling results can be found in Fig.14.

Fig.14 The sampling results of the 3-qubit DEGA (target string $\tau =101$).

Full size|PPT slide

The sampling results demonstrate that $\tau =101$ is obtained exactly after measurement. Besides, the total number of quantum gates is 35 and the circuit depth is 17.

5.3 The 4-qubit DEGA, the target string τ = 1001

Let Boolean function $f:\{0,1{\}}^4\to \{0,1\}$. Suppose

(81)$f(x)=\{\begin{array}{ll}1,& x=1001,\\ 0,& x\ne 1001,\end{array}$

where $x\in \{0,1{\}}^4$ and $\tau =1001$ is the target string. When $n=4$, we can decomposes the original search problem into $\lfloor n/2\rfloor =2$ parts. To be specific, we choose last 2 bits in $x$ to divide $f$, then we can get $2^2=4$ subfunctions $f_{0,j}:\{0,1{\}}^2\to \{0,1\}$:

(82)$f_{0,0}(m_0)=f(m_{0}00),$

(83)$f_{0,1}(m_0)=f(m_{0}01),$

(84)$f_{0,2}(m_0)=f(m_{0}10),$

(85)$f_{0,3}(m_0)=f(m_{0}11),$

where $m_0\in \{0,1{\}}^2$ and $j\in \{0,1,2,3\}$. Obviously, $f_{0,0}(m_0)=f_{0,2}(m_0)=f_{0,3}(m_0)\equiv 0$, and

(86)$f_{0,1}(m_0)=\{\begin{array}{ll}1,& m_0=10,\\ 0,& m_0\ne 10,\end{array}$

where $m_0\in \{0,1{\}}^2$ and $10$ is the target substring.

Afterwards, we generate a new function $g_0:\{0,1{\}}^2\to \{0,1\}$ through above four subfunctions,

(87)$\begin{array}{rl}{g}_0(m_0)=& \text{OR}\left(f_{0,0}(m_0),f_{0,1}(m_0),f_{0,2}(m_0),f_{0,3}(m_0)\right)\\ =& \{\begin{array}{ll}1,& m_0=10,\\ 0,& m_0\ne 10,\end{array}\end{array}$

where $m_0\in \{0,1{\}}^2$.

Similarly, we choose first 2 bits in $x$ to divide $f$, then we can get $2^2=4$ subfunctions $f_{1,j}:\{0,1{\}}^2\to \{0,1\}$:

(88)$f_{1,0}(m_1)=f(00m_1),$

(89)$f_{1,1}(m_1)=f(01m_1),$

(90)$f_{1,2}(m_1)=f(10m_1),$

(91)$f_{1,3}(m_1)=f(11m_1),$

where $m_1\in \{0,1{\}}^2$ and $j\in \{0,1,2,3\}$. Obviously, $f_{1,0}(m_1)=f_{1,1}(m_1)=f_{1,3}(m_1)\equiv 0$, and

(92)$f_{1,2}(m_1)=\{\begin{array}{ll}1,& m_1=01,\\ 0,& m_1\ne 01,\end{array}$

where $m_1\in \{0,1{\}}^2$ and $01$ is the target substring.

Afterwards, we generate a new function $g_1:\{0,1{\}}^2\to \{0,1\}$ through above four subfunctions,

(93)$\begin{array}{rl}{g}_1(m_1)=& \text{OR}\left(f_{1,0}(m_1),f_{1,1}(m_1),f_{1,2}(m_1),f_{1,3}(m_1)\right)\\ =& \{\begin{array}{ll}1,& m_1=01,\\ 0,& m_1\ne 01,\end{array}\end{array}$

where $m_1\in \{0,1{\}}^2$.

So far, we have successfully obtained the subfunctions of two parts, $g_0(m_0)$ and $g_1(m_1)$. Next, we need to run the 2-qubit Grover’s algorithm for each part. Thus, we can build the completed circuit (see Fig.15). Note that since the reading order on MindQuantum is from right to left, which is the opposite of our reading order from left to right, the 2-qubit Grover’s algorithm corresponding to $g_1(m_1)$ is located on the top of the circuit.

Fig.15 Quantum circuit of the 4-qubit DEGA (target string $\tau =1001$).

Full size|PPT slide

By sampling the circuit in Fig.15 10 000 times, the sampling results can be found in Fig.16.

Fig.16 The sampling results of the 4-qubit DEGA (target string $\tau =1001$).

Full size|PPT slide

The sampling results demonstrate that $\tau =1001$ is obtained exactly after measurement. Besides, the total number of quantum gates is 28 and the circuit depth is 9.

If the original or modified Grover’s algorithm is employed to search 1001, we can build the completed circuits (see Fig.17 and Fig.18) respectively. By sampling the circuits in Fig.17 and Fig.18 10 000 times respectively, the sampling results can be found in Fig.19 and Fig.20.

Fig.17 Quantum circuit of the 4-qubit Grover’s algorithm (target string $\tau =1001$).

Full size|PPT slide

Fig.18 Quantum circuit of the 4-qubit modified Grover’s algorithm (target string $\tau =1001$). The parameter in the circuit is $\varphi =2\arcsin \left(\sin \left(\frac{\pi }{4J+6}\right)/\sin \theta \right)=2.195057699090115\approx 2.1951$, where $J=\lfloor (\pi /2-\theta )/(2\theta )\rfloor$ and $\theta =\arcsin \left(\sqrt{1/2^4}\right)$.

Full size|PPT slide

Fig.19 The sampling results of the 4-qubit Grover’s algorithm (target string $\tau =1001$).

Full size|PPT slide

Fig.20 The sampling results of the 4-qubit modified Grover’s algorithm (target string $\tau =1001$).

Full size|PPT slide

It can be found that the probability of Grover’s algorithm acquiring target string $\tau =1001$ is 0.9627, which is not exact, while the modified Grover’s algorithm can accurately obtain $\tau =1001$. The number of quantum gates required by two algorithms is 70, and the circuit depth is 25.

5.4 The 5-qubit DEGA, the target string τ = 01001

Let Boolean function $f:\{0,1{\}}^5\to \{0,1\}$. Suppose

(94)$f(x)=\{\begin{array}{ll}1,& x=01001,\\ 0,& x\ne 01001,\end{array}$

where $x\in \{0,1{\}}^5$ and $\tau =01001$ is the target string. When $n=5$, we can decomposes the original search problem into $\lfloor n/2\rfloor =2$ parts. To be specific, we choose last 2 bits in $x$ to divide $f$, then we can get $2^2=4$ subfunctions $f_{0,j}:\{0,1{\}}^3\to \{0,1\}$:

(95)$f_{0,0}(m_0)=f(m_{0}00),$

(96)$f_{0,1}(m_0)=f(m_{0}01),$

(97)$f_{0,2}(m_0)=f(m_{0}10),$

(98)$f_{0,3}(m_0)=f(m_{0}11),$

where $m_0\in \{0,1{\}}^3$ and $j\in \{0,1,2,3\}$. Obviously, $f_{0,0}(m_0)=f_{0,2}(m_0)=f_{0,3}(m_0)\equiv 0$, and

(99)$f_{0,1}(m_0)=\{\begin{array}{l}1,m_0=010,\\ 0,m_0\ne 010,\end{array}$

where $m_0\in \{0,1{\}}^3$ and $010$ is the target substring.

Afterwards, we generate a new function $g_0:\{0,1{\}}^3\to \{0,1\}$ through above four subfunctions,

(100)$\begin{array}{rl}{g}_0(m_0)=& \text{OR}\left(f_{0,0}(m_0),f_{0,1}(m_0),f_{0,2}(m_0),f_{0,3}(m_0)\right)\\ =& \{\begin{array}{l}1,m_0=010,\\ 0,m_0\ne 010,\end{array}\end{array}$

where $m_0\in \{0,1{\}}^3$.

Similarly, we choose first $3$ bits in $x$ to divide $f$, then we can get $2^3=8$ subfunctions $f_{1,j}:\{0,1{\}}^2\to \{0,1\}$:

(101)$f_{1,0}(m_1)=f(000m_1),f_{1,4}(m_1)=f(100m_1),$

(102)$f_{1,1}(m_1)=f(001m_1),f_{1,5}(m_1)=f(101m_1),$

(103)$f_{1,2}(m_1)=f(010m_1),f_{1,6}(m_1)=f(110m_1),$

(104)$f_{1,3}(m_1)=f(011m_1),f_{1,7}(m_1)=f(111m_1),$

where $m_1\in \{0,1{\}}^2$ and $j\in \{0,1,\cdots ,7\}$. Obviously, $f_{1,0}(m_1)=$$f_{1,1}(m_1)$=$f_{1,3}(m_1)=f_{1,4}(m_1)=f_{1,5}(m_1)=f_{1,6}(m_1)=f_{1,7}(m_1)\equiv 0$, and

(105)$f_{1,2}(m_1)=\{\begin{array}{ll}1,& m_1=01,\\ 0,& m_1\ne 01,\end{array}$

where $m_1\in \{0,1{\}}^2$ and $01$ is the target substring.

Afterwards, we generate a new function $g_1:\{0,1{\}}^2\to \{0,1\}$ through above eight subfunctions,

(106)$\begin{array}{rl}{g}_1(m_1)=& \text{OR}\left(f_{1,0}(m_1),f_{1,1}(m_1),\cdots ,f_{1,7}(m_1)\right)\\ =& \{\begin{array}{ll}1,& m_1=01,\\ 0,& m_1\ne 01,\end{array}\end{array}$

where $m_1\in \{0,1{\}}^2$.

So far, we have successfully obtained the subfunctions of two parts, $g_0(m_0)$ and $g_1(m_1)$. Next, we need to run the 3-qubit modified Grover’s algorithm for the part of subfunction $g_0(m_0)$, and the 2-qubit Grover’s algorithm for the part of subfunction $g_1(m_1)$. Thus, we can build the completed circuit (see Fig.21). Once again since the reading order on MindQuantum is from right to left, which is the opposite of our reading order from left to right, the 2-qubit Grover’s algorithm corresponding to $g_1(m_1)$ is located on the top of the circuit.

Fig.21 Quantum circuit of the 5-qubit DEGA (target string $\tau =01001$). The parameter in the circuit is $\varphi =2\arcsin \left(\sin \left(\frac{\pi }{4J+6}\right)/\sin \theta \right)=2.1268800471555034\approx 2.1269$, where $J=\lfloor (\pi /2-\theta )/(2\theta )\rfloor$ and $\theta =\arcsin \left(\sqrt{1/2^3}\right)$.

Full size|PPT slide

By sampling the circuit in Fig.21 10 000 times, the sampling results can be found in Fig.22.

Fig.22 The sampling results of the 4-qubit DEGA (target string $\tau =01001$).

Full size|PPT slide

The sampling results demonstrate that $\tau =01001$ is obtained exactly after measurement. Besides, the total number of quantum gates is 53 and the circuit depth is 17.

If the original or modified Grover’s algorithm is employed to search $\tau =01001$, we can build the completed circuits (see Fig.23 and Fig.24 respectively). By sampling the circuits in Fig.23 and Fig.24 10 000 times respectively, the sampling results can be found in Fig.25 and Fig.26.

Fig.23 Quantum circuit of the 5-qubit Grover’s algorithm (target string $\tau =01001$).

Full size|PPT slide

Fig.24 Quantum circuit of the 5-qubit modified Grover’s algorithm (target string $\tau =01001$). The parameter in the circuit is $\varphi =2\arcsin \left(\sin \left(\frac{\pi }{4J+6}\right)/\sin \theta \right)=2.764763603060391\approx 2.7648$, where $J=\lfloor (\pi /2-\theta )/(2\theta )\rfloor$ and $\theta =\arcsin \left(\sqrt{1/2^5}\right)$.

Full size|PPT slide

Fig.25 The sampling results of the 5-qubit Grover’s algorithm (target string $\tau =01001$).

Full size|PPT slide

Fig.26 The sampling results of the 5-qubit modified Grover’s algorithm (target string $\tau =01001$).

Full size|PPT slide

It can be found that the probability of Grover’s algorithm acquiring target string $\tau =01001$ is 0.9993, which is not exact, while the modified Grover’s algorithm can accurately obtain $\tau =01001$. The number of quantum gates required by two algorithms is 117, and the circuit depths are 33.

Through the above experiments, we can know the specific steps of implement $n$-qubit DEGA, where $n\in \{2,3,4,5\}$. Besides, we found that the modified Grover’s algorithm and the DEGA can achieve exact search, while the Grover’s algorithm can obtain target strings with high probability (see Fig.27). In addition, the number of quantum gates and circuit depth required by the original and modified Grover’s algorithms are the same, which will deepen as $n$ increases. However, the DEGA requires fewer quantum gates (see Fig.28) and shallower circuit depth (Fig.29). The circuit depth of the DEGA only depends on the parity of $n$, and it does not deepen as $n$ increases.

Fig.27 The probability of obtaining the target string by different algorithms.

Full size|PPT slide

Fig.28 The number of quantum gates required by different algorithms.

Full size|PPT slide

Fig.29 The depth of quantum circuit of different algorithms.

Full size|PPT slide

5.5 The depolarization channel

In the above experiments, we ignore the influence of noise, which means that we can achieve theoretically exact or high probability search. However, due to the existence of noise, there are certain errors in the operation of each type of quantum gate on a real quantum computer.

In this subsection, we consider the depolarization channel that is a essential type of quantum noise. After that, we will simulate the 5-qubit DEGA running in the depolarization channel and compare with the original and modified Grover’s algorithms. Through such simulations, it shows the DEGA will be more resistant to the depolarization channel noise.

In the depolarization channel [35], a single qubit will be replaced by the completely mixed state $I/2$ with a probability of $p$ and remain unaltered with a probability of $1-p$. It means the state of the quantum system has changed to

(107)$\epsilon (\rho )=(1-p)\rho +p\left({\displaystyle \frac{I}{2}}\right),$

where $\rho$ represents the initial quantum state. For arbitrary state $\rho$, we have

(108)${\displaystyle \frac{I}{2}}={\displaystyle \frac{\rho +X\rho X+Y\rho Y+Z\rho Z}{4}},$

where $X,Y$ and $Z$ are Pauli operators. Inserting Eq. (108) into Eq. (107) gives

(109)$\epsilon (\rho )=\left(1-{\displaystyle \frac{3p}{4}}\right)\rho +{\displaystyle \frac{p}{4}}\left(X\rho X+Y\rho Y+Z\rho Z\right).$

For simplicity, the depolarization channel is sometimes written as

(110)$\epsilon (\rho )=\left(1-p\right)\rho +{\displaystyle \frac{p}{3}}\left(X\rho X+Y\rho Y+Z\rho Z\right),$

which indicates the state $\rho$ will remain unaltered with the a probability of $1-p$, and the Pauli operators $X,Y,Z$ will be applied with a probability of $p/3$ for each operators.

Furthermore, the depolarizing channel can be extended to a $d$-dimensional ($d>2$) quantum system. Similarly, the depolarizing channel of a $d$-dimensional quantum system replaces the completely mixed state $I/d$ with a probability of $p$, and remains unaltered with a probability of $1-p$. The corresponding quantum operation is

(111)$\epsilon (\rho )=(1-p)\rho +p\left({\displaystyle \frac{I}{d}}\right).$

On MindQuantum, we simulate the quantum algorithms running in the depolarization channel by adding noise behind each quantum gate. That is, we can rebuild the quantum circuits of the original and modified Grover’s algorithms and the DEGA in the depolarization channel (see Fig.30 to Fig.32). In the process of simulation, we set the noise parameter $p=0.01$ and DC represents the depolarization channel.

Fig.30 Quantum circuit of the 5-qubit Grover’s algorithm (target string $\tau =01001$) in the depolarizing channel.

Full size|PPT slide

Fig.31 Quantum circuit of the 5-qubit modified Grover’s algorithm (target string $\tau =01001$) in the depolarizing channel. The parameter in the circuit is $\varphi =2\arcsin \left(\sin \left(\frac{\pi }{4J+6}\right)/\sin \theta \right)=2.764763603060391\approx 2.7648$, where $J=\lfloor (\pi /2-\theta )/(2\theta )\rfloor$ and $\theta =\arcsin \left(\sqrt{1/2^5}\right)$.

Full size|PPT slide

Fig.32 Quantum circuit of the 5-qubit DEGA (target string $\tau =01001$) in the depolarizing channel. The parameter in the circuit is $\varphi =2\arcsin \left(\sin \left(\frac{\pi }{4J+6}\right)/\sin \theta \right)=2.1268800471555034\approx 2.1269$, where $J=\lfloor (\pi /2-\theta )/(2\theta )\rfloor$ and $\theta =\arcsin \left(\sqrt{1/2^3}\right)$.

Full size|PPT slide

By sampling the above three circuits 10 000 times, respectively. In order to better reproduce the experimental results, we set the random seeds of simulator and sampling both being 42. It is worth noting that modifying the random seed will alter the sampling outcome. In actuality, the random seed is a function to generate random number. The simulator will sample the quantum circuit according to the generated random number. As a result, various random numbers provide varied sampling outcomes in the simulator. Then, if we set the random seed to a fixed value (set the random seed being 42 in the full text), the experimental results in this paper can be reproduced when repeating the same experiment. At last, the sampling results can be found in Fig.33 to Fig.35, respectively.

Fig.33 The sampling results of the 5-qubit Grover’s algorithm in the depolarizing channel. The noise parameter $p=0.01$.

Full size|PPT slide

Fig.34 The sampling results of the 5-qubit modified Grover’s algorithm in the depolarizing channel. The noise parameter $p=0.01$.

Full size|PPT slide

Fig.35 The sampling results of the 5-qubit DEGA in the depolarizing channel. The noise parameter $p=0.01$.

Full size|PPT slide

It can be seen that due to the existence of noise, it will not achieve exact search. Compared with other states, $\tau =01001$ can be obtained with a higher probability, which means that the target string can be successfully searched. The probability obtained by Grover’s algorithm is 0.3495, the probability by the modified Grover’s algorithm is 0.3501, and the probability by the DEGA is 0.6208. Obviously, the probability of the DEGA is higher.

Furthermore, we set the noise parameter $p$ as $0,0.01,\cdots ,0.09$, and count the probability of obtaining $\tau =01001$ in each sampling by different algorithms. The statistical chart as shown in Fig.36.

Fig.36 The probability of obtaining $\tau =01001$ by different algorithms.

Full size|PPT slide

With the increase of noise parameter $p$, the probability of obtaining $\tau =01001$ decreases. In addition, in the noisy environment, the probabilities of getting target string by the original and modified Grover’s algorithms are close. At the same time, under the premise of the same noise parameter, the probability of acquiring $\tau =01001$ by the DEGA is higher than those of the original and modified Grover’s algorithms.

When $p=0.07$, the sampling results can be found in Fig.37 to Fig.39, respectively. The probability of obtaining the target string $\tau =01001$ are 0.0363, 0.0366 and 0.0899, respectively. The desired results were drown out by the channel noise in the original and modified Grover’s algorithms. However, $\tau =01001$ can still be obtained with a higher probability than other states in the DEGA. Even if $p=0.09$, the DEGA still works (see Fig.40 to Fig.42).

Fig.37 The sampling results of the 5-qubit Grover’s algorithm in the depolarizing channel. The noise parameter $p=0.07$.

Full size|PPT slide

Fig.38 The sampling results of the 5-qubit modified Grover’s algorithm in the depolarizing channel. The noise parameter $p=0.07$.

Full size|PPT slide

Fig.39 The sampling results of the 5-qubit DEGA in the depolarizing channel. The noise parameter $p=0.07$.

Full size|PPT slide

Fig.40 The sampling results of the 5-qubit Grover’s algorithm in the depolarizing channel. The noise parameter $p=0.09$.

Full size|PPT slide

Fig.41 The sampling results of the 5-qubit modified Grover’s algorithm in the depolarizing channel. The noise parameter $p=0.09$.

Full size|PPT slide

Fig.42 The sampling results of the 5-qubit DEGA in the depolarizing channel. The noise parameter $p=0.09$.

Full size|PPT slide

It can be found that although the number of qubits of the DEGA is the same as those of the original and modified Grover’s algorithms, our circuit depth is shallower, so that our scheme is more resistant to the depolarization channel noise. In other words, it further illustrates that distributed quantum algorithm has the superiority of resisting noise.

6 Conclusion

Quantum computation is entering the noisy intermediate-scale quantum (NISQ) era. Currently, small-qubit quantum computers are much easier to implement than large-scale universal quantum computers. Hence, researchers are considering how several small-scale devices might collaborate to accomplish a task on a large scale.

In this paper, we have focused on the combination of distributed computing and the exact Grover’s algorithm, and considered a search problem that includes only one target item in the unordered database. After that, we have proposed a distributed exact Grover’s algorithm (DEGA), which decomposes the original search problem into $\lfloor n/2\rfloor$ parts.

Specifically, (i) our algorithm is as exact as the modified version of Grover’s algorithm by Long, which means the theoretical probability of finding the objective state is 100%; (ii) the actual depth of our circuit is $8(n\text{mod}2)+9$, which is less than the circuit depths of the original and modified Grover’s algorithms, $1+8\lfloor \frac{\pi }{4}\sqrt{2^n}\rfloor$ and $9+8\lfloor \frac{\pi }{4}\sqrt{2^n}-\frac{1}{2}\rfloor$, respectively. It only depends on the parity of $n$, and it does not deepen as $n$ increases; (iii) additional auxiliary qubits will not be employed. In our framework, the total number of qubits is $n$ rather than $2^k(n-k)$, where $2^k$ represents the number of computing nodes in the previous distributed method.

Eventually, we have provided particular situations of the DEGA on MindQuantum (a quantum software). It has further demonstrated the correctness of the DEGA and explicated the specific steps of implement $n$-qubit DEGA, where $n\in \{2,3,4,5\}$. Through the experiments, we have found that the modified Grover’s algorithm and the DEGA can achieve exact search, while Grover’s algorithm can obtain target strings with high probability. In addition, the number of quantum gates and circuit depth required by the original and modified Grover’s algorithms are the same, which will deepen as $n$ increases. However, the DEGA requires fewer quantum gates and shallower circuit depth. The circuit depth of the DEGA only depends on the parity of $n$, and it does not deepen as $n$ increases.

After that, we have simulated a $5$-qubit DEGA running in the depolarization channel and compared with the original and modified Grover’s algorithms. Through such simulations, it shows the DEGA will be more resistant to the depolarization channel noise. In other words, it further illustrates that distributed quantum algorithm has the superiority of resisting noise.

However, we have only designed a distributed exact quantum algorithm for the case of unique target in search problem, so it is still open that designing a distributed exact quantum algorithm solves the search problem with the case of multiple targets.

7 Appendix A: The equivalence of Eq. (15) and Eq. (16)

Let

(112)$\left(\begin{array}{cc}{L}_{11}& L_{12}\\ L_{21}& L_{22}\end{array}\right)=-{\mathrm{e}}^{\mathrm{i}\varphi }\left[\cos \left({\displaystyle \frac{\alpha }{2}}\right)I+\mathrm{i}\sin \left({\displaystyle \frac{\alpha }{2}}\right)(n_{x}X+n_{y}Y+n_{z}Z)\right].$

In order to prove the equivalence of Eq. (15) and Eq. (16), it is equivalent to proving

(113)$\left(\begin{array}{cc}{L}_{11}& L_{12}\\ L_{21}& L_{22}\end{array}\right)=\left(\begin{array}{cc}-{\mathrm{e}}^{\mathrm{i}\varphi }(1+({\mathrm{e}}^{\mathrm{i}\varphi }-1){\sin }^2\theta )& -{\mathrm{e}}^{\mathrm{i}\varphi }(1-{\mathrm{e}}^{-\mathrm{i}\varphi })\sin \theta \cos \theta \\ -{\mathrm{e}}^{\mathrm{i}\varphi }({\mathrm{e}}^{\mathrm{i}\varphi }-1)\sin \theta \cos \theta & -{\mathrm{e}}^{\mathrm{i}\varphi }(1-(1-{\mathrm{e}}^{-\mathrm{i}\varphi }){\sin }^2\theta )\end{array}\right).$

Inserting Pauli gates to the right of Eq. (112), we have

(114)$\begin{array}{rl}& -{\mathrm{e}}^{\mathrm{i}\varphi }\left[\cos \left(\frac{\alpha }{2}\right)I+\mathrm{i}\sin \left(\frac{\alpha }{2}\right)(n_{x}X+n_{y}Y+n_{z}Z)\right]\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left[\cos \left(\frac{\alpha }{2}\right)\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)+\mathrm{i}\sin \left(\frac{\alpha }{2}\right)\left(n_x\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)+n_y\left(\begin{array}{cc}0& -\mathrm{i}\\ \mathrm{i}& 0\end{array}\right)+n_z\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right)\right)\right]\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(\begin{array}{cc}\cos \left({\displaystyle \frac{\alpha }{2}}\right)+\mathrm{i}\sin \left({\displaystyle \frac{\alpha }{2}}\right)n_z& \mathrm{i}\sin \left({\displaystyle \frac{\alpha }{2}}\right)n_x+\sin \left({\displaystyle \frac{\alpha }{2}}\right)n_y\\ \mathrm{i}\sin \left({\displaystyle \frac{\alpha }{2}}\right)n_x-\sin \left({\displaystyle \frac{\alpha }{2}}\right)n_y& \cos \left({\displaystyle \frac{\alpha }{2}}\right)-\mathrm{i}\sin \left({\displaystyle \frac{\alpha }{2}}\right)n_z\end{array}\right)=\left(\begin{array}{cc}{L}_{11}& L_{12}\\ L_{21}& L_{22}\end{array}\right),\end{array}$

where

(115)$n_x={\displaystyle \frac{\cos \theta }{\cos \beta }}\cos \left({\displaystyle \frac{\varphi }{2}}\right),n_y={\displaystyle \frac{\cos \theta }{\cos \beta }}\sin \left({\displaystyle \frac{\varphi }{2}}\right),n_z={\displaystyle \frac{\cos \theta }{\cos \beta }}\cos \left({\displaystyle \frac{\varphi }{2}}\right)\tan \theta .$

Besides, we know that

(116)$\alpha =4\beta ,\sin \beta =\sin \left({\displaystyle \frac{\varphi }{2}}\right)\sin \theta .$

Furthermore, we have

$\begin{array}{rl}{L}_{11}& =-{\mathrm{e}}^{\mathrm{i}\varphi }\left(\cos \left(\frac{\alpha }{2}\right)+\mathrm{i}\sin \left(\frac{\alpha }{2}\right)n_z\right)\\ & =-{\mathrm{e}}^{\mathrm{i}\varphi }\left(\cos \left(\frac{\alpha }{2}\right)+\mathrm{i}\sin \left(\frac{\alpha }{2}\right)\frac{\cos \theta }{\cos \beta }\cos \left(\frac{\varphi }{2}\right)\tan \theta \right)\end{array}$

(117)$\begin{array}{rl}& =-{\mathrm{e}}^{\mathrm{i}\varphi }\left(\cos \left(2\beta \right)+\mathrm{i}\sin \left(2\beta \right)\frac{\text{bcancel}\cos \theta }{\cos \beta }\cos \left(\frac{\varphi }{2}\right)\frac{\sin \theta }{\text{bcancel}\cos \theta }\right)\\ & =-{\mathrm{e}}^{\mathrm{i}\varphi }\left(1-2{\sin }^2\beta +2\mathrm{i}\sin \beta \text{bcancel}\cos \beta \frac{1}{\text{bcancel}\cos \beta }\cos \left(\frac{\varphi }{2}\right)\sin \theta \right)\\ & =-{\mathrm{e}}^{\mathrm{i}\varphi }\left(1-2{\left(\sin \left(\frac{\varphi }{2}\right)\sin \theta \right)}^2+2\mathrm{i}\left(\sin \left(\frac{\varphi }{2}\right)\sin \theta \right)\cos \left(\frac{\varphi }{2}\right)\sin \theta \right)\\ & =-{\mathrm{e}}^{\mathrm{i}\varphi }\left(1-2{\sin }^2\left(\frac{\varphi }{2}\right){\sin }^2\theta +\mathrm{i}\sin \varphi {\sin }^2\theta \right)\\ & =-{\mathrm{e}}^{\mathrm{i}\varphi }\left(1+\left(1-2{\sin }^2\left(\frac{\varphi }{2}\right)+\mathrm{i}\sin \varphi -1\right){\sin }^2\theta \right)\\ & =-{\mathrm{e}}^{\mathrm{i}\varphi }\left(1+\left(\cos \varphi +\mathrm{i}\sin \varphi -1\right){\sin }^2\theta \right)\\ & =-{\mathrm{e}}^{\mathrm{i}\varphi }(1+({\mathrm{e}}^{\mathrm{i}\varphi }-1){\sin }^2\theta ),\end{array}$

(118)$\begin{array}{rl}{L}_{12}=& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(\mathrm{i}\sin \left(\frac{\alpha }{2}\right)n_x+\sin \left(\frac{\alpha }{2}\right)n_y\right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(\mathrm{i}\sin \left(\frac{\alpha }{2}\right)\frac{\cos \theta }{\cos \beta }\cos \left(\frac{\varphi }{2}\right)+\sin \left(\frac{\alpha }{2}\right)\frac{\cos \theta }{\cos \beta }\sin \left(\frac{\varphi }{2}\right)\right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(\mathrm{i}\sin \left(2\beta \right)\frac{\cos \theta }{\cos \beta }\cos \left(\frac{\varphi }{2}\right)+\sin \left(2\beta \right)\frac{\cos \theta }{\cos \beta }\sin \left(\frac{\varphi }{2}\right)\right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(2\mathrm{i}\sin \beta \text{bcancel}\cos \beta \frac{\cos \theta }{\text{bcancel}\cos \beta }\cos \left(\frac{\varphi }{2}\right)+2\sin \beta \text{bcancel}\cos \beta \frac{\cos \theta }{\text{bcancel}\cos \beta }\sin \left(\frac{\varphi }{2}\right)\right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(2\mathrm{i}\left(\sin \left(\frac{\varphi }{2}\right)\sin \theta \right)\cos \theta \cos \left(\frac{\varphi }{2}\right)+2\left(\sin \left(\frac{\varphi }{2}\right)\sin \theta \right)\cos \theta \sin \left(\frac{\varphi }{2}\right)\right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(\mathrm{i}\sin \varphi +1+2{\sin }^2\left(\frac{\varphi }{2}\right)-1\right)\sin \theta \cos \theta \\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(1-\left(\cos \varphi -\mathrm{i}\sin \varphi \right)\right)\sin \theta \cos \theta \\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }(1-{\mathrm{e}}^{-\mathrm{i}\varphi })\sin \theta \cos \theta ,\end{array}$

(119)$\begin{array}{rl}{L}_{21}=& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(\mathrm{i}\sin \left(\frac{\alpha }{2}\right)n_x-\sin \left(\frac{\alpha }{2}\right)n_y\right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(\mathrm{i}\sin \left(\frac{\alpha }{2}\right)\frac{\cos \theta }{\cos \beta }\cos \left(\frac{\varphi }{2}\right)-\sin \left(\frac{\alpha }{2}\right)\frac{\cos \theta }{\cos \beta }\sin \left(\frac{\varphi }{2}\right)\right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(\mathrm{i}\sin \left(2\beta \right)\frac{\cos \theta }{\cos \beta }\cos \left(\frac{\varphi }{2}\right)-\sin \left(2\beta \right)\frac{\cos \theta }{\cos \beta }\sin \left(\frac{\varphi }{2}\right)\right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(2\mathrm{i}\sin \beta \text{bcancel}\cos \beta \frac{\cos \theta }{\text{bcancel}\cos \beta }\cos \left(\frac{\varphi }{2}\right)-2\sin \beta \text{bcancel}\cos \beta \frac{\cos \theta }{\text{bcancel}\cos \beta }\sin \left(\frac{\varphi }{2}\right)\right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(2\mathrm{i}\left(\sin \left(\frac{\varphi }{2}\right)\sin \theta \right)\cos \theta \cos \left(\frac{\varphi }{2}\right)-2\left(\sin \left(\frac{\varphi }{2}\right)\sin \theta \right)\cos \theta \sin \left(\frac{\varphi }{2}\right)\right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(\mathrm{i}\sin \varphi +1-2{\sin }^2\left(\frac{\varphi }{2}\right)-1\right)\sin \theta \cos \theta \\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(\left(\cos \varphi +\mathrm{i}\sin \varphi \right)-1\right)\sin \theta \cos \theta \\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }({\mathrm{e}}^{\mathrm{i}\varphi }-1)\sin \theta \cos \theta ,\end{array}$

$\begin{array}{rl}{L}_{22}=& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(\cos \left(\frac{\alpha }{2}\right)-\mathrm{i}\sin \left(\frac{\alpha }{2}\right)n_z\right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(\cos \left(\frac{\alpha }{2}\right)-\mathrm{i}\sin \left(\frac{\alpha }{2}\right)\frac{\cos \theta }{\cos \beta }\cos \left(\frac{\varphi }{2}\right)\tan \theta \right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(\cos \left(2\beta \right)-\mathrm{i}\sin \left(2\beta \right)\frac{\text{bcancel}\cos \theta }{\cos \beta }\cos \left(\frac{\varphi }{2}\right)\frac{\sin \theta }{\text{bcancel}\cos \theta }\right)\end{array}$

(120)$\begin{array}{rl}=& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(1-2{\sin }^2\beta -2\mathrm{i}\sin \beta \text{bcancel}\cos \beta \frac{1}{\text{bcancel}\cos \beta }\cos \left(\frac{\varphi }{2}\right)\sin \theta \right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(1-2{\left(\sin \left(\frac{\varphi }{2}\right)\sin \theta \right)}^2-2\mathrm{i}\left(\sin \left(\frac{\varphi }{2}\right)\sin \theta \right)\cos \left(\frac{\varphi }{2}\right)\sin \theta \right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(1-2{\sin }^2\left(\frac{\varphi }{2}\right){\sin }^2\theta -\mathrm{i}\sin \varphi {\sin }^2\theta \right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(1-\left(2{\sin }^2\left(\frac{\varphi }{2}\right)-1+\mathrm{i}\sin \varphi +1\right){\sin }^2\theta \right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }\left(1-\left(-\cos \varphi +\mathrm{i}\sin \varphi +1\right){\sin }^2\theta \right)\\ =& -{\mathrm{e}}^{\mathrm{i}\varphi }(1-(1-{\mathrm{e}}^{-\mathrm{i}\varphi }){\sin }^2\theta ).\end{array}$

To sum up, it can be seen from Eq. (117) to Eq. (120) that Eq. (15) and Eq. (16) are equivalent.

References

[1] P. Benioff. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. J. Stat. Phys., 1980, 22(5): 563

[2] P. Benioff. Quantum mechanical Hamiltonian models of Turing machines. J. Stat. Phys., 1982, 29(3): 515

[3] D. Deutsch. Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A, 1985, 400(1818): 97

[4] D. Deutsch, R. Jozsa. Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A, 1992, 439(1907): 553

[5] E.BernsteinU. Vazirani, Quantum complexity theory, in: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC’93), 1993, pp 11–20

[6] D. R. Simon. On the power of quantum computation. SIAM J. Comput., 1997, 26(5): 1474

[7] P.W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in: Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994, pp 124–134

[8] L. K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 1997, 79(2): 325

[9] A. W. Harrow, A. Hassidim, S. Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 2009, 103(15): 150502

[10] D.ChristophH. Peter, A quantum algorithm for finding the minimum, arXiv: quant-ph/9607014v2 (1996)

[11] H. Ramesh, V. Vinay. String matching in O~(n+m) quantum time. J. Discrete Algorithms, 2003, 1(1): 103

[12] A.AmbainisK. BalodisJ.Iraids, ., Quantum speedups for exponential-time dynamic programming algorithms, in: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. San Diego: SIAM, 2019, pp 1783–1793

[13] A.AndrisL. Nikita, Quantum algorithms for computational geometry problems, in: 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, 2020

[14] G. Brassard, P. Hoyer, M. Mosca. . Quantum amplitude amplification and estimation. Contemp. Math., 2002, 305: 53

[15] Z. J. Diao. Exactness of the original Grover search algorithm. Phys. Rev. A, 2010, 82(4): 044301

[16] G. L. Long. Grover algorithm with zero theoretical failure rate. Phys. Rev. A, 2001, 64(2): 022307

[17] J. Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2018, 2: 79

[18] J. I. Cirac, P. Zoller. Quantum computations with cold trapped ions. Phys. Rev. Lett., 1995, 74(20): 4091

[19] C. Y. Lu, X. Q. Zhou, O. Guhne, W. B. Gao, J. Zhang, Z. S. Yuan, A. Goebel, T. Yang, J. W. Pan. Experimental entanglement of six photons in graph states. Nat. Phys., 2007, 3(2): 91

[20] Y. Makhlin, G. Schön, A. Shnirman. Quantum-state engineering with Josephson-junction devices. Rev. Mod. Phys., 2001, 73(2): 357

[21] J. Berezovsky, M. H. Mikkelsen, N. G. Stoltz, L. A. Coldren, D. D. Awschalom. Picosecond coherent optical manipulation of a single electron spin in a quantum dot. Science, 2008, 320(5874): 349

[22] R. Hanson, D. D. Awschalom. Coherent manipulation of single spins in semiconductors. Nature, 2008, 453(7198): 1043

[23] H.BuhrmanH. Röhrig, Distributed quantum computing, in: Mathematical Foundations of Computer Science 2003: 28th International Symposium, Berlin Heidelberg, Springer, 2003, pp 1–20

[24] A. Yimsiriwattan, Jr Lomonaco. Distributed quantum computing: A distributed Shor algorithm. Quantum Inf. Comput. II., 2004, 5436: 360

[25] R. Beals, S. Brierley, O. Gray. . Efficient distributed quantum computing. Proc. R. Soc. A, 2013, 469(2153): 0120686

[26] K. Li, D. W. Qiu, L. Li, S. Zheng, Z. Rong. Application of distributed semiquantum computing model in phase estimation. Inf. Process. Lett., 2017, 120: 23

[27] J. Avron, O. Casper, I. Rozen. Quantum advantage and noise reduction in distributed quantum computing. Phys. Rev. A, 2021, 104(5): 052404

[28] D.W. QiuL. LuoL.G. Xiao, Distributed Grover’s algorithm, arXiv: 2204.10487v3 (2022)

[29] J. W. Tan, L. G. Xiao, D. W. Qiu, L. Luo, P. Mateus. Distributed quantum algorithm for Simon’s problem. Phys. Rev. A, 2022, 106(3): 032417

[30] L.G. XiaoD. W. QiuL.LuoP.Mateus, Distributed Shor’s algorithm, Quantum Inf. Comput. 23(1&2), 27 (2023)

[31] L.G. XiaoD. W. QiuL.Luo, ., Distributed quantum−classical hybrid Shor’s algorithm, arXiv: 2304.12100 (2023)

[32] X.ZhouD. W. QiuL.Luo, Distributed exact quantum algorithms for Bernstein−Vazirani and search problems, arXiv: 2303.10670 (2023)

[33] H.LiD.W. Qiu L.Luo, Distributed exact quantum algorithms for Deutsch−Jozsa problem, arXiv: 2303.10663 (2023)

[34] MindQuantum, URL: gitee.com/mindspore/mindquantum, 2021

[35] M.A. NielsenI.L. Chuang, Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, 2002

Declarations

The authors declare that they have no competing interests and there are no conflicts.

Data availability statement

No data associated in the manuscript.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Nos. 61572532 and 61876195) and the Natural Science Foundation of Guangdong Province of China (No. 2017B030311011).

RIGHTS & PERMISSIONS

2023 Higher Education Press