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.
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.
Quantum information science strives to leverage the quantum-mechanical nature of our universe in order to achieve large improvements in certain information processing tasks. In deep-space optical communications, current receivers for the pure-state classical-quantum channel first measure each qubit channel output and then classically post-process the measurements. This approach is sub-optimal. In this dissertation we investigate a recently proposed quantum algorithm for this task, which is inspired by classical belief-propagation algorithms, and analyze its performance on a simple 5-bit code. We show that the algorithm is optimal for each bit and it appears to achieve optimal performance when deciding the full transmitted message. We also provide explicit circuits for the algorithm in terms of standard gates. This suggests a near-term quantum communication advantage over the aforementioned sub-optimal scheme. Quantum error correction is vital to building a universal fault-tolerant quantum computer. We propose an efficient algorithm that can translate a given logical Clifford operation on a stabilizer code into all (equivalence classes of) physical Clifford circuits that realize that operation. In order to achieve universality, one also needs to implement at least one non-Clifford logical operation. So, we develop a mathematical framework for a large subset of diagonal operations in the Clifford hierarchy, which we call Quadratic Form Diagonal (QFD) gates. Then we use the QFD formalism to characterize all stabilizer codes whose code spaces are preserved under the transversal action of the non-Clifford T gates on the physical qubits. We also discuss a few purely-classical coding problems motivated by transversal T gates. A conscious effort has been made to keep this dissertation self-contained, by including necessary background material on quantum information and computation.
Recently, Renes proposed a quantum algorithm called belief propagation with quantum messages (BPQM) for decoding classical data encoded using a binary linear code with tree Tanner graph that is transmitted over a pure-state CQ channel \cite{renes_2017}, i.e., a channel with classical input and pure-state quantum output. The algorithm presents a genuine quantum counterpart to decoding based on the classical belief propagation algorithm, which has found wide success in classical coding theory when used in conjunction with LDPC or Turbo codes. More recently Rengaswamy et al. \cite{rengaswamy_2020} observed that BPQM implements the optimal decoder on a small example code, in that it implements the optimal measurement that distinguishes the quantum output states for the set of input codewords with highest achievable probability. Here we significantly expand the understanding, formalism, and applicability of the BPQM algorithm with the following contributions. First, we prove analytically that BPQM realizes optimal decoding for any binary linear code with tree Tanner graph. We also provide the first formal description of the BPQM algorithm in full detail and without any ambiguity. In so doing, we identify a key flaw overlooked in the original algorithm and subsequent works which implies quantum circuit realizations will be exponentially large in the code dimension. Although BPQM passes quantum messages, other information required by the algorithm is processed globally. We remedy this problem by formulating a truly message-passing algorithm which approximates BPQM and has quantum circuit complexity O(poly n,polylog 1ϵ) , where n is the code length and ϵ is the approximation error. Finally, we also propose a novel method for extending BPQM to factor graphs containing cycles by making use of approximate cloning. We show some promising numerical results that indicate that BPQM on factor graphs with cycles can significantly outperform the best possible classical decoder.
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---measured in bits communicated per pulse---achievable with a receiver that detects (converts from optical to electrical domain) each modulated pulse one at a time, versus with the quantum-optimal joint-detection receiver that acts on a long codeword comprised of n modulated pulses; an effect often termed superadditive capacity. The action of this receiver cannot be described as the detection of each individual pulse, interspersed with classical feedforward and soft-information post-processing. 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 single qubit, described by an inner product that is a function of the mean photon number of each BPSK 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 analyze this 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. We quantify its performance improvement over the (Dolinar) receiver that optimally detects one pulse at a time. Our result suggests that a BPQM-receiver might attain the Holevo capacity, the quantum limit of classical communication capacity, of this BPSK-modulated pure-loss channel. This suggests a new application for a small, special-purpose, photonic quantum computer capable of so-called cat-basis universal qubit logic.
Abstract 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). 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.
Belief propagation with quantum messages (BPQM) provides a low-complexity alternative to collective measurements for communication over classical--quantum channels. Prior BPQM constructions and density-evolution (DE) analyses have focused on binary alphabets. Here, we generalize BPQM to symmetric q-ary pure-state channels (PSCs) whose output Gram matrix is circulant. For this class, we show that bit-node and check-node combining can be tracked efficiently via closed-form recursions on the Gram-matrix eigenvalues, independent of the particular physical realization of the output states. These recursions yield explicit BPQM unitaries and analytic bounds on the fidelities of the combined channels in terms of the input-channel fidelities. This provides a DE framework for symmetric q-ary PSCs that allows one to estimate BPQM decoding thresholds for LDPC codes and to construct polar codes on these channels.
Demonstrations of quantum advantage have largely focused on computational speedups and on quantum simulation of many-body physics, limited by fidelity and the capability of current devices. Discriminating laser-pulse-modulated classical-communication code words at the minimum allowable probability of error using universal-quantum processing presents a promising parallel direction, one that is of both fundamental importance in quantum state discrimination and technological relevance in deep-space laser communications. Here we present an experimental realization of a quantum joint detection receiver for binary phase shift keying modulated code words of a 3-bit linear tree code using a recently proposed quantum algorithm: belief propagation with quantum messages. The receiver, translated to a quantum circuit, was experimentally implemented on a trapped-ion device---the recently released Honeywell LT-1.0 system using 171Yb+ ions, which possesses all-to-all connectivity and midcircuit measurement capabilities that are essential to this demonstration. We conclusively realize a previously postulated but hitherto not demonstrated joint quantum detection scheme and provide an experimental framework that surpasses the quantum limit on the minimum average decoding error probability associated with pulse-by-pulse detection in the low-mean-photon-number limit. The full joint detection scheme bridges across photonic and trapped-ion-based quantum information science, mapping the photonic coherent states of the modulation alphabet onto inner product-preserving states of single-ion qubits. Looking ahead, our work opens new avenues in hybrid realizations of quantum-enhanced receivers with applications in astronomy and emerging space-based platforms.