Faster Together: Collective Quantum Search

Abstract

Joining independent quantum searches provides novel collective modes of quantum search (merging) by utilizing the algorithm’s underlying algebraic structure. If n quantum searches, each targeting a single item, join the domains of their classical oracle functions and sum their Hilbert spaces (merging), instead of acting independently (concatenation), then they achieve a reduction of the search complexity by factor $\mathcal{O}(\sqrt{n})$.

1. Introduction

The quantum search algorithm, from its initial conception [1–3], to the subsequent manifold of ongoing developments, see e.g., the various open research projects addressing the association of quantum search with e.g., quantum entanglement [4], quantum programming [5], error faultiness [6], fixed-point quantum search [7], and quantum walks [8], constitutes one of the pillars of the research area of quantum computing. Despite its simplicity and the manifested versatility in applications the algorithm remains a challenge to meet, especially when it is considered as a computational primitive that could be synthesized in non trivial ways with itself.

This point of view is put forward in this work, where utilizing the underlying algebraic structure of the search algorithm and its matrix representation theory [9], the algorithm is treated as a computational unit composed in two different ways, to be called merging and concatenation. Merging of two algorithms creates a computational advantage that reduces search complexity in contradistinction to non joint searches of simple concatenation. More accurately, it is shown that the merging of n single searches with database dimensions N_k = 2^k, k = 1, …, n, causes a complexity reduction proportional of square root of n. This main result of collective search is scrutinized in all intermediated joining schemes, where among n searches k are merged and the rest are left concatenated, via partitioning databases into distinct groups of merged algorithms and then concatenating the resulting groups. The logistics of joining schemes is carried out via Young diagrams and tableaux of partitions, as well as majorization theory [10]. (Proofs and examples are placed in the second part of the paper).

1.1. Single Quantum Search

Find 1 ≤ k < N marked elements from the set Δ = {1, 2, …N}, by improving the classical complexity $\mathcal{O}(N)$ of the search.

The ν binary strings (a₁, a₂, …, a_ν) from the elements of classical database with size N = 2^ν, which are assigned via (a₁, a₂, …, a_ν) → |a₁, a₂, …, a_ν〉 ≡ |i〉, i = 1,…, N, to N basis vectors of Hilbert space H = (span{|0〉, |1〉})^⊗ν. Via the assignment |i〉 → |i〉 〈i|, this leads to the database $\Pi ={\left\{|i\rangle \langle i|\right\}}_{i=1}^N={\left\{{\rho }_i\right\}}_{i=1}^N\approx l_2(\mathrm{\Delta })/U(1)$ consisting of a collection of N pure density matrices. Let the oracle function f, introduced as the characteristic function of subset I ⊂ Δ of marked items, namely f(i) = 1 for i ∈ I and f(i) = 0 for i ∉ I. The density matrices ρ_x, ρ_s, for the marked and initial vectors are expressed in terms of vectors |x〉, |x^⊥〉, and $|s\rangle =\frac{1}{\sqrt{N}}{\sum }_{i=1}^N|i\rangle$, where |x〉 and |s〉, are the the solution state and the equiprobable superposition of all database states, respectively. Define the reflection operators J_x = 1 – 2 |s〉 〈s|, and the unitary search operator U_G = −J_sJ_x, that implements a search via the action $\rho \to U_G\rho U_G^{†}$ Next, introduce the Σ₀, Σ₁, Σ₂ and Σ₃ as the Hermitian generators of oracle algebra A_f [9],

$$\begin{array}{l}{\Sigma }_1=|x\rangle \langle x^{\perp }|+|x^{\perp }\rangle \langle x|,{\Sigma }_2=-i|x\rangle \langle x^{\perp }|+i|x^{\perp }\rangle \langle x|,\\ {\Sigma }_3=|x\rangle \langle x^{\perp }|-|x^{\perp }\rangle \langle x|,{\Sigma }_0=|x\rangle \langle x^{\perp }|+|x^{\perp }\rangle \langle x|,\end{array}$$

with commutation relations [Σ_α, Σ_b] = 2iΣ_c (cyclically), a, b, c ∈ {0, 1, 2, 3}, and Σ₀ central, i.e., A_f ≈ u(2) (see Appendix for the representation theory).

In terms of oracle algebra generators the search operator reads U_G = exp(iθΣ₂), with $\theta =\arcsin (-2\sqrt{k(N-k)}/N$. It holds that $U_G^m=\exp (im\theta {\Sigma }_2)$, m ∈ N, and then ${\rho }^{(m)}:=U_G^m{\rho }_s{U}_G^{m†}$, and p_m = Tr(ρ^(m) |x〉 〈x|) = cos² (mθ – α) p_m = 1 iff cos²(mθ – α) = 1, for N ≫ 1, k < N, i.e., the complexity of the algorithm is $\mathcal{O}(\sqrt{N/k})$.

2. Collective Quantum Search: Merging and Concatenation

Considering joining of two searches in Hilbert spaces $H_r=span{\left\{|i\rangle \right\}}_{i=1}^{N_r}$, r = 1, 2, with dimensions N₁, N₂ in the form of concatenation, we first need to embed their database vectors into a larger space H₁ ⊕ H₂ of dimension N₁ + N₂, by padding in zeros into their components, on their top or on their tail, until their number becomes N₁ + N₂. By convention, concatenating searches of dim N₁ with one of dim N₂, would mean to form new basis vectors ${\{|\theta \rangle }_{N_1}\oplus {|i\rangle }_{N_2};i=1,\dots ,N_2\}$, and ${\{|i\rangle }_{N_1}\oplus {|\theta \rangle }_{N_2},i=1,\dots ,N_1\}$, where we denote by ${|\theta \rangle }_{N_1}$, ${|\theta \rangle }_{N_2}$, the respective null vector with all their components being zero. These two new sets of basis vectors constitute the database of the jointed algorithms of dim N₁ + N₂. The marked vector to be called |x_conc〉 will read

$$|x_{conc}\rangle ={|x_1\rangle }_{N_1}\oplus {|\theta \rangle }_{N_2}+{|\theta \rangle }_{N_1}\oplus {|x_2\rangle }_{N_2}=\left(\begin{array}{c}|x_1\rangle \\ |x_2\rangle \end{array}\right).$$

Definition 1. l-merging and l-concatenation. Let l quantum search algorithms [1] U_r(f_r) : H_r → H_r, r = 1, 2, …, l with$H_r=span{\left\{|i\rangle \right\}}_{i=1}^{N_r}$ their database Hilbert spaces, $U_r(f_r)=-J_{s_r}{J}_{x_r}$, where the reflection operators$J_{s_r}=1-2|s_r\rangle \langle s_r|$, and$J_{x_r}=1-2|x_r\rangle \langle x_r|$, are defined wrt some vectors |x_r〉 and |s_r〉, with$|s_r\rangle =\frac{1}{\sqrt{N_r}}{\sum }_{i=1}^{N_r}|i\rangle$, and$|x_r\rangle ={\sum }_{i=1}^{N_r}{f}_r(i)|i\rangle \in H_r$ the target vectors; here : $f_r:Z_{N_r}\to Z_2$ their respective oracle functions. We further denote the merged space by$H_{merg}={\oplus }_{r=1}^l{H}_r$ with N_merg = N₁ + N₂ + ⋯·+ N_l, let also a quantum search algorithm U_merg(f_merg) : H_merg → H_merg, with$H_{merg}=span{\left\{|i\rangle \right\}}_{i=1}^{N_{merg}}$its space, $U_{merg}(f_{merg})=-J_{|s_{merg}\rangle }{J}_{|x_{merg}\rangle }$,its search unitary, and$f_{merg}:Z_{N_{merg}}\to Z_2$ its l-target oracle function, and also denoted by$|x_{merg}\rangle ={\sum }_{i=1}^{N_{merg}}{f}_{merg}(i)|i\rangle$, the l-target vector.

Lemma 1. Let a 2-concatenation with search operator$U_{conc}=-J_{|s_{merg}\rangle }{J}_{|x_{merg}\rangle }$. Then the following decomposition is valid U_conc = U₁ ⊕ U₂, where U₁, U₂ are the search operators in Hilbert spaces with dimensions N₁, N₂, respectively.

2.1. Collective Quantum Search: Joining Schemes and Young Diagrams

By convention we take the horizontal direction in a Young diagram (for notation c.f. [11]) to denote merging (the number of row boxes equals the number of merged searches), and in the vertical direction the number of rows denotes concatenated sets, i.e.,

Recall the partial order of majorization between partitions [10]. Let partitions π = (π₁, …, π_s) and ρ = (ρ₁, …, ρ_t); if s ≥ t then π weakly majorizes ρ, written as π^w≻ρ, if the following inequalities are satisfied,

$${\displaystyle \sum _{i=1}^k{\pi }_i}\ge {\displaystyle \sum _{i=1}^k{\rho }_i},1\le k\le t,{\displaystyle \sum _{i=1}^s{\pi }_i}\ge {\displaystyle \sum _{i=1}^t{\rho }_i}.$$

If the last relation above is only an equality, then π majorizes ρ, written as π ≻ ρ. Associating partitions to Young diagrams, i.e., π → Y (π), an equivalent definition of majorization of partitions is induced via

Lemma 2. (Muirhead’s Lemma) If π, ρ ⊢ m, then π ≻ ρ iff Y (π) can be obtained from Y (ρ) by moving boxes up to lower numbered rows.

In this way all, Young diagrams of given m are partially ordered in the poset {π ⊢ m, ≻}, via their associated Young diagrams as shown schematically below,

$$\stackrel{moveboxesup}{\begin{array}{ccc}Y(\pi )& \leftarrow & Y(\rho )\\ \downarrow & & \uparrow \\ \pi & \succ & \rho \end{array}}$$

In the context of collective search, we say equivalently that if diagram Y (π) of a partition π describing a joining scheme for a set of searches, has been obtained from some other Y (ρ) by merging some searches among them, i.e.,

$$\begin{array}{ccc}Y(\pi )& \stackrel{moveboxesup,mergingasearch}{\leftarrow }& Y(\rho ),\end{array}$$

then π ≻ ρ.

2.2. Collective Quantum Search: Complexity

For the corresponding search complexities T_π, T_ρ we have the following lemma.

Lemma 3. The search complexity function T_π(N₁, …, N_n), for a given joining scheme of n searches with dimensions N₁, …, N_n, described by partition π, is a Schur concave function, for which it is valid that for any two weakly majorized partitions π^w≻ρ of n, the corresponding complexities are anti-isotonic, i.e., T_π ≤ T_ρ.

For simplicity’s sake, hereafter and unless otherwise stated we consider that a single search algorithm has only one marked element, i,e., k = 1. Symbolism: $\langle N_k;N_l\rangle \equiv \frac{N_k+\cdots +N_l}{l-k+1}.$ We state the following lemma.

Lemma 4. Let l searches with database Hilbert space dimensions {N₁, …, N_l}, arranged in a Young tableau either as an l -box row, in case of merging, or as an l-box column, in case of concatenation. Denoting the corresponding complexities as$T_{merg}^{(N_1,\dots ,N_l)}=\lfloor \frac{\pi }{4}\sqrt{\langle N_1;N_l\rangle }\rfloor$ and$T_{conc}^{(N_1,\dots ,N_l)}=\lfloor \frac{\pi }{4}\sqrt{N_1}\rfloor +\cdots +\lfloor \frac{\pi }{4}\sqrt{N_l}\rfloor$ respectively, it is valid that$T_{merg}^{(N_1,\dots N_l)}\le T_{conc}^{(N_1,\dots N_l)}$.

Having introduced themain concepts andmathematical tools of collective quantumsearch we proceed to state and show the main result.

Consider the ratio of the extreme values of complexities T_conc/T_merg, “all concatenated” over “all merged”. The sequence ${\left\{N_i\right\}}_{i=1}^n$ of dimensions, can be of two distinct kinds : (i) ${\left\{N_i\right\}}_{i=1}^n$ an unbounded sequence, e.g., N_i’s are consecutive terms of sequence 2ⁱ (a natural choice for database sizes), in this case we show that $T_{conc}/T_{merg}=\mathcal{O}(\sqrt{n})$; if the sequence ${\left\{N_i\right\}}_{i=1}^n$ is bounded (e.g., $N_i=2^{b_i}$,where ${\left\{b_i\right\}}_{i=1}^n$ is bounded), then the ratio $\frac{T_{conc}}{T_{merg}}\in \Theta (n)$, i.e., it is asymptotically linear in n, the number of databases (for “Big Theta” notation c.f. [12]). Next lemma and proposition provides an estimation for the search complexity for arbitrary database dimensions.

Lemma 5. If$T_{conc}^{(c)}={\displaystyle \sum {}_{i=1}^n}\frac{{}^{\pi }}{4}\sqrt{N_i}$and$T_{merg}^{(c)}=\frac{{}^{\pi }}{4}\sqrt{\frac{1}{n}{\displaystyle \sum {}_{i=1}^n}{N}_i}$, are the continuous analogues (continuous functions) for complexities T_conc, T_merg, then, i)$T_{merg}=\lfloor T_{merg}^{(c)}\rfloor$ ii)$\frac{T_{conc}^{(c)}}{T_{merg}^{(c)}}-\frac{n}{T_{merg}^{(c)}}<\frac{T_{conc}}{T_{merg}}<\frac{T_{conc}^{(c)}}{T_{merg}^{(c)}-1}$.

