1 Introduction

Quantum correlations lie at the heart of quantum information theory. They are responsible for some tasks that possess no classical counterpart. Among those correlations, entanglement is perhaps one of the most fundamental and nonclassical features exhibited by quantum systems [1–9]. Other measures have been introduced in the literature that grasp features that are not captured by entanglement, like the maximum violation of a Bell inequality, that is, nonlocality. The maximum violation of a Bell inequality for N parties is a good figure of merit that complements entanglement in those scenarios where the study of truly multipartite quantum correlations renders somehow impossible [10, 11].

Now, when it comes to quantum computing, the presence of multipartite entanglement is not a sufficient condition for a pure state quantum computer to be hard to simulate classically. Jozsa and Linden [12] stressed the fact that if the quantum computer is described using stabilizer formalism, there are many highly entangled states that have simple classical descriptions. Also, we have to bear in mind that being hard to simulate classically does not imply the corresponding quantum process to be doing any useful computation

Few discovered quantum algorithms provide an exponential speed-up over classical algorithms. Shor’s algorithm [13] is perhaps the most important because it can be used to factor large numbers and hence has implications for classical cryptography methods.

In the case of the Grover quantum search algorithm [14], the speed of calculation is improved by a factor of \(O(\sqrt{N})\) with respect to the best classical result. Certainly it is not an exponential improvement, but considerable. The two physical mechanisms that are believed to make possible the former speed-up over classical algorithms are on the one hand quantum correlations and on the other hand quantum parallelism, the superposition principle.

Therefore, taking into account that Grover’s algorithm provides a considerable—although nonexponential—speed-up, and given that multipartite entanglement is necessary (though not sufficient) for pure state quantum search, we investigate in the present work what quantum correlations are doing during the search process. The aforementioned study was discussed recently in the literature [15–18], although only two-qubit correlations were considered.

The actual role of entanglement or nonlocality in quantum algorithms is very less known. All effort has been devoted entirely on proving it is present, in sufficient quantities to make classical simulation inefficient [19–22]. We aim to throw some light on the question of what role it plays by calculating global quantum correlation measures as they vary during the course of the execution of Grover’s algorithm. Specifically, we shall pay special attention to the evolution of quantum correlations present between the qubits in a given register. By tracing the evolution of entanglement during the search, we shall obtain a better insight into how this algorithm works. To be clear, we reiterate that we are not trying to prove whether entanglement or any other correlation is present, we take them as given.

The present contribution is organized as follows. In Sect. 2, we revisit the details of the Grover search algorithm. Next, the correlations measures employed during the evolution of the search algorithm are introduced in Sect. 3. The corresponding results for bipartite and multipartite quantum correlations are shown in Sect. 4. Finally, some conclusions are drawn in Sect. 5.

2 Grover’s algorithm revisited

Grover [14] introduced in 1996 a faster than classical search algorithm in an unsorted database. Let us discuss the details of the algorithm. Suppose that we have a quantum circuit with an input register of n qubits plus some auxiliary ancillas, which are not of our concern now. A key ingredient in the algorithm is the Hadamard gate

$$\begin{aligned} H=\frac{1}{\sqrt{2}} \left( \begin{array}{ll} 1 &{}\, 1\\ 1 &{}\, -1\\ \end{array}\right) , \end{aligned}$$
(1)

which converts single-qubit states into a coherent superposition of them. It is convenient to introduce the gate W resulting of the action of n times the application of the Hadamard gate in our quantum circuit

$$\begin{aligned} W_H= & {} H\otimes H\otimes \cdots \otimes H \,(\equiv H^{\otimes n}) \, |0\ldots 0\rangle \nonumber \\= & {} \frac{1}{\sqrt{2^n}} \big (|00\ldots 00\rangle + |00\ldots 01\rangle +\cdots +|11\ldots 11\rangle \big ) \nonumber \\= & {} \frac{1}{\sqrt{2^n}} \sum _{i=0}^{2^n-1}|i\rangle \end{aligned}$$
(2)

on the initial register of n qubits, set initially at \(\mathbf{x}=|\mathbf{0}\rangle \). It is clear that what the \(W_H\) gate does is to create a uniform superposition of all possible states of the register of n qubits, starting from an initial state preparation of all states being reset to \(|\mathbf{0}\rangle \).

We also need an operator (\(2^n\times 2^n\) matrix) that flips only one element while leaving the remaining \(2^n-1\) untouched (\(|\mathbf{x}\rangle \rightarrow |\mathbf{x}\rangle \)). Thus, we obtain the gate

