Entanglement in Quantum Search Database: Periodicity Variations and Counting

Abstract

Employing the single item search algorithm of N dimensional database it is shown that: First, the entanglement developed between two any-size parts of database space varies periodically during the course of searching. The periodic entanglement of the associated reduced density matrix quantified by several entanglement measures (linear entropy, von Neumann, Renyi), is found to vanish with period $\mathcal{O}\left(sqrt\right(N\left)\right)$. Second, functions of equal entanglement are shown to vary also with equal period. Both those phenomena, based on size-independent database bi-partition, manifest a general scale invariant property of entanglement in quantum search. Third, measuring the entanglement periodicity via the number of searching steps between successive canceling out, determines N, the database set cardinality, quadratically faster than ordinary counting. An operational setting that includes an Entropy observable and its quantum circuits realization is also provided for implementing fast counting. Rigging the marked item initial probability, either by initial advice or by guessing, improves hyper-quadratically the performance of those phenomena.

1. Introduction

Entanglement is believed to be a necessary resource for quantum computational speedup. Especially to oracle based algorithms such as Grover’s algorithm (for the original papers on the algorithm see [1,2,3,4] and for some later developments see e.g., [5,6,7]), the question has been studied extensively see e.g., [8,9,10,11,12], and for general quantum algorithms see the review [13].

This work reveals and studies analytically the periodic variation of the entanglement in a generalized version of Grover’s search. In that general variant of the algorithm the initial probability of its single marked item has been has rigged from probability $\frac{1}{N}$ to $0\le p\le 1$. By rigging the initial probability of the marked item, (an act stemmed either by prior information or by guess about the target item), a hyper-quadratic reduction of the classical search complexity is achieved. The algorithm is mathematically formulated in terms of the so called ${\mathcal{A}}_f\approx SU\left(2\right)$ “Oracle matrix algebra”, determined by a Boolean characteristic function $f:\{1,2,\dots ],N=2^n\}\to \{0,1\}$, c.f. [14,15,16,17]. The work proceeds by treating a set $\mathit{S}$ of cardinality N as a search-able database with no additional structure. Within this formalism, search appears as a $SU\left(2\right)$ periodic orbit, formed by a collection of qubits encoding algorithm’s database, enumerated by $\mathit{S}$. Searching manifests itself by means of quantum entanglement. This entanglement is developed between any two arbitrary parts which may partitioned the database space. The interesting feature of this type of bi-partite entanglement is its periodic variation in the course of searching. Indeed it is explicitly shown that the entanglement, quantified by various measures, has a periodically vanishing behaviour. The period of these vanishing moments is of order $\mathcal{O}\left(\frac{\pi }{4\sqrt{p}}\right)$ for $0<p\ll 1$ and $N\gg 1$. Specifically for $p=\frac{1}{N},$ i.e., in the case of standard search algorithm, the period is $\mathcal{O}\left(\frac{\pi }{4}\sqrt{N}\right)$, i.e., it equals the order of search complexity of the algorithm (further analysis below). This result motivates further the introduction of the fast counting problem. The problem concerns the fast determination of the database cardinality N in less than N counts of some sort to be determined (for a similar problem see [18]). The proposed solution shows that by using the periodicity of entanglement the task of fast counting is accomplished quadratically faster that N.

In outline this work, within the framework of the quantum search algorithm, deals with the following three topics:

First, it demonstrates the periodic evolution of entanglement as a function of search time (number of iterations) with period $\mathcal{O}\left(\sqrt{N}\right)$. This entanglement, quantified by measures such that Renyi, von Neumann and Wootters measures [19,20,21], refers to quantum entanglement developed between any two parts comprising by r and $n-r$ qubits of the total n qubit database. The entanglement is found to be independent of the size r, a result which implies a scale invariance (c.f. [22]) (Section 3).

Second, it proves generally that the periodic entanglement function of merit (e.g., Renyi entropy), takes all its possible values, at least one and at most four times within the period interval of order $\mathcal{O}\left(\sqrt{N}\right)$; it also provides a specific example of this phenomenon via a few qubit database (Section 4).

Third, it proposes a way to utilize the quadratic speedup in search time and the consequential periodic variation of database entanglement in order to speedup the counting of the dimension N of database in units of search trials. This proposal is complemented by finding an operational way for simulating the measurements of entanglement by means of an appropriate observable. This observable is identified as a generalized Y quantum unitary channel for which a unitary dilation is determined, a Hamiltonian model of which is also provided (Section 5).

Finally the work extends standard quantum search to the case of search with rigged initial probability and explains some ensuing consequences on the entanglement periodicity (Section 2).

2. Search with Rigged Marked Item Probability

(The reading of this section would require some knowledge of the algebraic framework of “Oracle algebra” which is provided in Appendix A).

Define ${\mathcal{D}}_M=\{\rho \in {\mathcal{M}}_M\left(\mathbb{C}\right);{\rho }^{†}=\rho ,\rho >0,Tr\rho =1\}.$ Let ${\left\{p_j\right\}}_{j=1}^N$ be the initial distribution of items-vector in database Hilbert space. Mark a single item $\left|x\right.〉$ with probability $p_x\equiv p\in (0,1),$ so that the initial vector $\left|\tilde{s}\right.〉={\sum }_{j=1}^N\sqrt{p_j}\left|j\right.〉$ equals $\left|\tilde{s}\right.〉=(cos\tilde{\alpha })\left|x\right.〉+(sin\tilde{\alpha })\left|x^{\perp }\right.〉,$ where $\left|x^{\perp }\right.〉=\frac{1}{\sqrt{1-p}}{\sum }_{j\ne x}\sqrt{p_j}\left|j\right.〉,$ and $\tilde{\alpha }={cos}^{-1}\left(\sqrt{p}\right).$ Operating m times on the initial state ${\pi }_N\left({\tilde{\rho }}_s\right)=\left|\tilde{s}\right.〉\left.〈\tilde{s}\right|,$ with search operator ${\pi }_N\left(\widetilde{U_G}\right)=exp\left(i\tilde{\theta }{\pi }_N\left({\Sigma }_2\right)\right),$ where $\tilde{\theta }=\pi -2\tilde{\alpha }$, yields a state that projects on target item ${\pi }_N\left({\tilde{\rho }}_x\right)=\left|x\right.〉\left.〈x\right|,$ with probability