Proposition 1. For arbitrary positive integers (database sizes) N_i, i = 1, 2, …, n it holds that

$$\sqrt{n}{T}_{merg}^{(c)}<T_{conc}^{(c)}\le n{T}_{merg}^{(c)}$$

Moreover, if N_i are:

• consecutive terms of the unbounded sequence${\left\{N_i\right\}}_{i=1}^n$ with N_i = 2ⁱ, then$T_{conc}=\mathcal{O}(\sqrt{n})T_{merg}$.
• terms of a bounded sequence of positive integers with$p=\sup {\left\{N_i\right\}}_{i=1}^n$, $q=\inf {\left\{N_i\right\}}_{i=1}^n$, then :

Remark 1.

• If$N_i=2^{b_i}$, for all i = 1, …, n, and${\left\{b_i\right\}}_{i=1}^n$ is an increasing and bounded above sequence of positive integers, the statement of lemma remains valid.
• Since lim_n→∞ N_n = 2⁶, database sizes N_n are asymptotically equal to a constant number, and this is true since (R, |·|) is a complete metric space. Observe that the curve in Figure 1 is close to line y = x (i.e., the ratio T_conc/T_merg is close to n). In the special case of constant sequence {N_j}, for the continuous versions$T_{conc}^{(c)}$, $T_{merg}^{(c)}$
• of the complexities, we have that$T_{conc}^{(c)}/T_{merg}^{(c)}=n$, for all n.
• Since every sequence in R has a monotone subsequence, it follows that, given a bounded above sequence {N_j}, we can always extract a monotone subsequence$\left\{N_{c_j}\right\}$ necessarily bounded, and therefore convergent. (c.f. Bolzano-Weirstrass theorem, stating that each bounded sequence in R^m has a convergent subsequence). Hence, even if {N_j} is bounded above but not convergent, if using only$\left\{N_{c_j}\right\}$ as database sizes, the ratio T_conc/T_merg will be close to database number.
• A geometric interpretation of inequalities of the proposition, providing bounds for the complexity, is that asymptotically, the ratio$\frac{T_{conc}}{T_{merg}}$ lies in the interior of an angle δ = arctan(λ) − arctan(λ⁻¹) with vertex at point (0, 0) and sides along directions nλ⁻¹ and nλ, symmetric wrt bisector y = x; it lies on the bisector if N_i = N, i.e., all distances are equal, (in this case the search operator is$U_{G;conc}(nN)={\oplus }_{i=1}^n{U}_G(N)=1_n\otimes U_G(N))$.

A special case of minimum complexity is stated in the following lemma.

Lemma 6. The complexity of an l merging is minimum and independent of l if and only if all involved database dimensions are equal.

2.3. Collective Quantum Search: Threshold Cases

Summarizing the study so far by referring to sequences (1ⁿ) ≺ π₂ ≺ … ≺ π_k−1 ≺ (n) and $T_{(1^n)}\ge T_{\pi }{}_{{}_2}\ge \cdots \ge T_{{\pi }_{k-1}}\ge T_{(n)}$, we note that: the first sequence concerns the weak ordering of partitions ranging from total concatenation to total merging of n searches. The second one concerns the associated numerical ordering of these schemes via comparison between their corresponding complexities. We seek to clarify which are the generic threshold cases in the sequences according to some criteria, i.e., the cases in which merging gives no computational advantage in search, due to some circumstantial reasons to be determined. Two such criteria are, the conjugate partition criterion (CPC), and the threshold partition criterion (TPC). In case of CPC the ∗ conjugation for partitions is used to single out as threshold cases the self-conjugate partitions π = π^∗ for which T_π = T_π∗, [13], under some specified database dimensions. In case of TPC the threshold cases are the so called threshold partition π, which hold a balanced number of boxes (searches) in the upper and lower parts of its Young diagram.

2.3.1. Conjugate Partition Criterion

The complexity of any joining scheme is determined both by the partition shaping its Young diagram and by filling of partition’s boxes by the respective Hilbert space dimensions N_i of quantum databases. A simplification is the standard tableau and particularly the physically motivated choice N_i = 2ⁱ. Consider n jointed searches interpolating between full concatenation with partition (1ⁿ) and full merging with partition (n). Consider the conjugation of partition π → π^∗, which produces partition π^∗ by turning rows into column and vice versa and then assign dimensions N_ij to each box (search), i.e., (π_i, j) → N_ij, and seeks values for N_ij, so that the ensuing complexities are equal, i.e., T_π = T_π∗. This equality is achieved by any intermediate joining scheme (1ⁿ) ≺ π ≺ (n), which is self conjugate, i.e., π = π^∗. E.g. in π ⊢ 6, partition π = (3, 2, 1) is self-conjugate and the next choice of dimensions gives equal complexity