$$\begin{aligned} I_0=\left( \begin{array}{ccccc} -1 &{}\quad 0 &{}\quad 0 &{}\quad \cdots &{}\quad 0\\ 0 &{}\quad 1 &{}\quad 0 &{}\quad \cdots &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 1 &{}\quad \cdots &{}\quad 0\\ \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad \cdots &{} \quad 1\\ \end{array}\right) . \end{aligned}$$
(3)

Now we wonder about the composite action \(G = W_H I_0 W_H\) on an arbitrary state \(|\Psi \rangle =\)(\(|a\rangle \otimes |b\rangle \otimes |c\rangle \otimes \cdots \otimes |z\rangle \)), that is, we firstly apply in our quantum circuit (2) to \(|\Psi \rangle \), followed by (3) and finally let us act (2) again. The resulting state is given by

$$\begin{aligned} \left( \begin{array}{cc} \left( -1+\frac{2}{2^n}\right) a+\frac{2}{2^n}(b+c+\cdots +z)&{} \\ \frac{2}{2^n}a + \left( -1+\frac{2}{2^n}\right) b+\frac{2}{2^n}(c+d+\cdots +z)&{}\\ \vdots &{} \\ \frac{2}{2^n}(a+b+\cdots +y)+\left( -1+\frac{2}{2^n}\right) z&{}\\ \end{array}\right) . \end{aligned}$$
(4)

The outcome of \(G|\mathbf{0}\rangle \) has a clear significance: every element is inverted around its mean, that is, every single element value \(x_j\) of the n qubits at stage or iteration j, turns into a new value \(x_{j+1}=2\overline{\alpha }-x_j\). We have to wait for the last ingredient to give sense to \(G|\mathbf{0}\rangle \). During our search, we need an oracle that identifies the element(s) we seek in the search. This is tantamount to assign the value 0 to the element which does not accomplish the characteristics of the search, while to give the value 1 to the element(s) that is(are) sought. To be more precise, every time we ask the oracle, we perform the operation

$$\begin{aligned} F:|\mathbf{x}\rangle \mapsto (-1)^{f(x)}|\mathbf{x}\rangle , \end{aligned}$$
(5)

where f(x) is either zero or one for some k values out of \(2^n\) components of a general state \(|\Psi _j(\mathbf{x})\rangle \), at iteration j, of our register of n qubits .

Now we can give sense to the action \(-GF\) on the register \(|\mathbf{x}\rangle \). Suppose that there is only one element out of n qubits that is being sought. We have \(N=2^n\), and all the amplitudes are equal to \(\frac{1}{\sqrt{2^n}}\). Suppose that the element \(c_k\) is the one we are looking for. Let us now apply F such that \(c_k\) is being flipped. By reversing about the mean, we obtain an enhancement of the amplitude of the element we are looking for. By repeating the action of \(-GF\) several times, we arrive at the desired result with probability \(p=c_k^2\) being maximum.

What is the efficiency of the algorithm? So far we have supposed that there is one only item to be found, but there can exist several of them. Suppose that according to this criterion, we represent the general state vector of the register at iteration j by the wave function

$$\begin{aligned} |\Psi _j(\mathbf{x})\rangle \, = \, s_j \sum _{\mathbf{x}\in S} |\mathbf{x}\rangle + c_j \sum _{\mathbf{x}\in NS} |\mathbf{x}\rangle , \end{aligned}$$
(6)

where S is the set of k solutions of the oracle \(f(\mathbf{x})=1\) (number of items pursued), whereas there are \(2^n-k\) terms of (6) which are not (set NS). This decomposition proves to be extremely useful. We assume without loss of generality that the coefficients in (6) are real. After the oracle, we have

$$\begin{aligned} |\Psi _j^{\prime }(\mathbf{x})\rangle \, = \, -s_j \sum _{\mathbf{x}\in S} |\mathbf{x}\rangle + c_j \sum _{\mathbf{x}\in NS} |\mathbf{x}\rangle . \end{aligned}$$
(7)

Recall that the average of amplitudes of (7) at this stage is given by

$$\begin{aligned} \overline{\alpha } \, = \, \frac{1}{2^n}\big ( -s_j k + c_j (2^n-k)\big ). \end{aligned}$$
(8)

After application of operator \(-GF\), we get the new state (\(j+1\))

$$\begin{aligned} |\Psi _{j+1}(\mathbf{x})\rangle \, = \, s_{j+1} \sum _{\mathbf{x}\in S} |\mathbf{x}\rangle + c_{j+1} \sum _{\mathbf{x}\in NS} |\mathbf{x}\rangle , \end{aligned}$$
(9)

