Quantum low-density parity-check (QLDPC) codes with asymptotically non-zero rates are prominent candidates for achieving fault-tolerant quantum computation, primarily due to the low operational depth of their syndrome-measurement circuits. Numerous studies advocate the necessity of fast decoders to fully harness the capabilities of QLDPC codes, thus driving the focus towards designing low-complexity iterative decoders. However, empirical investigations indicate that such iterative decoders are susceptible to having a high error floor when decoding QLDPC codes. The main objective of this paper is to analyze the decoding failures of thehypergraph-product(HGP) andlifted-product(LP) codes and to design decoders that mitigate these failures, thus achieving a reduced error floor. The suboptimal performance of these codes can predominantly be ascribed to two structural phenomena: (1) stabilizer-induced trapping sets (TS), which correspond to stabilizer-induced subgraphs in the Tanner graphs, and (2) classical trapping sets (TS), which originate from the classical codes used in the construction of HGP and LP codes. The dynamics of stabilizer-induced TSs are examined, and a straightforward modification of iterative decoders is proposed to circumvent these TSs. Moreover, this work proposes a systematic methodology for designing decoders that can circumvent the classical TSs in both HGP and LP codes by deriving them from decoders capable of avoiding the TSs in the parent classical LDPC codes. When decoders that can avoid stabilizer-induced TSs are run in parallel with those that can mitigate the effect of classical TSs, the logical error rate improves significantly in the error-floor region.

Physical platforms such as trapped ions suffer from coherent noise that does not follow a simple stochastic model. Stochastic errors in quantum systems occur randomly but coherent errors are more damaging since they can accumulate in a particular direction. We consider coherent noise acting transversally, giving rise to an effective error which is a$Z$-rotation on each qubit by some angle$\theta $. Rather than address coherent noise through active error correction, we investigate passive mitigation through decoherence free subspaces. In the language of stabilizer codes, we require the noise to preserve the code space, and to act trivially (as the logical identity operator) on the protected information. Thus, we develop necessary and sufficient conditions for all transversal$Z$-rotations to preserve the code space of a stabilizer code. These conditions require the weight-$2~Z$-stabilizers to cover all the qubits that are in the support of the$X$-component of some stabilizer. Furthermore, the weight-$2~Z$-stabilizers generate a direct product of single-parity-check codes with even block length. By adjusting the sizes of these components, we are able to construct a large family of QECC codes oblivious to coherent noise, one that includes the$[[4L^{2}, 1, 2L]]$Shor codes. The Shor codes are examples of constant excitation codes, where logical qubits are encoded as a code state that is a sum of physical states indexed by binary vectors with the same weight. Constant excitation codes are oblivious to coherent noise since a transversal$Z$-rotation acts as a global phase. We prove that a CSS code is oblivious to coherent noise if and only if it is a constant excitation code, and that if the code is error-detecting, then the (constant) weights in different cosets of the$X$-stabilizers are identical.

Physical platforms such as trapped ions suffer from coherent noise that does not follow a simple stochastic model. We view coherent errors as rotations about a particular axis, and observe that since they can accumulate coherently over time, they can be more damaging. It is natural to consider coherent noise acting transversally giving rise to an effective error, which is a$Z$-rotation on each qubit by some angle$\theta$. Rather than addressing coherent noise through active error correction, we instead investigate passive mitigation through decoherence free subspaces. In the language of stabilizer codes, we require the noise to preserve the code space, and to act trivially (as the logical identity operator) on the protected information. Thus, we develop necessary and sufficient conditions for all transversal$Z$-rotations to preserve the code space of a stabilizer code. These conditions require the existence of a large number of weight 2$Z$-stabilizers, and together, these weight 2$Z$-stabilizers generate a direct product of single-parity-check codes. By adjusting the size of these components, we are able to construct a large family of CSS codes, oblivious to coherent noise, that includes the$[[4L^{2}, 1,2L]]$Shor codes. Given$m$even and given any$[[n, k, d]]$CSS code, we can construct an$[[mn, k, d^{\prime}\geq d]]$CSS code that is oblivious to coherent noise. This result is generalized to stabilizer codes in [Hu, Liang, Rengaswamy, and Calderbank 2020]. The MacWilliams Identities play a central role in the technical analysis, and classical coding theorists may be interested in connections to classical codes with all weights divisible by some integer$d$.

In 2018, Renes [IEEE Trans. Inf. Theory, vol. 64, no. 1, pp. 577-592 (2018)] developed a general theory of channel duality for classical-input quantum-output channels. His result shows that a number of well-known duality results for linear codes on the binary erasure channel can 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 on the quantum pure-state channel (PSC) and coding for wiretap secrecy on the classical binary symmetric channel (BSC). Similarly, coding for error correction on the BSC is related to wire-tap secrecy on the PSC. 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 the optimality of square-root measurement for linear codes on the PSC and the Fourier duality of linear codes.

