Optimized quantum random-walk search algorithm for multi-solution search*
Zhang Yu-Chaoa),b), Bao Wan-Sua),b), Wang Xianga),b), Fu Xiang-Quna),b)
Zhengzhou Information Science and Technology Institute, Zhengzhou 450004, China
Synergetic Innovation Center of Quantum Information and Quantum Physics, University of Science and Technology of China, Hefei 230026, China

Corresponding author. E-mail: 2010thzz@sina.com

*Project supported by the National Basic Research Program of China (Grant No. 2013CB338002).

Abstract

This study investigates the multi-solution search of the optimized quantum random-walk search algorithm on the hypercube. Through generalizing the abstract search algorithm which is a general tool for analyzing the search on the graph to the multi-solution case, it can be applied to analyze the multi-solution case of quantum random-walk search on the graph directly. Thus, the computational complexity of the optimized quantum random-walk search algorithm for the multi-solution search is obtained. Through numerical simulations and analysis, we obtain a critical value of the proportion of solutions q. For a given q, we derive the relationship between the success rate of the algorithm and the number of iterations when q is no longer than the critical value.

Keyword: 03.67.Lx; 03.67.Ac; quantum search algorithm; quantum random walk; multi-solution; abstract search algorithm
1. Introduction

The concepts of quantum computation and quantum computer[1] were proposed by Feynman in 1982. In 1985, Deutsch pointed out that the parallel quantum computation could be achieved by taking advantage of the coherent superposition of quantum states.[2] However, it was not until later when Shor’ s algorithm[3] and Grover’ s algorithm[4] were proposed that extensive attention into quantum computers and quantum algorithms was aroused.[57] These greatly promoted the development of quantum computation and quantum communication technologies.

Essentially, Grover’ s algorithm is an exhaustive algorithm on the quantum computer. It solves the unsorted database search and achieves the quadratic speed-up compared with the classical algorithm. Although the Grover algorithm does not reach the obvious increase in speed compared with Shor’ s algorithm, the widely applicable search algorithm has also attracted people’ s attention. With the in-depth study, the efficiency of Grover’ s algorithm has been constantly improved, and it is more and more applied in practical problems. In 2001, Long proposed an improved Grover’ s algorithm with a success rate of 1 by replacing the phase inversion by phase rotation.[8] The Long algorithm[8] has proven to be optimal and the simplest by far.[9] In 2010, Wang et al. proposed a quantum algorithm for searching a target solution of fixed weight, which is more efficient to search for the NTRU private key.[10] In practice, the search space often contains a multi-solution. When Grover’ s algorithm is applied to the multi-solution search, the success rate of the algorithm has the potential to reduce. If the proportion of solutions is between 1/4 and 1/2, the success rate will reduce to 1/2. To solve this problem, there have been many improved algorithms proposed.[1113] Through altering the phase matching and the number of iterations, the success rate of the algorithm can be improved obviously. In Ref. [14], the multi-solution of Long’ s algorithm was also briefly mentioned. Moreover, the quantum deletion algorithms, [15, 16] which are related to the quantum search algorithm are presented. All the above studies make Grover’ s algorithm be used more and more widely, and promote the development of the quantum search algorithm.

In recent years, quantum random walks have attracted much attention.[1719] The quantum random walk is a generalization of random walk with the quantum mechanical, which can be used to design effective quantum algorithms.[2022] In 2003, Shenvi et al. proposed an algorithm based on quantum random walks (SKW algorithm), which is applied to the unsorted database search as Grover’ s algorithm.[23] The SKW algorithm is similar in many steps to the operation of Grover’ s algorithm. Both algorithms make use of the Grover diffusion operator. Both algorithms use an oracle which marks the target state with a phase of − 1, and both algorithms have a running time of . Because it has been proved that the quantum random walks can be physically implemented, [24, 25] the proposed SKW algorithm provides a new approach to achieve the quantum search algorithm. Although the SKW algorithm is not superior to Grover’ s algorithm in computational complexity, it has certain advantages in physical implementation and resistance to errors. In 2006, Li studied the effects of the error in the Grover diffusion operator on the SKW algorithm and found that the resistance to errors of the SKW algorithm is stronger than that of Grover’ s algorithm.[26] In 2008, Potocek put forward an optimized quantum random-walk search algorithm (optimized SKW algorithm) on the basis of the SKW algorithm, and the success rate of the algorithm and the number of iterations were further optimized.[27] In 2015, Zhang et al. studied the effects of the error in phase inversions on the optimized SKW algorithm and found that it is more robust against phase errors than Grover’ s algorithm.[28] Therefore, studying the search algorithm based on quantum random walks has certain theoretical significance and practical value.