where we have the celebrated ‘inversion around the mean’ expressions \(s_{j+1}=2\overline{\alpha }-s_j,\,c_{j+1}=2\overline{\alpha }-c_j\). Expanding coefficients we have two recursion relations between coefficients \(s_{j+1}\) and \(c_{j+1}\), that transforms (\(s_j,c_j\)) into (\(s_{j+1},c_{j+1}\)) (the action of \(-GF\)). Because all operations done on the generic state \(|\Psi _j(\mathbf{x})\rangle \) are unitary, due to the fact that it is initially normalized to unity (\(s_{0}=c_{0}=\frac{1}{\sqrt{2^n}}\)), it must preserve its norm. This condition entails that

$$\begin{aligned} |\langle \Psi _j(\mathbf{x})|\Psi _j(\mathbf{x})\rangle |^2\,=\, k\,s_{j}^2\, +\,(2^n-k)c_{j}^2\,=\,1, \end{aligned}$$
(10)

which is equivalent to an ellipse with coordinates \(s_j=\frac{1}{\sqrt{k}}\sin \theta _j\), \(c_j=\frac{1}{\sqrt{2^n-k}}\cos \theta _j\), for some angle \(\theta _j\). After simplifying the aforementioned recursion relation, we obtain

$$\begin{aligned} \sin \theta _{j+1}= & {} \sin (\theta _{j}+\omega ), \nonumber \\ \cos \theta _{j+1}= & {} \cos (\theta _{j}+\omega ), \end{aligned}$$
(11)

provided we identify \(\cos \omega \) with \(1-\frac{2k}{2^n}\). After imposing the initial conditions mentioned before, we arrive at the final expression for the \(2^n\) coefficients of \(|\Psi _j(\mathbf{x})\rangle \) at step j:

$$\begin{aligned} s_{j}= & {} \frac{1}{\sqrt{k}}\sin \big ((2j+1)\nu \big ), \nonumber \\ c_{j}= & {} \frac{1}{\sqrt{2^n-k}}\cos \big ((2j+1)\nu \big ), \end{aligned}$$
(12)

with \(\sin ^2 \nu = \frac{k}{2^n}\).

We finish the search once we have absolute certainty about the result. In other words, \(ks_{j}^2=\sin ^2\big ((2j+1)\nu \big )=1\) for some \(j^{*}\). If the number of qubits n is high enough, then \(j^{*}\) is the closest integer value to

$$\begin{aligned} \bigg [\frac{\pi }{4}\sqrt{\frac{2^n}{k}}\bigg ]\,=\,O(\sqrt{2^n}). \end{aligned}$$
(13)

With this analysis we show that Grover’s algorithm is of \(O(\sqrt{N})\), as opposed to the best classical result N / 2.

3 Correlations measures employed

Research on the properties and applications of multipartite entanglement measures has attracted considerable attention in recent years [23–33]. One of the first useful entanglement measures for n-qubit pure states \(|\phi \rangle \) to be proposed was the one introduced by Meyer and Wallach [24]. It was later pointed out by Brennen [25] that the measure advanced by Meyer and Wallach is equivalent to the average of all the single-qubit linear entropies, that is, the average entanglement of each qubit of the system with the remaining \((n-1)\) qubits.

One way of characterizing the global amount of entanglement exhibited by an n-qubit state is provided by the sum of the (bipartite) entanglement measures associated with the \(2^{n-1}-1\) possible bipartitions of the n-qubits system [23]. This particular number takes into account that the marginal density matrices describing the \(k\hbox {th}\) party, after tracing out the rest, are equivalent to those of \(n-k\) parties because of the relation \(\left( {\begin{array}{c}n\\ k\end{array}}\right) =\left( {\begin{array}{c}n\\ n-k\end{array}}\right) \). In essence, these entanglement measures are given by the degree of mixedness of the marginal density matrices associated with each bipartition. In our case, we shall use the von Neumann entropy

$$\begin{aligned} S_{{\text {VN}}} = \sum _i-{\text {Tr}}[\rho _i \ln \rho _i] , \end{aligned}$$
(14)

where the sum is performed over all \(2^{n-1}-1\) different bipartitions.