$$\tilde{p}\left(m\right)=Tr\left[{\pi }_N\left(\tilde{\rho }\left(m\right)\right){\pi }_N\left({\tilde{\rho }}_x\right)\right]={cos}^2(\tilde{\alpha }-m\tilde{\theta }).$$

(1)

At m-th step the density matrix is

$$\begin{array}{cc}\hfill {\pi }_N\left(\tilde{\rho }\left(m\right)\right)& \equiv {\widetilde{U_G}}^m{\pi }_N\left(\widetilde{{\rho }_s}\right){\widetilde{U_G}}^{m†}\hfill \end{array}$$

(2)

$$\begin{array}{cc}\hfill & =\frac{1}{2}\left({\pi }_N\left({\Sigma }_0\right)+{\tilde{s}}_1\left(m\right){\pi }_N\left({\Sigma }_1\right)+{\tilde{s}}_3\left(m\right){\pi }_N\left({\Sigma }_1\right)\right)\hfill \end{array}$$

(3)

with ${\tilde{s}}_1\left(m\right)\equiv 〈{\Sigma }_1〉=-sin(2m\tilde{\theta }-2\tilde{\alpha }),$ ${\tilde{s}}_3\left(m\right)\equiv 〈{\Sigma }_3〉=cos(2m\tilde{\theta }-2\tilde{\alpha })$, where $〈{\Sigma }_{1,3}〉={\pi }_S\left({\tilde{\rho }}^{\left(s\right)}{\Sigma }_{1,3}\right)$ the mean values of the algebra generators, abbreviated to ${\tilde{s}}_i\equiv 〈{\Sigma }_i〉$. The first time when $\tilde{p}\left(m\right)=1,$ equals $m=\tilde{m}\left(p\right)=\frac{\tilde{\alpha }}{\tilde{\theta }}=\frac{{cos}^{-1}\left(\sqrt{p}\right)}{{sin}^{-1}\left(2\sqrt{p-p^2}\right)}.$ Initial and target states are unitarilly related i.e., $\left|\tilde{s}\right.〉={\pi }_N\left(\tilde{R}\right)\left|x\right.〉\equiv exp(-i\tilde{\alpha }{\pi }_N\left({\Sigma }_2\right))\left|x\right.〉$ [14,15,16,17].

The evolved state $\left|{\tilde{s}}^{\left(m\right)}\right.〉={\pi }_N\left({\widetilde{U_G}}^m\right)\left|\tilde{s}\right.〉,$ projects on the target state with probability $\tilde{p}\left(m\right)={\left|〈x|{\tilde{s}}^{\left(m\right)}〉\right|}^2,$ determined exclusively by the $xx$-matrix element of the combined unitary operators ${\pi }_N({\widetilde{U_G}}^m·\tilde{R}),$ explicitly $\tilde{p}\left(m\right)=\left.〈x\right|[{\pi }_N({\widetilde{U_G}}^m·\tilde{R})\circ {\pi }_N{({\widetilde{U_G}}^m·\tilde{R})}^{*}]\left|x\right.〉,$ i.e., by the $xx$-matrix element of its element-wise product with its complex conjugate. This suggests that any unitary transformation on the initial vector $\left|\tilde{s}\right.〉\to V\left|\tilde{s}\right.〉$ that accepts the marked vector as fixed point up to a phase i.e., $V\left|x\right.〉=e^{i\varphi }\left|x\right.〉,$ gives an equal complexity search algorithm; such transformations belong to $U\left(1\right)\otimes U(N-1)$ group, hence the algorithm’s search evolution orbit $\left|s^{\left(m\right)}\right.〉$ belongs to the $U\left(N\right)/U\left(1\right)\otimes U(N-1)=C{P}^{N-1}$ Grassmannian space ([20]; see also the hidden subgroup problem aspects of Grover’s algorithm [23]).

The asymptotic limit when $0<p\ll 1$ and $N\to \infty$, yields $\tilde{\theta }\left(p\right)=\mathcal{O}\left(p^{\frac{1}{2}}\right)$ and $\tilde{m}\left(p\right)=\mathcal{O}\left(\frac{\pi }{4\sqrt{p}}\right).$ Some indicative choices of probability p would provide new possibilities for search complexity and associated counting time (see related subsequent analysis). The following cases of p are interesting for $\tilde{p}\left(\tilde{m}\left(p\right)\right)=1$: (i) in general for $0<p\ll 1,$ we obtain $\tilde{m}\approx \mathcal{O}(1/\sqrt{p});$ (ii) for $p=1/N$ and $N\gg 1$ we obtain the standard optimal result $\tilde{m}\approx \mathcal{O}\left(\frac{\pi }{4}\sqrt{N}\right);$ (iii) for quadratically larger item probability $p=1/\sqrt{N}$ and $N\gg 1$, we obtain a quadratic speed up of search complexity $\tilde{m}\approx \mathcal{O}\left(\frac{\pi }{4}{N}^{1/4}\right);$ (iv) slowing down parameter $\tilde{m}$ below its classical value (with $p=1/N),$ is also possible: e.g., the choice $p=1/N^2$ yields $\tilde{m}\approx \mathcal{O}\left(N\right),$ while if $p=1/N^3$ then $\tilde{m}\approx \mathcal{O}\left(N\sqrt{N}\right).$

3. Reduced Subsystems of Database Qubits

Let $N=2^n,$ $k=1$ (one marked item, e.g., $\left|1\right.〉$), and $R=2^r,$ and let $L=N/R.$ We get the r-qubit reduced density matrix ${\pi }_R\left({\tilde{\rho }}^{\left(r\right)}\left(m\right)\right)$ from the n-qubit one by tracing out $(n-r)$-qubits (without including the marked item).

Next we adopt a unifying notation for describing the density matrix via index s, where $s=n$ for total qubits or $s=r$ for r qubits and $s=n-r$ for the rest of the qubits. Also the corresponding dimension index $S=2^s$ with values $S=N=2^n$ or $S=R=2^r$ and $S=L=2^{n-r}$. Then we write

$${\pi }_S\left({\tilde{\rho }}^{\left(s\right)}\right)=\frac{1}{2}({\pi }_S\left({\Sigma }_0\right)+(x^{\left(s\right)}-(S-1)w^{\left(s\right)}){\pi }_S\left({\Sigma }_3\right)+2y^{\left(s\right)}\sqrt{S-1}{\pi }_S\left({\Sigma }_1\right)).$$

