More Like this

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

   https://doi.org/10.1109/TIT.2024.3514921  

   Allaix, Matteo; Lu, Yuxiang; Yao, Yuhang; Pllaha, Tefjol; Hollanti, Camilla; Jafar, Syed A (February 2025, IEEE Transactions on Information Theory)

   Linear computations over quantum many-to-one communication networks offer opportunities for communica- tion 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 × 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. 

   more » « less
2. Stabilizer Entanglement Distillation and Efficient Fault-Tolerant Encoders

   https://doi.org/10.1103/PRXQuantum.6.010339  

   Shi, Yu; Patil, Ashlesha; Guha, Saikat (March 2025, PRX Quantum)

   Entanglement is essential for quantum information processing, but is limited by noise. We address this by developing high-yield entanglement distillation protocols with several advancements. (1) We extend the 2-to-1 recurrence entanglement distillation protocol to higher-rate n-to-(n−1) protocols that can correct any single-qubit errors. These protocols are evaluated through numerical simulations focusing on fidelity and yield. We also outline a method to adapt any classical error-correcting code for entanglement distillation, where the code can correct both bit-flip and phase-flip errors by incorporating Hadamard gates. (2) We propose a constant-depth decoder for stabilizer codes that transforms logical states into physical ones using single-qubit measurements. This decoder is applied to entanglement distillation protocols, reducing circuit depth and enabling protocols derived from high-performance quantum error-correcting codes. We demonstrate this by evaluating the circuit complexity for entanglement distillation protocols based on surface codes and quantum convolutional codes. (3) Our stabilizer entanglement distillation techniques advance quantum computing. We propose a fault-tolerant protocol for constant-depth encoding and decoding of arbitrary states in surface codes, with potential extensions to more general quantum low-density parity-check codes. This protocol is feasible with state-of-the-art reconfigurable atom arrays and surpasses the limits of conventional logarithmic depth encoders. Overall, our study integrates stabilizer formalism, measurement-based quantum computing, and entanglement distillation, advancing both quantum communication and computing. 

   more » « less
3. Classical Coding Problem from Transversal T Gates

   https://doi.org/10.1109/ISIT44484.2020.9174408  

   Rengaswamy, Narayanan; Calderbank, Robert; Newman, Michael; Pfister, Henry D. (June 2020, 2020 IEEE International Symposium on Information Theory (ISIT))

   null (Ed.)

   Universal quantum computation requires the implementation of a logical non-Clifford gate. In this paper, we characterize all stabilizer codes whose code subspaces are preserved under physical T and T † gates. For example, this could enable magic state distillation with non-CSS codes and, thus, provide better parameters than CSS-based protocols. However, among non-degenerate stabilizer codes that support transversal T, we prove that CSS codes are optimal. We also show that triorthogonal codes are, essentially, the only family of CSS codes that realize logical transversal T via physical transversal T. Using our algebraic approach, we reveal new purely-classical coding problems that are intimately related to the realization of logical operations via transversal T. Decreasing monomial codes are also used to construct a code that realizes logical CCZ. Finally, we use Ax's theorem to characterize the logical operation realized on a family of quantum Reed-Muller codes. This result is generalized to finer angle Z-rotations in https://arxiv.org/abs/1910.09333. 

   more » « less
4. Bridging the Capacity Gap Between Interactive and One-Way Communication

   https://doi.org/10.1137/1.9781611974782.138  

   Haeupler, Bernhard; Velingker, Ameya (October 2017, ACM-SIAM Symposium on Discrete Algorithms)

   We study the communication rate of coding schemes for interactive communication that transform any two-party interactive protocol into a protocol that is robust to noise. Recently, Haeupler [11] showed that if an ∊ > 0 fraction of transmissions are corrupted, adversarially or randomly, then it is possible to achieve a communication rate of Furthermore, Haeupler conjectured that this rate is optimal for general input protocols. This stands in contrast to the classical setting of one-way communication in which error-correcting codes are known to achieve an optimal communication rate of 1 In this work, we show that the quadratically smaller rate loss of the one-way setting can also be achieved in interactive coding schemes for a very natural class of input protocols. We introduce the notion of average message length, or the average number of bits a party sends before receiving a reply, as a natural parameter for measuring the level of interactivity in a protocol. Moreover, we show that any protocol with average message length ℓ = Ω(poly(1/∊)) can be simulated by a protocol with optimal communication rate 1 - Θ(Η(∊)) over an oblivious adversarial channel with error fraction e. Furthermore, under the additional assumption of access to public shared randomness, the optimal communication rate is achieved ratelessly, i.e., the communication rate adapts automatically to the actual error rate e without having to specify it in advance. This shows that the capacity gap between one-way and interactive communication can be bridged even for very small (constant in e) average message lengths, which are likely to be found in many applications. 

   more » « less
5. Coprime Bivariate Bicycle Codes and Their Layouts on Cold Atoms

   https://doi.org/10.22331/q-2026-02-23-2009  

   Wang, Ming; Mueller, Frank (February 2026, Quantum)

   Quantum computing is deemed to require error correction at scale to mitigate physical noise by reducing it to lower noise levels while operating on encoded logical qubits. Popular quantum error correction schemes include CSS code, of which surface codes provide regular mappings onto 2D planes suitable for contemporary quantum devices together with known transversal logical gates. Recently, qLDPC codes have been proposed as a means to provide denser encoding with the class of bivariate bicycle (BB) codes promising feasible design for devices.This work contributes a novel subclass of BB codes suitable for quantum error correction. This subclass employs $coprimes$ and the product $xy$ of the two generating variables $x$ and $y$ to construct polynomials, rather than using $x$ and $y$ separately as in vanilla BB codes. In contrast to vanilla BB codes, where parameters remain unknown prior to code discovery, the rate of the proposed code can be determined beforehand by specifying a factor polynomial as an input to the numerical search algorithm. Using this coprime-BB construction, we found a number of surprisingly short to medium-length codes that were previously unknown. We also propose a layout on cold atom arrays tailored for coprime-BB codes. The proposed layout reduces both move time for short to medium-length codes and the number of moves of atoms to perform syndrome extractions. We consider an error model with global laser noise on cold atoms, and simulations show that our proposed layout achieves significant improvements over prior work across the simulated codes. 

   more » « less