  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.