A considerable amount of research has been devoted to unveil the mathematical structures underlying entanglement, in particular concerning those states which possess maximum entanglement, as given by some appropriate measure. Indeed, highly entangled multipartite states generate intense interest for quantum information processing and one-way universal quantum computing [34]. They are essential for several quantum error codes and communication protocols [35], since they are robust against decoherence. What differs here from the work of Meyer and Wallach is the fact that we introduce new quantum correlations measures in the study of the performance of the Grover search algorithm. As we shall see, we shall not arrive at the same conclusions for we do not address the same questions.

Another measure for entanglement that we shall consider is based on the conjecture (numerically checked by us) that the inequality [36]

$$\begin{aligned} 0 \, \le \, d_E\equiv C^{2}_{1(2..n)}-\sum _{i=2}^{n} C^{2}_{1i} \, \le \, 1 \end{aligned}$$
(15)

holds for an arbitrary number n of qubits in a pure state \(\rho =|\Psi \rangle _{1..n}\langle \Psi |\). \(C^{2}_{xy}\) stands for the concurrence squared between qubits x, y and \(C^{2}_{1(2..n)}=4\,\hbox {det}\rho _1\), with \(\rho _1={\text {Tr}}_{2..n}\)(\(\rho \)). We regard the quantity \(d_E\) between inequalities as a proper measure for multipartite entanglement, and so it is considered here.

A good witness of useful correlations is, in many cases, the violation of a Bell inequality by a quantum state. Most of our knowledge on Bell inequalities and their quantum mechanical violation is based on the CHSH inequality [37]. With two dichotomic observables per party, it is the simplest [38] (up to local symmetries) nontrivial Bell inequality for the bipartite case with binary inputs and outcomes. Let \(A_1\) and \(A_2\) be two possible measurements on A side whose outcomes are \(a_j\in \lbrace -1,+1\rbrace \), and similarly for the B side. Mathematically, it can be shown that, following LVM, \(|{\mathcal {B}}_{{\text {CHSH}}}^{{\text {LVM}}}(\lambda )|=|a_1b_1+a_1b_2+a_2b_1-a_2b_2|\le 2\). Since \(a_1\)(\(b_1\)) and \(a_2\)(\(b_2\)) cannot be measured simultaneously, instead one estimates after randomly chosen measurements the average value \({\mathcal {B}}_{{\text {CHSH}}}^{{\text {LVM}}} \equiv \sum _{\lambda } {\mathcal {B}}_{{\text {CHSH}}}^{{\text {LVM}}}(\lambda ) \mu (\lambda )= E(A_1,B_1)+E(A_1,B_2)+E(A_2,B_1)-E(A_2,B_2)\), where \(E(\cdot )\) represents the expectation value. Therefore, the CHSH inequality reduces to

$$\begin{aligned} |{\mathcal {B}}_{{\text {CHSH}}}^{{\text {LVM}}}| \le 2. \end{aligned}$$
(16)

Quantum mechanically, since we are dealing with qubits, these observables reduce to \(\mathbf{A_j}(\mathbf{B_j})=\mathbf{a_j}(\mathbf{b_j}) \cdot \mathbf{\sigma }\), where \(\mathbf{a_j}(\mathbf{b_j})\) are unit vectors in \({\mathbb {R}}^3\) and \(\mathbf{\sigma }=(\sigma _x,\sigma _y,\sigma _z)\) are the usual Pauli matrices. Therefore, the quantal prediction for (16) reduces to the expectation value of the operator \({\mathcal {B}}_{{\text {CHSH}}}\)

$$\begin{aligned} \mathbf{A_1}\otimes \mathbf{B_1} + \mathbf{A_1}\otimes \mathbf{B_2} + \mathbf{A_2}\otimes \mathbf{B_1} - \mathbf{A_2}\otimes \mathbf{B_2}. \end{aligned}$$
(17)

Tsirelson showed [39–41] that CHSH inequality (16) is maximally violated by a multiplicative factor \(\sqrt{2}\) (Tsirelson’s bound) on the basis of quantum mechanics. In fact, it is true that \(|{\text {Tr}}(\rho _{{\textit{AB}}}{\mathcal {B}}_{{\text {CHSH}}})|\le 2\sqrt{2}\) for all observables \(\mathbf{A_1}\), \(\mathbf{A_2}\), \(\mathbf{B_1}\), \(\mathbf{B_2}\), and all states \(\rho _{{\textit{AB}}}\). Increasing the size of Hilbert spaces on either A and B sides would not give any advantage in the violation of the CHSH inequalities. In general, it is not known how to calculate the best such bound for an arbitrary Bell inequality, although several techniques have been developed [42].