However, the SKW algorithm was proposed only to search for one solution. Although numerical calculations suggest that it can also be used to search for a multi-solution, no related demonstrations and results have been presented. This is because when there is one solution, we use the method of geometric description to prove that the SKW algorithm is a rotation in the plane defined by the initial state and the final state, and the final state is composed primarily of the solution. When the number of solutions is larger than one, we cannot construct the final state properly to prove the algorithm by geometric description. In general, one solution is just a special case of multi-solution. Moreover, the optimized SKW algorithm can be generalized to the multi-solution case (Ref. [27]) based on the assumption that the SKW algorithm is applicable to the multi-solution case. Therefore, the research on the multi-solution case of the algorithm is meaningful and necessary whether on the algorithm itself or the follow-up research. In 2004, Ambainis et al. proposed an abstract search algorithm which is applied to search on the graph, and verified the correctness of the SKW algorithm with one solution.[29] In the same year, Szegedy showed how to analyze the multi-solution case for a different quantum walk algorithm, element distinctness.[30] These investigations provided ideas and possibilities for the study of the multi-solution case of the SKW algorithm and the optimized SKW algorithm.

This paper studies the multi-solution search of the optimized SKW algorithm. We first generalize the abstract search algorithm to the multi-solution case which is originally applied to search for one solution on the graph. Thus, it can be applied to analyze the multi-solution search of quantum random walk on the graph directly. Then, we obtain the computational complexity of the optimized SKW algorithm with multi-solution through the generalized abstract search algorithm. Using theoretical analysis and numerical simulations, we find that if the proportion of solutions q is small, the success rate of the algorithm and the number of iterations decrease with the increase of q. Finally, we obtain a critical value of q. When q is not larger than the critical value, for a given q, we derive the relationship between the success rate of the algorithm and the number of iterations.

The rest of this paper is organized as follows. In Section 2, we introduce the background. The optimized SKW algorithm with multi-solution is proposed in Section 3. In Section 4, we give the results of numerical simulations. The conclusion is given in Section 5.

2. Background
2.1. SKW algorithm

The SKW algorithm is based on a quantum random walk on a hypercube. Let Cn = (Vn, En) denote the graph of the n-dimensional hypercube. The vertices Vn of the hypercube are labelled by binary, x = (x1, x2, … , xn), xi = {0, 1}. The Hamming weight of x is | x | . They are connected only if their Hamming distance is 1. The Hilbert space of the SKW algorithm is HCnHVn where HVn is the 2n-dimensional Hilbert space representing the vertices, and HCn is the n-dimensional space associated with the quantum coin.

The operator of the SKW algorithm can be written as U' = SC' , where S is the shift operator

where | ed〉 = | 0 · · · 010 · · · 0〉 corresponds to the edges originating from the given vertex, S performs a control transfer depending on the state of d. If the target is xtg, the coin operator can be written as

where C0 is generally chosen as the Grover operator: − I + 2| SC〉 〈 SC| , and , C1 is generally chosen to be − I, taking on the function of an oracle. Without loss of generality, we can assume that xtg = 0.

The initial state of the SKW algorithm is the equal superposition over all states . Applying the evolution operator U' to | ψ 0〉 with times, we will obtain the target | 0〉 with a probability close to 0.5.

2.2. Optimized SKW algorithm

The optimized SKW algorithm is based on the SKW algorithm, but quantum random walks occur on an (n + 1)-dimensional hypercube, p(x) = | x| mod 2 is denoted the parity bit of x. Then a map from the 2n-dimensional space to the 2n + 1-dimensional space can be built, xx' = x | | p(x). After mapping, x corresponds to the vertices of an (n + 1)-dimensional hypercube, and the Hamming weights of them are even. Because x is one-to-one with x' , the oracle is capable of identifying the target after mapping.

The operator of the optimized SKW algorithm can be written as U' = S (C0I) SC' . Each iteration C' is only applied once, which is equivalent to calling the oracle once. The initial state is the equal superposition over coin space and the even vertice space | ψ 0(e)〉 . Applying the evolution operator U' to | ψ 0(e)〉 with times, the probability to obtain the target | 0〉 is close to 1.

2.3. Abstract search algorithm