(4)

The following outline shows the parameters relevant to the two cases:

$$\begin{array}{ccccc}{x}^{\left(n\right)},y^{\left(n\right)},w^{\left(n\right)}& \searrow & & & \\ \updownarrow & & \tilde{a}(k,p),\tilde{b}(k,p)& ⟷& 〈{\Sigma }_{1,3}〉\\ x^{\left(r\right)},y^{\left(r\right)},w^{\left(r\right)}& \nearrow & & \end{array}.$$

Given the relations $x^{\left(n\right)}={\tilde{a}}^2,y^{\left(n\right)}=\tilde{a}\tilde{b},w^{\left(n\right)}={\tilde{b}}^2,$ the two sets of Bloch vector components are related as

$$\begin{array}{ccc}\hfill x^{\left(r\right)}& =& x^{\left(n\right)}+(L-1)w^{\left(n\right)},\hfill \\ \hfill y^{\left(r\right)}& =& \sqrt{x^{\left(n\right)}{w}^{\left(n\right)}}+(L-1)w^{\left(n\right)},\hfill \\ \hfill w^{\left(r\right)}& =& L{w}^{\left(n\right)},\hfill \end{array}$$

where $\tilde{a}\left(m\right)=cos(\tilde{\alpha }-m\tilde{\theta }),$ and $\tilde{b}\left(m\right)=\frac{1}{\sqrt{N-1}}sin(\tilde{\alpha }-m\tilde{\theta })$. Also $\tilde{a}(m+\frac{2\pi }{\tilde{\theta }})=\tilde{a}\left(m\right)$ $\tilde{b}(m+\frac{2\pi }{\tilde{\theta }})=\tilde{b}\left(m\right),$ which implies for the Bloch components that $x^{\left(n\right)}(m+\frac{\pi }{\tilde{\theta }})=x^{\left(n\right)}\left(m\right),y^{\left(n\right)}(m+\frac{\pi }{\tilde{\theta }})=y^{\left(n\right)}\left(m\right)$ and $w^{\left(n\right)}(m+\frac{\pi }{\tilde{\theta }})=w^{\left(n\right)}\left(m\right),$ which in turn implies the periodicity of the Bloch vector components of the reduced density matrix $x^{\left(r\right)}(m+\frac{\pi }{\tilde{\theta }})=x^{\left(r\right)}\left(m\right),y^{\left(r\right)}(m+\frac{\pi }{\tilde{\theta }})=y^{\left(r\right)}\left(m\right)$ and $w^{\left(r\right)}(m+\frac{\pi }{\tilde{\theta }})=w^{\left(r\right)}\left(m\right),$ with exactly the same period $\tilde{T}=\frac{\pi }{\tilde{\theta }}=\frac{\pi }{{sin}^{-1}\left(2\sqrt{p-p^2}\right)}.$ Further we notice that due to special relation between reduced and un-reduced density matrix Bloch vector components, the period of the later ones do not depend on the parameter r, for any $(r,n-r)$ partition scheme of the set of database qubits; e.g., $$\begin{gathered} \begin{array}{|ccccc|}\hline & & & & \\ \hline\end{array} \\ \begin{array}{|ccc|}\hline & & \\ \hline\end{array} \end{gathered}$$ for $n-r=5$ and $r=3$.

As a consequence of this property, any polynomial or analytic functional of the $\tilde{T}$-periodic reduced density matrix will inherit its periodicity to the functional, which now is also periodic with a new period depending on $\tilde{T}$. As a particular such functional we can use e.g., the entropic measure of the entanglement developed between any two subsets $(r,n-r)$ of the total database. Such a function would also be periodic in the number of search iterations. This is the origin of the entanglement periodicity between any two parts.

Explicitly for such a case the S dimensional density matrix would read

$${\pi }_S\left({\tilde{\rho }}^{\left(s\right)}\left(m\right)\right)=\left(\begin{array}{cccc}{x}^{\left(s\right)}& y^{\left(s\right)}& \cdots ]& y^{\left(s\right)}\\ y^{\left(s\right)}& w^{\left(s\right)}& \cdots ]& w^{\left(s\right)}\\ ⋮& ⋮& \ddots & ⋮\\ y^{\left(s\right)}& w^{\left(s\right)}& \cdots ]& w^{\left(s\right)}\end{array}\right),$$

(5)

where $x^{\left(s\right)}=\frac{1}{2}(1+〈{\mathsf{\Sigma }}_3〉),$ $y^{\left(s\right)}=\frac{1}{\sqrt{S-1}}〈{\mathsf{\Sigma }}_1〉,w^{\left(s\right)}=\frac{1}{2(S-1)}(1-〈{\mathsf{\Sigma }}_3〉).$

Remark 1.

(1) By way of example consider the particular cases $k=1,3$ (one, three marked items), with vectors $|1\rangle ,$ and $\left\{\right|2\rangle ,|3\rangle ,|4\rangle \}$ respectively. The density matrix ${\pi }_N\left({\tilde{\rho }}^{\left(n\right)}\left(m\right)\right)$ in its N dimensional representation reads respectively,

$$\begin{array}{cc}\hfill {\pi }_N\left({\tilde{\rho }}^{\left(n\right)}\left(m\right)\right)& =\left(\begin{array}{cccccc}★& \blacksquare & \blacksquare & \blacksquare & \blacksquare & \cdots \\ \blacksquare & ▾& ▾& ▾& ▾& \cdots \\ \blacksquare & ▾& ▾& ▾& ▾& \cdots \\ \blacksquare & ▾& ▾& ▾& ▾& \cdots \\ ⋮& ⋮& ⋮& ⋮& ⋮& \ddots \end{array}\right),\hfill \end{array}$$

(6)

$$\begin{array}{cc}\hfill {\pi }_N\left({\tilde{\rho }}^{\left(n\right)}\left(m\right)\right)& =\left(\begin{array}{cccccc}▾& \blacksquare & \blacksquare & \blacksquare & ▾& \cdots \\ \blacksquare & ★& ★& ★& \blacksquare & \cdots \\ \blacksquare & ★& ★& ★& \blacksquare & \cdots \\ \blacksquare & ★& ★& ★& \blacksquare & \cdots \\ ▾& \blacksquare & \blacksquare & \blacksquare & ▾& \cdots \\ ⋮& ⋮& ⋮& ⋮& ⋮& \ddots \end{array}\right),\hfill \end{array}$$