The indicated filling with dimensions p, q, r, s fulfils condition, i.e., T_(3,2,1) = T_(3,2,1)∗.

2.3.2. Threshold Partition Criterion

Proceeding from full concatenation to full merging of n searches by moving up one box at a time (merging one more search), creates diagrams that majorize all preceding ones, as explained. Explicitly, let of division of a Y (π) into two disjoint pieces, Y_u(π) with boxes lying on and to the right of the diagonal, and Y_d(π) be the rest piece, i.e., Y(π) = Y_u(π)∪Y_d(π). E.g. for partition π = (6, 5, 3, 3, 2, 2, 1) the diagrams Y (π), Y_u(π) and Y_d(π) are

Let next y_u(π) be a partition whose parts are the lengths of the rows of the shifted shape Y_u(π), and y_d(π) be the partition whose parts are the lengths of the columns of Y_d(π). If n is even and π ⊢ n, then partition π is called graphic partition iff y (π)^w≺y_d(π) and it is called threshold partition π_th iff y_u(π_th) = y_d(π_th) [13]. In the case of threshold partition it follows that T_yu(π) = T_yd(π) and that half of the number of merging responsible for crossing the diagonal have already happened (i.e., $|y_u|=|y_d|=\frac{N}{2}$). This threshold relation landmarks the midway situation before the onset of total merging. For the example above the pairs y_u(π) = (6, 4, 1), y_d(π) = (6, 4, 1), and y_u(π) = (7, 3, 1), y_d(π) = (6, 3, 2) satisfy the TPC.

2.4. Oracle Algebra for Collective Quantum Search

Let database Hilbert spaces $H_{N_1}$, $H_{N_2}$, $H_{N_3}$, where $H_{N_i}=l_2({\mathrm{\Delta }}_{N_i})$ with N₁ = N₂ = N₃ = 4, and let the marked items be the first, the third, and the second elements in $H_{N_1}$, $H_{N_2}$, $H_{N_3}$, respectively. To the partitions (111), (21), (3), of 3, correspond the joining (i) a 3−merging in database $H_{N_1+N_2+N_3}={\oplus }_{i=1}^3{H}_{N_i}$, (ii) a 2-merging in $H_{N_1+N_2}={\oplus }_{i=1}^2{H}_{N_i}$, a single in $H_{N_3}$, and concatenation between them, and finally (iii) concatenation of searches in $H_{N_1}$, $H_{N_2}$, $H_{N_3}$. Using notation $|x_N^{\pi }\rangle$ and ${\pi }_N({\Sigma }_a^{\pi })$, a = 1, 2, 3, 0 we have:

• 3-merging in $H_{N_1+N_2+N_3}$;
  The marked items are |1〉, |7〉, |10〉, so $|x_{12}^{(3)}\rangle =\frac{1}{\sqrt{3}}(|1\rangle +|7\rangle +|10\rangle )$, $|x_{12}^{(3)}{}^{\perp }\rangle =\frac{1}{\sqrt{9}}(|2\rangle +|3\rangle +|4\rangle +|5\rangle +|6\rangle +|8\rangle +|9\rangle +|11\rangle +|12\rangle )$,and the 12-dim representation of oracle Ealgebra generators are

  $$\begin{array}{c}{\pi }_{12}({\Sigma }_1^{(3)})={\pi }_{12}\left(|x_{12}^{(3)}\rangle \langle x_{12}^{(3)\perp }|\right)+H.c.,{\pi }_{12}({\Sigma }_2^{(3)})={\pi }_{12}\left(-i|x_{12}^{(3)}\rangle \langle x_{12}^{(3)\perp }|\right)+H.c.,\\ {\pi }_{12}({\Sigma }_3^{(3)})={\pi }_{12}\left(|x_{12}^{(3)}\rangle \langle x_{12}^{(3)}|\right)-H.c.,{\pi }_{12}({\Sigma }_0^{(3)})={\pi }_{12}\left(|x_{12}^{(3)}\rangle \langle x_{12}^{(3)}|\right)+H.c.\end{array}$$
• 2-merging in $H_{N_1+N_2}$, single search in $H_{N_3}$, and concatenation between them; The marked items are |1〉, |7〉 in $H_{N_1+N_2}$, and |2〉 in $H_{N_3}$, so $|x_8^{(2,1)}\rangle =\frac{1}{\sqrt{2}}(|1\rangle +|7\rangle )$, $|x_8^{(2,1)}{}^{\perp }\rangle =\frac{1}{\sqrt{6}}(|2\rangle +|3\rangle +|4\rangle +|5\rangle +|6\rangle +|8\rangle )$, $|x_4^{(2,1)}\rangle =|2\rangle$, $|x_4^{(2,1)\perp }\rangle =\frac{1}{\sqrt{3}}(|1\rangle +|3\rangle +|4\rangle )$. Since e.g., $|x_{12}^{(2,1)}\rangle =|x_8^{(2,1)}\rangle \oplus |x_4^{(2,1)}\rangle$, the generators decompose

  $${\pi }_{12}({\Sigma }_a^{(2,1)})={\pi }_8({\Sigma }_a^{(2,1)})\oplus {\pi }_4({\Sigma }_a^{(2,1)}).$$
• Single searches in $H_{N_1}$, $H_{N_2}$ and $H_{N_3}$ and concatenation between them;
  The marked items are |1〉, ∈ $H_{N_1}$,|3〉 ∈ $H_{N_2}$, and |2〉 ∈ $H_{N_3}$ and |2〉 ∈. E.g. for $H_{N_1}$, $|x_4^{(1,1,1)}\rangle =|1\rangle$, $|x_4^{(1,1,1)\perp }\rangle =\frac{1}{\sqrt{3}}(|2\rangle +|3\rangle +|4\rangle )$, etc, so for a = 1, 2, 3, 0, the following decomposition is obtained,

  $${\pi }_{12}({\Sigma }_a^{(1,1,1)})=\underset{H_{1,2,3}}{\oplus }{\pi }_4({\Sigma }_a^{(1,1,1)}).$$

Having the oracle algebra matrix generators we compute the unitary search operators for the three corresponding partitions,

$$\begin{array}{c}{U}_G^{(3)}=\exp \left(i{\theta }_{12}{\pi }_{12}({\Sigma }_2^{(3)})\right),\\ U_G^{(2,1)}=\exp \left(i{\theta }_8{\pi }_8({\Sigma }_2^{(2,1)})\right)\oplus \exp \left(i{\theta }_4{\pi }_4({\Sigma }_2^{(2,1)})\right),\\ U_G^{(1,1,1)}=\underset{H_{1,2,3}}{\oplus }\exp \left(i{\theta }_4{\pi }_4({\Sigma }_2^{(1,1,1)})\right),\end{array}$$

where ${\theta }_N=\arcsin (-2\sqrt{k(N-k)}/N)$ with k = 1. By means of a similar search unitary, the collective quantum search complexity measures can be computed.

2.4.1. Generalized Azimuthal Symmetry

Let the partition τ = (N₁, N₂, ⋯, N_l) of N of length l = l(τ), and let the one parameter subgroup $U_a(1)=e^{i{\varphi }_a{\pi }_a({\Sigma }_3)}$, generated by π_a(Σ₃) ∈ End(H_a). Let the group G = U(N) and the subgroup $K={\oplus }_{a=N_1}^{N_l}{U}_a(1)$. Consider a concatenation of l searches for a given partition τ ⊢ N, with search operator $U_G^{(\tau )}:={\oplus }_{a=N_1}^{N_l}{U}_G^{(a)}$ and search step implemented by the transformation $\rho \to U_G^{(\tau )}\rho U_G^{(\tau )†}$. Let further the unitary operator $V_3(\varphi )={\oplus }_{a=N_1}^{N_l}{e}^{i{\varphi }_a{\pi }_a({\Sigma }_3)}\in K$, $\varphi ={({\varphi }_a)}_{a=N_1}^{N_l}\in {[0,2\pi )}^l$ then the transformation

$$\rho \to {\rho }^{\prime }=V_3(\varphi )U_G^{(\tau )}\rho U_G^{(\tau )†}{V}_3{(\varphi )}^{†},$$

preserves the projection of density matrix ρ along the collective marked vector $|x\rangle \langle x|:={\oplus }_{a=N_1}^{N_l}|x_a\rangle \langle x_a|$, or equivalently preserves the ${\oplus }_{a=N_1}^{N_l}{\pi }_a({\Sigma }_3)$ component of the collective density matrix [9]. This implies the search complexity remains invariant under the action of V₃.