Although it is known that the violation of an n-particle Bell-like inequality of some sort by an n-particle entangled state is not enough, per se, to prove genuine multipartite nonlocality, it is the only approximation left in practice. Mermin, Ardehali, Belinskii and Klyshko (MABK) inequalities [43–45] are such that they constitute extensions of the Clauser–Horne–Shimony–Holt (CHSH) Bell inequalities [37] with the requirement that generalized GHZ states maximally violate them. In the case of multiqubit systems, one must instead use a generalization of the CHSH inequality to n qubits. MABK inequalities are of such nature that they constitute extensions of older inequalities. To concoct an extension to the multipartite case, we shall introduce a recursive relation [46] that will allow for more parties. This is easily done by considering the operator

$$\begin{aligned} B_{n+1} \propto [(B_1+B_1^{\prime }) \otimes B_n + (B_1-B_1^{\prime }) \otimes B_n^{\prime }] , \end{aligned}$$
(18)

with \(B_n\) being the Bell operator for n parties and \(B_1=\mathbf{v} \cdot \mathbf{\sigma }\), with \(\mathbf{\sigma }=(\sigma _x,\sigma _y,\sigma _z)\) and \(\mathbf{v}\) a real unit vector. The prime on the operator denotes the same expression but with all vectors exchanged. The concomitant maximum value

$$\begin{aligned} B_n^{\max } \equiv \max _{ \mathbf {a_j},\mathbf {b_j} }\,\,{\text {Tr}} (\rho {B_{N}}) \end{aligned}$$
(19)

will serve as a measure for the nonlocality content of a given state \(\rho \) of n qubits if \(\mathbf{a_j}\) and \(\mathbf{b_j}\) are unit vectors in \({\mathbb {R}}^3\). The nonlocality measure (19) is maximized by generalized GHZ states, \(2^{\frac{n+1}{2}}\) being the corresponding maximum value. The threshold for MABK Bell violation is given by the previous value over a \(\sqrt{2}\) factor. For instance, for \(n=3\) it is equal to 2, and for \(n=4\), equal to 4.

However, there exist other measures [47] such as the Svetlichny inequalities [48] which serve the same purpose, having a similar structure extended to the n-partite scenario [49, 50].

We are going to call ‘global measures’ the maximum violation of the MABK (19) Bell inequality and the total sum of entropies (14) performed over all \(2^{n-1}-1\) different bipartitions, for they naturally involve all qubits in the register of the quantum search. On the other hand, we shall call ‘local measures’ the ones that just employ usual measures for two qubits, such as (15), where there is a simple sum for concurrences. High values mean the following: maximum MABK violation of (19) only occurs for generalized GHZ states, and it is \(2^{\frac{N+1}{2}}\); maximum of (14) implies most of the reduced matrices being maximally mixed, while for (15) it is usually almost one. Low values of all previous measures imply being either zero or O(1).

4 Results

Where do we find multipartite correlation during the search process? Whenever we apply \(-GF\) on a reference state, we induce all qubits to interact between them. If we start with the state \(\mathbf{x}=|\mathbf{0}\rangle \), we do not have any entanglement initially. But as soon as we make them interact, we create several superpositions of all possible states of the register, until a single state is reached, the solution to the search algorithm. Therefore, we end up in a product state and no entanglement is present.

In order to discuss quantum correlations in the pure state (9), we need to define the corresponding density matrix \(\rho \). Assuming \(a \equiv s_{j} = \frac{1}{\sqrt{k}}\sin \big ((2j+1)\nu \big )\) and \(b \equiv c_{j} = \frac{1}{\sqrt{2^n-k}}\cos \big ((2j+1)\nu \big )\), with \(k=1\), the state \(\rho \) \(2^n \times 2^n\) in the computational basis is given by

$$\begin{aligned} \left( \begin{array}{ccccccccc} a^2&{}\quad ab&{}\quad ab&{}\quad ab&{}\quad ab&{}\quad ab&{}\quad ab&{}\quad ab&{}\quad \ldots \\ ab&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad \ldots \\ ab&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad \ldots \\ ab&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad \ldots \\ ab&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad \ldots \\ ab&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad \ldots \\ ab&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad \ldots \\ ab&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad b^2&{}\quad \ldots \\ \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \ddots \\ \end{array}\right) \end{aligned}$$
(20)

Any reduced state of m parties is obtained tracing out the remaining \(n-m\) qubits in the register. Due to symmetry, it is not difficult to prove that the reduced density matrix for any reduced state \(\rho _m\), which is a \(2^m \times 2^m\) real, symmetric matrix, is of the form

