[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Next Article in Journal
Efficient Low-PAR Waveform Design Method for Extended Target Estimation Based on Information Theory in Cognitive Radar
Previous Article in Journal
Steady-State Analysis of a Flexible Markovian Queue with Server Breakdowns
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Entropy
Volume 21
Issue 3
10.3390/e21030260
entropy-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Coherence Depletion in Quantum Algorithms

by
Ye-Chao Liu
,
Jiangwei Shang
* and
Xiangdong Zhang
Beijing Key Laboratory of Nanophotonics and Ultrafine Optoelectronic Systems, School of Physics, Beijing Institute of Technology, Beijing 100081, China
*
Author to whom correspondence should be addressed.
Entropy 2019, 21(3), 260; https://doi.org/10.3390/e21030260
Submission received: 3 February 2019 / Accepted: 5 March 2019 / Published: 7 March 2019
(This article belongs to the Section Quantum Information)
Browse Figures
Figure 1
<p>In the case of <math display="inline"><semantics> <mrow> <mi>n</mi> <mo>=</mo> <mn>10</mn> </mrow> </semantics></math> qubits, we plot the values of coherence with respect to the number of Grover iterations <span class="html-italic">k</span>: (<b>a</b>) the relative entropy of coherence <math display="inline"><semantics> <msubsup> <mi mathvariant="script">C</mi> <mi>r</mi> <mrow> <mo>(</mo> <mi>k</mi> <mo>)</mo> </mrow> </msubsup> </semantics></math> in Equation (<a href="#FD13a-entropy-21-00260" class="html-disp-formula">13a</a>); (<b>b</b>) <math display="inline"><semantics> <mrow> <msubsup> <mi mathvariant="script">C</mi> <mrow> <msub> <mi>l</mi> <mn>1</mn> </msub> </mrow> <msup> <mrow> <mo>(</mo> <mi>k</mi> <mo>)</mo> </mrow> <mo>′</mo> </msup> </msubsup> <mo>=</mo> <msub> <mo form="prefix">log</mo> <mn>2</mn> </msub> <mrow> <mo stretchy="false">(</mo> <msubsup> <mi mathvariant="script">C</mi> <mrow> <msub> <mi>l</mi> <mn>1</mn> </msub> </mrow> <mrow> <mo>(</mo> <mi>k</mi> <mo>)</mo> </mrow> </msubsup> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </semantics></math> with <math display="inline"><semantics> <msubsup> <mi mathvariant="script">C</mi> <mrow> <msub> <mi>l</mi> <mn>1</mn> </msub> </mrow> <mrow> <mo>(</mo> <mi>k</mi> <mo>)</mo> </mrow> </msubsup> </semantics></math> being the <math display="inline"><semantics> <msub> <mi>l</mi> <mn>1</mn> </msub> </semantics></math>-norm of coherence in Equation (<a href="#FD13b-entropy-21-00260" class="html-disp-formula">13b</a>). The plots show the results with <math display="inline"><semantics> <mrow> <mi>M</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mn>4</mn> </mrow> </semantics></math> and 16 solutions, respectively. The minimal values indicate that an solution is found. As we can see, with the number of possible solutions increased, not only the number of Grover iterations needed decreases, but also the minimal value of coherence increases accordingly. See text and <a href="#entropy-21-00260-f002" class="html-fig">Figure 2</a> for more details.</p> "> Figure 2
<p>Minimal coherence of the system state with respect to the logarithm of the number of solutions <math display="inline"><semantics> <mrow> <msub> <mo form="prefix">log</mo> <mn>2</mn> </msub> <mi>M</mi> </mrow> </semantics></math>. As we can see, with the number of solutions <span class="html-italic">M</span> increased, the minimal value of coherence gets bigger which clearly indicates a superposition state consisting of more terms.</p> ">
Versions Notes

Abstract

:
Besides the superior efficiency compared to their classical counterparts, quantum algorithms known so far are basically task-dependent, and scarcely any common features are shared between them. In this work, however, we show that the depletion of quantum coherence turns out to be a common phenomenon in these algorithms. For all the quantum algorithms that we investigated, including Grover’s algorithm, Deutsch–Jozsa algorithm, and Shor’s algorithm, quantum coherence of the system states reduces to the minimum along with the successful execution of the respective processes. Notably, a similar conclusion cannot be drawn using other quantitative measures such as quantum entanglement. Thus, we expect that coherence depletion as a common feature can be useful for devising new quantum algorithms in the future.

1. Introduction

The emergence of quantum algorithms that can solve problems exponentially faster than any classical algorithms is one of the leading incentives for the rapid development of quantum information science over the last three decades. Especially exciting is the new concept of computing that makes use of quantum fundamental principles, coined quantum computing [1]. In 1992, the Deutsch–Jozsa (DJ) algorithm [2] was first proposed, which can confirm a given function’s type with only one single evaluation, compared to at worst 2 n − 1 + 1 (n being the number of two-valued digits) queries by any possible classical algorithms. Moreover, the DJ algorithm is deterministic in the sense that it can always produce the correct answer, which greatly improves the original solution by Deutsch [3] that can only succeed with probability of one half. Soon, the basic problem of factoring a large integer was offered a new quantum solution, that is, Shor’s algorithm [4]. The exponentially faster speed-up over any classical approaches could be used to break public-key cryptography schemes, such as the widely used Rivest–Shamir–Adleman (RSA) scheme, once a quantum computer were built. Then, it is Grover’s search algorithm [5] which is used to locate a target item in an unsorted database. For this problem, Grover’s algorithm runs only quadratically faster compared to any classical algorithms, but it has been proven to be asymptotically optimal [6].
Coincidentally, all the quantum algorithms mentioned above were proposed in the 1990s. Since the dawn of this century, however, few new speed-up quantum algorithms have been designed that are comparable in impact to the existing ones. For two exceptional developments, see the DQC1 algorithm [7] and the HHL algorithm [8] which we skip to consider in the current work. One of the possible reasons for this lies in the fact that all the quantum algorithms known so far are basically task-dependent; in other words, they share very few common features, if there were any. Along with this line, the series of works by Latorre and coauthors [9,10,11] reported that all known efficient quantum algorithms obey a majorization principle (see Reference [12] for a recent experimental realization of majorization.). To be more precise, the time arrow in these algorithms is a majorization arrow, which is conjectured to be a sort of driving force for the respective processes. Aside from this one, there are no other general features being reported.
In this paper, however, we present a new common feature underling the efficient quantum algorithms in terms of quantum coherence (see Section 2 for a brief review). Note that we only consider the ideal scenario of no decoherence from the environment. Specifically, we find that coherence of the system states all reduces to the minimum along with the successful execution of the respective algorithms. In a rough sense, this is a “coherence arrow” in quantum algorithms, but with many flexibilities. This feature is similar to the majorization principle, with the possible reason being that both the concepts of coherence and majorization are basis-dependent [13,14]. However, unlike the descriptive nature of majorization, quantum coherence can be computed quantitatively using various coherence measures. In this aspect, the feature that we find with coherence is a more versatile tool compared to the majorization principle. On the other hand, a similar conclusion cannot be drawn using other quantitative measures, including quantum entanglement, which may be argued that entanglement is basis-independent [15]. For instance, although works such as Reference [16] showed that entanglement has some relations with the quantum advantage, others [17,18,19] also demonstrated that the quantum speed-up can exist without entanglement.
Actually, the analysis of quantum algorithms using coherence is not new [20,21,22], but the respective algorithms were considered independently in those works and a unified picture is missing. For instance, in Reference [20] the author examined the role played by coherence as a resource in the DJ and related algorithms, and found that the less coherence there is, the worse the algorithm will perform. However, from different perspectives, both References [21,22] reported that the success probability of Grover’s algorithm relies on coherence. Nevertheless, the results presented in this paper give a combined view of all the quantum algorithms known so far with coherence.
This paper is organized as follows. In Section 2, we briefly review the resource theory of quantum coherence, and introduce the commonly used coherence measures. Then we start with the investigation of Grover’s algorithm in Section 3, where the evolution of quantum coherence is thoroughly analyzed. Next, we move on to the DJ algorithm in Section 4 and Shor’s algorithm in Section 5. In Section 6, the consequences of coherence played in quantum algorithms are discussed, along with a comparison with other quantitative measures such as quantum entanglement. We close with a short conclusion in Section 7.

2. Resource Theory of Quantum Coherence

Along with the rapid development of quantum information science, an alternative way of assessing quantum phenomena as resources has appeared. Consequently, many tasks that are not previously possible within the realm of classical physics may be now exploited with the new approach. This resource-driven viewpoint has motivated the development of a quantitative theory that captures the resource character of physical properties in a mathematically rigorous manner. The formulation of such resource theories was initially pursued with the quantitative theory of entanglement [23,24], but has since spread to encompass many other operational settings, including quantum coherence [25,26,27]; see Reference [28] for a recent review.
Resource theory provides a unified framework for studying resource quantification and manipulations under restricted operations that are deemed free. For coherence, we are restricted to incoherent operations, so only incoherent states are free. Recall that a state is incoherent if it is diagonal in the reference basis. Recently, it has been demonstrated that coherence can be converted to other quantum resources, such as entanglement and discord by certain operations [29,30,31]. However, compared to entanglement and discord, evidence shows that coherence may be a potentially more fundamental quantum resource [32]. To quantify coherence, a rigorous framework has been proposed by Baumgratz et al. in Reference [33]. In this work, we employ the two most commonly used coherence measures, namely the relative entropy of coherence and the l 1 -norm of coherence.
The relative entropy of coherence [33] is defined as
C r ( ρ ) = S ( ρ diag ) − S ( ρ ) ,
where S ( ρ ) = − tr ( ρ log 2 ρ ) is the von Neumann entropy and ρ diag = ∑ i ρ i i | i 〉 〈 i | denotes the state obtained from ρ by deleting all the off-diagonal elements. For pure states, the von Neumann entropy is 0, so the relative entropy can be simplified to
C r ( ρ ) = S ( ρ diag ) , if tr ( ρ 2 ) = 1 .
The l 1 -norm of coherence [33] is defined intuitively as
C l 1 ( ρ ) = ∑ i ≠ j | ρ i j | ,
which comes from the fact that coherence is tied to the off-diagonal elements of the states. Recently, it is demonstrated by Zhu et al. [34] that the l 1 -norm of coherence is the analog of negativity in entanglement theory and sum negativity in the resource theory of magic-state quantum computation. It is worth mentioning that both the relative entropy and the l 1 -norm are proper measures of quantum coherence.

3. Grover’s Algorithm

We start with Grover’s algorithm [5], which is a quantum search algorithm that runs quadratically faster than any equivalent classical algorithms. Given an unsorted database with N items, this algorithm can find the target item using only O ( N ) steps, compared to at least O ( N ) steps required by any classical schemes. Although not offering an exponential speed-up, Grover’s algorithm has been proven to be asymptotically optimal for the search problem [6]. For convenience, we assume N = 2 n such that the N entries in the database can be supplied by n qubits. Let f ( x ) be a function that takes in index x = 0 , 1 , ⋯ , N − 1 , and outputs f ( x ) = 1 if x is a solution to the search problem, and f ( x ) = 0 otherwise.
Grover’s algorithm begins with the initialized equal superposition state,
| ψ ( 0 ) 〉 = 1 2 n ∑ x = 0 2 n − 1 | x 〉 ,
which has the maximal coherence
C r ( 0 ) = S ( I / 2 n ) = n ,
C l 1 ( 0 ) = ∑ i ≠ j 2 n − 1 1 2 n = 2 n − 1 .
Suppose there are exactly M solutions in the database with 1 ≤ M ≤ N , we can re-express | ψ ( 0 ) 〉 as
| ψ ( 0 ) 〉 = N − M N | α 〉 + M N | β 〉 ,
where | α 〉 represents the group of states that are not solutions to the search problem (marked by x n below), while | β 〉 represents those that are solutions (marked by x s ). Explicitly, we have
| α 〉 ≡ 1 N − M ∑ x n | x n 〉 ,
| β 〉 ≡ 1 M ∑ x s | x s 〉 .
Then, a subroutine known as the Grover iteration is applied to | ψ ( 0 ) 〉 repeatedly. The Grover iteration consists of two basic operations G = D O , i.e.,
O : | x 〉 → ( − 1 ) f ( x ) | x 〉 ,
D = 2 | ψ ( 0 ) 〉 〈 ψ ( 0 ) | − I ,
where O is an oracle (a black-box operation), and D is the Grover diffusion operator. After k iterations of applying G, the state becomes
| ψ ( k ) 〉 ≡ G k | ψ 〉 = cos ω | α 〉 + sin ω | β 〉 ,
where
ω = 2 k + 1 2 θ , with cos θ 2 = N − M N .
It is not difficult to see that with high probabilities, a solution to the search problem can be obtained by having k = π 4 N M Grover iterations, where the symbol ⌊ · ⌉ denotes the closest integer to the rational number inside. Next, we calculate the quantum coherence of state | ψ ( k ) 〉 , such that
C r ( k ) = − 2 cos 2 ω log | cos ω | N − M + sin 2 ω log | sin ω | M ,
C l 1 ( k ) = N − M | cos ω | + M | sin ω | 2 − 1 .
Note that the oracle O only marks the solution by changing the phase of state | β 〉 , i.e.,
O | ψ ( k ) 〉 = cos ω | α 〉 − sin ω | β 〉 ,
so, this operation will not change the coherence. It is the operation D that indeed changes the coherence.
In Figure 1, we plot the values of coherence with respect to the number of Grover iterations k, for the case of n = 10 qubits. Note that in Figure 1b, we plot instead C l 1 ( k ) ′ = log 2 ( C l 1 ( k ) + 1 ) . As can be seen, a solution to the search problem is found when the coherence first reaches the minimum value, that is, when k * = π 4 N M . At this point, the task of Grover’s algorithm is actually completed. However, if the Grover iteration is continued, a periodic feature of the coherence appears such that we will get the solution again around 2 k * iterations. This observation is repeated as long as the Grover iteration goes on.
Another phenomenon from the plots is as follows: with the number of possible solutions increased, not only the number of Grover iterations needed decreases, but also the minimal value of coherence gets bigger accordingly. This is easy to understand as several answers ( M > 1 ) make up a superposition state of which the coherence is finite; see Figure 2. To understand it better, let us look at the derivatives of the coherence in Equation (13), which are given by
d C r ( k ) d k = θ sin [ ( 2 k + 1 ) θ ] log M N − M cot 2 2 k + 1 2 θ ,
d C l 1 ( k ) d k = θ { ( 2 M − N ) sin [ ( 2 k + 1 ) θ ] + 2 ( N − M ) M sgn { sin [ ( 2 k + 1 ) θ ] } cos [ ( 2 k + 1 ) θ ] } .
By forcing the derivatives to be zero, we get four different cases:
  • cos 2 k + 1 2 θ = 0 corresponds to the minimal values in Figure 1, namely the solution state | β 〉 .
  • cot 2 2 k + 1 2 θ = cot 2 θ 2 corresponds to the maximal values in Figure 1. Because of the square in this solution, there are actually two peaks close to each other (not quite visible if the number of solutions M is small). The right peak corresponds to the superposition state | ψ ( 0 ) 〉 , while the left one corresponds to O | ψ ( 0 ) 〉 .
  • cos 2 k + 1 2 θ = ± 1 corresponds to the local minimal values between the two peaks in Figure 1. Because the distance between these two peaks is exactly 1 and we are considering discrete operations, so this local valley has no physical meaning.
  • θ = 0 means that there is no solution, i.e., M = 0 .
To summarize, one learns that the depletion of quantum coherence can be regarded as a signal for the successful executions of Grover’s algorithm. We will see later that the same conclusion can be drawn for other quantum algorithms including the Deutsch–Jozsa algorithm and Shor’s algorithm.

4. Deutsch–Jozsa Algorithm

Given a function f ( x ) defined over the variable x = 0 , 1 , ⋯ , 2 n − 1 with n being the number of dichotomic-valued digits, the Deutsch–Jozsa (DJ) algorithm [2] aims to confirm whether f ( x ) is constant for all values of x, or else it is balanced, namely f ( x ) = 1 for exactly half of all possible x, and 0 for the other half. Although of little practical use, the DJ algorithm is deterministic in the sense that it can always produce the correct answer using only one correspondence, whereas it requires at worst 2 n − 1 + 1 queries for any possible classical algorithms.
Same as Grover’s algorithm, the DJ algorithm begins by first preparing the equal superposition state of Equation (4),
| ψ ( 0 ) 〉 = 1 2 n ∑ x = 0 2 n − 1 | x 〉 ,
which has the maximal coherence
C r ( 0 ) = n ,
C l 1 ( 0 ) = 2 n − 1 .
However, unlike Grover’s algorithm, no iteration is needed in the DJ algorithm. The next step is an oracle U f : | x 〉 → ( − 1 ) f ( x ) | x 〉 that transforms the state to
| ψ ( 1 ) 〉 = 1 2 n ∑ x = 0 2 n − 1 ( − 1 ) f ( x ) | x 〉 ,
which leaves the coherence unchanged. The final step of the DJ algorithm is to apply the Hadamard gate H, such that the state becomes
| ψ ( 2 ) 〉 = 1 2 n ∑ y = 0 2 n − 1 ∑ x = 0 2 n − 1 ( − 1 ) x · y + f ( x ) | y 〉 ,
where x · y is the bitwise inner product of x and y. Now, by examining the probability of measuring | 0 〉 ⊗ n , i.e., ∑ x ( − 1 ) f ( x ) / 2 n 2 , one gets 1 if f ( x ) is constant and 0 if it is balanced. Depending on the function type of f ( x ) , the coherence of | ψ ( 2 ) 〉 can have the following two cases:
  • If f ( x ) is a constant function, then
    | ψ ( 2 ) 〉 = 1 2 n ± 2 n 0 ⋯ 0 T ,
    the coherence of which is C r ( 2 ) = C l 1 ( 2 ) = 0 .
  • If f ( x ) is a balanced function, then
    C r ( 2 ) ∈ [ 0 , n − 1 ] ,
    C l 1 ( 2 ) ∈ [ 0 , 2 n − 1 − 1 ] .
For the second case, the coherence has a range instead of a single value due to the possible different forms of the balanced function. For instance, if f ( x ) takes values 01010101 ⋯ (for more than three qubits), then | ψ ( 2 ) 〉 is nothing but a basis state with coherence being zero. However, if f ( x ) takes the sequence such as 01100101 ⋯ , then | ψ ( 2 ) 〉 is a superposition of basis states with nonzero coherence. Notably, the coherence cannot take the maximal value as that in Equation (17), because the basis state | 0 〉 disappears in | ψ ( 2 ) 〉 for the balanced case.
Therefore, no matter what the function type of f ( x ) is, we find that the coherence of the system state always decreases once the algorithm stops. Again, coherence depletion can be used as a good signature to signal the success of the DJ algorithm.

5. Shor’s Algorithm/Quantum Order-Finding

Shor’s algorithm [4] is a particular instance of the family of quantum phase-estimation algorithms [35]. Informally, Shor’s algorithm solves the following problem: given an integer N, find its prime factors. The crucial step in Shor’s algorithm is the so-called quantum order-finding (QOF) subroutine which offers the quantum speed-up over any classical approaches. For two positive integers x and N, the objective of QOF is to determine the order of x modulo N, which is defined as the least integer r > 0 , such that x r = 1 ( mod N ) .
The QOF subroutine begins with t = 2 L + 1 + log ( 2 + 1 2 ϵ ) qubits initialized to | 0 〉 (the first register) and L qubits initialized to | 1 〉 (the second register), where L ≡ ⌈ log ( N ) ⌉ denotes the closest integer larger than log ( N ) and ϵ is the error tolerance. Application of the Hadamard gate H on the first register transforms the initial state to
| ψ ( 0 ) 〉 = 1 2 t ∑ j = 0 2 t − 1 | j 〉 | 1 〉 ,
which has the maximal coherence on the first t qubits, i.e.,
C r ( 0 ) = t ,
C l 1 ( 0 ) = 2 t − 1 .
Then a black-box operation U x , N : | j 〉 | k 〉 → | j 〉 | x j ( mod N ) 〉 transforms the state to
| ψ ( 1 ) 〉 = 1 2 n ∑ j = 0 2 t − 1 | j 〉 | x j ( mod N ) 〉 .
Although the state | ψ ( 1 ) 〉 looks rather different from | ψ ( 0 ) 〉 , its coherence (on the first t qubits) does not change, namely
C r ( 1 ) = C r ( 0 ) = t ,
C l 1 ( 1 ) = C l 1 ( 0 ) = 2 t − 1 .
Because of the periodic nature of the component | x j ( mod N ) 〉 , the state | ψ ( 1 ) 〉 can be approximated as
| ψ ( 1 ) 〉 ≈ 1 r 2 n ∑ s = 0 r − 1 ∑ j = 0 2 t − 1 e 2 π i · s j / r | j 〉 | u s 〉 .
The period of the phase in | ψ ( 1 ) 〉 can be obtained by applying inverse Fourier transform to the first register, such that
| ψ ( 2 ) 〉 = 1 r ∑ s = 0 r − 1 | s / r ˜ 〉 | u s 〉 ,
where | s / r ˜ 〉 is a pretty good approximation of the phase s / r . Now, coherence of the state | ψ ( 2 ) 〉 becomes
C r ( 2 ) = − r 2 · 1 r 2 log 1 r 2 = 2 log r ,
C l 1 ( 2 ) = r 4 − r 2 r 2 = r 2 − 1 ,
which are functions of the solution r. Finally, by measuring the first t qubits, the solution r is obtained by applying the continued fractions algorithm [1]. Once again, we find that coherence of the system state reduces to the minimum by the end of the QOF subroutine, in turn also in Shor’s algorithm.

6. Discussion

For all the quantum algorithms that we have explored including Grover’s algorithm, DJ algorithm and Shor’s algorithm, we find that quantum coherence plays a consistent role for signaling the completion of all processes. To be more precise, upon successful executions of these algorithms, coherence of the respective systems all reduces to the minimum compared to the initial values. Specifically, all the three quantum algorithms begin with the equal superposition state which has the maximal coherence. Then, an oracle is applied, which leaves the coherence unchanged. The final step can be seen as an adjustment for the system states, that is, diffusion operation for Grover’s algorithm, Hadamard operation for DJ algorithm, and quantum inverse Fourier transform for Shor’s algorithm. It is this final step of operation that indeed reduces the coherence. Hence, as a guide for future quantum-algorithm design, the coherence-depletion operation might be taken as an indispensable requirement for the relevant processes.
Then, it is natural to ask whether other quantitative measures such as entanglement may play a similar role as coherence in quantum algorithms. Unfortunately, the answer is negative. Many previous works have shown that a general principle cannot be drawn using entanglement. For instance, in References [36,37,38] the authors analyzed thoroughly the entanglement properties in Shor’s algorithm, and found that entanglement may vary with different entanglement measures. Then, similar conclusions were reported in References [39,40,41,42] for the DJ algorithm. In particular, Reference [17] showed that quantum algorithms can be efficiently simulated classically even when entanglement exists, whereas References [17,18,19] demonstrated that quantum algorithms can show advantage without entanglement. One of the possible reasons for the failure of using entanglement as a signature is due to the differences in definitions of entanglement and coherence (also majorization), since both the concepts of coherence and majorization are basis-dependent [13,14], while entanglement not.
No doubt that entanglement is a key (but not really sufficient [24]) resource for the quantum speed-up in all these algorithms [16], it cannot be used as a good signature in quantum algorithms. Actually, it is an NP-hard problem [43,44] to even detect entanglement if the system size is large, let alone to quantify it. For multipartite quantum systems, entanglement can be classified into different forms depending on how the subsystems are distributed. This complexity further makes any possible entanglement measures hard to compute. Therefore, although essential for the quantum speed-up, entanglement is not a good signature to use for quantum algorithms as compared to coherence. Moreover, this fact also serves as an additional evidence that coherence may be a potentially more fundamental quantum resource than entanglement and discord, as initially argued in Reference [32].

7. Conclusions

The scarceness of efficient quantum algorithms suggests that maybe some basic principles are missing. In this paper, we find that the depletion of quantum coherence turns out to be a common feature in these algorithms. For all the three quantum algorithms that we investigated including Grover’s algorithm, Deutsch–Jozsa algorithm and Shor’s algorithm, quantum coherence of the system states all reduces to the minimum along with the successful execution of the respective algorithms. However, a similar conclusion cannot be drawn using other quantitative measures such as quantum entanglement. Therefore, besides the fundamental interests in resource theory, this special feature of quantum coherence is expected to be useful for devising new quantum algorithms in the future.

Author Contributions

Y.-C.L. performed the numerical calculations. All authors contributed to the interpretation of the results, and writing of the manuscript.

Funding

This work has been supported by the National Key R&D Program of China under Grant No. 2017YFA0303800 and the National Natural Science Foundation of China through Grant Nos. 11574031 and 11805010. J.S. also acknowledges support by the Beijing Institute of Technology Research Fund Program for Young Scholars.

Acknowledgments

We thank Huangjun Zhu and Hui Khoon Ng for fruitful discussions. We are also grateful to Miguel Martín-Delgado for pointing out their recent work on majorization [12] to us.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Nielsen, M.A.; Chuang, I.L. Quantum Computation and Quantum Information, 10th ed.; Cambridge University Press: New York, NY, USA, 2011. [Google Scholar]
  2. Deutsch, D.; Jozsa, R. Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A 1992, 439, 553. [Google Scholar] [CrossRef]
  3. Deutsch, D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 1985, 400, 97. [Google Scholar] [CrossRef]
  4. Shor, P.W. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 20–22 November 1994; pp. 124–134. [Google Scholar] [CrossRef]
  5. Grover, L.K. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC ’96), Philadelphia, PA, USA, 22–24 May 1996; ACM: New York, NY, USA, 1996; pp. 212–219. [Google Scholar] [CrossRef]
  6. Bennett, C.H.; Bernstein, E.; Brassard, G.; Vazirani, U. Strengths and Weaknesses of Quantum Computing. SIAM J. Comput. 1997, 26, 1510. [Google Scholar] [CrossRef]
  7. Knill, E.; Laflamme, R. Power of one bit of quantum information. Phys. Rev. Lett. 1998, 81, 5672. [Google Scholar] [CrossRef]
  8. Harrow, A.W.; Hassidim, A.; Lloyd, S. Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 2009, 103, 150502. [Google Scholar] [CrossRef] [PubMed]
  9. Latorre, J.I.; Martín-Delgado, M.A. Majorization arrow in quantum-algorithm design. Phys. Rev. A 2002, 66, 022305. [Google Scholar] [CrossRef]
  10. Orús, R.; Latorre, J.I.; Martín-Delgado, M.A. Natural Majorization of the Quantum Fourier Transformation in Phase-Estimation Algorithms. Quantum Inf. Process. 2002, 1, 283. [Google Scholar] [CrossRef]
  11. Orús, R.; Latorre, J.I.; Martín-Delgado, M.A. Systematic analysis of majorization in quantum algorithms. Eur. Phys. J. D 2004, 29, 119. [Google Scholar] [CrossRef]
  12. Flamini, F.; Viggianiello, N.; Giordani, T.; Bentivegna, M.; Spagnolo, N.; Crespi, A.; Corrielli, G.; Osellame, R.; Martin-Delgado, M.A.; Sciarrino, F. Observation of photonic states dynamics in 3-D integrated Fourier circuits. J. Opt. 2018, 20, 074001. [Google Scholar] [CrossRef] [Green Version]
  13. Winter, A.; Yang, D. Operational Resource Theory of Coherence. Phys. Rev. Lett. 2016, 116, 120404. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  14. Zhu, H.; Ma, Z.; Cao, Z.; Fei, S.M.; Vedral, V. Operational one-to-one mapping between coherence and entanglement measures. Phys. Rev. A 2017, 96, 032316. [Google Scholar] [CrossRef]
  15. Nielsen, M.A.; Kempe, J. Separable States Are More Disordered Globally than Locally. Phys. Rev. Lett. 2001, 86, 5184. [Google Scholar] [CrossRef] [PubMed]
  16. Jozsa, R. Quantum effects in algorithms. In Quantum Computing and Quantum Communications; Springer: Berlin/Heidelberg, Germany, 1999; pp. 103–112. [Google Scholar]
  17. Jozsa, R.; Linden, N. On the role of entanglement in quantum-computational speed-up. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 2003, 459, 2011–2032. [Google Scholar] [CrossRef] [Green Version]
  18. Boyer, M.; Brodutch, A.; Mor, T. Entanglement and deterministic quantum computing with one qubit. Phys. Rev. A 2017, 95, 022330. [Google Scholar] [CrossRef]
  19. Datta, A.; Shaji, A.; Caves, C.M. Quantum discord and the power of one qubit. Phys. Rev. Lett. 2008, 100, 050502. [Google Scholar] [CrossRef] [PubMed]
  20. Hillery, M. Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation. Phys. Rev. A 2016, 93, 012111. [Google Scholar] [CrossRef]
  21. Anand, N.; Pati, A.K. Coherence and entanglement monogamy in the discrete analogue of analog Grover search. arXiv, 2016; arXiv:1611.04542. [Google Scholar]
  22. Shi, H.L.; Liu, S.Y.; Wang, X.H.; Yang, W.L.; Yang, Z.Y.; Fan, H. Coherence depletion in the Grover quantum search algorithm. Phys. Rev. A 2017, 95, 032307. [Google Scholar] [CrossRef]
  23. Gühne, O.; Tóth, G. Entanglement detection. Phys. Rep. 2009, 474, 1–75. [Google Scholar] [CrossRef] [Green Version]
  24. Horodecki, R.; Horodecki, P.; Horodecki, M.; Horodecki, K. Quantum entanglement. Rev. Mod. Phys. 2009, 81, 865. [Google Scholar] [CrossRef]
  25. Horodecki, M.; Oppenheim, J. (Quantumness in the context of) resource theories. Int. J. Mod. Phys. B 2013, 27, 1345019. [Google Scholar] [CrossRef]
  26. Del Rio, L.; Kraemer, L.; Renner, R. Resource theories of knowledge. arXiv, 2015; arXiv:1511.08818. [Google Scholar]
  27. Coecke, B.; Fritz, T.; Spekkens, R.W. A mathematical theory of resources. Inf. Comput. 2016, 250, 59. [Google Scholar] [CrossRef]
  28. Streltsov, A.; Adesso, G.; Plenio, M.B. Colloquium: Quantum coherence as a resource. Rev. Mod. Phys. 2017, 89, 041003. [Google Scholar] [CrossRef]
  29. Streltsov, A.; Singh, U.; Dhar, H.S.; Bera, M.N.; Adesso, G. Measuring Quantum Coherence with Entanglement. Phys. Rev. Lett. 2015, 115, 020403. [Google Scholar] [CrossRef] [PubMed]
  30. Ma, J.; Yadin, B.; Girolami, D.; Vedral, V.; Gu, M. Converting Coherence to Quantum Correlations. Phys. Rev. Lett. 2016, 116, 160407. [Google Scholar] [CrossRef] [PubMed]
  31. Chitambar, E.; Hsieh, M.H. Relating the Resource Theories of Entanglement and Quantum Coherence. Phys. Rev. Lett. 2016, 117, 020402. [Google Scholar] [CrossRef] [PubMed]
  32. Yao, Y.; Xiao, X.; Ge, L.; Sun, C.P. Quantum coherence in multipartite systems. Phys. Rev. A 2015, 92, 022112. [Google Scholar] [CrossRef]
  33. Baumgratz, T.; Cramer, M.; Plenio, M.B. Quantifying Coherence. Phys. Rev. Lett. 2014, 113, 140401. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  34. Zhu, H.; Hayashi, M.; Chen, L. Axiomatic and operational connections between the l1-norm of coherence and negativity. Phys. Rev. A 2018, 97, 022342. [Google Scholar] [CrossRef]
  35. Cleve, R.; Ekert, A.; Macchiavello, C.; Mosca, M. Quantum algorithms revisited. Proc. R. Soc. Lond. A 1998, 454, 339. [Google Scholar] [CrossRef]
  36. Parker, S.; Plenio, M.B. Entanglement simulations of Shor’s algorithm. J. Mod. Opt. 2002, 49, 1325. [Google Scholar] [CrossRef]
  37. Orús, R.; Latorre, J.I. Universality of entanglement and quantum-computation complexity. Phys. Rev. A 2004, 69, 052308. [Google Scholar] [CrossRef]
  38. Kendon, V.M.; Munro, W.J. Entanglement and its Role in Shor’s Algorithm. Quantum Inf. Comput. 2006, 6, 630–640. [Google Scholar]
  39. Azuma, H.; Bose, S.; Vedral, V. Entangling capacity of global phases and implications for the Deutsch-Jozsa algorithm. Phys. Rev. A 2001, 64, 062308. [Google Scholar] [CrossRef] [Green Version]
  40. Bruß, D.; Macchiavello, C. Multipartite entanglement in quantum algorithms. Phys. Rev. A 2011, 83, 052313. [Google Scholar] [CrossRef]
  41. Collins, D.; Kim, K.W.; Holton, W.C. Deutsch-Jozsa algorithm as a test of quantum computation. Phys. Rev. A 1998, 58, R1633. [Google Scholar] [CrossRef]
  42. Kenigsberg, D.; Mor, T.; Ratsaby, G. Quantum advantage without entanglement. Quantum Inf. Comput. 2006, 6, 606–615. [Google Scholar]
  43. Gurvits, L. Classical deterministic complexity of Edmonds’ Problem and quantum entanglement. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, San Diego, CA, USA, 9–11 June 2003; ACM Press: New York, NY, USA, 2003; pp. 10–19. [Google Scholar]
  44. Gharibian, S. Strong NP-hardness of the quantum separability problem. Quantum Inf. Comput. 2010, 10, 343–360. [Google Scholar]
Entropy 21 00260 g001 550
Figure 1. In the case of n = 10 qubits, we plot the values of coherence with respect to the number of Grover iterations k: (a) the relative entropy of coherence C r ( k ) in Equation (13a); (b) C l 1 ( k ) ′ = log 2 ( C l 1 ( k ) + 1 ) with C l 1 ( k ) being the l 1 -norm of coherence in Equation (13b). The plots show the results with M = 1 , 2 , 4 and 16 solutions, respectively. The minimal values indicate that an solution is found. As we can see, with the number of possible solutions increased, not only the number of Grover iterations needed decreases, but also the minimal value of coherence increases accordingly. See text and Figure 2 for more details.
Figure 1. In the case of n = 10 qubits, we plot the values of coherence with respect to the number of Grover iterations k: (a) the relative entropy of coherence C r ( k ) in Equation (13a); (b) C l 1 ( k ) ′ = log 2 ( C l 1 ( k ) + 1 ) with C l 1 ( k ) being the l 1 -norm of coherence in Equation (13b). The plots show the results with M = 1 , 2 , 4 and 16 solutions, respectively. The minimal values indicate that an solution is found. As we can see, with the number of possible solutions increased, not only the number of Grover iterations needed decreases, but also the minimal value of coherence increases accordingly. See text and Figure 2 for more details.
Entropy 21 00260 g001
Entropy 21 00260 g002 550
Figure 2. Minimal coherence of the system state with respect to the logarithm of the number of solutions log 2 M . As we can see, with the number of solutions M increased, the minimal value of coherence gets bigger which clearly indicates a superposition state consisting of more terms.
Figure 2. Minimal coherence of the system state with respect to the logarithm of the number of solutions log 2 M . As we can see, with the number of solutions M increased, the minimal value of coherence gets bigger which clearly indicates a superposition state consisting of more terms.
Entropy 21 00260 g002

Share and Cite

MDPI and ACS Style

Liu, Y.-C.; Shang, J.; Zhang, X. Coherence Depletion in Quantum Algorithms. Entropy 2019, 21, 260. https://doi.org/10.3390/e21030260

AMA Style

Liu Y-C, Shang J, Zhang X. Coherence Depletion in Quantum Algorithms. Entropy. 2019; 21(3):260. https://doi.org/10.3390/e21030260

Chicago/Turabian Style

Liu, Ye-Chao, Jiangwei Shang, and Xiangdong Zhang. 2019. "Coherence Depletion in Quantum Algorithms" Entropy 21, no. 3: 260. https://doi.org/10.3390/e21030260

APA Style

Liu, Y. -C., Shang, J., & Zhang, X. (2019). Coherence Depletion in Quantum Algorithms. Entropy, 21(3), 260. https://doi.org/10.3390/e21030260

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop