Quantum computation shows a huge advantage in dealing with many classical problems because of its powerful parallel computing ability. So far, some remarkable quantum algorithms have been proposed, including Grover’ s algorithm^[1] and Shor’ s algorithm.^[2] Compared with the classical algorithm, Grover’ s algorithm provides a quadratic increase in speed and Shor’ s algorithm provides an exponential increase in speed. The random-walk is a strategy often used in the design of classical algorithms. As a random-walk on a general graph can be used to address hard problems such as k-SAT and graph connectivity.^{[3, 4]} So it is a natural question to ask whether the algorithm based on quantum random walks that can provide an increase in speed. With the in-depth study of quantum random walk, mixing time and hitting time on some graphs which are superior to the classic counterparts are constantly explored.^{[5– 7]} It shows a potential in the design of the quantum algorithm. Therefore, the research of quantum random walks^{[8– 10]} and the algorithms based on quantum random walks have become a hot topic.

In 2003, a quantum random-walk search algorithm (called as SKW algorithm)^[11] was proposed by Shenvi. It iterates times with a success rate of 0.5 approximately, reaching quadratic increase in speed on an unstructured 2ⁿ-sized database. In 2008, Potocek put forward the optimized quantum random-walk search algorithm (optimized SKW algorithm).^[12] It iterates times with a success rate of 1 approximately. These two algorithms are not superior to Grover’ s algorithm in computational complexity, but they have certain advantages in physical implementation and resistance to errors.^{[13, 14]} Since then, many algorithms based on quantum random walks have been proposed.^{[15– 17]} On the other hand, when solving the spatial search problem, algorithms based on quantum random-walks are proved to be better than Grover’ s algorithm.^{[18, 19]}

In practice, errors in the implementation of quantum algorithms are inevitable. The error in each step may be very small; but the scale of quantum computation is usually exponential, small errors may accumulate into large errors and affect the algorithm results. Different errors have different effects on the algorithm. Studying the effects on the quantum algorithm can improve the reliability of it and be beneficial for the implementation of the algorithm. There are two main types of errors. One results from the gate imperfection, and errors in most of the existing research are generated by it. In 2000, Long found systematic errors in phase inversions and random errors in Hadmard– Walsh transformations are the dominant effects in Grover’ s algorithm.^[20] In 2003, Shenvi studied the robustness of Grover’ s algorithm to a random phase error in the oracle and the error tolerability of the algorithm.^[21] In 2006, Li studied the effects of the error in phase inversions on the SKW algorithm and found that in addition to reducing the probability of the marked state eventually, the error also reduces the maximum probability of the unmarked state, which is different from Grover’ s algorithm.^[22] The other is generated by decoherence. Decoherence is due to the quantum system disturbed by the influence of random events, such as random measurements. It will result in the entanglement of quantum states and superposition properties being destroyed, weakening the coherence. As the particularity and randomness of this kind of error are generated, it is difficult to make a relevant theoretical analysis. Investigations on this kind of error in the algorithm are rare. In 2009, Abal et al. investigated different errors in the SKW algorithm including the error generated by decoherence in the shift operator.^[23]

In addition, the other significance of studying decoherence in the quantum algorithm based on quantum random walks is that it may have positive effects on the algorithm.^[24] Because quantum random walk is highly sensitive to the effects of decoherence, the right amount of decoherence can result in a particular probability distribution and quantum speed up. This is also very encouraging for the prospects of using quantum random walks as the basis of powerful quantum algorithms. Currently, the effects of decoherence on quantum random walks on various graphs have been studied fully.^{[25– 27]} In 2003, Kendon and Tregenna found a small amount of decoherence in a walk on the line or the cycle is beneficial, producing more uniform distributions (line) and faster mixing to a uniform distribution (cycle).^[24] In 2008, Marquezino found a controlled amount of decoherence help in obtaining a shorter mixing time to a uniform probability distribution over the hypercube.^[28] Thus, we notice that the optimized SKW algorithm is also based on a walk on the hypercube. When it is in the presence of decoherence, it will make the probability distribution uniform over the hypercube, which concerns how the success rate of the algorithm can be achieved. On the other hand, the mixing time concerns the required number of iterations. So, the final effects of decoherence on the optimized SKW algorithm remain to be studied.