Discriminating between quantum states is a fundamental task in quantum information theory. Given two quantum states, ρ+and ρ-, the Helstrom measurement distinguishes between them with minimal probability of error. However, finding and experimentally implementing the Helstrom measurement can be challenging for quantum states on many qubits. Due to this difficulty, there is a great interest in identifying local measurement schemes which are close to optimal. In the first part of this work, we generalize previous work by Acin et al. (Phys. Rev. A 71, 032338) and show that a locally greedy (LG) scheme using Bayesian updating can optimally distinguish between any two states that can be written as a tensor product of arbitrary pure states. We then show that the same algorithm cannot distinguish tensor products of mixed states with vanishing error probability (even in a large subsystem limit), and 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. The DP approach finds the optimal series of local measurements and optimal order of subsystem measurement to distinguish between the two tensor-product states.1

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.

Quantum technologies are maturing by the day and their near-term applications are now of great interest. Deep-space optical communication involves transmission over the pure-state classical-quantum channel. For optimal detection, a joint measurement on all output qubits is required in general. Since this is hard to realize, current (sub-optimal) schemes perform symbol-by-symbol detection followed by classical post-processing. In this paper we focus on a recently proposed belief propagation algorithm by Renes that passes qubit messages on the factor graph of a classical error-correcting code. More importantly, it only involves single-qubit Pauli measurements during the process. For an example 5-bit code, we analyze the involved density matrices and calculate the error probabilities on this channel. Then we numerically compute the optimal joint detection limit using the Yuen-Kennedy-Lax conditions and demonstrate that the calculated error probabilities for this algorithm appear to achieve this limit. This represents a first step towards achieveing quantum communication advantage. We verify our analysis using Monte-Carlo simulations in practice.

The non-linear binary Kerdock codes are known to be Gray images of certain extended cyclic codes of length codewords by △ z √-1 produces stabilizer states, that are N = 2 over Z4. We show that exponentiating these Z4-valued 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. (2016), 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.

The binary non-linear Kerdock codes are Gray images of Z4-linear Kerdock codes of length N = 2m. We show that exponentiating z = √-1 by these Z4-valued codewords produces stabilizer states, which are the common eigenvectors of maximal commutative subgroups (MCS) of the Pauli group. We use this quantum description to simplify the proof of the classical weight distribution of Kerdock codes. Next, we partition stabilizer states into N + 1 mutually unbiased bases and prove that automorphisms of the Kerdock code permute the associated MCS. This automorphism group, represented as symplectic matrices, is isomorphic to the projective special linear group PSL(2, N) and forms a unitary 2-design. The design described here was originally discovered by Cleve et al. (2016), but the connection to classical codes is new. This significantly simplifies the description of the design and its translation to circuits.

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 CN×Nas a 2m×2m binary sym-plectic matrix, where N=2m. We show that for an [[ m, m-k ]] stabilizer code every logical Clifford operator has 2k(k+1)/2symplectic solutions, and we enumerate them efficiently using symplectic transvections. The desired circuits are then obtained by writing each of the solutions as a product of elementary symplectic matrices. For a given operator, our assembly of all of its physical realizations enables optimization over them with respect to a suitable metric. 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 well-known [[ 6,4,2 ]] code. Programs implementing our algorithms can be found at https://github.com/nrenga/symplectic-arxiv18a.

Regular spatially-coupled low-density parity-check ensembles have gained significant interest, since they were shown to universally achieve the capacity of binary memoryless channels under low-complexity belief-propagation decoding. In this paper, we focus primarily on the performance of these ensembles over binary channels affected by bursts of erasures. We first develop an analysis of the finite length performance for a single burst per code word and no errors otherwise. We first assume that the burst erases a complete spatial position, modeling for instance node failures in distributed storage. We provide new tight lower bounds for the block erasure probability (PB) at finite block length and bounds on the coupling parameter for being asymptotically able to recover the burst. We further show that expurgating the ensemble can improve the block erasure probability by several orders of magnitude. Later we extend our methodology to more general channel models. In a first extension, we consider bursts that can start at a random location in the code word and span across multiple spatial positions. Besides the finite length analysis, we determine by means of density evolution the maximum correctable burst length. In a second extension, we consider the case where in addition to a single burst, random bit erasures may occur. Finally, we consider a block erasure channel model which erases each spatial position independently with some probability p, potentially introducing multiple bursts simultaneously. All results are verified using Monte-Carlo simulations.

Arikan introduced polar codes in 2009 and proved that they achieve the symmetric capacity, under low-complexity successive cancellation decoding, of any binary-input discrete memoryless channel. Arikan's construction is based on the Kronecker product of 2-by-2 matrices and it was extended to larger matrices by ŗaşoğlu et al. in 2010. In this paper, we construct cyclic polar codes based on a mixed-radix Cooley-Tukey decomposition of the Galois field Fourier transform. Ignoring the twiddle factors between stages, the derived fast Fourier transform is essentially a Kronecker product of small Fourier transform matrices. Thus, one can define a successive cancellation decoder and observe that the coordinate channels polarize. Choosing the locations of the frozen symbols in the resulting polar code is identical to choosing the locations of zeros in the Fourier transform of the codewords and, thus, the code is cyclic.