The abstract search algorithm consists of two unitary transformations U1 and U2 and two states | ψ start〉 and | ψ good〉 . It requires the following properties.

(i) U1 = I − 2 | ψ good〉 〈 ψ good| .

(ii) U2 | ψ start〉 = | ψ start〉 , the amplitude of | ψ start〉 is real, and there is no other eigenvector with eigenvalue 1.

(iii) U2 is described by a real unitary matrix.

The abstract search algorithm applies the unitary transformation (U2U1)T to the initial state with a proper T. The final state (U2U1)T | ψ start〉 has a sufficiently large inner product with | ψ good〉 . The main properties of abstract search algorithm will be given in the following.

Since U2 is a real unitary matrix, its non-± 1 eigenvalues come in pairs of complex conjugate numbers. Denote them by e± iθ 1, … , e± iθ m. Let θ min = min (θ 1, … , θ m) and U' = U2U1.

Lemma 1 Define the arc A as the set of eiθ for all real θ satisfying − θ min < θ < θ min. Then U' has at most two eigenvalues in A.

Let and be the eigenvectors with eigenvalues eiθ j and e− iθ j, respectively. We express | ψ good〉 as a superposition of the eigenvectors of U2 as

Lemma 2 It is possible to select and so that and is a real number.

Lemma 3 The eigenvalues of U' in A are e± iα where

Let | ω α 〉 and | ω α 〉 be the two eigenvectors with eigenvalues eiα and e− iα , respectively. Define

and then, | ω start〉 is close to the starting state | ψ start〉 .

Lemma 4 Assume that α < θ min/2, and then

Lemma 5 Assume that α < θ min/2. Let , and then

According to the Lemmas of the abstract search algorithm, we can regard the algorithm being studied as an instance of the abstract search algorithm and then obtain the computational complexity of it.

3. Optimized SKW algorithm with multi-solution
3.1. Generalization of the abstract search algorithm

The abstract search algorithm is proposed for the search of quantum random walks on the graph, but it applies to one solution. In Theorem 5 of Ref. [29], it is generalized to the case of two solutions. In this section, we will generalize the abstract search algorithm to the multi-solution case.

Lemma 6 The abstract search algorithm searching for four solutions v1, v2, v3, v4 is reduced to search for , where

and s is the equal superposition over coin space.

Proof Assume v1 and v2 are two solutions and | ψ 〉 is the initial state, and U' is the operator of the algorithm. Then we can obtain the following relationship according to Claim 12 in Ref. [29]:

where . The above relationship regards the case of searching for v1 and v2 as the case of searching for . Similarly, if v3 and v4 are two solutions, we have

where . Then we add up Eqs. (7) and (8) by the left and right respectively, having the following relationship:

Thus, the abstract search algorithm searching for four solutions reduces to searching for two superposition states. Lemma 6 is proved.

Lemma 7 The abstract search algorithm searching for four solutions v1, v2, v3, v4 is reduced to searching for , where .

Proof According to Eq. (7), the abstract search algorithm searching for two solutions v1 and v2 in space {v1, v2, … , vN} is reduced to searching for with the initial state

Similarly, searching for two solutions and in space is reduced to searching for with the initial state . Therefore

If | s' i〉 is composed of elements in {v1, v2, … , vN} with the form of , the scale of is M = [N(N − 1)]/2, and there is

With Eq. (10), we have

Combining Eqs. (9) and (11), we obtain the following relationship:

where

Lemma 7 is proved.

Theorem 1 The abstract search algorithm searching for 2m solutions (2 < m < log 2N) is reduced to searching for 1, where .

Proof By induction, we proved the case of four solutions. If the inductive assumption case of 2m− 1 solutions is true, then we have

where . Similarly, according to the derivation of Eq. (9) from Eqs. (7) and (8), we can obtain

which shows that the abstract search algorithm searching for 2m solutions is reduced to searching for 1 and 2.

On the other hand, the abstract search algorithm searching for two solutions 1 and 2 in space {1, 2, … , M} is reduced to searching for with the initial state

thus

When | i〉 is composed of elements in {v1, v2, … , vN} with the form of , the scale of {i} is , and there is

With Eq. (15), we have

Combining Eqs. (14) and (16), we obtain

where . Theorem 1 is hence proved.

In this subsection, we generalize the abstract search algorithm to the case of multi-solution. Based on the above conclusion, we can use the abstract search algorithm to analyze the quantum random-walk search on the various graphs directly.

3.2. Computational complexity of the algorithm

