Search

Iterative decoder failures of quantum low density parity check (QLDPC) codes are attributed to substructures in the code's graph, known as trapping sets, as well as degenerate errors that can arise in quantum codes. Failure inducing sets are subsets of codeword coordinates that, when initially in error, lead to decoding failure in a trapping set. The purpose of this paper is to examine failure inducing sets of QLDPC codes under syndrome-based iterative decoding. As for classical LDPC codes, we show that absorbing sets play a central role in understanding decoder failures. Raveendran and Vasi\~c initiated the study of quantum trapping sets, where beyond the classical-type trapping sets, they identified rigid symmetric structures (a.k.a symmetric stabilizers) responsible for degenerate errors. In this paper, we show that this behavior is part of a much more general phenomenon that can be described by the absorbing set framework.

Linear computations over quantum many-to-one communication networks offer opportunities for communication cost improvements through schemes that exploit quantum entanglement among transmitters to achieve superdense coding gains, combined with classical techniques such as interference alignment. The problem becomes much more broadly accessible if suitable abstractions can be found for the underlying quantum functionality via classical black box models. This work formalizes such an abstraction in the form of an "$N$-sum box", a black box generalization of a two-sum protocol of Song \emph{et al.} with recent applications to $N$-server private information retrieval. The $N$-sum box has a communication cost of $N$ qudits and classical output of a vector of $N$ $q$-ary digits linearly dependent (via an $N \times 2N$ transfer matrix) on $2N$ classical inputs distributed among $N$ transmitters. We characterize which transfer matrices are feasible by our construction, both with and without the possibility of additional locally invertible classical operations at the transmitters and receivers. Furthermore, we provide a sample application to Cross-Subspace Alignment (CSA) schemes to obtain efficient instances of Quantum Private Information Retrieval (QPIR) and Quantum Secure Distributed Batch Matrix Multiplication (QSDBMM). We first describe $N$-sum boxes based on maximal stabilizers and we then consider non-maximal-stabilizer-based constructions to obtain an instance of Quantum Symmetric Private Information Retrieval.

We consider high-dimensional MIMO transmissions in frequency division duplexing (FDD) systems. For precoding, the frequency selective channel has to be measured, quantized and fed back to the base station by the users. When the number of antennas is very high this typically leads to prohibitively high quantization complexity and large feedback. In 5G New Radio (NR), a modular quantization approach has been applied for this, where first a low-dimensional subspace is identified for the whole frequency selective channel, and then subband channels are linearly mapped to this subspace and quantized. We analyze how the components in such a modular scheme contribute to the overall quantization distortion. Based on this analysis we improve the technology components in the modular approach and propose an orthonormalized wideband precoding scheme and a sequential wideband precoding approach which provide considerable gains over the conventional method. We compare the performance of the developed quantization schemes to prior art by simulations in terms of the projection distortion, overall distortion and spectral efficiency, in a scenario with a realistic spatial channel model., Comment: 15 pages,9 figures, to appear in TWC

In quantum private information retrieval (QPIR), a user retrieves a classical file from multiple servers by downloading quantum systems without revealing the identity of the file. The QPIR capacity is the maximal achievable ratio of the retrieved file size to the total download size. In this paper, the capacity of QPIR from MDS-coded and colluding servers is studied for the first time. Two general classes of QPIR, called stabilizer QPIR and dimension-squared QPIR induced from classical strongly linear PIR are defined, and the related QPIR capacities are derived. For the non-colluding case, the general QPIR capacity is derived when the number of files goes to infinity. A general statement on the converse bound for QPIR with coded and colluding servers is derived showing that the capacities of stabilizer QPIR and dimension-squared QPIR induced from any class of PIR are upper bounded by twice the classical capacity of the respective PIR class. The proposed capacity-achieving scheme combines the star-product scheme by Freij-Hollanti et al. and the stabilizer QPIR scheme by Song et al. by employing (weakly) self-dual Reed--Solomon codes., Comment: This work extends arXiv:2102.02511

We describe in details the interplay between binary symplectic geometry and quantum computation, with the ultimate goal of constructing highly structured codebooks. The Binary Chirps (BCs) are Complex Grassmannian Lines in $N = 2^m$ dimensions used in deterministic compressed sensing and random/unsourced multiple access in wireless networks. Their entries are fourth roots of unity and can be described in terms of second order Reed-Muller codes. The Binary Subspace Chirps (BSSCs) are a unique collection of BCs of $\textit{ranks}$ ranging from $r=0$ to $r = m$, embedded in $N$ dimensions according to an on-off pattern determined by a rank $r$ binary subspace. This yields a codebook that is asymptotically 2.38 times larger than the codebook of BCs, has the same minimum chordal distance as the codebook of BCs, and the alphabet is minimally extended from $\{\pm 1,\pm i\}$ to $\{\pm 1,\pm i, 0\}$. Equivalently, we show that BSSCs are stabilizer states, and we characterize them as columns of a well-controlled collection of Clifford matrices. By construction, the BSSCs inherit all the properties of BCs, which in turn makes them good candidates for a variety of applications. For applications in wireless communication, we use the rich algebraic structure of BSSCs to construct a low complexity decoding algorithm that is reliable against Gaussian noise. In simulations, BSSCs exhibit an error probability comparable or slightly lower than BCs, both for single-user and multi-user transmissions., Comment: arXiv admin note: text overlap with arXiv:2005.07900

In fault-tolerant quantum computation and quantum error-correction one is interested on Pauli matrices that commute with a circuit/unitary. We provide a fast algorithm that decomposes any Clifford gate as a $\textit{minimal}$ product of Clifford transvections. The algorithm can be directly used for finding all Pauli matrices that commute with any given Clifford gate. To achieve this goal, we exploit the structure of the symplectic group with a novel graphical approach.