(7)

where the elements of the matrices above have be given by means of the symbols ★, $▾$, $\blacksquare$, the explicit values of which are as follows:

$$\begin{array}{ccc}\hfill ★& =& \frac{1}{2}+\frac{1}{2}{\tilde{s}}_3\left(m\right)={cos}^2(\tilde{\alpha }-m\tilde{\theta }),\hfill \end{array}$$

(8)

$$\begin{array}{ccc}\hfill ▾& =& \frac{1}{N-1}(\frac{1}{2}-\frac{1}{2}{\tilde{s}}_3\left(m\right))=\frac{1}{N-1}{sin}^2(\tilde{\alpha }-m\tilde{\theta }),and\hfill \end{array}$$

(9)

$$\begin{array}{ccc}\hfill \blacksquare & =& \frac{1}{\sqrt{N-1}}{\tilde{s}}_1\left(m\right)=cos(\tilde{\alpha }-m\tilde{\theta })sin(\tilde{\alpha }-m\tilde{\theta }).\hfill \end{array}$$

(10)

The structure of the matrix is a cross shape with the cross point filled with $k\times k$ stars and crossing lines decorated with boxes while the rest of the sites are filled with triangles. While the thickness and position of the crossing box varies depending on k, the shape of the cross is permanent and characterizes the underline “Oracle algebra” structure of the algorithm.

(2) The matrices ${\pi }_N({\tilde{\rho }}^{(n)}(m))$, ${\pi }_R({\tilde{\rho }}^{(r)}(m))$ are homogeneous of degree 2 with respect to their arguments $\tilde{a}$, $\tilde{b}$.

(3) The success probability is periodic with respect to m, i.e., $\tilde{p}(m+\tilde{T})=\tilde{p}(m)$, with period $\tilde{T}=\pi /\tilde{\theta }$. This implies that $\tilde{a}\left(m\right),\tilde{b}\left(m\right)$, are periodic functions with period $2\tilde{T}$. Further any homogeneous function of degree 2 with respect to $\tilde{a}\left(m\right),\tilde{b}\left(m\right)$, are also periodic with period $\tilde{T}.$ E.g., the components ${\tilde{s}}_{1,3}\left(m\right)$ and ${\tilde{s}}_{1,3}^{\left(r\right)}$ are periodic with period $\tilde{T}.$ This property induces periodicity to operator $\tilde{\rho }\left(m\right)$ and to each of its matrix representations i.e., ${\pi }_S({\tilde{\rho }}^{(s)}(m+\tilde{T}))={\pi }_S({\tilde{\rho }}^{(s)}(m))$, for $S=N,R$ and $s=n,r$ respectively.

(4) Analytic functions of $\tilde{\rho }\left(m\right)$ (e.g., entanglement measures) are periodic with respect to m with period equal to the period of the smallest non-zero degree monomial in $\tilde{\rho }\left(m\right).$

(5) If $0<p<1,$ e.g., $p\approx 1$ then ${lim}_{p\to 1}\tilde{m}\left(p\right)=\frac{1}{2},$ so practically the target item is reached after a single step.

(6) In the uniform case of not rigged probability i.e., $p=\frac{1}{N},$ the tilted parameters become no-tilded i.e., angles $\tilde{\alpha },\tilde{\theta }$ and parameters $\tilde{a}\left(m\right),\tilde{b}\left(m\right),$ become respectively $\alpha =arccos\left(\sqrt{1/N}\right)$, $\theta =arcsin(2\sqrt{N-1}/N)$, and $a\left(m\right)=cos(\alpha -m\theta ),b\left(m\right)=\frac{1}{\sqrt{N-1}}sin(\alpha -m\theta ).$ For $N\gg 1$, we have $\tilde{m}\to \mathcal{O}\left(\sqrt{N}\right).$

Entanglement in quantum search: Next we investigate the periodicity of the variation of quantum entanglement in the course of search. Firstly designate by $m_{*}$ and $m_{**}$, two sequences of moments of projectivity of the density matrix, meaning steps $m,$ when $\rho \left(m\right)$ becomes projective matrix, in which cases the entanglement is zero.

Entanglement measures: Next we specialize to some important cases of entanglement measures, such as: Quantum Renyi (Ren), von Neumann entropy (vN), and Wooters concurrence $C_{(1,1)}$ (W), with definitions

$$\begin{array}{ccc}\hfill E_{\mathrm{Ren}}\left({\pi }_R\left({\tilde{\rho }}^{\left(r\right)}\left(m\right)\right)\right)& \equiv & E_{\mathrm{Ren}}\left(m\right)=\frac{1}{1-a}{log}_{2}Tr\left({\pi }_R{\left({\tilde{\rho }}^{\left(r\right)}\left(m\right)\right)}^a\right),0<a\ne 1\hfill \\ \hfill E_{\mathrm{vN}}\left({\pi }_R\left({\tilde{\rho }}^{\left(r\right)}\left(m\right)\right)\right)& \equiv & E_{\mathrm{vN}}\left(m\right)=-Tr({\pi }_R\left({\tilde{\rho }}^{\left(r\right)}\left(m\right)\right)ln{\pi }_R\left({\tilde{\rho }}^{\left(r\right)}\left(m\right)\right))\hfill \\ \hfill C_{(1,1)}\left({\pi }_R\left({\tilde{\rho }}^{\left(r\right)}\left(m\right)\right)\right)& \equiv & C_{(1,1)}\left(m\right)=max\{0,{\lambda }_1-{\lambda }_2-{\lambda }_3-{\lambda }_4\}=2\left|\tilde{a}\tilde{b}-{\tilde{b}}^2\right|,\hfill \end{array}$$

respectively [19,20,21], for reduced density matrix ${\pi }_R\left({\tilde{\rho }}^{\left(r\right)}\left(m\right)\right).$

For Wooters concurrence, the ${\lambda }_i$’s are in decreasing order the square roots of the eigenvalues of the matrix $\rho \tilde{\rho }$ where $\rho =({\sigma }_y\otimes {\sigma }_y){\rho }^{*}({\sigma }_y\otimes {\sigma }_y).$

