Browsing by Author "Pfister, Henry D"

High-dimensional probability distributions are important objects in a wide variety of applications for example, most prediction and inference applications focus on computing the posterior marginal of a subset of variables conditioned on observations of another subset of variables. In practice, this is untractable due to the curse of dimensionality. In some problems, high-dimensional joint probability distributions can be represented by factor graphs. For such problems, belief propagation (BP) is a polynomial-time algorithm that provides an efficient approximation of the posterior marginals, and it is exact if the factor graph does not contain cycles. With rapid improvements in machine learning over the past decade, using machine learning techniques to optimize system parameters is an emerging field in communication research.

This thesis considers applying BP for communication systems, and focuses on incorporating domain knowledge into machine learning models. For compressive sensing, two variants of relaxed belief propagation (RBP) algorithm are proposed. One improves the stability over a larger class of measurement matrices and the other reduces the computational complexity when measurement matrix is in the product of several sparse matrices. For optical communication, the non-linear Schrodinger equation is solved by modeling the signal in each step of split-step Fourier method as a multivariate complex Gaussian distribution. Then, the parameters of the Gaussian are tracked through in digital back-propagation. For recursive decoding for Reed–Muller codes, the algebraic structure of the code is utilized and a recursive BP approach for redundant factor graphs is developed for near-optimal decoding. Finally, we use deep unfolding to unroll BP decoding as a recursive neural network and introduce the idea of a the parameter adaptive network to learn the relation between channel SNR and optimal BP weight factors.

Quantum information science strives to leverage the quantum-mechanical nature of our universe in order to achieve large improvements in certain information processing tasks. Such tasks include quantum communications and fault-tolerant quantum computation. In this dissertation, we make contributions to both of these applications.

In deep-space optical communications, the mathematical abstraction of the binary phase shift keying (BPSK) modulated pure-loss optical channel is called the pure-state channel. It takes classical inputs and delivers quantum outputs that are pure (qubit) states. To achieve optimal information transmission, if classical error-correcting codes are employed over this channel, then one needs to develop receivers that collectively measure all output qubits in order to optimally identify the transmitted message. In general, it is hard to determine these optimal collective measurements and even harder to realize them in practice. So, current receivers first measure each qubit channel output and then classically post-process the measurements. This approach is sub-optimal. 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 makes optimal decisions for the value of 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. For deep-space optical communications, this suggests a near-term quantum advantage over the aforementioned sub-optimal scheme. Such a communication advantage appears to be the first of its kind.

Quantum error correction is vital to building a universal fault-tolerant quantum computer. An $[\![ n,k,d ]\!]$ quantum error-correcting code (QECC) protects $k$ information (or logical) qubits by encoding them into quantum states of $n > k$ physical qubits such that any undetectable error must affect at least $d$ physical qubits. In this dissertation we focus on stabilizer QECCs, which are the most widely used type of QECCs. Since we would like to perform universal (i.e., arbitrary) quantum computation on the $k$ logical qubits, an important problem is to determine fault-tolerant $n$-qubit physical operations that induce the desired logical operations. Our first contribution here is a systematic algorithm that can translate a given logical Clifford operation on a stabilizer QECC into all (equivalence classes of) physical Clifford circuits that realize that operation. We exploit binary symplectic matrices to make this translation efficient and call this procedure the Logical Clifford Synthesis (LCS) algorithm.

In order to achieve universality, a quantum computer also needs to implement at least one non-Clifford logical operation. We develop a mathematical framework for a large subset of diagonal (unitary) operations in the Clifford hierarchy, and we refer to these as Quadratic Form Diagonal (QFD) gates. We show that all $1$- and $2$-local diagonal gates in the hierarchy are QFD, and we rigorously derive their action on Pauli matrices. This framework of QFD gates includes many non-Clifford gates and could be of independent interest. Subsequently, we use the QFD formalism to characterize all $[\![ n,k,d ]\!]$ stabilizer codes whose code subspaces are preserved under the transversal action of $T$ and $T^{-1}$ gates on the $n$ physical qubits. The $T$ and $T^{-1}$ gates are among the simplest non-Clifford gates to engineer in the lab. By employing a ``reverse LCS'' strategy, we also discuss the logical operations induced by these physical gates. We discuss some important corollaries related to triorthogonal codes and the optimality of CSS codes with respect to $T$ and $T^{-1}$ gates. We also describe a few purely-classical coding problems motivated by physical constraints arising from fault-tolerance. Finally, we discuss several examples of codes and determine the logical operation induced by physical $Z$-rotations on a family of quantum Reed-Muller codes. A conscious effort has been made to keep this dissertation self-contained, by including necessary background material on quantum information and computation.

This dissertation makes contributions to two rapidly developing fields: quantum information theory and machine learning. It has recently been demonstrated that reinforcement learning is an effective tool for a wide variety of tasks in quantum information theory, ranging from quantum error correction to quantum control to preparation of entangled states. In this work, we demonstrate that reinforcement learning is additionally highly effective for the task of multiple quantum hypothesis testing.