This equality of complexities is expressed in terms of the minimization of the projection of time-evolved collective density matrix on the collective marked item, i.e.,

$$\begin{array}{l}1=\underset{\alpha }{\min }\langle x|U_G^{(\tau )\alpha }{\rho }_{ss}{U}_G^{(\tau )†\alpha }|x\rangle \\ =\underset{\alpha }{\min }\langle x|\left(U_G^{(\tau ){\alpha }_1}{V}_3(\varphi )U_G^{(\tau ){\alpha }_2}\dots V_3(\varphi )U_G^{(\tau ){\alpha }_r}\right){\rho }_{ss}\\ \times {\left(U_G^{(\tau ){\alpha }_1}{V}_3(\varphi )U_G^{(\tau ){\alpha }_2}\dots V_3(\varphi )U_G^{(\tau ){\alpha }_r}\right)}^{†}|x\rangle ,\end{array}$$

where α = α₁ + ⋯ + α_r, which is a generalization of an analogues formula for l = 1, describing the azimuthal symmetry of single search algorithm [9]. To any partition τ ⊢ N there corresponds a symmetry group M_τ = G/K for the collective quantum search.

3. Proofs, Examples, and Discussion

In this second part of the paper we have put together a number of items:

• “Collective quantum search: Merging and Concatenation”, with proofs of lemmas and numerical examples; in the following section.
• “Collective quantum search: Joining Schemes and Young diagrams” we have placed the proof of the main proposition and of the auxiliary lemmas, together with numerical examples that demonstrate the workings of collective quantum search; in the final section.
• “Oracle algebra and representations” we introduce the mathematical details of the oracle algebra and some examples from its matrix representations.

3.1. Collective Quantum Search

3.1.1. Merging and Concatenation

Proof. (Lemma 1) The target vector decomposes in $|x_{conc}\rangle =|x_1\rangle \oplus {|\varnothing \rangle }_{N_2}+{|\varnothing \rangle }_{N_1}\oplus |x_2\rangle \in H_1\oplus H_2$. Let the initial vectors |x_conc〉, |s_conc〉 and the corresponding projection operators |x_conc〉〈x_conc|, |s_conc〉 〈s_conc|. Then

$$\begin{array}{c}|s_{conc}\rangle =|s_1\rangle \oplus {|\varnothing \rangle }_{N_2}+{|\varnothing \rangle }_{N_1}\oplus |s_2\rangle =\left(\begin{array}{l}|s_1\rangle \\ |s_2\rangle \end{array}\right)\\ |s_{conc}\rangle \langle s_{conc}|=\left(\begin{array}{cc}|s_1\rangle \langle s_1|& \\ & |s_2\rangle \langle s_2|\end{array}\right)=|s_1\rangle \langle s_1|\oplus |s_2\rangle \langle s_2|\\ J_{s_{conc}}=1_{N_1+N_2}-2|s_{conc}\rangle \langle s_{conc}|=\left(\begin{array}{cc}{J}_{s_1}& \\ & J_{s_2}\end{array}\right)=J_{s_1}\oplus J_{s_2}.\end{array}$$

Similarly

$$|x_{conc}\rangle \langle x_{conc}|=|x_1\rangle \langle x_1|\otimes |x_2\rangle \langle x_2|$$

and

$$J_{x_{conc}}=1_{N_1+N_2}-2|x_{conc}\rangle \langle x_{conc}|=\left(\begin{array}{cc}{J}_{x_1}& \\ & J_{x_2}\end{array}\right)=J_{x_1}\oplus J_{x_2}$$

So the search operator by means of the previous decomposition splits into a direct sum, i.e.

$$U_{conc}(f_{conc})=-(J_{s_1}\oplus J_{s_2})(J_{x_1}\oplus J_{x_2})=U_1\oplus U_2.$$

Similarly, for an l-concatenation it is valid that $U_{conc}={\oplus }_{j=1}^l{U}_j.$ □

Symmetries of U_conc and U_merg. For concatenation, the search operator is determined up to a V₁ ⊕ V₂ unitary, i.e.

$$U_{conc}=-(V(N_1)\oplus V(N_2))(J_{s_1}\oplus J_{s_2}){(V(N_1)\oplus V(N_2))}^{†}(J_{x_1}\oplus J_{x_2}).$$

Note that V(N₁) ⊕ V(N₂) is the diagonal subgroup of group V(N₁ + N₂). By induction on l, a l-concatenation algorithm, has ${\oplus }_{i=1}^{l}V$ (Nl)-symmetry, which is the diagonal subgroup of U(N_merg).

Grover [2] showed that for a single search algorithm with one target vector, the unitary search operator U_G = −J_sJ_x can be replaced by a more general operator which is also unitary and it can be in one of the two following equivalent forms

$$\begin{array}{l}{U}_G=-J_s{V}^{†}{J}_{x}V\\ U_G=-V^{†}{J}_{s}V{J}_x,\end{array}$$

with V ∈ U(N). These symmetries survive in the case of joined searches as follows. For merged algorithms the unitary symmetry is U(N_merg), i.e.,

$$U_{merg}=-J_{s_{merg}}V{(N_{merg})}^{†}{J}_{x_{merg}}V(N_{merg}).$$

3.1.2. Joining Schemes and Young diagrams

Partitions are specified by lower case Greek letters. If λ is a partition of a non negative integer k, we write λ ⊢ k and call k the weight of the partition, and λ = (λ₁, …, λ_k) is a sequence of non negative integers λ_i for i = 1, 2, …, k, such that λ₁ ≥ λ₂ ≥ … ≥ λ ≥ 0 with ${\displaystyle {\sum }_{i=1}^k{\lambda }_i=k}$. The non zero λ_i are called the parts of λ and their number l(λ) is the length of λ. In specifying λ, the trailing zeros, that is those λ_i = 0, are often omitted. By way of illustration, if k = 10, we regard (4, 2, 2, 1, 1, 0, 0, 0, 0, 0) and (4, 2, 2, 1, 1) as the same partition λ, for which it holds that |λ| = 10 and l(λ) = 5. Each partition λ of weight |λ| = k, and length l(λ) defines a (Ferrers) Young diagram Y (λ) consisting of |λ| boxes arranged in l(λ) left-adjusted rows of lengths from top to bottom λ₁, …, λ_l(λ), while zeros in λ do not appear in Y (λ) (in the English convention). The notation follows in large part that of [11].

The notion of number partition is associated to the joining of quantum searches as follows: given a number of search algorithms m with database dimensions N₁, N₂, …, N_m, we can join them either by merging or by concatenating in various ways therefore number m is partitioned as λ ⊢ m, where every part λ_i of λ denotes the number of algorithms joined in a similar way, i.e., either by merging or by concatenation. Thus every possible joining scheme corresponds to a Ferrers diagram and vice versa, i.e., π → T_π, ρ → T_ρ, we find by way of example that T_π ≤ T_ρ.

The latter implies that the sequence of majorized partitions is mapped to the multi-set of complexities, i.e., the example of partitions of 6 worked out below yields

$$\begin{array}{l}\pi ⊢6:6\succ 51\succ 42\succ \frac{3^2}{{41}^2}\succ 321\succ \frac{2^3}{{31}^3}\succ 2^2{1}^2\succ {21}^4\succ 1^6\\ T_{\pi }:3<4<6\le \frac{6}{7}<9\le \frac{9}{10}<12<14<17\end{array}$$

The multi-set of complexities {3, 4, 6, 6, 7, 9, 9, 10, 12, 14, 17} form a piecewise ordered set where the numerical ordering is anti-isotonic wrt the majorization order i.e., in general π ≻ ρ corresponds to T_π ≤ T_ρ. See Figure 2 below.

3.1.3. Complexity

Proof. (Lemma 3) Let an integer partition π = (π₁, …, π_j, …, π_l(π)) ⊢ n, and the multi-variable functions ${\varphi }_{\mu }(x):{\mathbf{R}}_{+}^n\to \mathbf{R}$, µ = 1, 2, …, l(π), where

$${\varphi }_{\mu }(x)=\lfloor \frac{\pi }{4}\frac{1}{\sqrt{{\pi }_{\mu }}}\sqrt{{\displaystyle \sum _{j=1}^{{\pi }_{\mu }}{x}_j}}\rfloor ,$$

with x = (x₁, …, x_n), and π_i the part i of partition π, which enumerates the number of databases involved in a merging scheme. Each of these functions ϕ_µ is a multi-variable Schur-concave function: indeed since $(x,y)\to \sqrt{x+y}$ is Schur-concave function and also x → ⌊ϕ(x)⌋ is a Schur-concave function if ϕ(x) is one (Chapter 3 in [10]), we conclude that ϕ_µ as well as their linear combination is a Schur-concave function.