In any representation ${\pi }_S,$ the reduced matrix ${\pi }_S\left({\rho }^{\left(s\right)}\left(m\right)\right)$ has the eigenvalues ${\lambda }_0\left(m\right)=0,$ with algebraic multiplicity $S-2$, and ${\lambda }_{1,2}=\frac{1}{2}(1\pm \sqrt{1+4(1-S)(wx-y^2)})$ (c.f. Appendix B, Proof of Lemma 2).

The quantum Renyi entropy ($0<a\ne 1$) is

$$E_{\mathrm{Ren}}\left({\lambda }_{1,2}\right)=\frac{1}{1-a}{log}_2\left({\lambda }_1^a+{\lambda }_2^a\right),$$

(11)

then recall that $wx-y^2=(L-1){(\tilde{a}-\tilde{b})}^2{\tilde{b}}^2,$ where $\tilde{a}=cos(\tilde{\alpha }-m\tilde{\theta }),$ $\tilde{b}=\frac{1}{\sqrt{N-1}}sin(\tilde{\alpha }-m\tilde{\theta }),$

Let any functional measure F$:D_N\to \mathbb{C},$ on the density matrix set $D_N$, either of polynomial or analytic type, such that the following is valid, $F\left(\rho \right)=0$ iff ${\rho }^2=\rho .$ Consider the density matrix ${\pi }_R\left({\tilde{\rho }}^{\left(n\right)}\left(m\right)\right)={\widetilde{U_G}}^m\left|\tilde{s}\right.〉\langle \tilde{s}|{\widetilde{U_G}}^{†m},$ when it is reduced to a state of arbitrary r qubits i.e., ${\pi }_R\left({\tilde{\rho }}^{\left(r\right)}\right)=T{r}_{n-r}{\pi }_N\left({\tilde{\rho }}^{\left(n\right)}\right).$

Proposition 1.

The following properties are. satisfied by ${\tilde{\rho }}^{\left(r\right)}\left(m\right)$:

(i) it is a periodic state wrt m, i.e., ${\pi }_R\left({\tilde{\rho }}^{\left(r\right)}(m+\tilde{T})\right)={\pi }_R\left({\tilde{\rho }}^{\left(r\right)}\left(m\right)\right)$ in any representation ${\pi }_R$ of the oracle algebra $A_f;$

(ii) during the course of search it becomes a projective state (pure state) for any r i.e., $\left({\pi }_R({\rho }^{\left(r\right)}\left(\tilde{m}\right)\right){)}^2={\pi }_R\left({\rho }^{\left(r\right)}\left(\tilde{m}\right)\right)$ at moments given by arithmetic progressions ${\tilde{m}}_{*}={\{\tilde{m}+k\tilde{T}\}}_{k=0}^{\infty }$ or ${\tilde{m}}_{**}={\{\tilde{m}-\frac{1}{\tilde{\theta }}arctan\left(\sqrt{N-1}\right)+k\tilde{T}\}}_{k=0}^{\infty }$. The asymptotic form of these sequences for the case $N\gg 1,$ and in general $0<p\ll 1,$ are ${\tilde{m}}_{*}^{\infty }={\left\{(2k+1)⌊\frac{\pi }{4\sqrt{p}}⌋\right\}}_{k=0}^{\infty }$ or ${\tilde{m}}_{**}^{\infty }={\left\{k⌊\frac{\pi }{2\sqrt{p}}⌋\right\}}_{k=0}^{\infty },$ and in particular in the uniform case, when $p=\frac{1}{N},$ we have respectively that ${\tilde{m}}_{*}^{\infty }={\left\{(2k+1)⌊\frac{\pi }{4}\sqrt{N}⌋\right\}}_{k=0}^{\infty },$ or ${\tilde{m}}_{**}^{\infty }={\left\{k⌊\frac{\pi }{2}\sqrt{N}⌋\right\}}_{k=0}^{\infty };$

(iii) the extremal points of Renyi functional $E_{\mathrm{Ren}}$ are: the sequences of minima are identified as ${\tilde{m}}_{*}$ and ${\tilde{m}}_{**}$ so that ${\tilde{m}}_{*}>{\tilde{m}}_{**},$ and the maxima ${\tilde{m}}_{\diamond \diamond }={\{\tilde{m}-\frac{\gamma }{2\tilde{\theta }}-k\tilde{T}\}}_{k=0}^{\infty }$ and ${\tilde{m}}_{\diamond }={\{{\tilde{m}}_{\diamond \diamond }\left(k\right)+\frac{\tilde{T}}{2}\}}_{k=0}^{\infty }$ so that ${\tilde{m}}_{\diamond }>{\tilde{m}}_{\diamond \diamond }.$

Figure 1 and Figure 2 display the three measures for $p=1/N$ (Figure 1), and Renyi entropy for $p=1/N,1/\sqrt{N}$ (Figure 2); details in figure captions.

The important point about these displays is that all zeros of the entropic measures are placed on the horizontal line of m’s and they belong to two inter-lasing sequences, ${\tilde{m}}_{*}$ and ${\tilde{m}}_{**}$. This property is true for any of the three displayed measures i.e., R, vN and W. The distance between every second zero equals the period $\tilde{T}$. This period is in fact related to success probability p via the formula $p=\frac{1}{2}(1\pm cos(\pi /\tilde{T}))$, (see Appendix B).

Concerning the behaviour of the entropy vs. #steps in Figure 1 and Figure 2: The plots of all entropic measures have common intervals of monotonicity, common positions of maxima and minima as well as that their common minima are vanishing points i.e., zeros.

Noticeable is the fact that the common intervals and minima, maxima, refer only to the entropic measures between them and not between the measures and the curve of success probability, c.f. the broken line vs. full lines in Figure 1.

Also this situation is independent from the relative size of the splitting r vs. $n-r$ of database qubits. Therefore we have a scale invariance of the position of the zeros for all entropy measures and all database splitting schemes.

Figure 3, displays the equal entanglement configurations determined by investigating their contours on the $r,m$ plane where various quantum search algorithms are located.

The following statements refer to the content of that figure:

(i) The equal Renyi entropy contours are organized in the contour curves wrt the iterations m and the number of remaining qubits r after database splitting;

