More Like this

1. 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
2. Designing the Quantum Channels Induced by Diagonal Gates

   https://doi.org/10.22331/q-2022-09-08-802  

   Hu, Jingzhen; Liang, Qingzhong; Calderbank, Robert (September 2022, Quantum)

   The challenge of quantum computing is to combine error resilience with universal computation. Diagonal gates such as the transversal T gate play an important role in implementing a universal set of quantum operations. This paper introduces a framework that describes the process of preparing a code state, applying a diagonal physical gate, measuring a code syndrome, and applying a Pauli correction that may depend on the measured syndrome (the average logical channel induced by an arbitrary diagonal gate). It focuses on CSS codes, and describes the interaction of code states and physical gates in terms of generator coefficients determined by the induced logical operator. The interaction of code states and diagonal gates depends very strongly on the signs of Z -stabilizers in the CSS code, and the proposed generator coefficient framework explicitly includes this degree of freedom. The paper derives necessary and sufficient conditions for an arbitrary diagonal gate to preserve the code space of a stabilizer code, and provides an explicit expression of the induced logical operator. When the diagonal gate is a quadratic form diagonal gate (introduced by Rengaswamy et al.), the conditions can be expressed in terms of divisibility of weights in the two classical codes that determine the CSS code. These codes find application in magic state distillation and elsewhere. When all the signs are positive, the paper characterizes all possible CSS codes, invariant under transversal Z -rotation through π / 2 l , that are constructed from classical Reed-Muller codes by deriving the necessary and sufficient constraints on l . The generator coefficient framework extends to arbitrary stabilizer codes but there is nothing to be gained by considering the more general class of non-degenerate stabilizer codes. 

   more » « less
3. Quantum codes and irreducible products of characters

   https://doi.org/10.1007/s10623-025-01599-8  

   Kubischta, Eric; Teixeira, Ian (April 2025, Designs, Codes and Cryptography)

   Abstract In a recent paper, we defined a type of weighted unitary design called a twisted unitary 1-group and showed that such a design automatically induced error-detecting quantum codes. We also showed that twisted unitary 1-groups correspond to irreducible products of characters thereby reducing the problem of code-finding to a computation in the character theory of finite groups. Using a combination of GAP computations and results from the mathematics literature on irreducible products of characters, we identify many new non-trivial quantum codes with unusual transversal gates. Transversal gates are of significant interest to the quantum information community for their central role in fault tolerant quantum computing. Most unitary$$\text {t}$$ $\text{t}$-designs have never been realized as the transversal gate group of a quantum code. We, for the first time, find nontrivial quantum codes realizing nearly every finite group which is a unitary 2-design or better as the transversal gate group of some error-detecting quantum code. 

   more » « less
4. CSS codes that are oblivious to coherent noise

   https://doi.org/10.1109/ISIT45174.2021.9518206  

   Hu, J.: Liang; Rengaswamy, N.; Calderbank, R (July 2021, IEEE International Symposium on Information Theory)

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

   more » « less
5. Pseudorandom Linear Codes Are List-Decodable to Capacity

   Putterman, Aaron; Pyne, Edward (January 2024, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024)

   We introduce a novel family of expander-based error correcting codes. These codes can be sampled with randomness linear in the block-length, and achieve list decoding capacity (among other local properties). Our expander-based codes can be made starting from any family of sufficiently low-bias codes, and as a consequence, we give the first construction of a family of algebraic codes that can be sampled with linear randomness and achieve list-decoding capacity. We achieve this by introducing the notion of a pseudorandom puncturing of a code, where we select n indices of a base code C ⊂ 𝔽_q^m in a correlated fashion. Concretely, whereas a random linear code (i.e. a truly random puncturing of the Hadamard code) requires O(n log(m)) random bits to sample, we sample a pseudorandom linear code with O(n + log (m)) random bits by instantiating our pseudorandom puncturing as a length n random walk on an exapnder graph on [m]. In particular, we extend a result of Guruswami and Mosheiff (FOCS 2022) and show that a pseudorandom puncturing of a small-bias code satisfies the same local properties as a random linear code with high probability. As a further application of our techniques, we also show that pseudorandom puncturings of Reed-Solomon codes are list-recoverable beyond the Johnson bound, extending a result of Lund and Potukuchi (RANDOM 2020). We do this by instead analyzing properties of codes with large distance, and show that pseudorandom puncturings still work well in this regime. 

   more » « less