Search

Quantum low-density parity-check (LDPC) codes are a promising family of quantum error-correcting codes for fault tolerant quantum computing with low overhead. Decoding quantum LDPC codes on quantum erasure channels has received more attention recently due to advances in erasure conversion for various types of qubits including neutral atoms, trapped ions, and superconducting qubits. Belief propagation with guided decimation (BPGD) decoding of quantum LDPC codes has demonstrated good performance in bit-flip and depolarizing noise. In this work, we apply BPGD decoding to quantum erasure channels. Using a natural modification, we show that BPGD offers competitive performance on quantum erasure channels for multiple families of quantum LDPC codes. Furthermore, we show that the performance of BPGD decoding on erasure channels can sometimes be improved significantly by either adding damping or adjusting the initial channel log-likelihood ratio for bits that are not erased. More generally, our results demonstrate BPGD is an effective general-purpose solution for erasure decoding across the quantum LDPC landscape., Comment: Published in 2024 60th Annual Allerton Conference Proceedings

We show that any sequence of well-behaved (e.g. bounded and non-constant) real-valued functions of $n$ boolean variables $\{f_n\}$ admits a sequence of coordinates whose $L^1$ influence under the $p$-biased distribution, for any $p\in(0,1)$, is $\Omega(\text{var}(f_n) \frac{\ln n}{n})$.

In the quantum compression scheme proposed by Schumacher, Alice compresses a message that Bob decompresses. In that approach, there is some probability of failure and, even when successful, some distortion of the state. For sufficiently large blocklengths, both of these imperfections can be made arbitrarily small while achieving a compression rate that asymptotically approaches the source coding bound. However, direct implementation of Schumacher compression suffers from poor circuit complexity. In this paper, we consider a slightly different approach based on classical syndrome source coding. The idea is to use a linear error-correcting code and treat the message to be compressed as an error pattern. If the message is a correctable error (i.e., a coset leader) then Alice can use the error-correcting code to convert her message to a corresponding quantum syndrome. An implementation of this based on polar codes is described and simulated. As in classical source coding based on polar codes, Alice maps the information into the ``frozen" qubits that constitute the syndrome. To decompress, Bob utilizes a quantum version of successive cancellation coding., Comment: Extended Version of ISIT 2024 Submission

Quantum low-density parity-check (QLDPC) codes have emerged as a promising technique for quantum error correction. A variety of decoders have been proposed for QLDPC codes and many of them utilize belief propagation (BP) decoding in some fashion. However, the use of BP decoding for degenerate QLDPC codes is known to have issues with convergence. These issues are typically attributed to short cycles in the Tanner graph and code degeneracy (i.e. multiple error patterns with the same syndrome). Although various methods have been proposed to mitigate the non-convergence issue, such as BP with ordered statistics decoding (BP-OSD) and BP with stabilizer inactivation (BP-SI), achieving better performance with lower complexity remains an active area of research. In this work, we propose a decoder for QLDPC codes based on BP guided decimation (BPGD), which has been previously studied for constraint satisfaction and lossy compression problems. The decimation process is applicable to both binary and quaternary BP and it involves sequentially fixing the value of the most reliable qubits to encourage BP convergence. Despite its simplicity, We find that BPGD significantly reduces the BP failure rate due to non-convergence, achieving performance on par with BP with ordered statistics decoding and BP with stabilizer inactivation, without the need to solve systems of linear equations., Comment: 19 pages, 8 figures

In this work, a novel data-driven methodology for designing polar codes for channels with and without memory is proposed. The methodology is suitable for the case where the channel is given as a "black-box" and the designer has access to the channel for generating observations of its inputs and outputs, but does not have access to the explicit channel model. The proposed method leverages the structure of the successive cancellation (SC) decoder to devise a neural SC (NSC) decoder. The NSC decoder uses neural networks (NNs) to replace the core elements of the original SC decoder, the check-node, the bit-node and the soft decision. Along with the NSC, we devise additional NN that embeds the channel outputs into the input space of the SC decoder. The proposed method is supported by theoretical guarantees that include the consistency of the NSC. Also, the NSC has computational complexity that does not grow with the channel memory size. This sets its main advantage over successive cancellation trellis (SCT) decoder for finite state channels (FSCs) that has complexity of $O(|\mathcal{S}|^3 N\log N)$, where $|\mathcal{S}|$ denotes the number of channel states. We demonstrate the performance of the proposed algorithms on memoryless channels and on channels with memory. The empirical results are compared with the optimal polar decoder, given by the SC and SCT decoders. We further show that our algorithms are applicable for the case where there SC and SCT decoders are not applicable.

Recently, the authors showed that Reed-Muller (RM) codes achieve capacity on binary memoryless symmetric (BMS) channels with respect to bit error rate. This paper extends that work by showing that RM codes defined on non-binary fields, known as generalized RM codes, achieve capacity on sufficiently symmetric non-binary channels with respect to symbol error rate. The new proof also simplifies the previous approach (for BMS channels) in a variety of ways that may be of independent interest., Comment: Extended version of ISIT 2023 accepted paper

Belief propagation (BP) is a classical algorithm that approximates the marginal distribution associated with a factor graph by passing messages between adjacent nodes in the graph. It gained popularity in the 1990's as a powerful decoding algorithm for LDPC codes. In 2016, Renes introduced a belief propagation with quantum messages (BPQM) and described how it could be used to decode classical codes defined by tree factor graphs that are sent over the classical-quantum pure-state channel. In this work, we propose an extension of BPQM to general binary-input symmetric classical-quantum (BSCQ) channels based on the implementation of a symmetric "paired measurement". While this new paired-measurement BPQM (PMBPQM) approach is suboptimal in general, it provides a concrete BPQM decoder that can be implemented with local operations., Comment: Extended version of submission to the 2022 Information Theory Workshop in Mumbai, India