The relation between the optimized SKW algorithm and the SKW algorithm was given in Ref. [27]. Therefore, we only need to research the computational complexity of the SKW algorithm with multi-solution. The proof for one solution case is presented in Section 8 of Ref. [29]. The operation of the SKW algorithm can be written as U' = U(I − 2| s, xtg〉 〈 s, xtg| ) by the previous conclusion. We assume 2m solutions with 2 < m < log 2N. According to the Theorem 5 in Ref. [29], we only need to replace in the process of proof, and then we will use the method presented in Theorem 1 of Ref. [29] to obtain the computational complexity of the SKW algorithm with multi-solution.

The eigenvalues and eigenvectors of U are already given in Ref. [31]. The quantum walk of the SKW algorithm stays in an 2n-imensional subspace spanned by 2n eigenvectors of U with eigenvalues eiθ k, where cosθ k = 1 − 2k/n for k = 0, … , n, each with degeneracy .[29] When k = 0, is the initial state which is the only eigenvector of eigenvalue 1. Let be the space spanned by . According to Section 8 in Ref. [29], | s, xtg〉 is also in .

Theorem 2. Furthermore, U' has no eigenvector of eigenvalue 1 in .

Proof For the first part, because U' = U(I − 2| s, xtg〉 〈 s, xtg| ), we only show and with . The first equality is true because is spanned by eigenvectors of U. Therefore, . Assuming , we have (I − 2| s, xtg〉 〈 s, xtg| )(| φ 〉 ) = | φ 〉 − 2 〈 s, xtg | φ 〉 | s, xtg〉 . This is a linear combination of | φ 〉 and | s, xtg〉 . Because . Similarly, if | s, xtg〉 is replaced by , it is a linear combination of | φ 〉 and . Therefore, .

For the second part, assume | ω 0〉 is an eigenvector of eigenvalue 1 of U' in , and then

This implies . Because , we obtain ,

which in turn implies that | ω 0〉 is an eigenvector of eigenvalue 1 of U. Because and , if the eigenvector of eigenvalue 1 of U is orthogonal to | ψ 〉 , it is orthogonal to . It follows that 〈 ψ | ω 0〉 = 0 which contradicts that .

Theorem 2 shows that the SKW algorithm with multi-solution starting in | ψ 〉 is restricted to a subspace of the Hilbert space. Since | ψ 〉 is the only 1-eigenvector of U in , we can regard the SKW algorithm with multi-solution as an instance of the abstract search algorithm on the space , with U1 = (I − 2| ψ good〉 〈 ψ good| ), U2 = U, | ψ start〉 = | ψ 〉 , and .

Then, according to Lemma 3, we evaluate

which determines the computational complexity of the algorithm. Assuming when there is only one solution. Thus we have and according to Ref. [31]. Therefore, when | s, xtg〉 is replaced by , we have

Because and , we obtain

Therefore, we only need to evaluate

which is the same as that in Section 8 of Ref. [29]. Therefore, and the computational complexity of the algorithm is .

Let | wα 〉 and | wα 〉 be the two eigenvectors with eigenvalues eiα and e− iα , respectively, and define . According to Lemma 4, 〈 ψ | wstart〉 is determined by α , , 1/(1 − cos θ k). The previous evaluations show that their values are the same as the case of one solution. Therefore, 〈 ψ | wstart〉 is also the same as that when there is one solution, and the starting state | ψ 〉 is close to | wstart〉 .

Finally, we show that measuring the final state can obtain the target with constant probability. For one solution case, there are

according to Claim 10 in Ref. [29]. Furthermore,

according to Section 8 in Ref. [29], and according to Lemma 5. Because , we have for the multi-solution case. Therefore, we can obtain the target with constant probability as long as m is a constant.

Through the above proofs, we obtain the computational complexity of the SKW algorithm with multi-solution. According to Ref. [27], the computational complexity of the optimized SKW algorithm with multi-solution is also .

4. Numerical simulations and results

Through the abstract search algorithm, we can only obtain the computational complexity of the algorithm with multi-solution, but it does not involve the number of iterations. Therefore, we will further research the relationship between the success of the algorithm, the number of iterations, and the proportion of solutions by numerical simulations.

According to the conclusion of Subsection 3.2, if the proportion of solutions is small, the target will be obtained with a constant probability. Therefore, we first study the relationship between the success rate of the algorithm and the number of iterations with a small proportion of solutions. Figure 1 shows the relationship between the success rate of the algorithm and the number of iterations when the database size is N = 28. The proportions of solutions q = M/N are 1/256, 2/256, 3/256 respectively.