The linear combination of ϕ_µ’s functions is also a Schur-concave function, and this in particular is valid for the search complexity T_π associated with a partition π, i.e., π → T_π, or explicitly

$$T_{\pi }(x)={\displaystyle \sum _{\mu =1}^{l_{(\pi )}}{\varphi }_{\mu }(x)}.$$

is Schur-concave.

So, if π, ρ ⊢ t s.t. π ≻ ρ, then T_π(N) ≤ T_ρ(N), where N = (N₁, …, N_t) □

Diagrammatically

$$\begin{array}{c}\pi \succ \rho \\ \downarrow \downarrow \\ T_{\pi }\le T_{\rho }\end{array}$$

Example 1. For n = 16 and the partition π = (6, 4, 4, 2), there are four functions of variables x = (x₁, …, x₁₆),

$$\begin{array}{l}{\varphi }_1(x_1,\dots ,x_{16})=\lfloor \frac{\pi }{4\sqrt{6}}\sqrt{x_1+x_2+x_3+x_4+x_5+x_6}\rfloor ,\\ {\varphi }_2(x_1,\dots ,x_{16})=\lfloor \frac{\pi }{4\sqrt{4}}\sqrt{x_7+x_8+x_9+x_{10}}\rfloor ,\\ {\varphi }_3(x_1,\dots ,x_{16})=\lfloor \frac{\pi }{4\sqrt{4}}\sqrt{x_{11}+x_{12}+x_{13}+x_{14}}\rfloor ,\\ {\varphi }_4(x_1,\dots ,x_{16})=\lfloor \frac{\pi }{4\sqrt{2}}\sqrt{x_{15}+x_{16}}\rfloor .\end{array}$$

each one of them and their linear combination is a Schur-concave function.

Proof. (Lemma 4) Applying Jensen inequality [14] for the convex function $x\to \sqrt{x}$ yields

$$\frac{\pi }{4}\sqrt{\frac{N_1+\cdots +N_l}{l}}\le \frac{1}{l}\left(\frac{\pi }{4}\sqrt{N_1}+\cdots +\frac{\pi }{4}\sqrt{N_l}\right)$$

which implies

$$\lfloor \frac{\pi }{4}\sqrt{\frac{N_1+\cdots +N_l}{l}}\rfloor \le \lfloor \frac{\pi }{4}\sqrt{N_1}\rfloor +\cdots +\lfloor \frac{\pi }{4}\sqrt{N_l}\rfloor .$$

In the relation above the equality is reached iff $0\le {\displaystyle \sum _{i=1}^l\left\{\frac{\pi }{4}\sqrt{N_i}\right\}<\frac{1}{2}}$, where {x} denotes the fractional part of the real number x. Notice that the special case where all the numbers appearing in the integral part are all integers, never occurs due to the involvement of π. □

Proof. (Lemma 6) Let N₁, …, N_l be the sizes of databases, then the complexity equals

$$T_{merg}^{(N_1,\dots ,N_l)}=\lfloor \frac{\pi }{4}\sqrt{\frac{N_1+\cdots +N_l}{l}}\rfloor .$$

Due to AM-GM inequality, we take that

$$T_{merg}^{(N_1,\dots ,N_l)}\ge \lfloor \frac{\pi }{4}\sqrt{\sqrt[l]{N_1\dots N_l}}\rfloor =\lfloor \frac{\pi }{4}\sqrt[2l]{N_1\dots N_l}\rfloor$$

The equality holds iff N₁ = … = N_l ≡ N, and therefore the minimum is

$$T_{merg,\min }^{(N,\dots ,N)}=\lfloor \frac{\pi }{4}\sqrt{N}\rfloor .$$

Remark 2.

• For comparison reasons we find that the complexity of l-concatenation algorithm is

  $$T_{conc}^{(N_1,\dots ,N_l)}={\displaystyle \sum _{j=1}^l\lfloor \frac{\pi }{4}\sqrt{N_j}\rfloor }$$

  since$U_{conc}=\oplus U_j(f_j)$. Moreover, if N₁ = … = N_l ≡ N, then

  $$T_{conc}^{(N,\dots ,N)}=l\lfloor \frac{\pi }{4}\sqrt{N_j}\rfloor =l{T}_{merg,\min }^{(N,\dots ,N)},$$
• The total tableau complexity for a joining scheme described by its corresponding Young diagram λ is computed as follows: let a Young diagram λ = (i₁, i₂, …, i_r) then the total search algorithm consists of r groups of concatenated sub-algorithms where each group contains i₁, i₂, …, i_r merged algorithms. Via previous lemma and remark, the tableau complexity equals$T_{\lambda }^{(N_1,\dots ,N_k)}=\lfloor \frac{\pi }{4}\sqrt{\frac{N_1+\cdots +N_{i_1}}{i_1}}\rfloor +\lfloor \frac{\pi }{4}\sqrt{\frac{N_{i_1+1}+\cdots +N_{i_1+i_2}}{i_2}}\rfloor +\cdots +\lfloor \frac{\pi }{4}\sqrt{\frac{N_{i_1+\dots +i_{r-1}+1}+\cdots +N_k}{i_r}}\rfloor$, where i₀ = 0 and i₁ +⋯+ i_r = k. If all databases are of equal size N, then for any diagram λ the tableau complexity equals$T_{\lambda }^{(N,\dots ,N)}=r\lfloor \frac{\pi }{4}\sqrt{N}\rfloor$.

3.1.4. Main Proposition

Next, we consider the ratio of the extreme values of complexities T_conc/T_merg (“all concatenated” over “all merged”), and regarding the sequence of the dimensions ${\left\{N_i\right\}}_{i=1}^n$, two cases are arising for its asymptotic behaviour. Moreover, for arbitrary positive integers (database sizes) N_i, i = 1, 2, …, n we prove that for the continuous analogues (continuous functions) for the complexities T_conc, T_merg, it holds that $\sqrt{n}<\frac{T_{conc}^{(c)}}{T_{merg}^{(c)}}\le n$.

In more details, if ${\left\{N_i\right\}}_{i=1}^n$ is an unbounded sequence, specifically N_i’s are consecutive terms of the geometric sequence 2ⁱ (which is the most natural and reasonable choice for database sizes), we conclude that $T_{conc}/T_{merg}=\mathcal{O}(\sqrt{n})$. Otherwise, namely if the sequence ${\left\{N_i\right\}}_{i=1}^n$ is bounded (e.g., $N_i=2^{b_i}$, where ${\left\{b_i\right\}}_{i=1}^n$ is bounded), it results that the ratio T_conc/T_merg is asymptotically linear with respect to the number n of the databases. This fact leads to an interesting observation: although the qualitative difference between a bounded and an unbounded sequence of database sizes is essential (notice that N_i = 2ⁱ increases exponentially fast), however, the quantitative change that entails to the ratio of complexities, is only quadratic (quadratic reduction) with respect to the database population.

Proof. (Lemma 5) Straightforward calculations. □

Proposition 2. For arbitrary positive integers (database sizes) N_i, i = 1, 2, …, n it holds that

$$\sqrt{n}{T}_{merg}^{(c)}<T_{conc}^{(c)}\le n{T}_{merg}^{(c)}$$

Moreover, if N_i are:

• consecutive terms of the unbounded sequence${\left\{N_i\right\}}_{i=1}^n$ with N_i = 2ⁱ, then$T_{conc}=\mathcal{O}(\sqrt{n})T_{merg}$
• terms of a bounded sequence of positive integers with$p=\sup {\left\{N_i\right\}}_{i=1}^n$, $q=\inf {\left\{N_i\right\}}_{i=1}^n$, $then:\frac{T_{conc}}{T_{merg}}\in \Theta (n)$, i.e., nλ⁻¹T_merg ≤ T_conc ≤ nλT_merg, with$\lambda =\lfloor \frac{\pi }{4}\sqrt{p}\rfloor {\lfloor \frac{\pi }{4}\sqrt{q}\rfloor }^{-1}$.

Proof. Applying the Cauchy-Schwarz inequality we obtain that: $T_{conc}^{(c)2}\le n^2{T}_{merg}^{(c)2}$. Moreover $T_{conc}^{(c)}={\displaystyle {\sum }_{i=1}^n\frac{\pi }{4}\sqrt{N_i}>}\frac{\pi }{4}\sqrt{{\displaystyle {\sum }_{i=1}^n{N}_i}}=T_{merg}^{(c)}\sqrt{n}$, so $\sqrt{n}<\frac{T_{conc}^{(c)}}{T_{conc}^{(c)}}$.

