$N$-Sum Box: An Abstraction for Linear Computation over Many-to-one Quantum Networks

Matteo Allaix, Yuxiang Lu, Yuhang Yao, Tefjol Pllaha, Camilla Hollanti, Syed A. Jafar

TL;DR

This paper introduces the $N$-sum box, a classical black-box abstraction that hides the underlying complexity of quantum entanglement to facilitate linear computation over many-to-one networks. By formalizing this model, the authors enable researchers to leverage quantum "superdense coding" gains—effectively doubling communication efficiency—for applications like Private Information Retrieval (PIR) without needing deep expertise in quantum mechanics.

What Problem Does This Paper Address?

In distributed computing, "many-to-one" networks (where multiple transmitters send data to a single receiver) are often bottlenecked by communication costs. While quantum mechanics offers a way to reduce these costs through entanglement and superdense coding, the barrier to entry is high. Most classical coding theorists and engineers lack the "quantum vocabulary" (e.g., stabilizers, Weyl operators, Bell states) to design protocols for a quantum internet.

The authors address this gap by creating a mathematical abstraction. Just as a computer scientist uses a "socket" to handle networking without knowing the physics of electrons in a wire, the $N$-sum box allows a coding theorist to treat a quantum multiple-access channel (QMAC) as a simple linear system with a specific, powerful advantage: it can transmit $2N$ classical values using only $N$ quantum bits (qudits).

Methods

The researchers utilize the Stabilizer Formalism, a framework for quantum computation, to build their abstraction.

  1. The $N$-Sum Box Model: They define a system with $N$ transmitters, each holding two classical inputs. These transmitters perform local quantum operations on entangled qudits and send them to a receiver. The receiver then performs a measurement to obtain $N$ classical outputs.
  2. Transfer Matrix Characterization: The core of the paper is determining which linear functions (represented by a "transfer matrix" $M$) are physically achievable. They prove that a matrix is feasible if it is Strongly Self-Orthogonal (SSO).
  3. Local Invertible Transformations (LITs): They show that by allowing transmitters to pre-process their inputs and the receiver to post-process the outputs using classical invertible matrices, the set of achievable functions expands significantly.
  4. Quantumization of CSA: They take a classical technique called Cross-Subspace Alignment (CSA)—used for efficient data retrieval—and "quantumize" it. By mapping CSA structures onto the $N$-sum box, they create Quantum CSA (QCSA) codes.

Datasets

Not discussed in the paper. As a theoretical work in information and coding theory, the "evaluation" consists of mathematical proofs and rate calculations rather than empirical testing on datasets.

Key Insights and Ideas

  • The "Superdense" Advantage: The $N$-sum box provides a 2-for-1 deal. In a classical setting, sending $N$ linear combinations of $2N$ inputs requires $2N$ symbols. The $N$-sum box does it with $N$ qudits, achieving the maximum gain allowed by the Holevo bound.
  • SSO is the Key: The feasibility of a quantum linear computation is entirely dictated by the "Strongly Self-Orthogonal" property of its transfer matrix. This provides a clear "design rule" for classical engineers.
  • Symmetric Privacy via Noise: By using "non-maximal" stabilizers (essentially leaving some parts of the quantum state "unfixed"), the box can produce randomized outputs. This is used to achieve Symmetric PIR, where the user gets their data, but the protocol ensures they don't learn anything extra about the database.
  • Bridging Fields: The $N$-sum box looks remarkably like a MIMO (Multiple-Input Multiple-Output) channel in wireless communications, but defined over finite fields rather than complex numbers.

Key Results

  • Feasibility Theorem: The authors provide a definitive test (Theorem 5) to determine if a desired linear computation is feasible over a quantum network using their construction.
  • Efficiency Doubling: For Quantum Private Information Retrieval (QPIR) and Quantum Secure Distributed Batch Matrix Multiplication (QSDBMM), the QCSA codes achieve a rate $R_Q = \min\{1, 2R_C\}$, where $R_C$ is the best possible classical rate. This represents a 100% improvement in communication efficiency.
  • Standard Form: They proved that any feasible quantum transfer matrix can be represented in a "standard form" ($M = [I \ S]$ where $S$ is symmetric), simplifying the design of future quantum protocols.

Limitations and Future Work

  • Idealized Channels: The paper assumes an "ideal" quantum channel. Future work is needed to account for decoherence and noise in real-world quantum hardware.
  • Linearity Constraint: The $N$-sum box is strictly for linear computations. While many important tasks (like matrix multiplication and PIR) are linear, non-linear distributed computations remain outside this specific abstraction.
  • Capacity Proofs: While the authors are "cautiously optimistic" that their stabilizer-based construction covers all possible linear functionalities for this setting, a formal information-theoretic proof that this exhausts the total capacity of a QMAC is still an open area of research.

Summary updated

Abstract

Linear computations over quantum many-to-one communication networks offer opportunities for communication cost improvements through schemes that exploit quantum entanglement among transmitters to achieve superdense coding gains, combined with classical techniques such as interference alignment. The problem becomes much more broadly accessible if suitable abstractions can be found for the underlying quantum functionality via classical black box models. This work formalizes such an abstraction in the form of an "$N$-sum box", a black box generalization of a two-sum protocol of Song \emph{et al.} with recent applications to $N$-server private information retrieval. The $N$-sum box has a communication cost of $N$ qudits and classical output of a vector of $N$ $q$-ary digits linearly dependent (via an $N \times 2N$ transfer matrix) on $2N$ classical inputs distributed among $N$ transmitters. We characterize which transfer matrices are feasible by our construction, both with and without the possibility of additional locally invertible classical operations at the transmitters and receivers. Furthermore, we provide a sample application to Cross-Subspace Alignment (CSA) schemes to obtain efficient instances of Quantum Private Information Retrieval (QPIR) and Quantum Secure Distributed Batch Matrix Multiplication (QSDBMM). We first describe $N$-sum boxes based on maximal stabilizers and we then consider non-maximal-stabilizer-based constructions to obtain an instance of Quantum Symmetric Private Information Retrieval.
BibTeX
@misc{allaix2023n,
  author = {Matteo Allaix and Yuxiang Lu and Yuhang Yao and Tefjol Pllaha and Camilla Hollanti and Syed A. Jafar},
  title = {{$N$-Sum Box: An Abstraction for Linear Computation over Many-to-one Quantum Networks}},
  year = {2023},
  eprint = {2304.07561},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2304.07561},
}

Loading related content...

Figure