(ii) Tracing any contour provides all pairs $(m,r)$ of fixed entanglement developed after m iterations between the two splitting sets with r and $n-r$ qubits respectively. Starting from e.g., point $(m_{max},r)$, of maximal m (box), and by tracing counter-clockwise its contour we encounter decreasing and increasing of values of m and r as it is indicated by up and down arrows $\downarrow ,\uparrow$ in the figure. Before returning to the initial point all equal entropy points have been traced out with landmarks the points $(m_d,r_{max})$ (disk),$(m_{min},r_d)$ (diamond) and $(m_d,r_{min})$ (circle), where $m_d,$ $r_d$ be the middle points. Operationally this indicates the various ways one can generate an equally entangled bi-partition of database by fiddling around with interaction time m and splitting dimensionR$(R=2^r,N/R=2^{n-r});$

(iii) All $m^{*},$ $m^{**}$ periodic zero-entanglement instances correspond to straight vertical parallel lines (dark in black-white or blue in color plot), which are independent from the values of r; (c.f. a similar scaling invariance discussed in [22]).

To provide an analytic explanation of the situation on Figure 3 we study the quantum Renyi entropy with respect to the variables $m,r$ which is

$$E_{\mathrm{Ren}}\left({\pi }_R\left({\tilde{\rho }}^{\left(r\right)}\left(m\right)\right)\right)\equiv E_{\mathrm{Ren}}(m,r)=\frac{1}{1-a}{log}_2\left({\lambda }_1^a+{\lambda }_2^a\right)$$

(12)

where ${\lambda }_{1,2}=\frac{1}{2}(1\pm \sqrt{1+4(1-S)(wx-y^2)})$.

By introducing the effective variables as

$$\begin{array}{ccc}\hfill \widehat{R}\left(r\right)& :& =\frac{2(N/R-1)(1-S)}{N-1}\hfill \end{array}$$

(13)

$$\begin{array}{ccc}\hfill \widehat{M}\left(m\right)& :& ={(\sqrt{N}sin(2\tilde{\alpha }-2m\tilde{\theta }+\omega )-1)}^2\hfill \end{array}$$

(14)

the entropy reads

$$E_{\mathrm{Ren}}(m,r)=\frac{1}{1-a}{log}_2\left\{\frac{1}{2^a}{\left(1+\sqrt{1+\widehat{M}\left(m\right)\widehat{R}\left(r\right)}\right)}^a+\frac{1}{2^a}{\left(1-\sqrt{1+\widehat{M}\left(m\right)\widehat{R}\left(r\right)}\right)}^a\right\}.$$

(15)

This formula implies that $E_{\mathrm{Ren}}$ is constant with respect to the variation of $\widehat{M}\left(m\right)$ and $\widehat{R}\left(r\right)$ iff their product $\widehat{M}\left(m\right)\widehat{R}\left(r\right)$ remains constant when variables m and r are varying.

4. Equal Entanglement Pre-Images

Regarding the number of iterations of the algorithm m as a continuous variable for the function $E_{\mathrm{Ren}}\left(m\right)$ and taking into account that $E_{\mathrm{Ren}}\left(m\right)$ is periodic with period $\tilde{T}$, a reasonable question can be posed: given a certain amount of entanglement what are the values of m associated with it, lying in the basic period interval $[0,\tilde{T}]$? Equivalently, what are the pre-images of the entanglement function $E_{\mathrm{Ren}}\left(m\right)$ for fixed $m\in [0,\tilde{T}]$?

Lemma 1.

The function $E_{\mathrm{Ren}}\left(m\right)$ takes all its possible resulting values, at least one and at most four times in the basic period interval $[0,\tilde{T}]$.

Proof. 

(A short technical part of the proof is deferred to Appendix B and its main part is provided below).

Let the points $A,B,B^{\prime },C,D,D^{\prime },E$ with abscissas in interval $[0,\tilde{T}]$ as follows

$$\begin{array}{ccc}\hfill A(m_A,y_A)& \equiv & A({\tilde{m}}_{**}\left(0\right),E_{\mathrm{Ren}}\left({\tilde{m}}_{**}\left(0\right)\right))\hfill \end{array}$$

(16)

$$\begin{array}{ccc}\hfill B(m_B,y_B)& \equiv & B({\tilde{m}}_{\diamond \diamond }\left(0\right),E_{\mathrm{Ren}}\left({\tilde{m}}_{\diamond \diamond }\left(0\right)\right))\hfill \end{array}$$

(17)

$$\begin{array}{ccc}\hfill B^{\prime }(m_{B^{\prime }},y_{B^{\prime }})& \equiv & B^{\prime }({\tilde{m}}_{\diamond \diamond }\left(0\right),0)\hfill \end{array}$$

(18)

$$\begin{array}{ccc}\hfill C(m_C,y_C)& \equiv & C({\tilde{m}}_{*}\left(0\right),E_{\mathrm{Ren}}\left({\tilde{m}}_{*}\left(0\right)\right))\hfill \end{array}$$

(19)

$$\begin{array}{ccc}\hfill D(m_D,y_D)& \equiv & D({\tilde{m}}_{\diamond }\left(0\right),E_{\mathrm{Ren}}\left({\tilde{m}}_{\diamond }\left(0\right)\right))\hfill \end{array}$$

(20)

$$\begin{array}{ccc}\hfill D^{\prime }(m_{D^{\prime }},y_{D^{\prime }})& \equiv & D^{\prime }({\tilde{m}}_{\diamond }\left(0\right),0)\hfill \end{array}$$

(21)

$$\begin{array}{ccc}\hfill E(m_E,y_E)& \equiv & E({\tilde{m}}_{**}\left(1\right),E_{\mathrm{Ren}}\left({\tilde{m}}_{**}\left(1\right)\right))\hfill \end{array}$$

(22)

Moreover the function $E_{\mathrm{Ren}}\left(m\right)$ is strictly increasing in each one of the intervals $[m_A,m_B]$, $[m_C,m_D]$ and strictly decreasing in each one of the intervals $[m_B,m_C]$, $[m_D,m_E],$ since for all $m\in [0,\tilde{T}]$ it holds that the sign of its first derivative on $[0,\tilde{T}]$ is positive for $m_A<m<m_B$, $m_C<m<m_D$ and negative for $m_B<m<m_C,$ $m_D<m<m_E$ (c.f. Figure 4).

Remark 2.