• Carrying out trivial calculations, we take :

  $$\frac{1}{n}{\left(\frac{T_{conc}^{(c)}}{T_{merg}^{(c)}}\right)}^2=1+\frac{2{\displaystyle {\sum }_{i\ne j}\sqrt{N_i{N}_j}}}{T_{merg}^{(c)2}}\frac{{\pi }^2}{16n}.$$

  In this first case, we have that N_i = 2ⁱ, so

  $$2{\displaystyle \sum _{i\ne j}\sqrt{N_i{N}_j}=2}{\left(\sqrt{2n}-1\right)}^2{\left(\sqrt{2}+1\right)}^2-2(2^n-1)$$

  and $T_{merg}^{(c)2}=\frac{{\pi }^2}{16n}2(2^n-1)$. Therefore:

  $$\frac{1}{n}{\left(\frac{T_{conc}^{(c)}}{T_{merg}^{(c)}}\right)}^2=\frac{{\left(1-\frac{1}{\sqrt{2^n}}\right)}^2{\left(\sqrt{2}+1\right)}^2}{1-\frac{1}{2^n}}.$$

  The RHS of the above asymptotically equals to ${\left(\sqrt{2}+1\right)}^2$, so $\frac{T_{conc}^{(c)}}{T_{merg}^{(c)}}\approx \left(\sqrt{2}+1\right)\sqrt{n}$, i.e.$\frac{T_{conc}^{(c)}}{T_{merg}^{(c)}}=\mathcal{O}(\sqrt{n})$ and $\frac{T_{conc}}{T_{merg}}=\mathcal{O}(\sqrt{n})$ because due to previous Lemma and

  $$\underset{n\to \infty }{\lim }\frac{n}{T_{merg}^{(c)}}=0,T_{merg}^{(c)}\gg 1$$

  asymptotically, it holds that

  $$\frac{T_{conc}}{T_{merg}}\approx \frac{T_{conc}^{(c)}}{T_{merg}^{(c)}}.$$
• Since $p=\sup {\left\{N_i\right\}}_{i=1}^n$, $q=\inf {\left\{N_i\right\}}_{i=1}^n$, then for all i = 1, 2, …, n, is valid that 2 ≤ q ≤ N_i ≤ p, so

  $$n\lfloor \frac{\pi }{4}\sqrt{q}\rfloor \le T_{conc}={\displaystyle \sum _{i=1}^n\lfloor \frac{\pi }{4}\sqrt{N_i}\rfloor \le }n\lfloor \frac{\pi }{4}\sqrt{p}\rfloor .$$

  Moreover $\lfloor \frac{\pi }{4}\sqrt{q}\rfloor \le T_{merg}\le \lfloor \frac{\pi }{4}\sqrt{p}\rfloor$. Therefore $n{\lambda }^{-1}\le \frac{T_{conc}}{T_{merg}}\le n\lambda$ and $\frac{T_{conc}}{T_{merg}}\in \Theta (n)$. □

3.1.5. Geometry of Complexity Reduction

All concave functions fulfil a very intuitive geometric condition with their graph, namely that the center of mass of a set of points lying on the graph is lying not above the graph itself. Quantifying this geometric property leads to the Jensen inequality [14], which in fact is the reason for achieving complexity reduction in various forms of joining schemes. This is demonstrated below by means of a numerical example.

Example 2. Numerical example (see Figure 3). Let the Young diagram of shape (5, 4, 1) and let the following Young tableau (strictly increasing row and column-wise, no repetitions)

where N_i’s are database sizes : N₁ = 2³, N₂ = 2⁴, N₃ = 2⁵, N₄ = 2⁶, N₅ = 2⁷, N₆ = 2⁸, N₇ = 2⁹, N₈ =2¹⁰, N₉ = 2¹¹, N₁₀ = 2¹²

Row 1

Referring to the graph of the complexity function$y=f(x)=\sqrt{x}$ we mark the 5 points$n^1=\left\{\left(2^3,\sqrt{2^3}\right),\left(2^4,\sqrt{2^4}\right),\left(2^6,\sqrt{2^6}\right),\left(2^9,\sqrt{2^9}\right),\left(2^{10},\sqrt{2^{10}}\right)\right\}$ and the center of mass vector c¹, with coordinates$\left(\frac{2^3+2^4+2^6+2^9+2^{10}}{5},\frac{\sqrt{2^3}+\sqrt{2^4}+\sqrt{2^6}+\sqrt{2^9}+\sqrt{2^{10}}}{5}\right)=(324.8,13.891)$ and its crossing point with the graph of$f:q^1=\left(324.8,\sqrt{324.8}\right)=(324.8,18.0222)$.

Row 2

In the graph of complexity function$f(x)=\sqrt{x}$ mark the 4 points$v^2=\left\{\left(2^5,\sqrt{2^5}\right),\left(2^7,\sqrt{2^7}\right),\left(2^8,\sqrt{2^8}\right),\left(2^{11},\sqrt{2^{11}}\right)\right\}$ the center of mass vector c² = (616.0, 19.556) and its crossing point with the graph$q^2=(616.0,\sqrt{616.0,})=(616.0,24.8193)$.

Row 3

In the graph of complexity function$f(x)=\sqrt{x}$ mark the 1 point v³ = c³ = q³ = (2¹², 2⁶).

Equal Complexity Tableaux and Shapes

Motivated by the geometric explanation of the complexity measure for various schemes of joining quantum search algorithms as has been studied in previous section, we proceed to address the problem of determining shapes and tableaux describing ways of joining searches. We study joining of database spaces of equal dimension N. The complexity is differentiated from one scheme to the other due to the difference of the associated Young diagram shapes, so we call it shape complexity.

$$\begin{array}{cccccc}\begin{array}{c}2\\ 11\end{array}& \begin{array}{c}3\\ 21\\ 111\end{array}& \begin{array}{c}4\\ 31\\ 22\\ 211\\ 1111\end{array}& \begin{array}{c}5\\ 41\\ 32\\ 311\\ 221\\ 2111\\ 11111\end{array}& \begin{array}{c}6\\ 51\\ 42\\ 411\\ 33\\ 321\\ 3111\\ 222\\ 2211\\ 21111\\ 111111\end{array}& \begin{array}{c}7\\ 61\\ 52\\ 43\\ 511\\ 421\\ 331\\ 4111\\ 322\\ 3211\\ 2221\\ 31111\\ 22111\\ 211111\\ 1111111\end{array}\end{array}$$

Joined quantum searches, all of which have equal Hilbert space dimension N and share the same shape complexity, are displayed as a pattern of bold typed integer partitions from 3 to 7 within the Young lattice. The pattern of equal complexities is independent from N.

$$c_y^1+c_y^2+c_y^3\le q_y^1+q_y^2+q_y^3$$

Figure 4 displays the contour of equal complexity families of joined quantum algorithms having unequal database sizes. A constant complexity difference (vertical segments) is chosen between tableau complexity (lower broken line) describing concatenation of groups of merged quantum searches and its upper bound (upper full line) describing the same group jointed by concatenation only.

Definition 2 Let the set Δ = {1, 2, …N}, a subset I ⊂ Δ, and the oracle function f, be the characteristic function of I with k elements, defined as f(i) = 1, for i ∈ I, and f(i) = 0, for i ∉ I. We define as the matrix oracle algebra A_f with respect to the characteristic function f of I ⊂ Δ, the set A_f = {A : A = αΣ₀(f) + βΣ₁(f) + γΣ₂(f) + δΣ₃(f)} where α, β, γ, δ ∈ R are arbitrary real [9,15].

Let also (a) the Hilbert space l₂(D), the vector

$$|x\rangle =\frac{1}{\sqrt{k}}{\displaystyle \sum _{i=1}^{N}f(i)}|i\rangle ,$$

and its orthogonal vector

$$|x^{\perp }\rangle =\frac{1}{\sqrt{N-k}}{\displaystyle \sum _{i=1}^N(1-f(i))}|i\rangle ,$$

with $k={\displaystyle {\sum }_{i=1}^{N}f(i)}$.

(b) the Hilbert space $H_N=span{\left\{|i\rangle \right\}}_{i=1}^N$, the matrix ${\left({\widehat{1}}_{st}\right)}_{ij}=1$, 1 ≤ i ≤ s, 1 ≤ j ≤ t, and the N dimensional matrix representation π_N : A_f → Lin(H_N).

Next, we introduce the following Σ₀, Σ₁, Σ₂, Σ₃, as the generators of A_f :

$$\begin{array}{l}{\displaystyle {\sum }_1=|x\rangle \langle x^{\perp }|+|x^{\perp }\rangle \langle x|},\\ {\displaystyle {\sum }_2=-i||x\rangle \langle x^{\perp }|+i||x^{\perp }\rangle \langle x|},\\ {\displaystyle {\sum }_3=|x\rangle \langle x|-|x^{\perp }\rangle \langle x^{\perp }|},\\ {\displaystyle {\sum }_0=|x\rangle \langle x|-|x^{\perp }\rangle \langle x^{\perp }|}.\end{array}$$

For the oracle function f(i) = 1, 1 ≤ i ≤ k < N, and zero otherwise, the representation above reads