In the classical private information retrieval (PIR) setup, a user wants to retrieve a file from a database or a distributed storage system (DSS) without revealing the file identity to the servers holding the data. In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. The QPIR problem has been treated by Song et al. in the case of replicated servers, both with and without collusion. QPIR over $[n,k]$ maximum distance separable (MDS) coded servers was recently considered by Allaix et al., but the collusion was essentially restricted to $t=n-k$ servers in the sense that a smaller $t$ would not improve the retrieval rate. In this paper, the QPIR setting is extended to allow for retrieval with high rate for any number of colluding servers $t$ with $1 \leq t \leq n-k$. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts, as well as those of the previously proposed coded and colluding QPIR schemes. This is enabled by considering the stabilizer formalism and weakly self-dual generalized Reed--Solomon (GRS) star product codes.

The teleportation model of quantum computation introduced by Gottesman and Chuang (1999) motivated the development of the Clifford hierarchy. Despite its intrinsic value for quantum computing, the widespread use of magic state distillation, which is closely related to this model, emphasizes the importance of comprehending the hierarchy. There is currently a limited understanding of the structure of this hierarchy, apart from the case of diagonal unitaries (Cui et al., 2017; Rengaswamy et al. 2019). We explore the structure of the second and third levels of the hierarchy, the first level being the ubiquitous Pauli group, via the Weyl (i.e., Pauli) expansion of unitaries at these levels. In particular, we characterize the support of the standard Clifford operations on the Pauli group. Since conjugation of a Pauli by a third level unitary produces traceless Hermitian Cliffords, we characterize their Pauli support as well. Semi-Clifford unitaries are known to have ancilla savings in the teleportation model, and we explore their Pauli support via symplectic transvections. Finally, we show that, up to multiplication by a Clifford, every third level unitary commutes with at least one Pauli matrix. This can be used inductively to show that, up to a multiplication by a Clifford, every third level unitary is supported on a maximal commutative subgroup of the Pauli group. Additionally, it can be easily seen that the latter implies the generalized semi-Clifford conjecture, proven by Beigi and Shor (2010). We discuss potential applications in quantum error correction and the design of flag gadgets., Comment: License changed. Accepted to Quantum on 26 Nov 2020

We consider codebooks of Complex Grassmannian Lines consisting of Binary Subspace Chirps (BSSCs) in $N = 2^m$ dimensions. BSSCs are generalizations of Binary Chirps (BCs), their entries are either fourth-roots of unity, or zero. BSSCs consist of a BC in a non-zero subspace, described by an on-off pattern. Exploring the underlying binary symplectic geometry, we provide a unified framework for BSSC reconstruction---both on-off pattern and BC identification are related to stabilizer states of the underlying Heisenberg-Weyl algebra. In a multi-user random access scenario we show feasibility of reliable reconstruction of multiple simultaneously transmitted BSSCs with low complexity., Comment: To appear in IEEE ISIT 2020

In the classical private information retrieval (PIR) setup, a user wants to retrieve a file from a database or a distributed storage system (DSS) without revealing the file identity to the servers holding the data. In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. The QPIR problem has been treated by Song \emph{et al.} in the case of replicated servers, both without collusion and with all but one servers colluding. In this paper, the QPIR setting is extended to account for maximum distance separable (MDS) coded servers. The proposed protocol works for any $[n,k]$-MDS code and $t$-collusion with $t=n-k$. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts. Further, it is demonstrated how the protocol can adapted to achieve significantly higher retrieval rates from DSSs encoded with a locally repairable code (LRC) with disjoint repair groups, each of which is an MDS code.

This paper further investigates \emph{Laplacian simplices}. A construction by Braun and the first author associates to a simple connected graph $G$ a simplex $\cP_G$ whose vertices are the rows of the Laplacian matrix of $G$. In this paper we associate to a reflexive $\cP_G$ a duality-preserving linear code $\cC(\cP_G)$. This new perspective allows us to build upon previous results relating graphical properties of $G$ to properties of the polytope $\cP_G$. In particular, we make progress towards a graphical characterization of reflexive $\cP_G$ using techniques from Ehrhart theory. We provide a systematic investigation of $\cC(\cP_G)$ for cycles, complete graphs, and graphs with a prime number of vertices. We construct an asymptotically good family of MDS codes. In addition, we show that any rational rate is achievable by such construction.

In this paper we study the equivalence of quantum stabilizer codes via symplectic isometries of stabilizer codes. We define monomially and symplectically equivalent stabilizer codes and determine how different the two notions can be. Further, we show that to monomial maps correspond local Clifford operators. We relate the latter with the LU-LC Conjecture.

In this paper we consider stabilizer codes over local Frobenius rings. First, we study the relative minimum distances of a stabilizer code and its reduction onto the residue field. We show that for various scenarios, a free stabilizer code over the ring does not underperform the according stabilizer code over the field. This leads us to conjecture that the same is true for all free stabilizer codes. Secondly, we focus on the isometries of stabilizer codes. We present some preliminary results and introduce some interesting open problems.

In this paper we study codes where the alphabet is a finite Frobenius bimodule over a finite ring. We discuss the extension property for various weight functions. Employing an entirely character-theoretic approach and a duality theory for partitions on Frobenius bimodules we derive alternative proofs for the facts that the Hamming weight and the homogeneous weight satisfy the extension property. We also use the same techniques to derive the extension property for other weights, such as the Rosenbloom-Tsfasman weight.