$$\begin{aligned} \rho _m=\left( \begin{array}{ccccc} \alpha &{}\quad \beta &{}\quad \beta &{} \quad \cdots &{}\quad \beta \\ \beta &{}\quad \gamma &{}\quad \gamma &{}\quad \cdots &{}\quad \gamma \\ \beta &{}\quad \gamma &{}\quad \gamma &{}\quad \cdots &{}\quad \gamma \\ \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots \\ \beta &{}\quad \gamma &{}\quad \gamma &{}\quad \cdots &{}\quad \gamma \\ \end{array}\right) _{2^m \times 2^m}, \end{aligned}$$
(21)

with \(\alpha \equiv a^2+\big (\frac{2^n}{2^m}-1\big )b^2\), \(\beta \equiv ab+\big (\frac{2^n}{2^m}-1\big )b^2\) and \(\gamma \equiv \frac{2^n}{2^m} b^2\). One can easily check the trace being unity for \(\alpha + (2^m-1)\gamma = a^2 + (2^n-1)b^2=1\). It can be shown due to the high symmetry of state (21) that, among the \(2^m\) concomitant eigenvalues, only two \(\{\lambda _1,\lambda _2\}\) are different from zero, namely

$$\begin{aligned} \frac{1}{2} \, \pm \, \sqrt{\bigg (\alpha -\frac{1}{2}\bigg )^2+(2^m-1)\beta ^2}. \end{aligned}$$
(22)

The concomitant proof is given in the Appendix. For all m, the corresponding eigenvectors have the form, in the computational basis \(\{|00..00\rangle ,|00..01\rangle ,\ldots ,|11..11\rangle \}\), of

$$\begin{aligned} |\lambda _i\rangle \,=\,N\cdot \bigg ( \frac{\beta (2^m-1)}{\lambda _i-\alpha }, 1, 1, \ldots , 1 \bigg )^{T}, \end{aligned}$$
(23)

where N is the normalization constant. These results will have strong implications as far as entanglement will be concerned, as we shall see.

Now that we are able to address any reduced density matrix in very much detail, we shall study quantum correlations for \(n=2,4,6\) and 8 qubits.

4.1 Bipartite nonlocality and entanglement

In the case of two qubits, the maximal violation of the CHSH Bell inequality can be found analytically. Let us consider (21) for \(m=2\). Following the steps in [11], let us change the basis for state \(\rho _2\) from the computational basis \(\{|00\rangle ,|01\rangle ,|10\rangle ,|11\rangle \}\) to the Bell basis \(\{|\Phi ^{+}\rangle ,|\Phi ^{-}\rangle ,|\Psi ^{+}\rangle ,|\Psi ^{-}\rangle \}\). In such basis, the state reads

$$\begin{aligned} \frac{1}{2} \left( \begin{array}{cccc} \alpha +2\beta +\gamma &{}\quad \alpha -\gamma &{}\quad 2(\beta +\gamma ) &{}\quad 0\\ \alpha -\gamma &{}\quad \alpha -2\beta +\gamma &{}\quad 2(\beta -\gamma ) &{}\quad 0\\ 2(\beta +\gamma ) &{}\quad 2(\beta -\gamma ) &{}\quad 4\gamma &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0\\ \end{array}\right) . \end{aligned}$$
(24)

If we consider in the Bell basis only the terms that contribute in the optimization of the CHSH Bell inequality, that is, in \({\text {Tr}}(\rho _2 B_{{\text {CHSH}}})\), we have

$$\begin{aligned} \left( \begin{array}{cccc} \rho _{11} &{}\quad i\rho ^{I}_{12} &{}\quad i\rho ^{I}_{13} &{}\quad \rho ^{R}_{14}\\ -i\rho ^{I}_{12} &{}\quad \rho _{22} &{}\quad \rho ^{R}_{23} &{}\quad i\rho ^{I}_{24}\\ -i\rho ^{I}_{13} &{}\quad \rho ^{R}_{23} &{}\quad \rho _{33} &{}\quad i\rho ^{I}_{34}\\ \rho ^{R}_{14} &{}\quad -i\rho ^{I}_{24} &{}\quad -i\rho ^{I}_{34} &{}\quad \rho _{44} \end{array} \right) . \end{aligned}$$
(25)

Thus, state \(\rho _2\) behaves as a state almost linear in the Bell basis as far as effective contribution to CHSH is concerned. That state reads