$$\begin{array}{r}{\pi }_N({\sum }_0)=\left(\begin{array}{cc}\frac{1}{k}{\widehat{1}}_{k\times k}& O_{k\times (N-k)}\\ O_{(N-k)\times k}& \frac{1}{N-k}{\widehat{1}}_{(N-k)\times (N-k)}\end{array}\right),\\ {\pi }_N({\sum }_1)=\left(\begin{array}{cc}{O}_{k\times k}& \frac{1}{\sqrt{k(N-k)}}{\widehat{1}}_{k\times (N-k)}\\ \frac{1}{\sqrt{k(N-k)}}{\widehat{1}}_{(N-k)\times k}& O_{(N-k)\times (N-k)}\end{array}\right),\\ {\pi }_N({\sum }_3)=\left(\begin{array}{cc}\frac{1}{k}{\widehat{1}}_{k\times k}& O_{k\times (N-k)}\\ O_{(N-k)\times k}& -\frac{1}{N-k}{\widehat{1}}_{(N-k)\times (N-k)}\end{array}\right),\end{array}$$

and therefore, for an arbitrary element A ∈ A_f, it holds that

$$\begin{array}{c}{\pi }_N({\sum }_2)=\left(\begin{array}{cc}{O}_{k\times k}& -i\frac{1}{\sqrt{k(N-k)}}{\widehat{1}}_{k\times (N-k)}\\ i\frac{1}{\sqrt{k(N-k)}}{\widehat{1}}_{(N-k)\times k}& O_{(N-k)\times (N-k)}\end{array}\right),\\ {\pi }_N(\alpha {\sum }_0+\beta {\sum }_1+\gamma {\sum }_2+\delta {\sum }_3)=\left(\begin{array}{cc}\frac{\alpha +\delta }{k}{\widehat{1}}_{k\times k}& \frac{\beta +i\gamma }{\sqrt{k(N-k)}}{\widehat{1}}_{k\times (N-k)}\\ \frac{\beta +i\gamma }{\sqrt{k(N-k)}}{\widehat{1}}_{(N-k)\times k}& \frac{\alpha +\delta }{N-k}{\widehat{1}}_{(N-k)\times (N-k)}\end{array}\right).\end{array}$$

4.1. Examples

Show cases: Here we show explicitly the vectors and matrices involved in the possible scenarios of joining via merging and/or concatenation for the specific example of three 4-dimensional quantum searches. Let databases ${\mathrm{\Delta }}_{N_1}$, ${\mathrm{\Delta }}_{N_2}$, ${\mathrm{\Delta }}_{N_3}$, with N₁ = N₂ = N₃ = 4, and let the market items be the first, the third, and the second elements in ${\mathrm{\Delta }}_{N_1}$, ${\mathrm{\Delta }}_{N_2}$, ${\mathrm{\Delta }}_{N_3}$ respectively, i.e., |1〉, |7〉, |10〉 in ${\mathrm{\Delta }}_{N_1+N_2+N_3}$. The three partitions of 3 are 1 + 1 + 1 = 2 + 1 = 3, we have three possible joining, i.e., (i) a 3−merging in database ${\mathrm{\Delta }}_{N_1+N_2+N_3}$, (ii) a 2-merging in ${\mathrm{\Delta }}_{N_1+N_2}$, a single in ${\mathrm{\Delta }}_{N_3}$, and a concatenation, and finally (iii) three single searches in ${\mathrm{\Delta }}_{N_1}$, ${\mathrm{\Delta }}_{N_2}$, ${\mathrm{\Delta }}_{N_3}$. We use the symbol • to denote non zero matrix elements, and · for zeros.

4.1.1. 3-Merging ${\mathrm{\Delta }}_{N_1+N_2+N_3}$

The marked items are |1〉, |7〉, |10〉, so $|x_{12}^{(3)}\rangle =\frac{1}{\sqrt{3}}(|1\rangle +|7\rangle +|10\rangle )$, $|x_{12}^{(3)\perp }\rangle =\frac{1}{\sqrt{9}}(|2\rangle +|3\rangle +|4\rangle +|5\rangle +|6\rangle +|8\rangle +|9\rangle +|11\rangle +|12\rangle )$, Therefore,

$$\begin{array}{l}|x_{12}^{(x)}\rangle ={\left(\frac{1}{\sqrt{3}},0,0,0,0,0,\frac{1}{\sqrt{3}},0,0,\frac{1}{\sqrt{3}},0,0\right)}^T,\\ |x_{12}^{(x)\perp }\rangle ={\left(0,\frac{1}{\sqrt{9}},\frac{1}{\sqrt{9}},\frac{1}{\sqrt{9}},\frac{1}{\sqrt{9}},\frac{1}{\sqrt{9}},0,\frac{1}{\sqrt{9}},\frac{1}{\sqrt{9}},0,\frac{1}{\sqrt{9}},\frac{1}{\sqrt{9}}\right)}^T,\\ {\pi }_{12}\left(|x_{12}^{(3)\perp }\rangle \langle x_{12}^{(3)}|\right)=\left(\begin{array}{llllllllllll}\cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \end{array}\right),\\ {\pi }_{12}\left(|x_{12}^{(3)}\rangle \langle x_{12}^{(3)}|\right)=\left(\begin{array}{llllllllllll}•\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill & \cdot \hfill & \hfill & \hfill \end{array}\right),\\ {\pi }_{12}\left(|x_{12}^{(3)\perp }\rangle \langle x_{12}^{(3)\perp }|\right)=\left(\begin{array}{llllllllllll}\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \hfill & \cdot \hfill & \cdot \hfill & \hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill \\ \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \hfill & \cdot \hfill & \cdot \hfill & \hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill \\ \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \hfill & \cdot \hfill & \cdot \hfill & \hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill & •\hfill \end{array}\right)\end{array}$$

Therefore, the generators of A_f are:

$$\begin{array}{l}{\pi }_{12}\left({\sum }_1^{(3)}\right)={\pi }_{12}\left(|x_{12}^{(3)}\rangle \langle x_{12}^{(3)\perp }|\right)+H.c.,\\ {\pi }_{12}\left({\sum }_2^{(3)}\right)={\pi }_{12}\left(-i|x_{12}^{(3)}\rangle \langle x_{12}^{(3)\perp }|\right)+H.c.,\\ {\pi }_{12}\left({\sum }_3^{(3)}\right)={\pi }_{12}\left(|x_{12}^{(3)}\rangle \langle x_{12}^{(3)}|\right)-{\pi }_{12}\left(|x_{12}^{(3)\perp }\rangle \langle x_{12}^{(3)\perp }|\right),\\ {\pi }_{12}\left({\sum }_0^{(3)}\right)={\pi }_{12}\left(|x_{12}^{(3)}\rangle \langle x_{12}^{(3)}|\right)+{\pi }_{12}\left(|x_{12}^{(3)\perp }\rangle \langle x_{12}^{(3)\perp }|\right).\end{array}$$

4.1.2. 2-Merging ${\mathrm{\Delta }}_{N_1+N_2}$, single ${\mathrm{\Delta }}_{N_3}$, and Concatenation

The marked items are |1〉, |7〉 in ${\mathrm{\Delta }}_{N_1+N_2}$, and |2〉 in ${\mathrm{\Delta }}_{N_3}$, so

$$\begin{array}{l}|x_8^{(2,1)}\rangle =\frac{1}{\sqrt{2}}\left(|1\rangle +|7\rangle \right)={\left(\frac{1}{\sqrt{2}},0,0,0,0,0,\frac{1}{\sqrt{2}},0\right)}^T,\\ |x_8^{(2,1)\perp }\rangle =\frac{1}{\sqrt{6}}\left(|2\rangle +|3\rangle +|4\rangle +|5\rangle +|6\rangle +|8\rangle \right)={\left(0,\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}},0,\frac{1}{\sqrt{6}}\right)}^T,\\ |x_4^{(2,1)}\rangle =|2\rangle ={\left(0,1,0,0\right)}^T,|x_4^{(2,1)\perp }\rangle =\frac{1}{\sqrt{3}}\left(|1\rangle +|3\rangle +|4\rangle \right)={\left(\frac{1}{\sqrt{3}},0,\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}}\right)}^T,\end{array}$$

and

$$|x_{12}^{(2,1)}\rangle ={(\frac{1}{\sqrt{2}},0,0,0,0,0,\frac{1}{\sqrt{2}},0,0,1,0,0)}^T,$$

$$|x_{12}^{(2,1)\perp }\rangle ={(0,\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}},0,\frac{1}{\sqrt{6}},\frac{1}{\sqrt{3}},0,\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}})}^T,$$

