Browsing by Author "Calderbank, Robert"

Filter results by typing the first few letters
Now showing 1 - 5 of 5
  • Codebooks of Complex Lines Based on Binary Subspace Chirps
    (2019-08-01) Tirkkonen, Olav; Calderbank, Robert
     A4 Artikkeli konferenssijulkaisussa
    Motivated by problems in machine-type wireless communications, we consider codebooks of complex Grassmannian lines in N = 2m dimensions. Binary Chirp (BC) codebooks of prior art are expanded to codebooks of Binary Subspace Chirps (BSSCs), where there is a binary chirp in a subset of the dimensions, while in the remaining dimensions there is a zero. BSSC codebooks have the same minimum distance as BC codebooks, while the cardinality is asymptotically 2.38 times larger. We discuss how BC codebooks can be understood in terms of a subset of the binary symplectic group Sp(2m, 2) in 2m dimensions; Sp(2m, 2) is isomorphic to a quotient group of the Clifford group acting on the codewords in N dimensions. The Bruhat decomposition of Sp(2m, 2) can be described in terms of binary subspaces in m dimensions, with ranks ranging from r=0 to r=m. We provide a unique parameterization of the decomposition. The BCs arise directly from the full-rank part of the decomposition, while BSSCs are a group code arising from the action of the full group with generic r. The rank of the binary subspace is directly related to the number of zeros (sparsity) in the BSSC. We develop a reconstruction algorithm that finds the correct codeword with O(N log2N) complexity, and present performance results in an additive white Gaussian noise scenario.
  • Low-Complexity Grassmannian Quantization Based on Binary Chirps
    (2022-05-16) Pllaha, Tefjol; Heikkila, Elias; Calderbank, Robert; Tirkkonen, Olav
     A4 Artikkeli konferenssijulkaisussa
    We consider autocorrelation-based low-complexity decoders for identifying Binary Chirp codewords from noisy signals in N = 2m dimensions. The underlying algebraic structure enables dimensionality reduction from N complex to m binary di- mensions, which can be used to reduce decoding complexity, when decoding is successively performed in the m binary dimensions. Existing low-complexity decoders suffer from poor performance in scenarios with strong noise. This is problematic especially in a vector quantization scenario, where quantization noise power cannot be controlled in the system. We construct two improvements to existing algorithms; a geometrically inspired algorithm based on successive projections, and an algorithm based on adaptive decoding order selection. When combined with a breadth-first list decoder, these algorithms make it possible to approach the performance of exhaustive search with low complexity.
  • Performance Analysis of Binary Chirp Decoding
    (2023) Bayanifar, Mahdi; Calderbank, Robert; Tirkkonen, Olav
     A4 Artikkeli konferenssijulkaisussa
    Binary Chirp (BC) codebooks consist of N(log2N + 3)/2 lines in CN, equivalent up to overall phase rotations. Exploiting the underlying algebraic structure, the BCs allow suboptimal decoders with complexity N(logN)2, based on autocorrelations between the received signal and its permuted versions. We analyze the performance of these decoders in additive white Gaussian noise channels, providing lower bounds of decoding error probability, which are tight in the limits of low and high signal-to-noise ratio. Due to the autocorrelation nature of the receiver, the error probability becomes a function of order statistics of χ2-distributed random variables. Our results can be used when dimensioning communication systems where BCs are used as component codes.
  • Reconstruction of Multi-user Binary Subspace Chirps
    (2020-06) Pllaha, Tefjol; Tirkkonen, Olav; Calderbank, Robert
     A4 Artikkeli konferenssijulkaisussa
    We consider codebooks of Complex Grassmannian Lines consisting of Binary Subspace Chirps (BSSCs) in N =2m 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 onoff 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.
  • Un-Weyl-ing the Clifford hierarchy
    (2020-12-09) Pllaha, Tefjol; Rengaswamy, Narayanan; Tirkkonen, Olav; Calderbank, Robert
     A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
    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.