D ISTRIBUTED computation networks are often limited by their communication costs. Improving the efficiency of distributed computation by reducing communication costs is an active area of research. Reductions in communication cost may be achieved by coding techniques that are specialized for the type of distributed computation task (e.g., aggregation [3], MapReduce [4], matrix multiplication [5]) as well as the nature of the communication network (wireless [3], cable [6], optical fiber [7], quantum networks [8]). For instance, coding for overthe-air computation reduces the communication cost of linear computation over many-to-one wireless networks, by taking advantage of the natural superposition property of the wireless medium [3].
Investigating the properties and the applications of quantum protocols is crucial for the development of a quantum internet [9], [10], [11], which operates on the principles of quantum mechanics and differs fundamentally from the classical internet used in our daily lives. Our focus in this work is on linear computations (possibly with privacy and security constraints) over quantum many-to-one communication networks. The potential for reduced communication costs in this setting comes from quantum entanglement among the transmitters, which creates opportunities for superdense coding gains [12], [13], [14], [15] as well as classical techniques such as interference alignment. However, unlike wireless networks for which there exists an abundance of simplified channel models and abstractions to facilitate analysis from coding, information-theoretic and signal-processing perspectives [16], [17], [18], similarly convenient abstractions of quantum communication networks are not readily available, which limits the study of quantum communication networks largely to quantum experts. Our work is motivated by the observation that a convenient abstraction for linear computation over quantum many-to-one networks is indeed available, although somewhat implicitly, in the works of Song and Hayashi, in the form of a quantum two-sum protocol [19], [20], and its subsequent generalizations, as applied to QPIR [21], [22], [23], [24], [25]. A similar type of linear computation with a classical-quantum multiple access channel has been discussed in [26], [27], and [28], where the classical-quantum multiple access channel might have noise, and further applied to the problem of quantum secret sharing and QPIR [29].
The two-sum protocol [20] is shown in Figure 1, both as a quantum circuit and as a black box. In the quantum circuit, we see two transmitters (Tx1 and Tx2), each in possession of one qubit of an entangled pair. The entangled state in this case is the Bell state |β 00 ⟩. As classical 2-bit inputs become available to the two transmitters ((x 1 , x 3 ) to Tx1, (x 2 , x 4 ) to Tx2), they perform conditional quantum operations (X, Z gates) on their respective qubits and then send them to the receiver (Rx), for a total communication cost of 2 qubits. The receiver performs a Bell measurement and obtains (y 1 , y 2 ) = (x 3 + x 4 , x 1 + x 2 ). The two-sum protocol can be abstracted into a black box, also shown in Figure 1, with inputs (x 1 , x 3 ), (x 2 , x 4 ) controlled by Tx1 and Tx2, respectively, and output y = Mx, where M = ( 1 1 0 0 0 0 1 1 ) is the transfer matrix of this 2-sum box and x ⊤ = x 1 , x 2 , x 3 , x 4 . The blackbox representation hides the details of the quantum circuit and specifies only the functionality (transfer matrix M) and the communication cost (2 qubits), which makes it possible for non-quantum experts to design low-communication-cost coding schemes for quantum communication networks using this black box, e.g., to take advantage of super-dense coding. Note that without entanglement, in order for the receiver to recover the same output (x 3 + x 4 , x 1 + x 2 ), the required communication cost is 4 qubits, i.e., twice as much. This factor of two improvement is an example of superdense coding gain.
The main contribution of this work is to formalize a generalization of the 2-sum box, namely an N -sum box. It is worth pointing out immediately that the technical foundations of the N -sum box are not new, indeed the construction draws upon the well-understood stabilizer formalism in quantum coding theory [30], [31], [32], [33], and most of the technical details of the generalization from 2-sum to N -sum are also contained in the works of Song and Hayashi on Quantum Private Information Retrieval [21]. Nevertheless, the crystallization of the black-box abstraction, as demonstrated in this study, holds significant promise for researchers in the classical information and coding theory domains. These researchers, though less acquainted with stabilizer codes and quantum coding theory, can still make valuable contributions to comprehending the fundamental boundaries of transmitterside entanglement-assisted distributed classical computation over quantum multiple access (QMAC) networks. This is achieved through the utilization of the aforementioned classical abstraction, which effectively conceals the intricate details of the underlying quantum circuitry. For example, wireless researchers with little background in quantum codes may recognize the N -sum box as the familiar MIMO MAC setting illustrated via an example in Figure 2. The main distinctions from the multiple antenna wireless setting are 1) that the channel is deterministic (noise-free), defined over a finite field (F q ) rather than complex numbers, and 2) that instead of being generated randomly by nature, the channel matrix can be freely designed as long as it is strongly self orthogonal (SSO) (cf. Definition 3). This is because it is shown in this work that feasible N -sum box transfer functions are precisely those matrices M ∈ F N ×2N q that are either strongly self-orthogonal themselves, or can be made strongly self-orthogonal by local invertible transformations (cf. Definition 1) at various transmitters and/or the receiver. Thus, from a wireless perspective, the problem of coding for the QMAC becomes conceptually equivalent to that of designing a coding scheme as well as the channel matrix for a MIMO MAC subject to given structural constraints imposed by the N -sum box abstraction (SSO), such that the resulting MIMO MAC is able to efficiently achieve the desired linear computation 'over-the-air' (actually, through quantum entanglement). The efficiency gained by 'over-theair' computation in this (constrained: SSO) MIMO MAC translates into superdense coding gain over the QMAC.
The N -sum box is intended to be useful primarily as a tool for exploring the information-theoretic capacity of F q -linear classical computations over an ideal QMAC, with the potential to shed new light into the fundamental limitations of superdense coding and quantum entanglement. As with other tools that information theorists have at their disposal, it is difficult to predict in advance if the N -sum box abstraction will turn out to be sufficient to construct capacity achieving schemes. Indeed the linear computation capacity of a MAC is a challenging problem even in the classical setting, especially for vector linear computations. Nevertheless, we are cautiously optimistic that the stabilizer-based construction exhausts the scope of the N -sum box functionality for F q -linear computations. The optimistic outlook is supported by prior works on capacity of QPIR [21], [23], [24] where N -sum boxes have been implicitly employed for capacity-achieving schemes, as well as a recent follow-up work that utilizes the N -sum-box abstraction from this work, to find the capacity of sum-computation over the QMAC [34], [35].
Last but not the least, even when an exact capacity characterization is beyond reach, a fruitful strategy is to utilize the N -sum box to design the best possible schemes allowed by the abstraction. In general the constraints of the abstraction may lead to entirely new schemes. However, certain applications of interest, of which QPIR is a prime example, have classical solutions with specialized structures that naturally resonate with the SSO constraint, the defining feature of N -sum boxes. For such applications, it can be particularly insightful to find ways to efficiently quantumize the classical solutions, leading not only to good quantum coding schemes but also a better understanding of the role of the SSO structure for linear computations. Notably, such a quantumization was introduced in [22] by blending the star-product scheme [36] with the two-sum protocol. In this work, to further illustrate this aspect, we provide another instance by quantumizing classical cross-subspace alignment (CSA) codes into QCSA codes. CSA codes have been used in a variety of schemes ranging from XSTPIR [37] and MDS coded XSTPIR [38] to secure distributed batch matrix multiplication (SDBMM) [5], [39]. Therefore, QCSA codes naturally open the door for the general quantum MDS-coded XSTPIR (MDS-coded QXST-PIR) setting as well as quantum SDBMM (QSDBMM).
In Section II we describe the stabilizer formalism over a finite field, which provides the quantum building block for stabilizer-based N -sum-box constructions. In Section III we formally define an N -sum box. In Section IV we study which constructions based on a maximal stabilizer are feasible both allowing and disallowing local invertible transformations, i.e., invertible transformations applied to the inputs by the transmitters or invertible transformations applied to the output by the receiver. In Section V we provide an application to CSA schemes to obtain a QCSA scheme that enables instances of MDS-coded QXSTPIR and QSDBMM. Finally in Section VI we consider constructions based on non-maximal stabilizers that enable instances of symmetric MDS-coded QXSTPIR without the need for shared randomness among the servers.
We denote by [N ] the set {1, . . . , N }, n ∈ N, and by F q the finite field with q elements. We use bold lower-case letters and bold upper-case letters to denote vectors and matrices, respectively. Given a matrix A, ⟨A⟩ row and ⟨A⟩ col denote the spaces spanned by the rows and columns of A, respectively, while A ⊤ and A † represent its transpose and its conjugate transpose, respectively.
The stabilizer formalism [30] is a compact framework for quantum computation that provides a useful bridge to classical computation. Recently, this framework has been leveraged to boost several classical protocols. We describe the stabilizer formalism over a finite field, for the details of which we refer the reader to [31] and [32]. Throughout, we will use the same notation as in [24].
Let q = p r with a prime number p and a positive integer r. Let H be a q-dimensional Hilbert space spanned by orthonormal states {|j⟩ : j ∈ F q }. For x ∈ F q , we define the trace tr x := r-1 i=0 x p i ∈ F p . Let ω := exp(2πı/p). For a, b ∈ F q , we define unitary matrices X(a) := j∈Fq |j + a⟩⟨j| and Z(b) := j∈Fq ω tr bj |j⟩⟨j| on H. For s = (s 1 , . . . , s 2N ) ∈ F 2N q , we define a unitary matrix W(s
For x = (x 1 , . . . , x N ), y = (y 1 , . . . , y N ) ∈ F N q , we define the tracial bilinear form ⟨x, y⟩ := tr N i=1 x i y i ∈ F p and the trace-symplectic bilinear form ⟨x, y⟩ S := ⟨x, Jy⟩, where J is the 2N × 2N matrix
The dual of a subspace V of F 2N q with respect to this form is
Symplectic matrices are precisely those matrices that preserve ⟨•, •⟩ S , and its columns form a symplectic basis for
Remark 1:
q is a symplectic matrix, then it is easy to see that the matrix F ′ = F Iκ 0 ∈ F 2N ×κ q , i.e., the matrix containing the first κ ∈ [N ] columns of F, satisfies the relation (F ′ )
⊤ JF ′ = 0. Conversely, a matrix satisfying such relation can be completed to a symplectic matrix [40]. Symplectic orthogonality in the vector space F 2N q is equivalent to commutativity in the Heisenberg-Weyl group HW N q := c W(s) : s ∈ F 2N q , c ∈ C \ {0} . In fact, there is a surjective homomorphism c W(s) ∈ HW N q → s ∈ F 2N q with kernel cI q N : c ∈ C \ {0} , and two matrices c 1 W(s 1 ), c 2 W(s 2 ) commute if and only if ⟨s 1 , s 2 ⟩ S = 0.
A commutative subgroup of HW N q not containing cI q N for any c ̸ = 1 is called a stabilizer group. Such groups are precisely those groups for which the aforementioned homomorphism is actually an isomorphism. Thus, a stabilizer group defines a self-orthogonal subspace, that is V ⊆ V ⊥ S , in F 2N q . Conversely, given a self-orthogonal subspace V of F 2N q , there exist complex numbers c v so that
forms a stabilizer group.
Example 1: Let X = X(1), Z = Z(1), I = X(0) (defined over the binary field). Consider the self-orthogonal subspace V of F 4 2 generated by s 1 = (1, 1, 0, 0) and s 2 = (0, 0, 1, 1). Then, the unitary matrices W(s 1 ) = X ⊗ X and W(s 2 ) = Z ⊗ Z generate the stabilizer group S(V) = {I ⊗ I, X ⊗ X, Z ⊗ Z, XZ ⊗ XZ}. On the other hand, the unitary matrices -W(s 1 ) = -X ⊗ X and W(s 2 ) = Z ⊗ Z generate the stabilizer group S ′ (V) = {I ⊗ I, -X ⊗ X, Z ⊗ Z, -XZ ⊗ XZ}.
Remark 2: In the previous example we showed that different choices for c v generate different stabilizer groups from a given self-orthogonal subspace. On the other hand, the homomorphism c W(s) ∈ HW N q → s ∈ F 2N q is surjective with kernel cI q N : c ∈ C \ {0} , which implies that, given a self-orthogonal subspace, there is a class of stabilizer groups that can be generated from it that vary only from the choice of the constants c v . Thus, there is a one-to-one correspondence between classes of stabilizer groups in HW N q and self-orthogonal subspaces in F 2N q . Throughout this paper, we focus primarily on maximal stabilizers, since they exhaust the scope of all possible stabilizer-based N -sum boxes (cf. Remark 20). Maximal stabilizers define strongly self-orthogonal (SSO) subspaces, i.e., V = V ⊥ S , which implies the property dim(V) = N . In Section VI we consider non-maximal stabilizer-based constructions for the cases when we want to discard N -κ of the N outputs of an N -sum box.
While V defines a stabilizer S(V), the quotient space F 2N q /V ⊥ S defines orthogonal projectors
which we use as a projective-value measurement (PVM). We will denote |s⟩ the state which P V s projects onto. Throughout this paper we will use the results shown in the following proposition.
Proposition 1 [24, Proposition 2.2]: Let V be a Ddimensional self-orthogonal subspace of F 2N q and S(V) be a stabilizer defined from V. For a coset s ∈ F 2N q /V ⊥ S , let s be its coset leader. Then, we obtain the following statements.
(a) For any v ∈ V, the operation W(v) ∈ S(V) is simultaneously and uniquely decomposed as
with orthogonal projections P V s such that
q /V ⊥ S and the quantum system H ⊗N is decomposed as
where the system W is the q D -dimensional Hilbert space spanned by |s⟩ : s ∈ F 2N q /V ⊥ S with the property
q , we have
Measuring with P V as in Equation (3) would yield a coset. Proposition 2 aims to clarify the notation of Proposition 1 by giving a unique representative of the outputted equivalence class. First, we need the following lemma to prove that matrices satisfying the conditions of the proposition exist.
Lemma 1: Let G ∈ F 2N ×κ q be such that G ⊤ JG = 0 and rank(G) = κ. Then there exists a full-rank matrix
, where g i is the i th column of G and g ′ j is the j th column of G ⊥ , and 2) G = G ⊥ Iκ 0 , i.e., G is the leftmost submatrix of G ⊥ . Proof: Let F be a symplectic completion of G, i.e., a symplectic matrix such that its first κ columns are equal to G, which exists by the conditions imposed on G (cf. Remark 1).
Then we can write it as
completion is given by
thus we can choose G ⊥ to be
It is easy to see that G ⊥ satisfies the two conditions of Lemma 1.
Then performing the PVM P V s : s ∈ F 2N q /V ⊥ S on the state |x⟩⟨x| ⊗ I q N -κ gives the outcome (x) h followed by N -κ uniformly random symbols with probability 1.
Proof: Condition 3 ensures that the matrices G and G ⊥ are full rank, so dim(V) = κ and dim(V ⊥ S ) = 2N -κ. By conditions 1 and 2 we have that V ⊆ V ⊥ S = ⟨G ⊥ ⟩ col , so a subgroup S(V) as in Equation ( 2) is a stabilizer. By Equation (5) we have that
, where W is the q κdimensional Hilbert space spanned by |s⟩ :
q , then we can uniquely decompose it as
In Proposition 1, we have that s = s + V ⊥ S = s + g : g ∈ V ⊥ S . It follows that every x ∈ s maps to a unique element s h ∈ F κ q . Thus, we can identify each coset s with the element s h . Then we identify the states
to avoid confusion with the computational basis, since W is the space spanned by the states |s⟩.
In the decomposition given by Equation ( 5) we have q κ distinct elements, since each H V s has dimension q N -κ . Thus, since there are q κ vectors s h ∈ F κ q , we can write Equation (4) as W(v) = s h ∈F κ q ω ⟨v,H1s h ⟩ S P V s h , where P V s h is the projection associated with the measurement outcome s h .
If κ = N , then dim(Im P V s h ) = 1 and we can decompose it as P V s h := |s h ⟩ W ⟨s h | W , otherwise the projection is given by a density matrix. Assume now that the system is in the state |x⟩ for some x ∈ F 2N q /V ⊥ S . By the discussion above, we can identify x with a unique x h ∈ F N q . Then,
We thus obtain the outcome (x) h with probability 1 after performing the PVM P
on the state |x⟩.
In general, assume the system is in the state |x⟩⟨x| ⊗ I q N -κ for some x ∈ F 2N q /V ⊥ S . By the discussion above, we can identify x with a unique x h ∈ F κ q . Then,
We thus obtain the outcome (x) h followed by N -κ random symbols from F q with probability 1 after performing the PVM P
□ Remark 3: The PVM can be more clearly expressed as
Example 3: Let G, G ⊥ as in Example 2. We can choose H to be the column we excluded from F in the previous example when defining G ⊥ , i.e., H = 0 0 0 1 ⊤ . Then, the map
In Example 5 we build a state over two qubits that is stabilized by a non-maximal stabilizer and for which the PVM P V outputs the same bit x 3 + x 4 and a uniformly-random bit after applying the Weyl operators on each qubit. Remark 4: If κ = N , then G ⊥ = G, so the first two conditions of Proposition 2 can be simply rewritten as G ⊤ JG = 0. In this case G defines an SSO subspace V, which is in correspondence with a maximal stabilizer S(V). Furthermore, measuring over the PVM P V is equivalent to first revert the unitary U G,H (cf. Remark 9) and measuring on the computational basis, as such unitary is needed to map the computational basis to the PVM basis.
As the PVM P V is applied on N qudits, one should expect N q-ary digits as output, but if κ < N , the output of the PVM has only κ q-ary digits according to Proposition 2. We will clarify this aspect in Section VI.
An N -sum box is a black box with the following functional form:
, or equivalently y = Mx, where y ∈ F N q is the output vector, x ∈ F 2N q is the input vector, and M ∈ F N ×2N q is the transfer matrix. The inputs to the N -sum box are controlled by N parties (transmitters), where transmitter n ∈ [N ] is controlling (x n , x N +n ). The output vector y is measured by another party, which we label as the receiver. The N -sum box is initialized with shared quantum entanglement among the N transmitters, i.e., N entangled q-dimensional qudits are prepared and distributed to the transmitters, one qudit per transmitter. The initial qudit entanglement is independent of the inputs x and any data that subsequently becomes available to the transmitters. No quantum resource is initially available to the receiver. In the course of operation of the N -sum box, each of the N transmitters acquires data from various sources, including possibly the receiver (e.g., queries in private information retrieval), based on which it performs conditional X, Z-gate operations on its own qudit, and then sends its qudit to the receiver. The receiver performs a quantum measurement on the N qudits, from which it recovers y.
In this setting, we allow the inputs (x n , x n+N ) from each transmitter n ∈ [N ] to be transformed by an invertible matrix. This corresponds to multiplying the input vector by local invertible transformations, which are defined as follows.
Definition 1: Let diag N,Fq be the set of diagonal matrices of dimension N × N and entries in F q . The set of local invertible transformations (LITs) is defined as
Notice that the submatrix with the entries in position (n, n), (n, n + N ), (n + N, n), (n + N, n + N ) of Λ ∈ LIT N,Fq is the invertible matrix applied by transmitter n ∈ [N ] to its inputs.
We also allow receiver invertible transformations, i.e., we allow the receiver to transform the output vector of the N -sum box by multiplying it by P ∈ GL N,Fq , where GL N,Fq is the set of invertible matrices with dimension N and entries in F q . This gives equivalent representations of the N -sum box as
IV. STABILIZER-BASED N -SUM BOXES First, we define strongly self-orthogonal matrices, which are used in the construction of N -sum boxes based on the stabilizer formalism.
Definition 3:
q is said to be strongly self-orthogonal (SSO) if its columns span an SSO subspace, or equivalently, if M ⊤ JM = 0 and rank(M) = N . The set of SSO matrices is denoted by M o .
Remark 5: The reason why we define strongly self-orthogonal matrices is because self-orthogonal matrices would not generate SSO subspaces. For example, in F 4 9 where F 9 ≡ F 3 [x]/(x 2 + x + 2) with generator element α, the matrix
is 0, but the space spanned by its rows wouldn not be strongly self-orthogonal since
Let us now characterize some classes of N -sum boxes that can be constructed based on the stabilizer formalism.
The following theorem describes which transfer matrices are feasible from a stabilizer-based construction when LITs are disallowed.
Theorem 1: Suppose there exists
Then there exists a stabilizer-based construction for an N -sum box over F q with transfer matrix M. Proof: Let U G,H ∈ C q N ×q N (cf. Remark 9) be the unitary matrix such that its i th column is the vector representing the state |ν(i)⟩ W identified by Equation ( 6), where
q is a bijection and W is the Hilbert space defined by a chosen stabilizer group within the class in correspondence with V = ⟨G⟩ col (cf. Remark 2). In other words, U G,H is the encoding operation for the chosen stabilizer group, as shown on the left side of Figure 3. Let |0⟩ W = U G,H |0⟩ be the initial entangled state over H ⊗N . Assume that transmitter n ∈ [N ] applies X(x n ), Z(x N +n ) on his qudit and sends it to the receiver. Then the quantum system received is in the state W(x)|0⟩ W = |(x) h ⟩ W . After performing the PVM P V defined in Equation ( 7) on the qudits the receiver measures (x) h without error by Proposition 2. Let M be the submatrix comprised of the bottom N rows of G H -1 , then we have that Mx = x h , which is the output of the measurement. We proved that for an N -sum box with transfer function M satisfying condition 3 there exists a quantum black box with input x and output Mx. □ Remark 6: The terminology "stabilizer-based construction" stems from the aforementioned correspondence between stabilizers and self-orthogonal spaces. Explicitly, let S = ⟨W(s 1 ), . . . , W(s κ )⟩ ⊆ HW N q be a stabilizer group, i.e., a stabilizer group with κ independent generators W(s i ) dependent on
be the matrix that has s i as its i th column, then G ⊤ JG = 0 and rank(G) = κ. For the case κ = N , the stabilizer is maximal, |0⟩ W is its stabilized state, and G ∈ M o .
Remark 7: A stabilizer-based construction for any feasible N -sum box y = Mx is information-theoretically optimal as a black-box implementation in the sense that its quantum download cost of N qudits cannot be improved upon by any other construction. In other words, there cannot exist a more efficient (in terms of download cost) construction (e.g., nonstabilizer based) that allows the receiver to recover the same y = Mx output with a total download cost that is strictly less than N qudits. This is because the transfer matrix M is full rank, and by the Holevo bound [41], N independent classical dits cannot be delivered with a communication cost of less than N qudits.
Remark 8: From a quantum coding-theoretic perspective, a stabilizer-based construction for an N -sum box is equivalent to preparing a stabilizer state, applying an N -qudit error corresponding to a string of 2N symbols from a finite field, and computing the syndrome on this state as output.
We denote by M sbc the set of all the transfer matrices resulting from stabilizer-based constructions with disallowed LITs. In the following, we establish that the set of transfer matrices achievable through the (G, H)-construction established by Theorem 1 is the same as the set of SSO matrices, i.e., Lemma 2:
q be such that M ⊤ ∈ M sbc . By condition 3 of Theorem 1 we have that MG = 0, and since G ∈ M o , we also have that G ⊤ JG = 0, which implies MG = G ⊤ JG. Since G is full-rank, also G ⊤ J is full-rank, so ⟨M⟩ row = ⟨G ⊤ J⟩ row as they both describe the null-space of G ⊤ . This implies that M = PG ⊤ J for an invertible matrix P ∈ GL N,Fq , and since JJ ⊤ = I we can conclude that
) is invertible and we can write its inverse as G H , where G, H ∈ F 2N ×N q are full-rank matrices. Clearly,
. With a similar argument as above, we have that ⟨G ⊤ ⟩ row = ⟨MJ⟩ row , from which we can easily conclude that G ⊤ JG = 0, i.e., G ∈ M o , thus proving M ∈ M sbc and M o ⊆ M sbc . □ Remark 9: Let G = ( A B ) ∈ M o be any SSO matrix and H = ( C D ) be such that the matrix F := G H is symplectic. Then, by Equation (1), we have 0 I F -1 = -B ⊤ A ⊤ which is again an SSO matrix. Combining this with Lemma 2 implies that we only need to complete G to a symplectic matrix (instead of invertible). The well-known connection between symplectic matrices and the stabilizer formalism [33] allows for a simpler description of the matrix U G,H , as the following example illustrates.
Example 4: Suppose we have two parties, Tx1 and Tx2, both possessing two bits a
, respectively (see Figure 1). The two-sum transmission protocol computes the sum of their bits (x 1 + x 2 , x 3 + x 4 ) starting with the Bell state |β 00 ⟩ = (|00⟩ + |11⟩)/ √ 2, which is stabilized by the stabilizer S = ⟨W(0, 0, 1, 1), W(1, 1, 0, 0)⟩. Consider the matrix
where G is determined by S and H is chosen so that F is a symplectic matrix. The symplectic matrix can be decomposed, e.g., using the Bruhat decomposition [42], [43], as
The components are precisely the symplectic representation of the quantum gates CNOT and a partial Hadamard H ⊗ I on the first qudit [44]. This is precisely the circuit U G,H for which |β 00 ⟩ = U G,H |00⟩. Using Equation (1) we then obtain the transfer matrix
which is exactly the functional form of the two-sum transmission protocol. This approach allows for a straightforward generalization that computes Mx starting with the state
The following theorem fully characterizes N -sum boxes without LITs and follows directly from Theorem 1, Remark 6 and Lemma 2.
Theorem 2: Let M ∈ M o . A construction based on a stabilizer S ⊆ HW N q exists for an N -sum box over F q with transfer matrix M ⊤ if and only if S is a maximal stabilizer.
In a nutshell, the construction starts with an SSO matrix G. The set of Weyl operators corresponding to the columns of G = [g 1 , g 2 , . . . , g N ] forms the generators of a commuting group of normal matrices W(g i ), i ∈ [N ]. Commutativity is guaranteed by the SSO property of G and the definition of the Weyl operators.
Because of the commutativity, these normal matrices W(g i ) are simultaneously diagonalizable -they share the same set of orthonormal eigenvectors. Let U G be a unitary matrix whose columns are these orthonormal eigenvectors. Any one of these, say the first column, |u⟩ := U G |0⟩, can be chosen to be the initial state for the N -sum box. Consider the Weyl operators normalized by their respective eigenvalues for the chosen eigenvector, i.e., W(g i ) = (1/λ i ) W(g i ) where W(g i ) |u⟩ = λ i |u⟩, so that |u⟩ has eigenvalue +1 for W(g i ).
These normalized Weyl operators are now seen as the "stabilizers", |u⟩ is the initial entangled state that is prepared for the N -sum box, and the columns of U G represent the orthonormal basis for the measurement that produces the output of the N -sum box. Note that while the set of orthonormal basis vectors is fixed by the choice of the SSO matrix G, the order in which these vectors appear as columns of U G dictates the representation of the measurement result. This choice is determined by the matrix H in Theorem 1. Each choice of H produces a matrix U G,H , which is nothing but a particular permutation of the columns of U G determined by the choice of H, thus producing different representations of the same measurement. The choices of G and H, and therefore the initial entangled state and the orthogonal measurement, are all agreed upon between the transmitters and the receiver in advance as part of the protocol design, based on the desired functionality (i.e., the desired transfer matrix M) of the Nsum box.
It is noteworthy that the normalization of the Weyl operators to act as stabilizers for the initial state is not essential for the N -sum box, where we send only classical information and an orthogonal measurement fully identifies the state. It is primarily a convenience chosen to retain the obvious connection to syndrome measurement in quantum error correction with stabilizer codes.
Now we explore what is possible when LITs are allowed. The following theorem shows that the transfer matrix of any (G, H) construction is equivalent (up to LITs) to the null-space of G ⊤ , which can be explicitly represented as ⟨J ⊤ G⟩ col .
Proposition 3: Let M ∈ F N ×2N q be such that M ⊤ ∈ M sbc . Then M LIT ≡ G ⊤ J, whose row-space is the null-space of G ⊤ . Proof: This follows directly from the proof of Lemma 2, since we can write M = PG ⊤ J for P ∈ GL N,Fq , i.e., M LIT ≡ G ⊤ J. □ A known property of SSO matrices is that they can be written in the so-called standard form [45], i.e., if M ∈ M o then there exist P ∈ GL N,Fq , Q ∈ GL 2N,Fq such that
where S is a symmetric N ×N matrix, i.e., S ⊤ = S. We denote by M s the set of transfer matrices in standard form, i.e.,
The following lemma shows that any SSO matrix M can be transformed by at most N signed column-swapping operations into a matrix
For completeness, the proof is included in Appendix A.
Lemma 3: For any M ∈ M o there exists a diagonal matrix Σ ∈ {0, 1}
N ×N such that
Remark 10: Notice that (M ′ ) ⊤ is obtained from M ⊤ by signed column-swapping operations, i.e., swapping corresponding columns of G l and G r with a sign-change operation. Specifically, if Σ i,i = 1, the i th column of G l is replaced with the negative of the i th column of G r , while the i th column of G r is replaced with the i th column of G l .
Our next result shows that with LITs, every feasible transfer matrix M ∈ M o has an equivalent representation in the standard form (M) ⊤ LIT ≡ I S , where S ⊤ = S. Notice that in Equation ( 8) the matrix Q is not necessarily an LIT. The contribution here is to show that the standard form remains valid when only LITs are allowed.
Theorem 3: For every M ∈ M sbc there exists M ′ ∈ M s such that (M ′ ) ⊤ LIT ≡ M ⊤ . Conversely, M s ⊆ M sbc . Proof: By Lemma 3 in Appendix A, there exists
) ⊤ and M ′ l is fullrank. Since multiplication on the left by an invertible square matrix preserves both rank and strong self-orthogonality, we obtain that
Conversely, it is easy to see that the standard form I S is strongly self-orthogonal, since it has rank N and
Clearly we have that M s ⊆ M o = M sbc . □ Remark 11: The standard form is not unique up to LITs. For example, Next, we define the set M LIT of all possible transfer matrices that we can obtain by applying LITs:
The following theorem shows that any transfer matrix in M LIT is equivalent, up to LITs, to a transfer matrix in standard form. Figure 4 provides an overview of the relationships between the various forms of transfer functions. Theorem 4: For every M ∈ M LIT there exists
and since the equivalence is transitive, we have that (M ′ ) ⊤ LIT ≡ M ⊤ . The converse is trivial by the definitions. □
Next we explore the problem of testing feasibility. Given a desired N -sum box specification Y = M ⊤ X for some M ∈ F 2N ×N q , the goal is to determine this N -sum box is feasible by stabilizer based constructions combined with local invertible transformations. The easiest case is if M is in the standard form M ⊤ = I S , which is immediately seen to be feasible. Another easy case is when M ∈ M o , which can be checked efficiently as well with complexity O(N 3 ). However, if M is neither in standard form, nor a full-rank strongly self-orthogonal matrix, it could still be feasible through local invertible transformations. Here we describe a test to determine such feasibility, or to rule it out with certainty, with complexity no more than O(N 4 ).
Theorem 5: The transfer matrix
q is feasible for an N -sum box construction, i.e., M ∈ M LIT , if and only if rank(M) = N and there exists an invertible diagonal matrix ∆ ∈ F N ×N q such that
Remark 12: Finding such a ∆ can be done with complexity O(N 4 ) by solving for the N elements of ∆ subject to the linear constraints imposed by the self-orthogonality condition.
Proof: Consider a general feasible setting. By Theorem 4 we can write M ⊤ = P I S Λ for some P ∈ GL N,Fq and
where the matrices
To prove the result it is only necessary to show that the matrix Λ ′ = Λ( I 0 0 ∆ ) is symplectic, i.e., it satisfies the property Λ ′ J(Λ ′ ) ⊤ = J, as symplectic matrices are known to be the only kind of matrices that preserves strong self-orthogonality:
by the commutativity of diag N,Fq . It follows that
For the other direction it is trivial to see that if such a ∆ exists, then
□ Remark 13: Notice that in the proof we proved that the matrix Λ ′ = Λ( I 0 0 ∆ ) is symplectic, i.e., it satisfies the property Λ ′ J(Λ ′ ) ⊤ = J, as symplectic matrices are known to be the only kind of matrices that preserves strong selforthogonality.
V. N -SUM BOX APPLICATION: QUANTUM CSA SCHEME Cross-subspace alignment (CSA) codes find applications in various private information retrieval (PIR) schemes (e.g., PIR with secure storage) and in secure distributed batch matrix multiplication (SDBMM). Using the developed N -sum box abstraction of a quantum multiple-access channel (QMAC), we translate CSA schemes over classical multiple-access channels into efficient quantum CSA schemes over a QMAC, achieving maximal superdense-coding gain. Because of the N -sum box abstraction, the underlying problem of coding to exploit quantum entanglements for CSA schemes becomes conceptually equivalent to that of designing a channel matrix for a MIMO MAC subject to given structural constraints imposed by the N -sum box abstraction, such that the resulting MIMO MAC is able to implement the functionality of a CSA scheme (encoding/decoding) over-the-air. Applications include Quantum PIR with secure and MDS-coded storage, as well as Quantum SDBMM. In this section we first introduce the classical CSA scheme, then give the definition of some important concepts and finally present the way to translate a CSA scheme to QCSA scheme and apply the QCSA scheme to specific problems.
Conceptually, the setting for a CSA coding scheme (over a finite field F q ) is the following. We have N distributed servers. The servers locally compute their answers A n , n ∈ [N ], to a user's query. Each answer A n is a linear combination of L symbols that are desired by the user, say δ 1 , δ 2 , • • • , δ L , and N -L symbols of undesired information (interference), say ν 1 , ν 2 , • • • , ν N -L . The linear combinations have a Cauchy-Vandermonde structure that is the defining characteristic of CSA schemes, such that the desired terms appear along the dimensions corresponding to the Cauchy terms, while the interference appears (aligned) along the dimensions corresponding to the Vandermonde terms. The b th instance of a CSA scheme is represented as
.
The CSA scheme requires that all the α i , f j are distinct elements in F q (thus needing q ≥ N + L), which guarantees that the N ×N matrix G CSA q N,L (α,f ) is invertible. After downloading A n from each server n, n ∈ [N ], the user is able to recover the desired symbols δ b 1 , . . . , δ b L by inverting CSA q N,L (α, f ). Thus, each instance b of the CSA scheme allows the user to retrieve L desired symbols at a cost of N downloaded symbols. The rate of the scheme, defined as the number of desired symbols recovered per downloaded symbol, is L/N . The reciprocal, N/L, is the download cost per desired symbol.
Remark 14: A noteworthy aspect of CSA schemes is that the number of servers can be reduced, i.e., the CSA scheme can be applied to N ′ < N servers, with a corresponding reduction in the number of desired symbols L ′ < L, as long as the dimension of interference is preserved, i.e., N -L = N ′ -L ′ . In the classical setting, this flexibility is not useful as it leads to a strictly higher download cost, i.e., N ′ /L ′ = (N -L)/L ′ + 1 > (N -L)/L + 1 = N/L. In the quantum setting, however, this will lead to a useful simplification.
In the following we represent GRS codewords as column vectors rather than the usual coding-theoretic notation with row vectors in order to be consistent with the standard notation used in linear computation. It follows that the GRS generator matrix is represented as a n × k matrix instead of the usual k × n matrix.
Definition 4 (GRS Code): Let C = GRS q n,k (α, u) be a Generalized Reed-Solomon (GRS) code over F q , where α = (α 1 , . . . , α n ) ∈ F 1×n q , u = (u 1 , . . . , u n ) ∈ F 1×n q , u i ̸ = 0 and α i ̸ = α j for all distinct i, j ∈ [n]. Its generator matrix can be defined as
, its dual code C ⊥ is defined as
The dual code of a GRS code is also a GRS code, e.g., according to the following construction [46].
Definition 6 (Dual GRS Code):
where u j ̸ = 0, we have
i.e., GRS q n,n-k (α, v) is an [n, n -k] code that is the dual of the code GRS q n,k (α, u). Definition 7 (QCSA Matrix): We define the QCSA q N,L (α, β, f ) matrix as the N × N matrix in (15), as shown at the bottom of the next page, where
and G GRS q N,⌈N/2⌉ (α,β) identified in Equation ( 15) are the generator matrices of [N, ⌊N/2⌋] and [N, ⌈N/2⌉] GRS codes, respectively. As a special case, setting β 1 = . . . = β N = 1, we have,
Remark 15: When N is an even number, the two submatrices G GRS q N,⌊N/2⌋ (α,β) and G GRS q N,⌈N/2⌉ (α,β) become the same sub-matrix G GRS q N,N/2 (α,β) .
Remark 16: The QCSA q N,L (α, β, f ) matrix is the product of an N × N diagonal matrix diag(β 1 , β 2 , • • • , β N ) and the N ×N Cauchy-Vandermonde matrix G CSA q N,L (α,f ) invoked by CSA schemes (cf. [38,Equation (11)]). The former is full rank since β n ̸ = 0, ∀n ∈ [N ], and the latter is full rank according to [38,Lemma 1]
Since multiplication with an invertible matrix preserves rank, the QCSA q N,L (α, β, f ) matrix is an invertible matrix.
C. From CSA Scheme to QCSA Scheme Given a CSA scheme over F q , we show how to translate it into a QCSA scheme over a QMAC. The process is described by the following three steps.
1) From the CSA q N,L (α, f ) matrix, construct two matrices
, a MIMO MAC with channel matrix M QCSA .
3) Over the MIMO MAC, realize 'over-the-air' decoding of two instances of the CSA scheme. By the N -sum box abstraction, this automatically maps to a quantum protocol (a QCSA scheme) and the efficiency gained by 'over-the-air' decoding in the MIMO MAC translates into the superdense coding gain over the QMAC. These steps are explained next.
1) Step 1. Generation of QCSA Matrices:
such that the sub-matrix G GRS q N,⌈N/2⌉ (α,u) of Q u N and the sub-matrix
according to Equation (13) and Equation ( 14).
2) Step 2. A suitable N -Sum Box: The N -sum box is specified by the following theorem.
Theorem 6: For the Q u N and Q v N constructed in Step 1, there exists a feasible N -sum box y = M QCSA x in F q with the N × 2N transfer matrix,
A proof of Theorem 6 is presented in Appendix B.
3) Step 3. QCSA Scheme as 'Over-the-Air' CSA: Using the MIMO MAC with channel matrix M QCSA identified in Step 2, we now describe how to achieve 'over-the-air' decoding of several instances of CSA schemes. Since the MIMO MAC is actually an N -sum box, which in fact represents a quantum protocol with communication cost N qudits, a QCSA scheme is automatically implied for the QMAC through the N -sum box abstraction.
First consider the case where we are given a CSA scheme with L ≤ N/2. With 2 instances of the CSA scheme we have
which retrieves 2L desired symbols at the download cost of 2N symbols. Now the corresponding QCSA scheme (overthe-air MIMO MAC) is obtained as follows.
where the N entries of u are non-zero, v is specified in Equation ( 17), ν 1 (↽) represents the last ⌊N/2⌋ -L symbols of
1 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
the vector ν 1 = ν 1 1 , . . . , ν 1 N -L , and ν (↽) (2) represents the last ⌈N/2⌉ -L symbols of the vector ν 2 = ν 2 1 , . . . , ν 2 N -L . Multiplication by diag(u, v) in Equation ( 21) simply involves each server j ∈ [N ] scaling its answers of the two instances of the CSA scheme A 1 j , A 2 j by u j , v j , respectively, and applying u j A 1 j , v j A 2 j to the inputs of the N -sum box (MIMO MAC) corresponding to that server. Evidently, all 2L desired symbols are recovered, and the total download cost is N qudits (one qudit from each server), for a normalized download cost of N/(2L) qudits per desired dit. The improvement from N/L (classical CSA) to N/2L (QCSA) reflects the factor of 2 superdense coding gain in communication efficiency.
If L > N/2, we discard 'redundant' servers (cf. Remark 14) and only employ N ′ = 2N -2L < N servers, choosing a CSA scheme with L ′ = N ′ /2, such that N -L = N ′ -L ′ , i.e., the dimensions of interference are preserved, which results in a download cost of N ′ /(2L ′ ) = 1 qudit per desired symbol.
Based on the approach described above, existing achievability results based on CSA schemes in the classical setting translate into corresponding achievability results for QCSA schemes in the quantum setting. In particular, the following corollaries follow immediately from this approach. Appendix C provides a proof of Corollary 1 and Section C-A provides a proof of Corollary 2.
Corollary 1: For the (N, M, K, X, T ) MDSXSTPIR [38], where N > X + T + K -1, a QCSA scheme achieves rate
i.e., the user is able to recover L = N R Q q-ary symbols of desired information for every N q-dimensional qudits that it downloads from the servers. Remark 17: In an MDSXSTPIR problem, there are M messages and N servers. Every K symbols of one message, together with X random noise symbols, are encoded according to an [N, K + X] MDS code and each codeword symbol is stored at one of the N servers. Thus, the storage cost of every server is 1 M of the size of all the M messages, and any group of up to X colluding servers learn nothing about the M messages. A user wishes to retrieve one of the M messages by querying the N distributed servers such that any group of up to T colluding servers can learn nothing about the desired message index.
Remark 18: In addition to establishing achievable rates for quantum versions of XSTPIR [37], MDS-XSTPIR [38] that have not been previously explored, Corollary 1 recovers existing achievability results in Quantum PIR for the cases of TPIR [21] and MDS-TPIR [24]. Relative to prior works, the field size required by the QCSA scheme is linear in N , because an even q ≥ L + N where L ≤ N 2 guarantees the existence of the QCSA matrix, while in [21], the field size is exponential in N , due to an O(N ) fold field extension step. It is also noteworthy that prior quantum PIR schemes employ mixed quantum states to achieve symmetric privacy, i.e., the user does not learn more than his desired information. While the QCSA scheme does not automatically ensure symmetric privacy, the same can be accomplished by noise alignment based on shared common randomness among servers as in [39]. In Section VI-B we discuss how we can achieve symmetric privacy automatically with a non-maximal stabilizer based construction. Shared (classical) common randomness among servers is not difficult to achieve when the servers share quantum entanglements.
Corollary 2: For the (N, X A , X B ), N > X A + X B SDBMM (secure distributed batch matrix multiplication) problem defined in [5], where L matrices A 1 , . . . , A L ∈ F λ×η q are X A -securely shared among N servers, another L matrices B 1 , . . . , B L ∈ F η×µ q are X B -securely shared among the same N servers, and the user wants to compute the L products
by querying the N > X A + X B servers, a QCSA scheme achieves the rate
i.e., from every N • (λµ) q-dimensional qudits downloaded from N servers, the user recovers L = N R Q desired product matrices in F λ×µ q . Let us note that in the original problem defined in [5], the S matrices A 1 , . . . , A S ∈ F L×K q and another S matrices B 1 , . . . , B S ∈ F K×M q are to be pairwise multiplied. The parameters (S, L, K, M ) from [5] are mapped to (L, λ, η, µ) to fit the notation in this work.
Remark 19: In both corollaries, the rate achieved with the QCSA scheme can be expressed as R Q = min{1, 2R C }, where R C is the rate achieved by the CSA scheme in the corresponding classical setting. Considering that rates greater than 1 are not possible according to the Holevo bound [41], it is apparent that the QCSA scheme achieves the maximal superdense-coding gain relative to the classical CSA scheme.
In Section II we noticed that the output of the measurement associated with a non-maximal stabilizer has less digits than one would expect. The reason is that the states that form a basis for the space W (cf. Equation ( 5)) associated to a non-maximal stabilizer are mixed states, so the remaining N -κ output digits result as uniformly random and can be discarded. Thus, non-maximal stabilizers can be useful to describe black boxes that output only κ q-ary digits while discarding the last N -κ digits, which we call (κ, N )-sum boxes.
Furthermore, given a maximal stabilizer with N generators S(V ′ ), one can always obtain a non-maximal stabilizer S(V) by choosing κ of those. Conversely, given a non-maximal stabilizer with κ generators S(V), one can always complete the generator basis to obtain a maximal stabilizer S(V ′ ).
These two observations suggest that, in order to obtain the stabilized state of a non-maximal stabilizer S(V), one can start with N qudits in the mixed state |0⟩ ⟨0| ⊗ I q N -κ q N -κ and apply the same unitary as one would use to generate |0⟩ W from |0⟩ in a maximal stabilizer S(V ′ ) that completes S(V). After we apply a unitary W(s) for some s ∈ F 2N q and measure using P V ′ , the output will have N -κ uniformly random digits. Here we consider a purification to clarify the evolution of the state before the measurement. By applying the same gates as one would use to prepare the initial entangled state for the two-sum transmission protocol, i.e., a Hadamard gate on the first qubit and a CNOT gate with the first qubit as control and the second qubit as target (cf. Example 4), we obtain the initial pure state
which is stabilized by the three independent Weyl operators W(1, 1, 0, 0, 0, 0), W(1, 0, 1, 0, 0, 0) and W(0, 1, 1, 0, 0, 0). Notice that applying the Hadamard gate and the CNOT gate is equivalent to a change of base of the qubits from the computational base to the Bell base, thus the PVM is performed by first applying those gates in reverse order to change the basis back to the computational basis, and then applying the classic measurement over the computational basis.
The state evolves in the following way:
where the first two steps are equivalent to the Weyl operator W(s) over the first two qubits and the last two steps are equivalent to the change of basis from the Bell basis to the computational basis before the measurement. Thus, after applying the Weyl operator W(s) and reverting the initial CNOT and Hadamard gates we end up with the qubits in the state
Let tr : H → R be the trace operator that maps a state to the trace of its density matrix. Let tr :
H 1 ⊗H 2 the partial trace over the third quantum system. In this case, given the density matrix D, the partial trace is given by tr(D) = Notice that, by the properties of the tensor product, the state over the first qubit has density matrix |x 3 + x 4 ⟩ ⟨x 3 + x 4 | after applying the partial trace operator. On the other side,
We conclude that, by tracing out the third qubit, the state has the density matrix
which outputs the bit x 3 + x 4 and a random bit.
A. Stabilizer-Based (κ, N )-Sum Boxes
The setting for (κ, N )-sum boxes is similar to the one described for N -sum boxes in Section III, with the difference that the transfer matrix M has dimensions κ × 2N and N -κ outputs of the measurement are discarded. The following theorem generalizes Theorem 1 to non-maximal-stabilizerbased sum boxes. The proof is omitted, as it is the same as the one provided for Theorem 1.
Theorem 7: Let G ∈ F 2N ×κ q and G ⊥ ∈ F 2N ×2N -κ q be matrices satisfying the conditions of Proposition 2, i.e., such that
Then there exists a stabilizer-based construction for a (κ, N )sum box over F q with transfer matrix
The following example shows the implementation of a (1, 2)-sum box over 2 qubits.
Example 6: Suppose we have two parties, Tx1 and Tx2, both possessing two bits a = (x 1 , x 3 ), b = (x 2 , x 4 ) ∈ F 2 2 , respectively. Let S = ⟨W(1, 1, 0, 0)⟩ be a 1-dimensional stabilizer over 2 qubits. Notice that its generator is the restriction to the first two qubits of W(1, 1, 0, 0, 0, 0), i.e., the first Weyl operator that fixes |φ ′ ⟩ defined in Example 5. The stabilizer has a generator matrix that can be completed to a symplectic matrix F as follows:
Thus, we can choose matrices G ⊤ and H as
The output of the box is then given by
Now, notice that the Weyl operator W(a) ⊗ W(b) applied by the transmitters together and the non-maximal stabilizer S correspond, respectively, to the Weyl operator W(s) and the stabilizer S(V) in Example 5. As the outputs match, it is easy to see that the (1,2)-sum box simplifies the description of the non-maximal-stabilizer construction. Remark 20: From the discussion above, one can see that maximal stabilizers exhaust the scope of stabilizer-based constructions for black boxes of the form Y = MX, where M ∈ F κ×2N q . More precisely, consider matrices G, H that satisfy the conditions of Theorem 1, i.e., the matrices associated to a stabilizer-based construction for an N -sum box. Then there is a correspondence between U G,H and the chosen maximal stabilizer S, where U G,H is the unitary that prepares the initial state |0⟩ W = U G,H |0⟩ for the N -sum box and S = S(⟨G⟩ col ). If we want N -κ of the outputs of an N -sum box to be discarded, we can consider the initial state
q N -κ , as operations on the qudits initially prepared in the mixed state do not affect their mixedness and measuring them at the end of the sum-box operations outputs random digits. Thus, (κ, N )-sum boxes can be obtained from N -sum boxes by changing the initial (unentangled) state to a mixed state and their description (as in Theorem 7) can be formalized by using a submatrix of G as the generator for the chosen non-maximal stabilizer.
The utilization of a (κ, N )-sum box may be perceived as inefficient due to the presence of non-informative qudits among the total N qudits being transferred. Nevertheless, it has some meaningful applications, e.g., it is useful to make symmetric QPIR protocols which use the N -sum box construction without the need for shared randomness among the servers like in classical PIR [39].
Remark 21: Notice that, in this case, we do not need to provide any additional information to the servers to provide symmetry for the protocol. In fact, we only need to change the initial entangled state distributed to the servers, rather than providing additional shared randomness to the servers which requires additional computations and storage.
For instance, consider the output of a QCSA scheme as given in Equation ( 24), i.e.,
where ν b (↽) represents the last ⌊N/2⌋ -L symbols of the interference vector ν
. This interference contains linear combinations of other files stored in the server that might be retrieved over many rounds by a malicious user. Thus, we want to "hide" the interference outputs by replacing them with random digits, which can be achieved in the following way. Some details are omitted, as the procedure is similar to the one shown in Appendix B.
Consider two GRS codes C 1 = GRS q N,L (α, u) and C 2 = GRS q N,L (α, v) where v is generated by u according to Equation ( 13), then we have that
Consider the matrices
where Hu C and Hv C are the Cauchy submatrices of QCSA matrices defined in Equation (15). This matrix satisfies the conditions of Theorem 7, then there exists a (2L, N )-sum box with transfer matrix
Clearly there exists a permutation matrix P π as defined in Equation ( 27) such that
The transfer matrix is given by
It is easily verified that the output of the (2L, N )-sum box is just
without the interference terms that appear in Equation (24). The QCSA scheme is thus symmetric, as the remaining N -2L outputs are randomized by construction.
be the 1 × M row vector that contains the (l, k) th symbol of all the M messages in the b th instance of a CSA scheme. There are N = 5 servers and the storage at server n ∈
and Z b 1 , Z b 2 are independent random noise vectors that are uniform over F 1×K q . Thus, it is obvious that the storage cost at each server is 2LM = 4M q-ary symbols. Comparing with the replicated storage, the storage cost is reduced to 1 K = 1 2 , since the M messages consist of 2LKM = 8M q-ary symbols in total. Also, due to the fact that the messages are padded with random noise, any X = 1 server learns nothing about the M messages.
A user wishes to retrieve the θ th message by querying the N = 5 servers, without letting any T = 1 server learn anything about θ. In the scheme of [38], for one instance of MDSXSTPIR there are K = 2 rounds of retrieval. In each round, the user downloads 1 q-ary answer symbol from each server. In the first round the user recovers W θ 1,1 , W θ 2,1 , while in the second round the user recovers W θ 1,2 , W θ 2,2 . Thus, in each round, the user recovers L = 2 symbols of the desired message W θ by downloading 5 symbols in total from the servers. The total downloaded symbols are N K = 10, while the retrieved desired symbols are LK = 4, thus achieving a rate of
Clearly, the rate is the same for two instances of the same scheme.
2) QCSA Scheme for General MDSXSTPIR: Let us briefly introduce the general CSA code-based classical MDSXSTPIR scheme [38], whereupon the translation to the quantum scheme is obtained as described in Section V-C. In the classical scheme there are K rounds of retrieval. In round κ, κ ∈ [K] a CSA N,L scheme is applied, where 0 < L = N -(X + T + K -1). Specifically, according to [38,Equations (65),(66)], the N answer symbols from the N servers in the κ th round of the b th instance of a CSA scheme are
2 . . . . . . . . . . . . . . . . . . . . .
2 . . . . . . . . . . . . . . . . . . . . .
b,(κ) 1 = δ b,(κ) 1 . . . W b,θ Lκ + F b,(κ) L = δ b,(κ) L * + F b,(κ) L+1 = ν b,(κ) 1 . . . * + F b,(κ) N = ν b,(κ) N -L X b,(κ) δ,ν (i) , (39) = G CSA N,L (α,f ) X b,(κ) δ,ν
where W b,θ 1,κ , • • • , W b,θ L,κ are the L = N -(X + T + K -1) symbols of the desired message W b,θ , * represents undesired information (interference) whose explicit expression is redundant, R b,(κ) is an N × 1 column vector which only depends on the message symbols that are decodable from the previous κ -1 rounds (to be proved for the quantum scheme later), CSA N,L (α,f ) R b,(κ) .
With the answers in the form of Equation ( 39) it is clear that in round κ ∈ [K], with 2 instances of the CSA scheme, 2L "desired" symbols δ Suppose that in the first (κ -1) rounds 2L(κ -1) symbols W b,θ l,k l∈[L],k∈[κ-1],b∈ [2] are successfully decoded, then the user can find the values R b,(κ) , b ∈ [2] in the κ th round as they only depend on the message symbols that are decoded in the previous (κ -1) rounds. The user is then able to find F b,(κ) , b ∈ [2], as F b,(κ) is just a deterministic function of R b,(κ) . Then by subtracting F b,(κ) l from δ b,(κ) l
, the user is able to recover W b,θ l,κ for all l ∈ [L], b ∈ [2]. That is to say, in the first κ rounds, the user is able to decode 2Lκ symbols W b,θ l,k l∈[L],k∈[κ],b∈ [2] . The induction is thus completed. Thus, the rate when L = N -(X + T + K -1) ≤ N 2 can be computed as 2L N = 2 1 -X+T +K-1 N . For the case where L > N 2 , we can eliminate "redundant" servers and construct a rate 1 scheme as mentioned in Section V-C. Corollary 1 is thus proved. □
Without loss of generality, let us prove that the specified rate is achievable for retrieving the (1, 1) th entry of the L products A 1 B 1 , . . . , A L B L . Other entries are similarly retrieved.
For any l ∈ [L], let C l = A l B l , and let c l be the (1, 1) th entry of the matrix C l . According to [5,Equations (103),(110),(112)], after applying a CSA N,L scheme with 0 < L = N -(X A + X B ), the N answer symbols from the N servers regarding the (1, 1) th entry of the L products are
2 . . . . . . . . . . . . . . . . . . . . .
where
L are the (1, 1) th entry of the L products in the b th instance of the CSA scheme, i.e., the L desired symbols, and * denotes the undesired information (interference) whose explicit expressions are redundant.
Thus, with 2 instances of the CSA scheme, 2L desired symbols can be recovered by using the N -sum Box specified in Theorem 2 when L = N -(X A + X B ) ≤ N 2 , according to Section V-C. The rate of retrieving one entry of the L products is thus 2L N = 2 1 -X A +X B N when L ≤ N 2 . Again, we can achieve rate 1 by eliminating "redundant" servers when L > N 2 , as mentioned in Section V-C. Corollary 2 is thus proved.
□