$$\begin{aligned} \frac{1}{2} \left( \begin{array}{cccc} \alpha +2\beta +\gamma &{}\quad 0 &{}\quad 0 &{}\quad 0\\ 0 &{}\quad \alpha -2\beta +\gamma &{}\quad 2(\beta -\gamma ) &{}\quad 0\\ 0 &{}\quad 2(\beta -\gamma ) &{}\quad 4\gamma &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0\\ \end{array}\right) . \end{aligned}$$
(26)

Let us define \(\rho _{11}=(\alpha +2\beta +\gamma )/2\), \(\rho _{22}=(\alpha -2\beta +\gamma )/2\), \(\rho _{33}=2\gamma \), \(\rho _{44}=0\) and \(\rho _{23}=\beta -\gamma \). Optimization is carried out as in [11] and after some algebra, we obtain

$$\begin{aligned} 2\sqrt{2}\sqrt{(\rho _{11}-\rho _{44})^2+(\rho _{22}-\rho _{33})^2+4\big (\rho ^{R}_{23}\big )^2}, \end{aligned}$$
(27)
Fig. 1
figure 1

(Color online) Evolution of the maximum violation of the CHSH Bell inequality for any pair of two qubits within a register of \(n=4\) qubits (crosses, green curve) and \(n=8\) qubits (diamonds, red curve). Violation of CHSH never occurs. See text for details

Full size image

with the diagonal elements of (26) arranged so that \(\rho _{11}>\rho _{22}>\rho _{33}>\rho _{44}\). Nonlocality \(CHSH^{\max }\) is depicted in Fig. 1 for the number of register qubits \(n=4,8\). We must recall that the relation of coefficients \(\{a,b\}\) with the number of qubits n in the register is given in (12), with \((k=1)\) \(\sin ^2 \nu = \frac{1}{2^n}\). If n become big enough, then \(\nu \approx 0\), which collapses the evolution of the state in the Grover search algorithm into a single one for all iterations, which has null correlations. On the other hand, \(\nu \approx 0\) implies more iterations in order to have full probability success.

As far as entanglement is concerned, the concurrence is measured in (21) for \(m=2\). As we can appreciate from Fig. 1, no violation of CHSH occurs. The concurrence measure is easy to compute as a function of the iteration step j, as performed in [15]. The concurrence reads

$$\begin{aligned} C_{xy}= & {} 2\big |\cos ((2j+1)\nu +\delta ) \nonumber \\&-\,\frac{1}{\sqrt{2^n-1}} \sin ((2j+1)\nu +\delta )\big | \nonumber \\&\times \,\frac{1}{\sqrt{2^n-1}}\sin ((2j+1)\nu +\delta ). \end{aligned}$$
(28)

As seen from (23), the more number of qubits n we have in the register, the less correlated the state will be, for the only different coefficient decreases very fast with n taking into account the functional form for \(\beta \). This fact is mathematically evident from (28). Usually, concurrence (28) is not very big from computations and decreases very fast as the total number of qubits in the register increase. As a matter of fact, evolution of the concurrence is very similar to the one corresponding to a Bell diagonal state (\(C=\max (2\lambda _{\max }-1,0)\), with \(\lambda _{\max }\) being the maximum eigenvalue of the reduced two-qubit matrix).

4.2 Multipartite nonlocality and entanglement

The maximum violation of MABK for \(n=4\) qubits is depicted in Fig. 2. Nonlocality is actually very low, which implies that no quantum correlation boosts the search. Regarding higher number of qubits, the situation does not improve. Nonlocality for \(n=6\) and \(n=8\) is shown in Fig. 3. Computing the maximum of MABK for \(n\ge 8\) becomes computationally demanding. As well as in the \(n=4\)-case, no Bell violation occurs, even when we compute nonlocality for the whole register.

Fig. 2
figure 2

(Color online) Evolution of the maximum violation of the MABK Bell inequality for \(n=4\) qubits (diamonds, red curve) and success probability (crosses, green curve). Violation of MABK never occurs. Also, the corresponding numerical value is very low. See text for details

Full size image
Fig. 3
figure 3

(Color online) Evolution of the maximum violation of the MABK Bell inequality for \(n=6\) qubits (diamonds, red curve) and \(n=8\) qubits (crosses, green curve). Violation of MABK never occurs in this case either. It can be appreciated that as n increases, the frequency decreases. See text for details

Full size image

Measure \(d_E\) (15) can be easily converted into an analytic expression from \(C^{2}_{1(2..n)}=4\,\hbox {det}\rho _1\), with \(\rho _1={\text {Tr}}_{2..n}\)(\(\rho \)) being (21) for \(m=1\), and the fact that the concurrence is the same between all two qubits in the register. With these information, the \(d_E\) measure reads