$\frac{d}{dm}{E}_{\mathrm{Ren}}\left(m\right)$ is continuous on $[0,\tilde{T}]$ with respect to m and vanishes only at points $m_B,m_C,m_D,m_E$. Therefore, it preserves its sign in each one of the open intervals.

Applying the Intermediate Value Theorem for $E_{\mathrm{Ren}}\left(m\right)$ and taking into account its monotonicity, we obtain that:

(i) if c is a number between $E_{\mathrm{Ren}}\left(m_A\right)$ and $E_{\mathrm{Ren}}\left(m_B\right)$, then there are exactly four points $m_{1,2,3,4}$ s.t. $E_{\mathrm{Ren}}\left(m_i\right)=c,$ $i=1,2,3,4$ and $m_1\in (m_A,m_{B^{\prime }}),m_2\in (m_{B^{\prime }},m_C),m_3\in (m_C,m_{D^{\prime }})and finally m_4\in (m_{D^{\prime }},m_E)$.

(ii) if $c=E_{\mathrm{Ren}}\left(m_B\right)$, then there are exactly three points $m_{1,2,3}$ s.t. $E_{\mathrm{Ren}}\left(m_i\right)=c,$ $i=1,2,3$ and $m_1=m_B,m_2\in (m_C,m_{D^{\prime }}),m_3\in (m_{D^{\prime }},m_D)$

(iii) if c is a number between $E_{\mathrm{Ren}}\left(m_B\right)$ and $E_{\mathrm{Ren}}\left(m_D\right)$, then there are exactly two $m_{1,2}$ s.t. $E_{\mathrm{Ren}}\left(m\right)=c,$ $i=1,2$ and $m_1\in (m_C,m_{D^{\prime }}),m_2\in (m_{D^{\prime }},m_E)$.

(iv) if $c=E_{\mathrm{Ren}}\left(m_D\right)$ (global maximum) then there is unique point m s.t. $E_{\mathrm{Ren}}\left(m\right)=c$, $m=m_D$.

Although we have proved the existence of $m_i$’s, the corresponding equations can not be easily solved analytically but $m_i$’s can be approximated. To this end we consider the piece-wise linear function $f\left(m\right)$ below which is a tent map for both the intervals $[m_A,m_C],$ $\left[m_{C,}{m}_E\right]$, and reads