This paper investigates the effects of decoherence generated by random broken links in the hypercube on the optimized SKW algorithm. First defining the shift operator with the possibility of broken links, the optimized SKW algorithm with decoherence is depicted. Then through numerical simulations and analysis, it is found that decoherence will reduce both the maximum success rate of the algorithm and the required number of iterations. The expression of the maximum success rate and the expression of the required number of iterations are obtained respectively. Based on the above relationships, we get the algorithmic computational complexity when it is in the presence of decoherence. We obtain the critical values of the decoherence rate (lna)/(3 · 2^{n− 2}) and . When the decoherence rate varies in different intervals of them, the algorithmic complexity will vary, taking and O(2ⁿ) as the critical values.

The rest of this paper is organized as follows. In Section  2, we introduce the optimized SKW algorithm. In Section  3, the optimized SKW algorithm with decoherence is depicted. Section  4 gives the numerical analysis and results of the algorithm with decoherence. Section  5 is the conclusion.

The data in the 2ⁿ-sized database can be expressed as x = (x₁, x₂, … x_n), x_i = {0, 1}. | x| is its Hamming weight and p(x) = | x| mod 2 is its parity bit. Then a map from 2ⁿ to 2^{n+ 1} can be built, x → x′ = x∥ p(x), i.e., adding the parity bit at the end. Due to the oracle containing information of the marked state and x is one-to-one with x′ , we suppose x′ can also be identified by the oracle.

Then x′ can correspond to the vertex of an n + 1 dimensional hypercube. They are connected only if their Hamming distance is 1. Assuming the marked vertex is | 0〉 , since the hypercube is symmetrical, its selection will not affect the final result. This database search problem is then equivalent to searching for a single marked vertex amongst the vertices on the hypercube.

In detail, the optimized SKW algorithm can be described by the repeated application of a unitary evolution operator UU′ on the Hilbert space H = H^C ⊗ H^S of an (n + 1)-dimensional hypercube. H^C represents the (n + 1)-dimensional Hilbert space of the quantum coin, and H^S represents the 2^{n + 1}-dimensional Hilbert space of the vertex. The state in H is | d, x〉 , where d specifies the state of the coin and x specifies the position on the hypercube. The unitary operators are

and

where the shift operator is

It will depend on the state of the coin d to perform a control transfer, mapping the state from | d, x〉 to | d, x ⨁ e_d〉 , where | e_d〉 = | 0 · · · 010 · · · 0〉 is a null vector except for a single 1 entry at the d-th component. The most remarkable fact about S is that it contains all information about the topology of the graph. The coin operator can be written as

C₀ is generally chosen as the Grover operator, i.e.

It acts on the unmarked vertices, where

C₁ is generally chosen as − I, acting on the marked vertex.

The detail steps of the optimized SKW algorithm are as follows:

(i) Initialize the quantum computer to the equal superposition over all states, | ψ ₀〉 = | S^C〉 ⊗ | S^S〉 . Using orthogonal projection P_e, | ψ ₀〉 is mapped to the basis vectors that the Hamming weight of vertexes are even, and obtain the initial state | ψ ₀^(e)〉 .

(ii) Apply the evolution operator UU′ = S · (C₀ ⊗ I) · S · C′ to the initial state | ψ ₀^(e)〉 with times. C′ is used to flip the phase of the marked state, C′ | S^C〉 ⊗ | x〉 = (− 1)^f(x)| S^C〉 ⊗ | x〉 , when | x〉 = | 0〉 , f(x) = 1; when | x〉 ≠ | 0〉 , f(x) = 0.

(iii) Measure the quantum state. The probability to obtain the marked state | S^C〉 ⊗ | 0〉 is 1 − O(1/(n + 1)).

Quantum coherence will be disturbed by the influence of random events, which are usually modeled by some nonunitary disturbances, such as random measurements, or unitary disturbances, such as broken links.^[25] These events are characterized by a rate defined in terms of a probability parameter δ . t₀ = 1/δ has been proved to be an important critical value.^[25] When the time of quantum random walks is beyond it, the characteristics of probability distribution of quantum random walks will disappear and the classical behavior emerge. This paper considers that decoherence is caused by topological noise which breaks links randomly between connected sites of the hypercube. Currently, the effects of this decoherence model on quantum random walks have been investigated deeply, including on a line, ^[25] on a plane^[26] and on a hypercube.^[28]

In detail, each vertex in an n dimensional hypercube is connected with other n adjacent vertices. At each time step, the link between two vertices will be broken at probability δ . When it is broken, the graph is no longer a hypercube. So, the shift operator in the original algorithm needs to be redefined to include the possibility of broken links, as

where

The function e_d(x) only depends on x and d. If at site x the link in direction d is broken, there will be | d, x ⊕ e_d〉 〈 d, x| = | d, x〉 〈 d, x ⊕ e_d| = | d, x〉 〈 d, x| . The probability flux which will originally cross the link can only be maintained in situ. The new shift operator S̃ will preserve unitarity, no matter which links break.