$$\begin{aligned} C^{2}_{1(2..n)}-\sum _{i=2}^{n} C^{2}_{1i}\,=\,4\big (\alpha \gamma - \beta ^2\big )-(n-1)C_{xy}^2 \leftarrow f(j;n). \end{aligned}$$
(29)

As n increases, \(d_E=f(j;n)\) decreases the frequency (the target is reached with more number of steps) and the numerical value becomes smaller and smaller. As far as entanglement measure (14) is concerned, any reduced state of m qubits possesses only two nonzero eigenvalues, having eigenstates (23) which resemble almost uniform pure states. Thus, we do expect measure (14) to be extremely low, as it is the case. Since there are only two eigenvalues \(\{ \lambda _1,\lambda _2 \}\), the states being the same for the same partition and the sum is taken over \(2^{n-1}-1\) m-partitions, measure (14) reads

$$\begin{aligned} S_{vN}= & {} - \frac{1}{2} \sum _{m=1}^{n-1} \left( {\begin{array}{c}n\\ m\end{array}}\right) \nonumber \\&\bigg ( \lambda _1(vj,m,n) \log \big (\lambda _1(vj,m,n)\big ) + \nonumber \\&\quad \lambda _2(vj,m,n) \log \big (\lambda _2(vj,m,n)\big ) \bigg ). \end{aligned}$$
(30)

It is interesting to notice that (30) can thus be computed analytically, a fact that greatly helps in computing entanglement measures in the Grover search algorithm.

Fig. 4
figure 4

(Color online) Evolution of the entanglement measures \(d_E\) (crosses, green curve) and \(S_{vN}\) (diamonds, red curve). The curve in blue (squares) depicts the probability of success. Although different in nature, both measures evolve in the same fashion. See text for details

Full size image

Measures (29) and (30) are plotted in Fig. 4 for \(n=4\) and Fig. 5 for \(n=8\). Their functional form follow the same pattern, although \(S_{vN}\) takes into account all possible bipartitions. \(d_E\) detects the presence of nonzero entanglement, whereas \(S_{vN}\) has very low values. \(S_{vN}\) conceptually grasps more details of the pure state of the register. Thus, practically speaking, we have either null or extremely low real multipartite entanglement.

Fig. 5
figure 5

(Color online) Same as in Fig. 4 but for \(n=8\) qubits. The green curve (crosses) corresponds to \(S_{vN}/100\), whereas the one in red (diamonds) is \(d_E\). Although it may seem that the numerical value of \(S_{vN}\) is considerable, it is in fact very low. Notice how smooth curves become as n increases. See text for details

Full size image

As far as the behavior of entanglement is concerned, its measure of evolution in the Grover algorithm can already be found for multipartite systems in [24, 51]. That is, the curves increase up to approximately half of the optimal number of iteration and then decease. The novelty in our case is that the measure of nonlocality is exactly doing the same thing, first pointed out in the present work. It seems to be a common trend for several entanglement measures and even for a quantum correlation measure such as nonlocality, very far from any definition related to quantum entanglement.

5 Discussion

In this work, we have studied global correlations in the whole process of the Grover search algorithm. What is meant by ‘global’ here are the quantum correlations that grasp the entire register containing several qubits, as opposed to ‘local’ were partitions are introduced to deal with bipartite quantum correlations. It is a general trend that global correlations are very low as opposed to local ones. All correlation measures have been given in analytic fashion, even when it is required to find all possible reduced matrices of the original pure state of the quantum register. These new results, when compared to the previous ones found in the literature, are more general since they tackle truly multipartite quantum correlations. Since both nonlocality and entanglement are either zero or extremely low, it is very difficult to address the precise role of quantum correlations in this particular quantum algorithm. These conclusions follow from Figs. 3 and 5. In Fig. 3, we can clearly appreciate how small the maximum violations of MABK Bell inequalities are from the corresponding exponential values \(2^{\frac{N+1}{2}}\) belonging to generalized GHZ states. Also, in Fig. 5, the huge difference between the values of \(S_{{\text {VN}}}\) and \(d_E\) are apparent.

One could explain that these low correlations are due to the high symmetry that is present in the problem. It might be the case. Studying much more complex algorithms (see, for instance [52]) could shed some light on the real role of quantum correlations in the speed-up process as compared to classical algorithms. However, in the present case, it appears as if only quantum parallelism was the only tool required from quantum mechanics to overcome their classical counterparts.