$$f\left(m\right)=\left\{\begin{array}{c}{s}_{AB}(m-m_A)+y_A,m_A\le m<m_B\\ s_{BC}(m-m_B)+y_B,m_B\le m<m_C\\ s_{CD}(m-m_C)+y_C,m_C\le m<m_D\\ s_{DE}(m-m_D)+y_D,m_D\le m\le m_E,\end{array}\right.$$

(23)

where $s_{PQ}$ equals the slope of the line determined by the points $P,Q$

$$S_{PQ}=\frac{y_P-y_Q}{x_P-x_Q}$$

and then we solve the equations $f\left(m_i\right)=c$ instead of $E_{\mathrm{Ren}}\left(m_i\right)=c.$ □

Remark 3.

Recall that the tent map with parameter μ is the real-valued (and continuous) function

$$f_{\mu }\left(x\right)=\mu min\{x,\left|1-x\right|\}=\left\{\begin{array}{c}\mu x,0\le x<1/2\\ \mu (1-x),x\ge 1/2\end{array}\right.$$

(24)

where μ is a positive real constant and $f_{\mu }$ maps $[0,1]$ on to itself. Our function $f\left(m\right)$ is an obvious linear generalization of the tent map for both the intervals $[m_A,m_C],$ $\left[m_{C,}{m}_E\right].$

Numerical Example: (c.f. Figure 4, red dots stand for the approximate points of equal entanglement).

$E_{\mathrm{Ren}}\left(m\right)=\frac{1}{1-a}{log}_2\left\{{\lambda }_1^a\left(m\right)+{(1-{\lambda }_1\left(m\right))}^a\right\},$ $a=0.7,$ $n=12,$ $r=3,$ $p=1/N$,

(a) for $c=0.52$, the four points are $m_1=14.0839,$ $m_2=35.6796,$ $m_3=63.6776,$ $m_4=86.6127$,

(b) for $c=E_{\mathrm{Ren}}\left(m_B\right)=0.91675$, the three points are $m_1=m_B=24.8817,$ $m_2=74.3453,$ $m_3=74.9450$,

(c) for $c=\frac{E_{\mathrm{Ren}}\left(m_B\right)+E_{\mathrm{Ren}}\left(m_D\right)}{2}=0.933621$, the two points are $m_1=74.7452,$ $m_2=75.5451$,

(d) for $c=E_{\mathrm{Ren}}\left(m_D\right)=0.948567$, the unique point is $k=m_D=75.1452$.

Remark 4.

Since $\tilde{\theta }\left(p\right)=\mathcal{O}\left(p^{\frac{1}{2}}\right)$ we have that $\tilde{T}=\frac{\pi }{\tilde{\theta }}=\mathcal{O}\left(p^{-\frac{1}{2}}\right).$ E.g., For $p=1/N$ and $p=1/\sqrt{N}$ we have that $\tilde{T}=\mathcal{O}\left(\sqrt{N}\right)$ and $\tilde{T}=\mathcal{O}\left(\sqrt[4]{N}\right)$ respectively.

5. Fast Counting and the Entropy Observable

Counting the number of elements of a given finite set $\mathcal{S}$, requires a number of counts equal to the cardinality N of set $\mathcal{S}$; one count for each element, as common sense asserts. Fast counting is a novel method that solves this problem in quantum setting, achieving counting in quadratically less than N counts, by casting the counting problem in the language of quantum algorithms. This is shown to be possible by employing Grover’s fast quantum search algorithm, after it has been reformulated mathematically in terms of the so called “Oracle matrix algebra”, by treating set $\mathcal{S}$ as a search-able database. Within this formalism, search appears as a SU(2) periodic orbit, formed by a collection of qubits encoding the database space of the algorithm. It has been previously shown that multi-particle entanglement developed among the qubits of two parts of a bi-partition of the database Hilbert space is periodic with respect to the number of queries which is of the order of $\mathcal{O}\left(\sqrt{N}\right)$. Therefore measuring the entanglement by means of any of the measures developed before would determines the cardinality N of $\mathcal{S}$ in only $\mathcal{O}\left(\sqrt{N}\right)$ measurements or counts. Operationally the period finding amounts to determine the distance (expressed as numbers of queries) between any two successive zeros for some chosen measure. In effect the counting method proposed would lead to a quadratic reduction of the number of necessary N counts. To emphasize the operational character of the counting method an appropriate quantum observable, namely the Entropy observable, will be introduced and be implemented by means of a specific quantum circuit. Measuring the search step between successive zeros of that observable on a database reduced density matrix would allow the determination of cardinality N quadratically faster than usual counting as was mentioned.

Quantum measurement of Entropy observable: Next we provide a operational way of obtaining the entropy $S_L$ of the reduced density of matrix of quantum search at the m-th step. Since $S_L$ provides a measure of entanglement between database qubits, then a quantum measurement like estimation to $S_L$ and its possible implementation would be an indispensable aspect of the algorithm. The following lemma summarizes the operational procedure.

Lemma 2.

The entropy $S_L\left(\rho \right)$ of the reduced evolved density matrix $\rho \equiv {\rho }^{(m;r)}$ equals

$$S_L\left(\rho \right)=1-〈\mathcal{E}\left({\rho }^{\otimes 2}\right)({\Sigma }_3\otimes {\Sigma }_3)〉,$$

where the the map

$$\mathcal{E}\left({\rho }^{\otimes 2}\right)=\frac{1}{2}{\rho }^{\otimes 2}+\frac{1}{2}({\Sigma }_2\otimes {\Sigma }_2){\rho }^{\otimes 2}{({\Sigma }_2\otimes {\Sigma }_2)}^{†}$$

identified as a generalized Y channel is unitarilly generated as

$$\mathcal{E}\left({\rho }^{\otimes 2}\right)=T{r}_{aux}V({\rho }_{aux}\otimes {\rho }^{\otimes 2})V^{†},$$

where a unitary dilation $V=e^{iH}$ is generated by the Hamiltonian

$$H=-arctan\left(\frac{1}{\sqrt{2}}\right){\sigma }_2\otimes ({\Sigma }_2\otimes {\Sigma }_2),$$

by means of an auxiliary qubit in state ${\rho }_{aux}=|0\rangle \langle 0|.$

Closing we note further that for employing other measures for the counting method, e.g., the Renyi entropy etc we will need an extension of the previous Lemma. Indeed a general measure in the form of Renyi entropy would require positive integer powers of the reduced density (recall that the definition of Renyi entropy involves real powers of density matrix in general), to be provided by means of an operational method. To address this question we formulate the next Lemma 3.

Lemma 3.

Let the S dimensional reduced density matrix ${\pi }_S\left({\tilde{\rho }}^{\left(s\right)}\left(m\right)\right)$, its ℓ-th power for all $\mathbb{N}\ni \ell \ge S$ equals

$${\pi }_S{\left({\tilde{\rho }}^{\left(s\right)}\left(m\right)\right)}^{\ell }=f_{\ell }\left(t\right){\pi }_S{\left({\tilde{\rho }}^{\left(s\right)}\left(m\right)\right)}^{S-1}-h_{\ell }\left(t\right){\pi }_S{\left({\tilde{\rho }}^{\left(s\right)}\left(m\right)\right)}^{S-2}$$

where $t\equiv {\lambda }_1{\lambda }_2$ be the product of the non-zero eigenvalues ${\lambda }_1,{\lambda }_2$ of ${\pi }_S\left({\tilde{\rho }}^{\left(s\right)}\left(m\right)\right),$ and $h_{\ell +1}\left(t\right)=t{f}_{\ell }\left(t\right)$, where $f_{\ell }\left(t\right)$ is related to Chebyshev polynomials of the second kind $U_{\ell }\left(t\right),$ via relation $b_{\ell }\left(t\right)=U_{\ell -1}\left(\frac{t}{2}\right),$ with

$$f_{\ell +S}\left(t\right)=-\frac{1}{2}\left\{(2t-1){\sqrt{t}}^{\ell -1}{b}_{\ell }(1/\sqrt{t})\right\}+2^{-\ell -1}\left({(1-\sqrt{1-4t})}^{\ell }+{(1+\sqrt{1-4t})}^{\ell }\right),$$

with initial conditions $f_S\left(t\right)=1$ and $f_{S+1}\left(t\right)=1-t.$

6. Discussion and Conclusions

While addressing the question of the resource responsible for the computation advantage of a given quantum algorithm or some other quantum technological task, the quantum entanglement has been considered as the main factor. However there are some important obstructions for such a claim: first an ambiguous measure of quantum advantage should be chosen and its causal relation with a measure for entanglement should be demonstrated. While there are examples where such a claim is corroborated, other cases are known where this is not evident [24]. As alternatives to such counterexamples other resources beyond quantum entanglement have been considered e.g., coherence, distinguish-ability, contextuality, interference etc (see [25] and references therein).

The paper in fact relates its content with the problem of resources of the quantum advantage exhibiting by quantum algorithms though it does not addresses it directly. This assertion is based on the fact that the fast counting problem that is investigated aims at determining the size(cardinality) N of a given set S has two solutions. A classical solution (the convention element counting procedure) with complexity(counting cost) N, and a quantum solution, suggested in the paper, with complexity(counting cost) $\mathcal{O}\left(sqrt\right(N\left)\right)$. The source of quadratic speed in counting is by construction due to the quantum entanglement developed among elements of the set S, following the formalism of quantum search algorithm or some of its variants.

Measuring the number of iterations of the algorithm intervening among two successive canceling out (of any measure) of entanglement, determines the period $\mathcal{O}\left(sqrt\right(N\left)\right)$, from which the integral part N is obtained. It is in fact the entanglement among database parts via its quadratic-ally fast periodic zeroing that promotes entanglement to be a resource of the computational (counting) advantage.

Several questions can be put forward for future investigations: is the studied phenomenon of the entanglement periodicity robust under e.g., tri-partition or even successive partitions of database total state vector space; how is the periodic oscillation of entanglement could be re-configured in the case of collective quantum search [16], where multiple searchers are combining their algorithms by merging and/or concatenating their oracle algebra representations to achieve additional search complexity reductions? Can the accelerated period of entanglement is valid for other measures of correlation like the ones mentioned previously? How the fast counting procedure is modified in the case of open, dissipative extensions of quantum search as those analysed in [25] and the more complicated ones as in [15,17] as well?