This paper considers the performance of Reed-Muller (RM) codes transmitted over binary memoryless symmetric (BMS) channels under bitwise maximum-a-posteriori (bit-MAP) decoding. Its main result is that, for a fixed BMS channel, the family of binary RM codes can achieve a vanishing bit-error probability at rates approaching the channel capacity. This partially resolves a long-standing open problem that connects information theory and error-correcting codes. In contrast with the earlier result for the binary erasure channel, the new proof does not rely on hypercontractivity. Instead, it combines a nesting property of RM codes with new information inequalities relating the generalized extrinsic information transfer function and the extrinsic minimum mean-squared error., Comment: 30 pages, minor changes (including title) from previous version to correct typos and clarify some statements, accepted to the IEEE Transactions on Information Theory

Sequencing a DNA strand, as part of the read process in DNA storage, produces multiple noisy copies which can be combined to produce better estimates of the original strand; this is called trace reconstruction. One can reduce the error rate further by introducing redundancy in the write sequence and this is called coded trace reconstruction. In this paper, we model the DNA storage channel as an insertion-deletion-substitution (IDS) channel and design both encoding schemes and low-complexity decoding algorithms for coded trace reconstruction. We introduce Trellis BMA, a new reconstruction algorithm whose complexity is linear in the number of traces, and compare its performance to previous algorithms. Our results show that it reduces the error rate on both simulated and experimental data. The performance comparisons in this paper are based on a new dataset of traces that will be publicly released with the paper. Our hope is that this dataset will enable research progress by allowing objective comparisons between candidate algorithms., Comment: Extended version of paper presented at ISIT 2021. On 8/20/2024, in Section III, added a note regarding the dataset of traces released with the paper

This work identifies information-theoretic quantities that are closely related to the required list size on average for successive cancellation list (SCL) decoding to implement maximum-likelihood decoding over general binary memoryless symmetric (BMS) channels. It also provides upper and lower bounds for these quantities that can be computed efficiently for very long codes. For the binary erasure channel (BEC), we provide a simple method to estimate the mean accurately via density evolution. The analysis shows how to modify, e.g., Reed-Muller codes, to improve the performance when practical list sizes, e.g., $L\in[8, 1024]$, are adopted. Exemplary constructions with block lengths $N\in\{128,512\}$ outperform polar codes of 5G over the binary-input additive white Gaussian noise channel. It is further shown that there is a concentration around the mean of the logarithm of the required list size for sufficiently large block lengths, over discrete-output BMS channels. We provide the probability mass functions (p.m.f.s) of this logarithm, over the BEC, for a sequence of the modified RM codes with an increasing block length via simulations, which illustrate that the p.m.f.s concentrate around the estimated mean., Comment: Revised and resubmitted to the IEEE Transactions on Information Theory

In 2018, Renes [IEEE Trans. Inf. Theory, vol. 64, no. 1, pp. 577-592 (2018)] (arXiv:1701.05583) developed a general theory of channel duality for classical-input quantum-output (CQ) channels. That result showed that a number of well-known duality results for linear codes on the binary erasure channel could be extended to general classical channels at the expense of using dual problems which are intrinsically quantum mechanical. One special case of this duality is a connection between coding for error correction (resp. wire-tap secrecy) on the quantum pure-state channel (PSC) and coding for wire-tap secrecy (resp. error correction) on the classical binary symmetric channel (BSC). While this result has important implications for classical coding, the machinery behind the general duality result is rather challenging for researchers without a strong background in quantum information theory. In this work, we leverage prior results for linear codes on PSCs to give an alternate derivation of the aforementioned special case by computing closed-form expressions for the performance metrics. The noted prior results include optimality of the square-root measurement (SRM) for linear codes on the PSC and the Fourier duality of linear codes. We also show that the SRM forms a suboptimal measurement for channel coding on the BSC (when interpreted as a CQ problem) and secret communications on the PSC. Our proofs only require linear algebra and basic group theory, though we use the quantum Dirac notation for convenience., Comment: 26 pages (+4 for appendices), single column, includes essential quantum background; we welcome your comments!

This paper presents a coding scheme for an insertion deletion substitution channel. We extend a previous scheme for the deletion channel where polar codes are modified by adding "guard bands" between segments. In the new scheme, each guard band is comprised of a middle segment of '1' symbols, and left and right segments of '0' symbols. Our coding scheme allows for a regular hidden-Markov input distribution, and achieves the information rate between the input and corresponding output of such a distribution. Thus, we prove that our scheme can be used to efficiently achieve the capacity of the channel. The probability of error of our scheme decays exponentially in the cube-root of the block length., Comment: Submitted to ISIT 2021

We consider near maximum-likelihood (ML) decoding of short linear block codes. In particular, we propose a novel decoding approach based on neural belief propagation (NBP) decoding recently introduced by Nachmani et al. in which we allow a different parity-check matrix in each iteration of the algorithm. The key idea is to consider NBP decoding over an overcomplete parity-check matrix and use the weights of NBP as a measure of the importance of the check nodes (CNs) to decoding. The unimportant CNs are then pruned. In contrast to NBP, which performs decoding on a given fixed parity-check matrix, the proposed pruning-based neural belief propagation (PB-NBP) typically results in a different parity-check matrix in each iteration. For a given complexity in terms of CN evaluations, we show that PB-NBP yields significant performance improvements with respect to NBP. We apply the proposed decoder to the decoding of a Reed-Muller code, a short low-density parity-check (LDPC) code, and a polar code. PB-NBP outperforms NBP decoding over an overcomplete parity-check matrix by 0.27-0.31 dB while reducing the number of required CN evaluations by up to 97%. For the LDPC code, PB-NBP outperforms conventional belief propagation with the same number of CN evaluations by 0.52 dB. We further extend the pruning concept to offset min-sum decoding and introduce a pruning-based neural offset min-sum (PB-NOMS) decoder, for which we jointly optimize the offsets and the quantization of the messages and offsets. We demonstrate performance 0.5 dB from ML decoding with 5-bit quantization for the Reed-Muller code., Comment: Accepted for publication in IEEE Journal on Selected Areas in Communications (J-SAC)