Quantum hypothesis testing consists of finding the quantum measurement which allows one to discriminate with minimal error between $m$ possible states $\{\rho_{k}\}|_{k=1}^{m}$ of a quantum system with corresponding prior probabilities $p_{k} = \text{Pr}[\rho = \rho_{k}]$. In the general case, although semi-definite programming offers a way to numerically approximate the optimal solution~\cite{Eldar_Semidefinite2}, a closed-form analytical solution for the optimal measurement is not known.

Additionally, when the quantum system is large and consists of many subsystems, the optimal measurement may be experimentally difficult to implement. In this work, we provide a comprehensive study of locally adaptive approaches to quantum hypothesis testing where only a single subsystem is measured at a time and the order and types of measurements implemented may depend on previous measurement results. Thus, these locally adaptive protocols present an experimentally feasible approach to quantum state discrimination.

We begin with the case of binary hypothesis testing (where $m=2$), and generalize previous work by Acin et al. (Phys. Rev. A 71, 032338) to show that a simple Bayesian-updating scheme can optimally distinguish between any pair of arbitrary pure, tensor product quantum states. We then demonstrate that this same Bayesian-updating scheme has poor asymptotic behaviour when the candidate states are not pure, and based on this we introduce a modified scheme with strictly better performance. Finally, a dynamic programming (DP) approach is used to find the optimal local protocol for binary state discrimination and numerical simulations are run for both qubit and qutrit subsystems.

Based on these results, we then turn to the more general case of multiple hypothesis testing where there may be several candidate states. Given that the dynamic-programming approach has a high complexity when there are a large number of subsystems, we turn to reinforcement learning methods to learn adaptive protocols for even larger systems. Our numerical results support the claim that reinforcement learning with neural networks (RLNN) is able to successfully find the optimal locally adaptive approach for up to 20 subsystems. We additionally find the optimal collective measurement through semidefinite programming techniques, and demonstrate that the RLNN approach meets or comes close to the optimal collective measurement in every random trial.

Next, we focus on quantum information theory and provide an operational interpretation for the entropy of a channel. This task is motivated by the central role of entropy across several areas of physics and science. We use games of chance as a more systematic and unifying approach to define entropy, as a system's performance in any game of chance depends solely on the uncertainty of the output. We construct families of games which result in a pre-order on channels and provide an operational interpretation for all pre-orders (corresponding to majorization, conditional majorization, and channel majorization respectively), and this defines the unique asymptotically continuous entropy function for classical channels.

The multidimensional joint distributions that represent complex systems with many

interacting elements can be computationally expensive to characterize. Methods

to overcome this problem have been introduced by a variety of scientific communities.

Here, we employ methods from statistics, information theory and statistical

physics to investigate some approximation techniques for inference over factor graphs

of spatially-coupled low density parity check (SC-LDPC) codes, estimation of the

marginals of stationary distribution in influence networks consisting of a number of

individuals with polarized beliefs, and estimation of per-node marginalized distribution

for an adoption model of polarized beliefs represented by a Hamiltonian energy

function.

The second chapter introduces a new method to compensate for the rate loss of

SC-LDPC codes with small chain lengths. Our interest in this problem is motivated

by the theoretical question of whether or not the rate loss can be eliminated by

small modications to the boundary of the protograph? We tackle this question by

attaching additional variable nodes to the check nodes at the chain boundary. Our

goal is to increase the code rate while preserving the BP threshold of the original

chain.

In the third chapter, we consider the diffusion of polarized beliefs in a social network

based on the influence of neighbors and the effect of mass media. The adoption

process is modeled by a stochastic process called the individual-based (IN-STOCH)

system and the effects of viral diffusion and media influence are treated at the individual

level. The primary difference between our model and other recent studies,

which model both interpersonal and media influence, is that we consider a third state,

called the negative state, to represent those individuals who hold positions against

the innovation in addition to the two standard states neutral (susceptible) and positive

(adoption). Also, using a mean-eld analysis, we approximate the IN-STOCH

system in the large population limit by deterministic differential equations which we

call the homogeneous mean-eld (HOM-MEAN) and the heterogeneous mean-eld

(HET-MEAN) systems for exponential and scale-free networks, respectively. Based

on the stability of equilibrium points of these dynamical systems, we derive conditions

for local and global convergence, of the fraction of negative individuals, to

zero.

The fourth chapter also focuses on the diffusion of polarized beliefs but uses a different

mathematical model for the diffusion of beliefs. In particular, the Potts model

from statistical physics is used to model the joint distribution of the individual's

states based on a Hamiltonian energy function. Although the stochastic dynamics

of this model are not completely dened by the energy function, one can choose any

Monte Carlo sampling algorithm (e.g., Metropolis-Hastings) to dene Markov-chain

dynamics. We are primarily interested in the stationary distribution of the Markov

chain, which is given by the Boltzmann distribution. The fraction of individuals in

each state at equilibrium can be estimated using both Markov-chain Monte Carlo

methods and the belief-propagation (BP) algorithm. The main benet of the Potts

model is that the BP estimates are asymptotically exact in this case.