$$\begin{array}{l}{\pi }_8\left(|x_8^{(2,1)\perp }\rangle \langle x_8^{(2,1)}|\right)=\left(\begin{array}{llllllll}\cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill \end{array}\right),\\ {\pi }_8\left(|x_8^{(2,1)}\rangle \langle x_8^{(2,1)}|\right)=\left(\begin{array}{llllllll}•\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill \\ •\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & •\hfill & \cdot \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \cdot \hfill & \hfill \end{array}\right)\\ {\pi }_8\left(|x_8^{(2,1)\perp }\rangle \langle x_8^{(2,1)\perp }|\right)=\left(\begin{array}{llllllll}\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \hfill & \cdot \hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill \\ \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill & \hfill & \cdot \hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill & •\hfill & •\hfill & \cdot \hfill & •\hfill \end{array}\right)\end{array}$$

Single${\mathrm{\Delta }}_{N_3}$

$$\begin{array}{l}{\pi }_4\left(|x_4^{(2,1)\perp }\rangle \langle x_4^{(2,1)}|\right)=\left(\begin{array}{llll}\cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ \hfill & \cdot \hfill & \hfill & \hfill \\ \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \end{array}\right),\\ {\pi }_4\left(|x_4^{(2,1)}\rangle \langle x_4^{(2,1)}|\right)=\left(\begin{array}{llll}\hfill & \cdot \hfill & \hfill & \hfill \\ \cdot \hfill & •\hfill & \cdot \hfill & \cdot \hfill \\ \hfill & \cdot \hfill & \hfill & \hfill \\ \hfill & \cdot \hfill & \hfill & \hfill \end{array}\right)\\ {\pi }_4\left(|x_4^{(2,1)\perp }\rangle \langle x_4^{(2,1)\perp }|\right)=\left(\begin{array}{llll}•\hfill & \hfill & •\hfill & •\hfill \\ \cdot \hfill & \hfill & \cdot \hfill & \cdot \hfill \\ •\hfill & \hfill & •\hfill & •\hfill \\ •\hfill & \hfill & •\hfill & •\hfill \end{array}\right)\end{array}$$

In this case, we can compute the generators of A_f, e.g., $\left({\displaystyle \sum {}_1^{(2,1)}}\right)$as follows.

Since $|x_{12}^{(2,1)}\rangle =|x_8^{(2,1)}\rangle \oplus |x_4^{(2,1)}\rangle$and $|x_{12}^{(2,1)\perp }\rangle \text{=}|x_8^{(2,1)\perp }\rangle \oplus |x_4^{(2,1)\perp }\rangle ,$ we have that:

$${\pi }_{12}\left({\displaystyle \sum {}_1^{(2,1)}}\right)={\pi }_{12}\left(|x_{12}^{(2,1)}\rangle \langle x_{12}^{(2,1)\perp }|\right)+H.c.={\pi }_8\left({\displaystyle \sum {}_1^{(2,1)}}\right)\oplus {\pi }_4\left({\displaystyle \sum {}_1^{(2,1)}}\right)$$

Similarly, ${\pi }_{12}\left({\displaystyle \sum {}_a^{(2,1)}}\right)={\pi }_8\left({\displaystyle \sum {}_a^{(2,1)}}\right)\oplus {\pi }_4\left({\displaystyle \sum {}_a^{(2,1)}}\right),$ for all a = 0,1,2,3.

4.1.3. Single ${\mathrm{\Delta }}_{N_1},$ Single, ${\mathrm{\Delta }}_{N_2},$ and Single ${\mathrm{\Delta }}_{N_3}$ in Concatenation

The marked items are |1〉 in ${\mathrm{\Delta }}_{N_1},$|3〉 in ${\mathrm{\Delta }}_{N_2},$and |2〉 ${\mathrm{\Delta }}_{N_3},$ and it holds that

$$|x_{12}^{(1,1,1)}\rangle ={(1,0,0,0,0,0,1,0,0,1,0,0)}^T,$$

$$|x_{12}^{(1,1,1)\perp }\rangle ={(0,\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},0,\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},0,\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},)}^T,$$

$$|x_4^{(1,1,1)}\rangle ={(1,0,0,0)}^T\in {\mathrm{\Delta }}_{N_1},|x_4^{(1,1,1)}\rangle ={(0,0,1,0)}^T\in {\mathrm{\Delta }}_{N_2},|x_4^{(1,1,1)}\rangle ={(0,1,0,0)}^T\in {\mathrm{\Delta }}_{N_3}.$$

4.1.4. Single e.g., for ${\mathrm{\Delta }}_{N_1}$

The marked item is the vector |1〉, therefore

$$|x_4^{(1,1,1)}\rangle ={(1,0,0,0)}^T,|x_4^{(1,1,1)\perp }\rangle ={(0,\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},)}^T,$$

$$\begin{array}{l}{\pi }_4\left(|x_4^{(1,1,1)}\rangle \langle x_4^{(1,1,1)\perp }|\right)=\left(\begin{array}{llll}\cdot \hfill & •\hfill & •\hfill & •\hfill \\ \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \end{array}\right),\\ {\pi }_4\left(|x_4^{(1,1,1)}\rangle \langle x_4^{(1,1,1)}|\right)=\left(\begin{array}{llll}•\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill \\ \cdot \hfill & \hfill & \hfill & \hfill \end{array}\right),\\ {\pi }_4\left(|x_4^{(1,1,1)\perp }\rangle \langle x_4^{(1,1,1)\perp }|\right)=\left(\begin{array}{llll}\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill \\ \cdot \hfill & •\hfill & •\hfill & •\hfill \end{array}\right).\end{array}$$

In order to compute the generators ${\pi }_{12}\left({\displaystyle \sum {}_a^{(1,1,1)}}\right),$ a = 0, 1, 2, 3, we proceed in an analogous manner to the previous case. For simplicity, we also introduce the following shorthand notation, to denote direct sums of vectors $|u_4^{(1,1,1)}\rangle$ in databases ${\mathrm{\Delta }}_{N_1},$${\mathrm{\Delta }}_{N_2},$${\mathrm{\Delta }}_{N_3}$ respectively, as well as direct sums for other operators and the corresponding ∑’s.

$$\underset{{\mathrm{\Delta }}_{1,2,3}}{\oplus }|u_4^{(1,1,1)}\rangle =|u_4^{(1,1,1)}\rangle \oplus |u_4^{(1,1,1)}\rangle \oplus |u_4^{(1,1,1)}\rangle ,$$

$$\underset{{\mathrm{\Delta }}_{1,2,3}}{\oplus }{\pi }_4\left({\displaystyle \sum {}_a^{(1,1,1)}}\right)={\pi }_4\left({\displaystyle \sum {}_a^{(1,1,1)}}\right)\oplus {\pi }_4\left({\displaystyle \sum {}_a^{(1,1,1)}}\right)\oplus {\pi }_4\left({\displaystyle \sum {}_a^{(1,1,1)}}\right).$$

Since $|x_{12}^{(1,1,1)}\rangle ={\oplus }_{{\mathrm{\Delta }}_{1,2,3}}|x_4^{(1,1,1)}\rangle$ and $|x_{12}^{(1,1,1)\perp }\rangle ={\oplus }_{{\mathrm{\Delta }}_{1,2,3}}|x_4^{(1,1,1)\perp }\rangle$, for e.g., ${\pi }_{12}\left({\displaystyle \sum {}_1^{(1,1,1)}}\right)$ we obtain that:

$$\begin{array}{l}{\pi }_{12}\left({\displaystyle \sum {}_1^{(1,1,1)}}\right)={\pi }_{12}\left(|x_{12}^{(1,1,1)}\rangle \langle x_{12}^{(1,1,1)\perp }|\right)+H.c.\\ =\underset{{\mathrm{\Delta }}_{1,2,3}}{\oplus }{\pi }_4\left(|x_4^{(1,1,1)}\rangle \langle x_4^{(1,1,1)\perp }|\right)+\underset{{\mathrm{\Delta }}_{1,2,3}}{\oplus }H.c.\\ =\underset{{\mathrm{\Delta }}_{1,2,3}}{\oplus }{\pi }_4\left(|x_4^{(1,1,1)}\rangle \langle x_4^{(1,1,1)\perp }|+H.c.\right)=\underset{{\mathrm{\Delta }}_{1,2,3}}{\oplus }{\pi }_4\left({\displaystyle \sum {}_1^{(1,1,1)}}\right).\end{array}$$

5. Discussion

An important follow up of this work concerns the fact that the collective quantum search can be cast in the language of cooperative game theory, and so wider problems of search complexity reduction can be addressed. In fact, cooperative game theory is an area where multi-agent entities choose to collaborate in various schemes in order to take advantage from the collaboration in lowering some computational load which would enable them to achieve a desirable shared objective, see e.g., [16], for a wealth of principles and examples. For this connection, particularly useful would be the special joining schemes determined by the partitions π = π^∗, π_th and π_max, as tools for studying coalition formation of merging teams of searches aiming to trade collectivity for less search complexity. This appears to be a favorite context for implementing and applying the idea of merging. In particular quantum search by merging as outlined here could also be applied in applications where quantum simulation of quantum searching is carried out by multi-particle Hamiltonian models (see e.g., [17] and references therein). These prospects will be taken up elsewhere.