We introduce a two-stage decimation process to improve the performance of neural belief propagation (NBP), recently introduced by Nachmani et al., for short low-density parity-check (LDPC) codes. In the first stage, we build a list by iterating between a conventional NBP decoder and guessing the least reliable bit. The second stage iterates between a conventional NBP decoder and learned decimation, where we use a neural network to decide the decimation value for each bit. For a (128,64) LDPC code, the proposed NBP with decimation outperforms NBP decoding by 0.75 dB and performs within 1 dB from maximum-likelihood decoding at a block error rate of $10^{-4}$.

We propose a new machine-learning approach for fiber-optic communication systems whose signal propagation is governed by the nonlinear Schr\"odinger equation (NLSE). Our main observation is that the popular split-step method (SSM) for numerically solving the NLSE has essentially the same functional form as a deep multi-layer neural network; in both cases, one alternates linear steps and pointwise nonlinearities. We exploit this connection by parameterizing the SSM and viewing the linear steps as general linear functions, similar to the weight matrices in a neural network. The resulting physics-based machine-learning model has several advantages over "black-box" function approximators. For example, it allows us to examine and interpret the learned solutions in order to understand why they perform well. As an application, low-complexity nonlinear equalization is considered, where the task is to efficiently invert the NLSE. This is commonly referred to as digital backpropagation (DBP). Rather than employing neural networks, the proposed algorithm, dubbed learned DBP (LDBP), uses the physics-based model with trainable filters in each step and its complexity is reduced by progressively pruning filter taps during gradient descent. Our main finding is that the filters can be pruned to remarkably short lengths-as few as 3 taps/step-without sacrificing performance. As a result, the complexity can be reduced by orders of magnitude in comparison to prior work. By inspecting the filter responses, an additional theoretical justification for the learned parameter configurations is provided. Our work illustrates that combining data-driven optimization with existing domain knowledge can generate new insights into old communications problems., Comment: 15 pages, 11 figures, submitted to IEEE J. Sel. Areas Commun., code available at https://github.com/chaeger/LDBP, extension of arXiv:1710.06234(1), arXiv:1804.02799(1), arXiv:1901.07592(2)

In this paper, we propose a model-based machine-learning approach for dual-polarization systems by parameterizing the split-step Fourier method for the Manakov-PMD equation. The resulting method combines hardware-friendly time-domain nonlinearity mitigation via the recently proposed learned digital backpropagation (LDBP) with distributed compensation of polarization-mode dispersion (PMD). We refer to the resulting approach as LDBP-PMD. We train LDBP-PMD on multiple PMD realizations and show that it converges within 1% of its peak dB performance after 428 training iterations on average, yielding a peak effective signal-to-noise ratio of only 0.30 dB below the PMD-free case. Similar to state-of-the-art lumped PMD compensation algorithms in practical systems, our approach does not assume any knowledge about the particular PMD realization along the link, nor any knowledge about the total accumulated PMD. This is a significant improvement compared to prior work on distributed PMD compensation, where knowledge about the accumulated PMD is typically assumed. We also compare different parameterization choices in terms of performance, complexity, and convergence behavior. Lastly, we demonstrate that the learned models can be successfully retrained after an abrupt change of the PMD realization along the fiber., Comment: 10 pages, 11 figures, to appear in the IEEE/OSA Journal of Lightwave Technology

Reinforcement learning with neural networks (RLNN) has recently demonstrated great promise for many problems, including some problems in quantum information theory. In this work, we apply RLNN to quantum hypothesis testing and determine the optimal measurement strategy for distinguishing between multiple quantum states $\{ \rho_{j} \}$ while minimizing the error probability. In the case where the candidate states correspond to a quantum system with many qubit subsystems, implementing the optimal measurement on the entire system is experimentally infeasible. We use RLNN to find locally-adaptive measurement strategies that are experimentally feasible, where only one quantum subsystem is measured in each round. We provide numerical results which demonstrate that RLNN successfully finds the optimal local approach, even for candidate states up to 20 subsystems. We additionally demonstrate that the RLNN strategy meets or exceeds the success probability for a modified locally greedy approach in each random trial. While the use of RLNN is highly successful for designing adaptive local measurement strategies, in general a significant gap can exist between the success probability of the optimal locally-adaptive measurement strategy and the optimal collective measurement. We build on previous work to provide a set of necessary and sufficient conditions for collective protocols to strictly outperform locally adaptive protocols. We also provide a new example which, to our knowledge, is the simplest known state set exhibiting a significant gap between local and collective protocols. This result raises interesting new questions about the gap between theoretically optimal measurement strategies and practically implementable measurement strategies., Comment: 21 pages, 14 figures, accepted for publication in Quantum

A product code with single parity-check component codes can be described via the tools of a multi-kernel polar code, where the rows of the generator matrix are chosen according to the constraints imposed by the product code construction. Following this observation, successive cancellation decoding of such codes is introduced. In particular, the error probability of single parity-check product codes over binary memoryless symmetric channels under successive cancellation decoding is characterized. A bridge with the analysis of product codes introduced by Elias is also established for the binary erasure channel. Successive cancellation list decoding of single parity-check product codes is then described. For the provided example, simulations over the binary input additive white Gaussian channel show that successive cancellation list decoding outperforms belief propagation decoding applied to the code graph. Finally, the performance of the concatenation of a product code with a high-rate outer code is investigated via distance spectrum analysis. Examples of concatenations performing within $0.7$ dB from the random coding union bound are provided., Comment: Submitted to the IEEE Transactions on Information Theory. The revised version of the first submission. Major changes: 1) No dedicated section for numerical results. Instead, simulations are provided right after the relevant section. 2) More simulation results are added, including those for the BEC. Comparisons to the state-of-art polar codes and 5G-NR LDPC codes provided