The actual steps of the optimized SKW algorithm with decoherence are as follows:

i) Initialize the quantum computer to the equal superposition over all states, | ψ ₀〉 = | S^C〉 ⊗ | S^S〉 . By orthogonal projection P_e, | ψ ₀〉 is mapped to the basis vectors that the Hamming weight of vertexes are even, obtaining the initial state | ψ ₀^(e)〉 .

ii) Apply the evolution operator to the initial state | ψ ₀^(e)〉 with t times, obtaining

The shift operator S̃ varies randomly in every Ũ _i and .

iii) Measure the quantum state. The probability to obtain the marked state | S^C〉 ⊗ | 0〉 is p̃ .

Because the link breaks randomly, it is not practical to build an algorithm model by theoretical analysis to study effects on the algorithm. We will first investigate the characteristics of the algorithm through numerical simulations when it is in the presence of decoherence. There are n · 2^{n− 1} links in the n-dimensional hypercube. Because the probability of each link being broken is δ , assuming per time step the number of broken links satisfies the Poisson distribution, i.e. δ · n · 2^{n− 1} and they are selected randomly.

First, we study the relation between the number of iterations and the success rate of the algorithm when n = 8. We simulate situations for δ = 0, δ = 5 × 10^{− 4}, and δ = 0.01 respectively. See Fig.  1.

Fig.  1.

	Figure Option ViewDownloadNew Window
	Fig.  1. Relation between the number of iterations t and the success rate of the algorithm p when n = 8. The asterisks line represents δ = 0.01. The “ x” line represents δ = 5 × 10− 4 and the circles line represents δ = 0.

We can see the general relation between the number of iterations and the success rate of the algorithm from Fig.  1. The circles line represents that it needs 13 iteration times to reach the maximum probability when the decoherence rate is 0. Its success rate of the algorithm changes periodically. The x line represents that it needs 12 iteration times to reach the maximum probability when the decoherence rate is 5 × 10^{− 4}, but it is smaller than the maximum probability obtained in the previous case, and the next peak of wave is even lower. So, the success rate of the algorithm no longer periodically changes. The asterisks line represents that the decoherence rate is 0.01. Both the maximum probability and the required number of iterations are the smallest, and the success rate changes gently.

Then we study the effects of decoherence on the different databases. Figure  2 shows the relation between the number of iterations and the success rate of the algorithm when the decoherence rate is 5 × 10^{− 4}. The database size is N = 2ⁿ and n = 7, 8, 9.

Fig.  2.

	Figure Option ViewDownloadNew Window
	Fig.  2. Relation between the number of iterations t and the success rate of the algorithm p when δ = 0.0005. The circles line represents n = 9. The asterisks line represents n = 8 and the “ + ” line represents n = 7.

It is shown that first the success rate increases with the increment of the number of iterations. The larger the database, the more the required number of iterations. However, the maximum probability that can be achieved is smaller.

Above we describe the optimized SKW algorithm with decoherence, making a preliminary study of the success rate of the algorithm and the number of iterations when it is in the presence of decoherence. The effects of the same decoherence rate on different databases have also been studied. Simulations show that the impact on the maximum probability is greater than that on the required number of iterations. For the same decoherence rate, the larger database will be subject to a greater impact. In the following we will further study the quantitative relationship between the success rate of the algorithm, the number of iterations, the decoherence rate, and the database size.

First we study the relationship between the decoherence rate and the maximum success rate of the algorithm. The size of databases are 2⁷, 2⁸, 2⁹ respectively. See Fig.  3.

Fig.  3.

	Figure Option ViewDownloadNew Window
	Fig.  3. Maximum success rate of the algorithm pmax versus the decoherence rate δ . The circles line represents n = 9. The asterisks line represents n = 8 and the “ + ” line represents n = 7.

It can be seen from Fig.  3 that the maximum success rate decreases exponentially with the increment of the decoherence rate. The larger the database, the faster the decrease. With curve fitting, we obtain the expression for the maximum success rate p_max, the size of the database 2ⁿ and the decoherence rate δ as

where p₀ is the success rate of the algorithm without decoherence. − 1 < b < 0, and with the increment of n, b gradually tends to 0. So the expression is derived approximately as

We notice that the form of this expression is the same as the expression of hitting time probability to the opposite corner in Section  6 of Ref.  [24], which is about the decoherence rate and the dimension of the hypercube. It means the impact of decoherence on them is similar.