Fig. 1. Relationship between the success rate of the algorithm and the number of iterations for N = 28. The different lines show results for different values of q.

It is known from Fig. 1 that the success rate of the algorithm changes periodically along with the number of iterations, and their relationship satisfies a trigonometric function approximately. If q is larger, the maximum success rate is smaller. This is consistent with the theoretical analysis. For one solution, the expression relating the success rate of the algorithm p and the number of iterations t is

where c is determined by n, and 1/c2 increases toward 1 with the increase of n. For multi-solution, considering the success rate of the algorithm p is equivalent to the proportion of solutions q when t = 0, we assume that the relationship satisfies

By using curve fitting, ω and a are obtained. With n increasing, and . Therefore, when ω t + a = π /2, .

Then, we study the relationship between the success rate of the algorithm and the number of iterations when q is big enough.

Figure 2 shows the success rate of the algorithm and the number of iterations for different databases with q = 1/2. Their relationship is no longer satisfying the previous function. Before the search, the success rate of the algorithm is 1/2 which is equivalent to the proportion of solutions q, and then it changes sharply along with the number of iterations. In practice, if q ≥ 1/2, we can directly obtain the target with a considerable probability without iterating the algorithm.

Fig. 2. Relationship between the success rate of the algorithm and the number of iterations when q = 0.5. The circles line represents N = 64 and the asterisks line represents N = 256.

We obtain an approximate critical value of q by numerical simulations. Only if q ≤ 5/64, the success rate of the algorithm can reduce to 0 every time, as shown in Figs. 3 and 4. Therefore, we assume that the relationship curve still satisfies the form of Eq. (19).

Finally, we study the relationship between the success rate of the algorithm and the proportion of solutions according to Eq. (19), as shown in Fig. 5. The solid line indicates the relationship for the optimized SKW algorithm when the number of iterations with the scale of database n being large enough and q ≤ 5/64. The dotted line indicates the relationship for Grover’ s algorithm. Because the success rate of the optimized SKW algorithm tends to 1 but not equal to 1, for the same proportion of solutions, the corresponding success rate is a little smaller than that of Grover’ s algorithm.

Fig. 3. Relationship between the success rate of the algorithm and the number of iterations when q = 5/64. The different lines show results for different values of N.

Fig. 4. Relationship between the success rate of the algorithm and the number of iterations when q = 6/64. The different lines show results for different values of N.

Fig. 5. Relationship between the success rate of the algorithm and the proportion of solutions for different algorithms.

In this section, we simulate the relationship between the success rate of the optimized SKW algorithm and the number of iterations. We obtain a critical valve of the proportion of solutions. When q ≤ 5/64, the success rate of the algorithm, the number of iterations, and the proportion of solutions satisfy a quantitative relationship approximatively. When q > 5/64, the computational complexity of algorithm is still , but the success rate of the algorithm is no longer periodically changing along with iterations.

5. Conclusion

This paper investigates the multi-solution search of the optimized SKW algorithm. For the problem that the geometric description method cannot be applied to the multi-solution case directly, we first give the generalization of the abstract search algorithm for the multi-solution case. Then, we demonstrate that the computational complexity of the optimized SKW algorithm with multi-solution is . For the small proportion of solutions q, we find that the success rate of the algorithm and the required number of iterations will decrease with the increase of q. Finally, a critical value of q is obtained. When q ≤ 5/64, the relationship between the success rate, the number of iterations, and the proportion of solutions satisfies a function as

When q > 5/64, the success rate is no longer periodically changing along with iterations, and the computational complexity of the algorithm is .