Efficient nonlinearity compensation in fiber-optic communication systems is considered a key element to go beyond the "capacity crunch''. One guiding principle for previous work on the design of practical nonlinearity compensation schemes is that fewer steps lead to better systems. In this paper, we challenge this assumption and show how to carefully design multi-step approaches that provide better performance--complexity trade-offs than their few-step counterparts. We consider the recently proposed learned digital backpropagation (LDBP) approach, where the linear steps in the split-step method are re-interpreted as general linear functions, similar to the weight matrices in a deep neural network. Our main contribution lies in an experimental demonstration of this approach for a 25 Gbaud single-channel optical transmission system. It is shown how LDBP can be integrated into a coherent receiver DSP chain and successfully trained in the presence of various hardware impairments. Our results show that LDBP with limited complexity can achieve better performance than standard DBP by using very short, but jointly optimized, finite-impulse response filters in each step. This paper also provides an overview of recently proposed extensions of LDBP and we comment on potentially interesting avenues for future work., Comment: 10 pages, 5 figures. Author version of a paper published in the Journal of Lightwave Technology. OSA/IEEE copyright may apply

A successive cancellation (SC) decoder with inactivations is proposed as an efficient implementation of SC list (SCL) decoding over the binary erasure channel. The proposed decoder assigns a dummy variable to an information bit whenever it is erased during SC decoding and continues with decoding. Inactivated bits are resolved using information gathered from decoding frozen bits. This decoder leverages the structure of the Hadamard matrix, but can be applied to any linear code by representing it as a polar code with dynamic frozen bits. SCL decoders are partially characterized using density evolution to compute the average number of inactivations required to achieve the maximum a-posteriori decoding performance. The proposed measure quantifies the performance vs. complexity trade-off and provides new insight into dynamics of the number of paths in SCL decoding. The technique is applied to analyze Reed-Muller (RM) codes with dynamic frozen bits. It is shown that these modified RM codes perform close to extended BCH codes., Comment: Accepted at the 2020 ISIT

For space-based laser communications, when the mean photon number per received optical pulse is much smaller than one, there is a large gap between communications capacity achievable with a receiver that performs individual pulse-by-pulse detection, and the quantum-optimal "joint-detection receiver" that acts collectively on long codeword-blocks of modulated pulses; an effect often termed "superadditive capacity". In this paper, we consider the simplest scenario where a large superadditive capacity is known: a pure-loss channel with a coherent-state binary phase-shift keyed (BPSK) modulation. The two BPSK states can be mapped conceptually to two non-orthogonal states of a qubit, described by an inner product that is a function of the mean photon number per pulse. Using this map, we derive an explicit construction of the quantum circuit of a joint-detection receiver based on a recent idea of "belief-propagation with quantum messages" (BPQM) (arXiv:1607.04833). We quantify its performance improvement over the Dolinar receiver that performs optimal pulse-by-pulse detection, which represents the best "classical" approach. We analyze the scheme rigorously and show that it achieves the quantum limit of minimum average error probability in discriminating 8 (BPSK) codewords of a length-5 binary linear code with a tree factor graph. Our result suggests that a BPQM-receiver might attain the Holevo capacity of this BPSK-modulated pure-loss channel. Moreover, our receiver circuit provides an alternative proposal for a quantum supremacy experiment, targeted at a specific application that can potentially be implemented on a small, special-purpose, photonic quantum computer capable of performing cat-basis universal qubit logic., Comment: v2: To appear in npj Quantum Information; see "supplementary_material.pdf" for additional content. Main paper: 22 pages single-column, 11 figures, includes simulations. Comments welcome!

We propose a model-based machine-learning approach for polarization-multiplexed systems by parameterizing the split-step method for the Manakov-PMD equation. This approach performs hardware-friendly DBP and distributed PMD compensation with performance close to the PMD-free case., Comment: 3 pages, 2 figures

We consider near maximum-likelihood (ML) decoding of short linear block codes based on neural belief propagation (BP) decoding recently introduced by Nachmani et al.. While this method significantly outperforms conventional BP decoding, the underlying parity-check matrix may still limit the overall performance. In this paper, we introduce a method to tailor an overcomplete parity-check matrix to (neural) BP decoding using machine learning. We consider the weights in the Tanner graph as an indication of the importance of the connected check nodes (CNs) to decoding and use them to prune unimportant CNs. As the pruning is not tied over iterations, the final decoder uses a different parity-check matrix in each iteration. For Reed-Muller and short low-density parity-check codes, we achieve performance within 0.27 dB and 1.5 dB of the ML performance while reducing the complexity of the decoder., Comment: This work was presented at the IEEE International Symposium on Information Theory (ISIT) 2020

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^{-1}$ 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 arXiv:1910.09333., Comment: This is a shorter version of arXiv:1910.09333. 5 pages main text. Presented at ISIT 2020. Comments welcome!