Correspondingly, the relationship between the decoherence rate and the required number of iterations is shown in Fig.  4. It can be seen from Fig.  4 that the required number of iterations decreases exponentially with the increment of the decoherence rate. The larger the database, the faster the decrease. With curve fitting, we obtain the expression for the required number of iterations t₀, the size of the database 2ⁿ and the decoherence rate δ as

where − 1 < c < 0. With the increment of n, c gradually tends to 0. So the expression is derived approximately as

Because δ ≥ 0, 0 < e ^{− 2n− 2 · δ} ≤ 1 is established. Assuming d is a constant, when e^{− 2n− 2 · δ} = d, we obtain δ = − lnd/2^{n− 2}. Therefore, when δ = 0, the required number of iterations is . When 0 < δ ≤ − ln d/2^{n− 2}, the required number of iterations is . Its computing scale does not change. When δ > − ln d/2^{n− 2}, the required number of iterations is , which means the computing scale is dropped.

Fig.  4.

	Figure Option ViewDownloadNew Window
	Fig.  4. Required number of iterations t0 versus the decoherence rate δ . The circles line represents n = 9. The asterisks line represents n = 8 and the “ + ” line represents n = 7.

From the above analyses, when the algorithm is in the presence of decoherence, both the maximum success rate and the required number of iterations will decrease. Therefore, the computational complexity of the algorithm may change. Here we define its computational complexity as the required number of iterations to obtain a success probability of p₀. If the probability of obtaining the marked state upon measurement after t iterations is p, then by repeating this procedure approximately p₀/p times, we can boost the overall success probability to p₀. Thus, the overall complexity of the algorithm is O(t/p).^[21] When it is in the presence of decoherence, let t = t₀ and p = p_max. So the overall complexity of the algorithm is O(t₀/p_max). Figure  5 shows the relationship between the decoherence rate δ and t₀/p_max.

Fig.  5.

	Figure Option ViewDownloadNew Window
	Fig.  5. t0/pmax vs the decoherence rate δ . The circles line represents n = 9. The asterisks line represents n = 8 and the “ + ” line represents n = 7.

Shown in Fig.  5, t₀/p_max increases with the increment of the decoherence rate. The larger the database, the faster the decrease. It suggests that decoherence will degrade the quantum effects of the algorithm and may lead to the algorithmic complexity increasing. Then, it will not speed up as expected. When the decoherence rate increases to a critical value, the quantum effects of the algorithm may disappear completely, which will not have any speed up compared with the classical search. We evaluate

When , we obtain . Because δ ≥ 0, e^{2n− 2 · 3δ} ≥ 1 is found. Assuming a is a constant, when e^{2n− 2 · 3δ} = a, we obtain δ = lna/3 · 2^{n− 2}.

In summary, when 0 < δ ≤ ln a/3 · 2^{n− 2}, the complexity of the algorithm is . It still has a quadratic increase in speed. When , the algorithm can only produce a certain quantum increase in speed. The complexity of the algorithm is , between and O(2ⁿ). When , the complexity of the algorithm is O(2ⁿ), which is the same with the classical search and has no quantum increase in speed. When , the algorithmic complexity may be beyond the classical search.

Above investigations show that the broken-link-type decoherence will make the probability distribution on the hypercube tend to be uniform. This is in conflict with the purpose of marking the target by oracle in the search algorithm, which attempts to focus the probability distribution on the target. Although the decoherence will result in the decrease of the required number of iterations, its ultimate impact on the algorithm is negative from the computational complexity point of view.

This paper studies the effects of broken-link-type decoherence on the optimized SKW algorithm in detail. By defining the shift operator with the possibility of broken links, the optimized SKW algorithm with decoherence is depicted. Through simulations and analyses, we find this decoherence will decrease the maximum success rate and the required number of iterations. We obtain two expressions for the maximum success rate and the required number of iterations as a function of the decoherence rate and the database size. When δ = 0, the required number of iterations is , which is the number of iterations of the ideal algorithm. When 0 < δ ≤ − lnd/2^{n− 2}, the required number of iterations is . Its computing scale is still , but the coefficient decreases. When δ > − ln d/2^{n− 2}, the required number of iterations is , which reduces the computing scale. Finally, we obtain the algorithmic complexity when it is in the presence of decoherence. The algorithmic complexity is O(2ⁿ), when the decoherence rate satisfies 0 < δ ≤ lna/3 · 2^{n− 2}. The algorithmic complexity is , when the decoherence rate satisfies . When , the algorithmic complexity is O(2ⁿ), which is the same with the classical search. When , the algorithmic complexity may be beyond the classical search. The above conclusions show that the ultimate effects of broken-link-type decoherence on the optimized SKW algorithm is negative.