Reference
1 Feynman R 1982 Int. J. Theor. Phys. 21 467 DOI:10.1007/BF02650179 [Cited within:1]
2 Deutsch D 1985 Proeeeding of the Royal Soeiety of London A: Mathematical, Physical and Engineering Sciences 400 97 DOI:10.1098/rspa.1985.0070 [Cited within:1]
3 Shor P W 1997 SIAM J. Comput. 26 1484 DOI:10.1137/S0097539795293172 [Cited within:1]
4 Grover L K 1996 Proceeding of the 28th ACM Symposium on Theory of Computation New York ACM Press 212 219 [Cited within:1]
5 Kane B E 1998 Nature 393 133 DOI:10.1038/30156 [Cited within:1]
6 Zhang Y Y, Hu H P and Lu S F 2011 Chin. Phys. B 20 040309 DOI:10.1088/1674-1056/20/4/040309 [Cited within:1]
7 Fu X Q, Bao W S, Li F D and Zhang Y C 2014 Chin. Phys. B 23 020306 DOI:10.1088/1674-1056/23/2/020306 [Cited within:1]
8 Long G L 2001 Phys. Rev. A 64 022307 DOI:10.1103/PhysRevA.64.022307 [Cited within:2]
9 Toyama F M, van Dij k W and Nogami Y 2013 Quantum Inf. Process. 12 1897 DOI:10.1007/s11128-012-0498-0 [Cited within:1]
10 Wang X, Bao W S and Fu X Q 2011 Chin. Sci. Bull. 56 484 DOI:10.1007/s11434-010-4113-4 [Cited within:1]
11 Long G L, Li Y S, Zhang W L and Niu L 1999 Phys. Lett. A 262 27 DOI:10.1016/S0375-9601(99)00631-3 [Cited within:1]
12 Long G L, Xiao L and Sun Y 2002 Phys. Lett. A 294 143 DOI:10.1016/S0375-9601(02)00055-5 [Cited within:1]
13 Li T, Bao W S, Lin W Q and Fu X Q 2014 Chin. Phys. Lett. 31 050301 DOI:10.1088/0256-307X/31/5/050301 [Cited within:1]
14 Long G L and Liu Y 2007 Front. Comput. Sci. China 1 247 DOI:10.1007/s11704-007-0026-z [Cited within:1]
15 Liu Y 2013 Chin. Sci. Bull. 58 2927 DOI:10.1360/972012-1799 [Cited within:1]
16 Liu Y and Ou-Yang X P 2013 Chin. Sci. Bull. 58 2329 DOI:10.1007/s11434-013-6064-z [Cited within:1]
17 Ampadu C 2014 Chin. Phys. B 23 030302 DOI:10.1088/1674-1056/23/3/030302 [Cited within:1]
18 Xue P, Qin H, Tang B, Zhan X, Bian Z H and Li J 2014 Chin. Phys. B 23 110307 DOI:10.1088/1674-1056/23/11/110307 [Cited within:1]
19 Wu J J, Zhang B D, Tang Y H, Qiang X G and Wang H Q 2013 Chin. Phys. B 22 050304 DOI:10.1088/1674-1056/22/5/050304 [Cited within:1]
20 Ambainis A 2007 SIAM J. Comput. 37 210 DOI:10.1137/S0097539705447311 [Cited within:1]
21 Tulsi A 2008 Phys. Rev. A 78 012310 DOI:10.1103/PhysRevA.78.012310 [Cited within:1]
22 Magniez F, Nayak A, Roland J and Santha M 2011 SIAM J. Comput. 40 142 DOI:10.1137/090745854 [Cited within:1]
23 Shenvi N, Kempe J and Whaley K B 2003 Phys. Rev. A 67 052307 DOI:10.1103/PhysRevA.67.052307 [Cited within:1]
24 Travaglione B C and Milburn G J 2002 Phys. Rev. A 65 032310 DOI:10.1103/PhysRevA.65.032310 [Cited within:1]
25 Dür W, Raussendorf R, Kendon V M and Briegel H J 2002 Phys. Rev. A 66 052319 DOI:10.1103/PhysRevA.66.052319 [Cited within:1]
26 Li Y 2006 Investigations on Quantum Rand om-Walk Search AlgorithmDissertation Shanghai East China Normal Universityin Chinese DOI:10.7666/d.y895053 [Cited within:1]
27 Potocek V, Gábris A, Kiss T and Jex I 2009 Phys. Rev. A 79 012325 DOI:10.1103/PhysRevA.79.012325 [Cited within:4]
28 Zhang Y C, Bao W S, Wang X and Fu X Q 2015 Chin. Phys. B 24 060304 DOI:10.1088/1674-1056/24/6/060304 [Cited within:1]
29 Ambainis A, Kempe J and Rivosh A 2005 Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms Society for Industrial and Applied Mathematics 1099 1108 [Cited within:11]
30 Szegedy M 2004arXiv: quant-ph/0401053 [Cited within:1]
31 Moore C and Russell A 2002 Rand omization and Approximation Techniques in Computer Science Berlin, Heidelberg Springer 164 178 DOI:10.1007/3-540-45726-7_14 [Cited within:2]