This thesis investigates lattice compression of polynomial matrices over finite fields. For an m x n matrix, the goal of lattice compression is to find an m x (m+k) matrix, for some relatively small k, such that the lattice span of two matrices are equivalent. For any m x n polynomial matrix with degree bound d, it can be compressed by multiplying by a random n x (m+k) matrix B with degree bound s. In this thesis, we prove that there is a positive probability that L(A)=L(AB) with k(s+1)=\Theta(\log(md)). This is shown to hold even when s=0 (i.e., where B is a matrix of constants). We also design a competitive probabilistic lattice compression algorithm of the Las Vegas type that has a positive probability of success on any input and requires O~(nm^{\theta-1}B(d)) field operations.

This thesis investigates lattice compression of polynomial matrices over finite fields. For an m x n matrix, the goal of lattice compression is to find an m x (m+k) matrix, for some relatively small k, such that the lattice span of two matrices are equivalent. For any m x n polynomial matrix with degree bound d, it can be compressed by multiplying by a random n x (m+k) matrix B with degree bound s. In this thesis, we prove that there is a positive probability that L(A)=L(AB) with k(s+1)=\Theta(\log(md)). This is shown to hold even when s=0 (i.e., where B is a matrix of constants). We also design a competitive probabilistic lattice compression algorithm of the Las Vegas type that has a positive probability of success on any input and requires O~(nm^{\theta-1}B(d)) field operations.

This thesis includes a survey of the results known for private and approximate private quantum channels. We develop the best known upper bound for &epsilon;-randomizing maps, <em>n</em> + 2log(1/&epsilon;) + <em>c</em> bits required to &epsilon;-randomize an arbitrary <em>n</em>-qubit state by improving a scheme of Ambainis and Smith [5] based on small bias spaces [16, 3]. We show by a probabilistic argument that in fact the great majority of random schemes using slightly more than this many bits of key are also &epsilon;-randomizing. We provide the first known nontrivial lower bound for &epsilon;-randomizing maps, and develop several conditions on them which we hope may be useful in proving stronger lower bounds in the future.

This thesis includes a survey of the results known for private and approximate private quantum channels. We develop the best known upper bound for &epsilon;-randomizing maps, <em>n</em> + 2log(1/&epsilon;) + <em>c</em> bits required to &epsilon;-randomize an arbitrary <em>n</em>-qubit state by improving a scheme of Ambainis and Smith [5] based on small bias spaces [16, 3]. We show by a probabilistic argument that in fact the great majority of random schemes using slightly more than this many bits of key are also &epsilon;-randomizing. We provide the first known nontrivial lower bound for &epsilon;-randomizing maps, and develop several conditions on them which we hope may be useful in proving stronger lower bounds in the future.