Discrimination between quantum states is a fundamental task in quantum information theory. Given two arbitrary tensor-product quantum states (TPQS) $\rho_{\pm} = \rho_{\pm}^{(1)} \otimes \cdots \otimes \rho_{\pm}^{(N)}$, determining the joint $N$-system measurement to optimally distinguish between the two states is a hard problem. Thus, there is great interest in identifying local measurement schemes that are optimal or close-to-optimal. In this work, we focus on distinguishing between two general TPQS. We begin by generalizing previous work by Acin et al. (Phys. Rev. A 71, 032338) to show that a locally greedy (LG) scheme using Bayesian updating can optimally distinguish between two states that can be written as tensor products of arbitrary pure states. Then, we show that even in the limit of large $N$ the same algorithm cannot distinguish tensor products of mixed states with vanishing error probability. This poor asymptotic behavior occurs because the Helstrom measurement becomes trivial for sufficiently biased priors. Based on this, we introduce a modified locally greedy (MLG) scheme with strictly better performance. In the second part of this work, we compare these simple local schemes with a general dynamic programming (DP) approach that finds the optimal series of local measurements to distinguish the two states. When the subsystems are non-identical, we demonstrate that the ordering of the systems affects performance and we extend the DP technique to determine the optimal ordering adaptively. Finally, in contrast to the binary optimal collective measurement, we show that adaptive protocols on sufficiently large (e.g., qutrit) subsystems must contain non-binary measurements to be optimal. (The code that produced the simulation results in this paper can be found at: https://github.com/SarahBrandsen/AdaptiveStateDiscrimination), Comment: 21 pages, 8 figures

In order to perform universal fault-tolerant quantum computation, one needs to implement a logical non-Clifford gate. Consequently, it is important to understand codes that implement such gates transversally. In this paper, we adopt an algebraic approach to characterize all stabilizer codes for which transversal $T$ and $T^{-1}$ gates preserve the codespace. Our Heisenberg perspective reduces this to a finite geometry problem that translates to the design of certain classical codes. We prove three corollaries: (a) For any non-degenerate $[[ n,k,d ]]$ stabilizer code supporting a physical transversal $T$, there exists an $[[ n,k,d ]]$ CSS code with the same property; (b) Triorthogonal codes are the most general CSS codes that realize logical transversal $T$ via physical transversal $T$; (c) Triorthogonality is necessary for physical transversal $T$ on a CSS code to realize the logical identity. The main tool we use is a recent efficient characterization of certain diagonal gates in the Clifford hierarchy (arXiv:1902.04022). We refer to these gates as Quadratic Form Diagonal (QFD) gates. Our framework generalizes all existing code constructions that realize logical gates via transversal $T$. We provide several examples and briefly discuss connections to decreasing monomial codes, pin codes, generalized triorthogonality and quasitransversality. We partially extend these results towards characterizing all stabilizer codes that support transversal $\pi/2^{\ell}$ $Z$-rotations. In particular, using Ax's theorem on residue weights of polynomials, we provide an alternate characterization of logical gates induced by transversal $\pi/2^{\ell}$ $Z$-rotations on a family of quantum Reed-Muller codes. We also briefly discuss a general approach to analyze QFD gates that might lead to a characterization of all stabilizer codes that support any given physical transversal $1$- or $2$-local diagonal gate., Comment: v2: Much improved proof for Theorem 2, and some presentation improvements in other proofs. Main sections: 16 pages, double column, IEEEtran style. Examples included. Comments welcome!

Quantum error-correcting codes are used to protect qubits involved in quantum computation. This process requires logical operators, acting on protected qubits, to be translated into physical operators (circuits) acting on physical quantum states. We propose a mathematical framework for synthesizing physical circuits that implement logical Clifford operators for stabilizer codes. Circuit synthesis is enabled by representing the desired physical Clifford operator in $\mathbb{C}^{N \times N}$ as a partial $2m \times 2m$ binary symplectic matrix, where $N = 2^m$. We state and prove two theorems that use symplectic transvections to efficiently enumerate all binary symplectic matrices that satisfy a system of linear equations. As a corollary of these results, we prove that for an $[\![ m,k ]\!]$ stabilizer code every logical Clifford operator has $2^{r(r+1)/2}$ symplectic solutions, where $r = m-k$, up to stabilizer degeneracy. The desired physical circuits are then obtained by decomposing each solution into a product of elementary symplectic matrices, that correspond to elementary circuits. This enumeration of all physical realizations enables optimization over the ensemble with respect to a suitable metric. Furthermore, we show that any circuit that normalizes the stabilizer of the code can be transformed into a circuit that centralizes the stabilizer, while realizing the same logical operation. Our method of circuit synthesis can be applied to any stabilizer code, and this paper discusses a proof of concept synthesis for the $[\![ 6,4,2 ]\!]$ CSS code. Programs implementing the algorithms in this paper, which includes routines to solve for binary symplectic solutions of general linear systems and our overall LCS (logical circuit synthesis) algorithm, can be found at: https://github.com/nrenga/symplectic-arxiv18a, Comment: Main content 12 pages, double column. This is primarily a shortened version of the paper arXiv:1803.06987 based on feedback received, and also has a much more improved introduction. It was presented at ISIT 2018 as well as posters in TQC 2018 and QIP 2019. All comments are welcome!

In this paper, we use reinforcement learning to find effective decoding strategies for binary linear codes. We start by reviewing several iterative decoding algorithms that involve a decision-making process at each step, including bit-flipping (BF) decoding, residual belief propagation, and anchor decoding. We then illustrate how such algorithms can be mapped to Markov decision processes allowing for data-driven learning of optimal decision strategies, rather than basing decisions on heuristics or intuition. As a case study, we consider BF decoding for both the binary symmetric and additive white Gaussian noise channel. Our results show that learned BF decoders can offer a range of performance-complexity trade-offs for the considered Reed-Muller and BCH codes, and achieve near-optimal performance in some cases. We also demonstrate learning convergence speed-ups when biasing the learning process towards correct decoding decisions, as opposed to relying only on random explorations and past knowledge.

This paper presents the first proof of polarization for the deletion channel with a constant deletion rate and a regular hidden-Markov input distribution. A key part of this work involves representing the deletion channel using a trellis and describing the plus and minus polar-decoding operations on that trellis. In particular, the plus and minus operations can be seen as combining adjacent trellis stages to yield a new trellis with half as many stages. Using this viewpoint, we prove a weak polarization theorem for standard polar codes on the deletion channel. To achieve strong polarization, we modify this scheme by adding guard bands of repeated zeros between various parts of the codeword. This gives a scheme whose rate approaches the mutual information and whose probability of error decays exponentially in the cube-root of the block length. We conclude by showing that this scheme can achieve capacity on the deletion channel by proving that the capacity of the deletion channel can be achieved by a sequence of regular hidden-Markov input distributions., Comment: Submitted to the IEEE Transactions on Information Theory. Presented in part at ISIT 2019

For the efficient compensation of fiber nonlinearity, one of the guiding principles appears to be: fewer steps are better and more efficient. We challenge this assumption and show that carefully designed multi-step approaches can lead to better performance-complexity trade-offs than their few-step counterparts., Comment: 4 pages, 3 figures, This is a preprint of a paper submitted to the 2019 European Conference on Optical Communication

The non-linear binary Kerdock codes are known to be Gray images of certain extended cyclic codes of length $N = 2^m$ over $\mathbb{Z}_4$. We show that exponentiating these $\mathbb{Z}_4$-valued codewords by $\imath \triangleq \sqrt{-1}$ produces stabilizer states, that are quantum states obtained using only Clifford unitaries. These states are also the common eigenvectors of commuting Hermitian matrices forming maximal commutative subgroups (MCS) of the Pauli group. We use this quantum description to simplify the derivation of the classical weight distribution of Kerdock codes. Next, we organize the stabilizer states to form $N+1$ mutually unbiased bases and prove that automorphisms of the Kerdock code permute their corresponding MCS, thereby forming a subgroup of the Clifford group. When represented as symplectic matrices, this subgroup is isomorphic to the projective special linear group PSL($2,N$). We show that this automorphism group acts transitively on the Pauli matrices, which implies that the ensemble is Pauli mixing and hence forms a unitary $2$-design. The Kerdock design described here was originally discovered by Cleve et al. (arXiv:1501.04592), but the connection to classical codes is new which simplifies its description and translation to circuits significantly. Sampling from the design is straightforward, the translation to circuits uses only Clifford gates, and the process does not require ancillary qubits. Finally, we also develop algorithms for optimizing the synthesis of unitary $2$-designs on encoded qubits, i.e., to construct logical unitary $2$-designs. Software implementations are available at https://github.com/nrenga/symplectic-arxiv18a, which we use to provide empirical gate complexities for up to $16$ qubits., Comment: 16 pages double-column, 4 figures, and some circuits. Accepted to 2019 Intl. Symp. Inf. Theory (ISIT), and PDF of the 5-page ISIT version is included in the arXiv package

The Clifford hierarchy is a foundational concept for universal quantum computation (UQC). It was introduced to show that UQC can be realized via quantum teleportation, given access to certain standard resources. While the full structure of the hierarchy is still not understood, Cui et al. (arXiv:1608.06596) recently described the structure of diagonal unitaries in the hierarchy. They considered diagonal gates whose action on a computational basis qudit state is described by a $2^k$-th root of unity raised to a polynomial function of the state, and they established the level of such unitaries in the hierarchy. For qubit systems, we consider $k$-th level diagonal gates that can be described just by quadratic forms of the state over the ring $\mathbb{Z}_{2^k}$ of integers mod $2^k$. These involve symmetric matrices over $\mathbb{Z}_{2^k}$ that can be used to efficiently describe all $2$-local and certain higher locality diagonal gates in the hierarchy. We also provide explicit algebraic descriptions of their action on Pauli matrices, which establishes a natural recursion to diagonal gates from lower levels. This involves symplectic matrices over $\mathbb{Z}_{2^k}$ and hence our perspective unifies these gates with the binary symplectic framework for Clifford gates. We augment our description with simple examples for certain standard gates. In addition to demonstrating structure, these formulas might prove useful in applications such as (i) classical simulation of quantum circuits, especially via the stabilizer rank approach, (ii) synthesis of logical non-Clifford unitaries, specifically alternatives to magic state distillation, and (iii) decomposition of arbitrary unitaries beyond the Clifford+$T$ set of gates, perhaps leading to shorter depth circuits. Our results suggest that some non-diagonal gates might be understood by generalizing other binary symplectic matrices to integer rings., Comment: v3: Fixed Theorem 11. v2: Main correction - our framework does not include all diagonal gates but only all 2-local and certain higher-locality ones. All formulas still remain intact. v2 has more examples and remarks for clarity. Abstract updated. PDF marking diff to v1 is included in the package. v1: Presented as a poster in QIP 2019. RevTeX 4.2, 12 pages, two-column, 1 table. Examples included

We consider the weighted belief-propagation (WBP) decoder recently proposed by Nachmani et al. where different weights are introduced for each Tanner graph edge and optimized using machine learning techniques. Our focus is on simple-scaling models that use the same weights across certain edges to reduce the storage and computational burden. The main contribution is to show that simple scaling with few parameters often achieves the same gain as the full parameterization. Moreover, several training improvements for WBP are proposed. For example, it is shown that minimizing average binary cross-entropy is suboptimal in general in terms of bit error rate (BER) and a new "soft-BER" loss is proposed which can lead to better performance. We also investigate parameter adapter networks (PANs) that learn the relation between the signal-to-noise ratio and the WBP parameters. As an example, for the (32,16) Reed-Muller code with a highly redundant parity-check matrix, training a PAN with soft-BER loss gives near-maximum-likelihood performance assuming simple scaling with only three parameters., Comment: 5 pages, 5 figures, submitted to ISIT 2019

Rapid improvements in machine learning over the past decade are beginning to have far-reaching effects. For communications, engineers with limited domain expertise can now use off-the-shelf learning packages to design high-performance systems based on simulations. Prior to the current revolution in machine learning, the majority of communication engineers were quite aware that system parameters (such as filter coefficients) could be learned using stochastic gradient descent. It was not at all clear, however, that more complicated parts of the system architecture could be learned as well. In this paper, we discuss the application of machine-learning techniques to two communications problems and focus on what can be learned from the resulting systems. We were pleasantly surprised that the observed gains in one example have a simple explanation that only became clear in hindsight. In essence, deep learning discovered a simple and effective strategy that had not been considered earlier., Comment: 5 pages, 4 figures, paper presented at ITW 2018, corrected version and updated reference list

We propose a low-complexity sub-banded DSP architecture for digital backpropagation where the walk-off effect is compensated using simple delay elements. For a simulated 96-Gbaud signal and 2500 km optical link, our method achieves a 2.8 dB SNR improvement over linear equalization., Comment: 3 pages, 3 figurs

We study low-complexity iterative decoding algorithms for product codes. We revisit two algorithms recently proposed by the authors based on bounded distance decoding (BDD) of the component codes that improve the performance of conventional iterative BDD (iBDD). We then propose a novel decoding algorithm that is based on generalized minimum distance decoding of the component codes. The proposed algorithm closes over 50% of the performance gap between iBDD and turbo product decoding (TPD) based on the Chase-Pyndiah algorithm. Moreover, the algorithm only leads to a limited increase in complexity with respect to iBDD and has significantly lower complexity than TPD. The studied algorithms are particularly interesting for high-throughput fiber-optic communications.

We consider time-domain digital backpropagation with chromatic dispersion filters jointly optimized and quantized using machine-learning techniques. Compared to the baseline implementations, we show improved BER performance and >40% power dissipation reductions in 28-nm CMOS., Comment: 3 pages, 3 figures, updated reference list, added one sentence in the result section for clarity

We study the problem of finding the smallest set of nodes in a network whose removal results in an empty $k$-core; where the $k$-core is the sub-network obtained after the iterative removal of all nodes of degree smaller than $k$. This problem is also known in the literature as finding the minimal contagious set. The main contribution of our work is an analysis of the performance of the recently introduced corehd algorithm [Scientific Reports, 6, 37954 (2016)] on random networks taken from the configuration model via a set of deterministic differential equations. Our analyses provides upper bounds on the size of the minimal contagious set that improve over previously known bounds. Our second contribution is a new heuristic called the weak-neighbor algorithm that outperforms all currently known local methods in the regimes considered., Comment: 17 pages, 2 figures, 3 tables

Reed-Muller (RM) codes exhibit good performance under maximum-likelihood (ML) decoding due to their highly-symmetric structure. In this paper, we explore the question of whether the code symmetry of RM codes can also be exploited to achieve near-ML performance in practice. The main idea is to apply iterative decoding to a highly-redundant parity-check (PC) matrix that contains only the minimum-weight dual codewords as rows. As examples, we consider the peeling decoder for the binary erasure channel, linear-programming and belief propagation (BP) decoding for the binary-input additive white Gaussian noise channel, and bit-flipping and BP decoding for the binary symmetric channel. For short block lengths, it is shown that near-ML performance can indeed be achieved in many cases. We also propose a method to tailor the PC matrix to the received observation by selecting only a small fraction of useful minimum-weight PCs before decoding begins. This allows one to both improve performance and significantly reduce complexity compared to using the full set of minimum-weight PCs., Comment: 5 pages, 3 figures, accepted for ISIT 2018

An important problem in fiber-optic communications is to invert the nonlinear Schr\"odinger equation in real time to reverse the deterministic effects of the channel. Interestingly, the popular split-step Fourier method (SSFM) leads to a computation graph that is reminiscent of a deep neural network. This observation allows one to leverage tools from machine learning to reduce complexity. In particular, the main disadvantage of the SSFM is that its complexity using M steps is at least M times larger than a linear equalizer. This is because the linear SSFM operator is a dense matrix. In previous work, truncation methods such as frequency sampling, wavelets, or least-squares have been used to obtain "cheaper" operators that can be implemented using filters. However, a large number of filter taps are typically required to limit truncation errors. For example, Ip and Kahn showed that for a 10 Gbaud signal and 2000 km optical link, a truncated SSFM with 25 steps would require 70-tap filters in each step and 100 times more operations than linear equalization. We find that, by jointly optimizing all filters with deep learning, the complexity can be reduced significantly for similar accuracy. Using optimized 5-tap and 3-tap filters in an alternating fashion, one requires only around 2-6 times the complexity of linear equalization, depending on the implementation., Comment: 5 pages, 5 figures, accepted for ISIT 2018

Quantum error-correcting codes can be used to protect qubits involved in quantum computation. This requires that logical operators acting on protected qubits be translated to physical operators (circuits) acting on physical quantum states. We propose a mathematical framework for synthesizing physical circuits that implement logical Clifford operators for stabilizer codes. Circuit synthesis is enabled by representing the desired physical Clifford operator in $\mathbb{C}^{N \times N}$ as a partial $2m \times 2m$ binary symplectic matrix, where $N = 2^m$. We state and prove two theorems that use symplectic transvections to efficiently enumerate all symplectic matrices that satisfy a system of linear equations. As an important corollary of these results, we prove that for an $[\![ m,m-k ]\!]$ stabilizer code every logical Clifford operator has $2^{k(k+1)/2}$ symplectic solutions. The desired physical circuits are then obtained by decomposing each solution as a product of elementary symplectic matrices. Our assembly of the possible physical realizations enables optimization over them with respect to a suitable metric. Furthermore, we show that any circuit that normalizes the stabilizer of the code can be transformed into a circuit that centralizes the stabilizer, while realizing the same logical operation. Our method of circuit synthesis can be applied to any stabilizer code, and this paper provides a proof of concept synthesis of universal Clifford gates for the $[\![ 6,4,2 ]\!]$ CSS code. We conclude with a classical coding-theoretic perspective for constructing logical Pauli operators for CSS codes. Since our circuit synthesis algorithm builds on the logical Pauli operators for the code, this paper provides a complete framework for constructing all logical Clifford operators for CSS codes. Programs implementing our algorithms can be found at https://github.com/nrenga/symplectic-arxiv18a, Comment: Single column, main text: 20 pages, full length with appendices: 32 pages. Includes pseudo-codes for all algorithms. Part of this work has been submitted to the 2018 IEEE International Symposium on Information Theory

Product codes (PCs) protect a two-dimensional array of bits using short component codes. Assuming transmission over the binary symmetric channel, the decoding is commonly performed by iteratively applying bounded-distance decoding to the component codes. For this coding scheme, undetected errors in the component decoding-also known as miscorrections-significantly degrade the performance. In this paper, we propose a novel iterative decoding algorithm for PCs which can detect and avoid most miscorrections. The algorithm can also be used to decode many recently proposed classes of generalized PCs such as staircase, braided, and half-product codes. Depending on the component code parameters, our algorithm significantly outperforms the conventional iterative decoding method. As an example, for double-error-correcting Bose-Chaudhuri-Hocquenghem component codes, the net coding gain can be increased by up to 0.4 dB. Moreover, the error floor can be lowered by orders of magnitude, up to the point where the decoder performs virtually identical to a genie-aided decoder that avoids all miscorrections. We also discuss post-processing techniques that can be used to reduce the error floor even further., Comment: 11 pages, 5 figures, submitted for possible publication to IEEE Transactions on Communications

A neural-network-based approach is presented to efficiently implement digital backpropagation (DBP). For a 32x100 km fiber-optic link, the resulting "learned" DBP significantly reduces the complexity compared to conventional DBP implementations., Comment: 3 pages, 2 figures

We propose a novel decoding algorithm for staircase codes which reduces the effect of undetected component code miscorrections. The algorithm significantly improves performance, while retaining a low-complexity implementation suitable for high-speed optical transport networks., Comment: 3 pages, 2 figures, author version of conference paper, European Conference on Optical Communciation (ECOC), Gothenburg, Sweden, 2017

Lyapunov exponents characterize the chaotic nature of dynamical systems by quantifying the growth rate of uncertainty associated with the imperfect measurement of initial conditions. Finite-time estimates of the exponent, however, experience fluctuations due to both the initial condition and the stochastic nature of the dynamical path. The scale of these fluctuations is governed by the Lyapunov susceptibility, the finiteness of which typically provides a sufficient condition for the law of large numbers to apply. Here, we obtain a formally exact expression for this susceptibility in terms of the Ruelle dynamical zeta function for one-dimensional systems. We further show that, for systems governed by sequences of random matrices, the cycle expansion of the zeta function enables systematic computations of the Lyapunov susceptibility and of its higher-moment generalizations. The method is here applied to a class of dynamical models that maps to static disordered spin chains with interactions stretching over a varying distance, and is tested against Monte Carlo simulations., Comment: 9 pages, 4 figures; v2: minor revisions made. Data relevant to this work can be accessed at http://dx.doi.org/10.7924/G88050N6

This paper considers the fundamental limit of compressed sensing for i.i.d. signal distributions and i.i.d. Gaussian measurement matrices. Its main contribution is a rigorous characterization of the asymptotic mutual information (MI) and minimum mean-square error (MMSE) in this setting. Under mild technical conditions, our results show that the limiting MI and MMSE are equal to the values predicted by the replica method from statistical physics. This resolves a well-known problem that has remained open for over a decade.

For any prime power $q$, Mori and Tanaka introduced a family of $q$-ary polar codes based on $q$~by~$q$ Reed-Solomon polarization kernels. For transmission over a $q$-ary erasure channel, they also derived a closed-form recursion for the erasure probability of each effective channel. In this paper, we use that expression to analyze the finite-length scaling of these codes on the $q$-ary erasure channel with erasure probability $\epsilon\in(0,1)$. Our primary result is that, for any $\gamma>0$ and $\delta>0$, there is a $q_{0}$ such that, for all $q\geq q_{0}$, the fraction of effective channels with erasure rate at most $N^{-\gamma}$ is at least $1-\epsilon-O(N^{-1/2+\delta})$, where $N=q^{n}$ is the blocklength. Since this fraction cannot be larger than $1-\epsilon-O(N^{-1/2})$, this establishes near-optimal finite-length scaling for this family of codes. Our approach can be seen as an extension of a similar analysis for binary polar codes by Hassani, Alishahi, and Urbanke. A similar analysis is also considered for $q$-ary polar codes with $m$ by $m$ polarizing matrices. This separates the effect of the alphabet size from the effect of the matrix size. If the polarizing matrix at each stage is drawn independently and uniformly from the set of invertible $m$ by $m$ matrices, then the linear operator associated with the Lyapunov function analysis can be written in closed form. To prove near-optimal scaling for polar codes with fixed $q$ as $m$ increases, however, two technical obstacles remain. Thus, we conclude by stating two concrete mathematical conjectures that, if proven, would imply near-optimal scaling for fixed~$q$., Comment: Extended version of a paper presented ISIT 2016. Submitted to IEEE Transactions on Information Theory, Oct. 2017

Generalized product codes (GPCs) are extensions of product codes (PCs) where coded bits are protected by two component codes but not necessarily arranged in a rectangular array. It has recently been shown that there exists a large class of deterministic GPCs (including, e.g., irregular PCs, half-product codes, staircase codes, and certain braided codes) for which the asymptotic performance under iterative bounded-distance decoding over the binary erasure channel (BEC) can be rigorously characterized in terms of a density evolution analysis. In this paper, the analysis is extended to the case where transmission takes place over parallel BECs with different erasure probabilities. We use this model to predict the code performance in a coded modulation setup with higher-order signal constellations. We also discuss the design of the bit mapper that determines the allocation of the coded bits to the modulation bits of the signal constellation., Comment: invited and accepted paper for the special session "Recent Advances in Coding for Higher Order Modulation" at the International Symposium on Turbo Codes & Iterative Information Processing, Brest, France, 2016

An upper bound on the feedback capacity of unifilar finite-state channels (FSCs) is derived. A new technique, called the $Q$-contexts, is based on a construction of a directed graph that is used to quantize recursively the receiver's output sequences to a finite set of contexts. For any choice of $Q$-graph, the feedback capacity is bounded by a single-letter expression, $C_\text{fb}\leq \sup I(X,S;Y|Q)$, where the supremum is over $P_{X|S,Q}$ and the distribution of $(S,Q)$ is their stationary distribution. It is shown that the bound is tight for all unifilar FSCs where feedback capacity is known: channels where the state is a function of the outputs, the trapdoor channel, Ising channels, the no-consecutive-ones input-constrained erasure channel and for the memoryless channel. Its efficiency is also demonstrated by deriving a new capacity result for the dicode erasure channel (DEC); the upper bound is obtained directly from the above expression and its tightness is concluded with a general sufficient condition on the optimality of the upper bound. This sufficient condition is based on a fixed point principle of the BCJR equation and, indeed, formulated as a simple lower bound on feedback capacity of unifilar FSCs for arbitrary $Q$-graphs. This upper bound indicates that a single-letter expression might exist for the capacity of finite-state channels with or without feedback based on a construction of auxiliary random variable with specified structure, such as $Q$-graph, and not with i.i.d distribution. The upper bound also serves as a non-trivial bound on the capacity of channels without feedback, a problem that is still open.

The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory that was recently answered in the affirmative for transmission over erasure channels [1], [2]. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. Thus, a natural question is what happens under block-MAP decoding. In [1], [2], by exploiting further symmetries of the code, the bit-MAP threshold was shown to be sharp enough so that the block erasure probability also converges to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as $N^{-\delta}$, for some $\delta>0$. Then, the block-MAP error probability also converges to 0. This technique applies to transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case., Comment: 7 pages, accepted at ISIT'16