Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Information Theory Workshop (ITW)

A General Construction of the Transfer Matrices of (k, N + t)-Sum Boxes

Martianus Frederic Ezerman, Gaojun Luo, Jihao Fan, Meng Cao

Published Sep 29, 2025• 0 citations
Publisher

Abstract

We closely study N-sum boxes and their transfer matrices. Recently formulated as an abstraction for linear computations over quantum network, such a box allows for tools from quantum information processing to be applied on classical computational problems. We investigate (k, N + t)-sum boxes, which are generalized version of the N-sum boxes, and propose a general construction of their transfer matrices. Seen in this light, an N-sum box is a special case when k = N and t = 0.

DOI
10.1109/itw62417.2025.11240546

Related papers

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

Matteo Allaix, Yuxiang Lu, Yuhang Yao +3 more

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 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 x 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.

Globecom•Dec 4, 2023•16 citations

N-Sum Box: An Abstraction for Linear Computation Over Many-to-One Quantum Networks

Matteo Allaix, Yuxiang Lu, Yuhang Yao +3 more

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 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.

IEEE Transactions on Information Theory•Dec 11, 2024•8 citations

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

Matteo Allaix, Yuxiang Lu, Yuhang Yao +3 more

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.

arXiv:2304.07561•Apr 15, 2023•0 citations

Quantum networks: General theory and applications

Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D’Ariano +1 more

Quantum networks: General theory and applications In this work we present a general mathematical framework to deal with

arXiv:1601.04864•Acta Physica Slovaca Reviews and Tutorials•Jun 1, 2011•39 citations

Quantum tomography protocols with positivity are compressed sensing protocols

Amir Kalev, Robert L. Kosut, Ivan H Deutsch

Abstract Characterising complex quantum systems is a vital task in quantum information science. Quantum tomography, the standard tool used for this purpose, uses a well-designed measurement record to reconstruct quantum states and processes. It is, however, notoriously inefficient. Recently, the classical signal reconstruction technique known as ‘compressed sensing’ has been ported to quantum information science to overcome this challenge: accurate tomography can be achieved with substantially fewer measurement settings, thereby greatly enhancing the efficiency of quantum tomography. Here we show that compressed sensing tomography of quantum systems is essentially guaranteed by a special property of quantum mechanics itself—that the mathematical objects that describe the system in quantum mechanics are matrices with non-negative eigenvalues. This result has an impact on the way quantum tomography is understood and implemented. In particular, it implies that the information obtained about a quantum system through compressed sensing methods exhibits a new sense of ‘informational completeness.’ This has important consequences on the efficiency of the data taking for quantum tomography, and enables us to construct informationally complete measurements that are robust to noise and modelling errors. Moreover, our result shows that one can expand the numerical tool-box used in quantum tomography and employ highly efficient algorithms developed to handle large dimensional matrices on a large dimensional Hilbert space. Although we mainly present our results in the context of quantum tomography, they apply to the general case of positive semidefinite matrix recovery.

arXiv:1502.00536•npj Quantum Information•Dec 8, 2015•111 citations

On Binomial Summations and a Generalised Quantum SWAP Gate

Colin Wilmott, Peter Wild

We give a quantum gate construction - composed entirely from incidents of the CNOT gate - that generalises the qubit SWAP gate to higher dimensions. This new construction is more regular than and is an improvement on the WilNOT quantum gate construction.

arXiv:0811.1879•Nov 12, 2008•0 citations
We closely study N-sum boxes and their transfer matrices. Recently formulated as an abstraction for linear computations over quantum network, such a box allows for tools from quantum information processing to be applied on classical computational problems. We investigate (k, N + t)-sum boxes, which are generalized version of the N-sum boxes, and propose a general construction of their transfer matrices. Seen in this light, an N-sum box is a special case when k = N and t = 0.
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 et al. with recent applications toNNN-server private information retrieval. The N- sum box has a communication cost ofNNNqudits and classical output of a vector ofNNNq-ary digits linearly dependent (via an N x 2N transfer matrix) on 2N classical inputs distributed amongNNNtransmitters. 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.
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 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 ofN qN~qN q-ary digits linearly dependent (via anN×2NN \times 2NN×2Ntransfer matrix) on2N2N2Nclassical 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.
NNN-Sum Box: An Abstraction for Linear Computation over Many-to-one Quantum Networks
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 "NNN-sum box", a black box generalization of a two-sum protocol of Song \emph{et al.} with recent applications to NNN-server private information retrieval. The NNN-sum box has a communication cost of NNN qudits and classical output of a vector of NNN qqq-ary digits linearly dependent (via an N×2NN \times 2NN×2N transfer matrix) on 2N2N2N classical inputs distributed among NNN 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 NNN-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.
Abstract Characterising complex quantum systems is a vital task in quantum information science. Quantum tomography, the standard tool used for this purpose, uses a well-designed measurement record to reconstruct quantum states and processes. It is, however, notoriously inefficient. Recently, the classical signal reconstruction technique known as ‘compressed sensing’ has been ported to quantum information science to overcome this challenge: accurate tomography can be achieved with substantially fewer measurement settings, thereby greatly enhancing the efficiency of quantum tomography. Here we show that compressed sensing tomography of quantum systems is essentially guaranteed by a special property of quantum mechanics itself—that the mathematical objects that describe the system in quantum mechanics are matrices with non-negative eigenvalues. This result has an impact on the way quantum tomography is understood and implemented. In particular, it implies that the information obtained about a quantum system through compressed sensing methods exhibits a new sense of ‘informational completeness.’ This has important consequences on the efficiency of the data taking for quantum tomography, and enables us to construct informationally complete measurements that are robust to noise and modelling errors. Moreover, our result shows that one can expand the numerical tool-box used in quantum tomography and employ highly efficient algorithms developed to handle large dimensional matrices on a large dimensional Hilbert space. Although we mainly present our results in the context of quantum tomography, they apply to the general case of positive semidefinite matrix recovery.