Quantum error correction with biased noise

Quantum computing offers powerful new techniques for speeding up the calculation of many classically intractable problems. Quantum algorithms can allow for the efficient simulation of physical systems, with applications to basic research, chemical modeling, and drug discovery; other algorithms have important implications for cryptography and internet security.

At the same time, building a quantum computer is a daunting task, requiring the coherent manipulation of systems with many quantum degrees of freedom while preventing environmental noise from interacting too strongly with the system. Fortunately, we know that, under reasonable assumptions, we can use the techniques of quantum error correction and fault tolerance to achieve an arbitrary reduction in the noise level.

In this thesis, we look at how additional information about the structure of noise, or "noise bias," can improve or alter the performance of techniques in quantum error correction and fault tolerance. In Chapter 2, we explore the possibility of designing certain quantum gates to be extremely robust with respect to errors in their operation. This naturally leads to structured noise where certain gates can be implemented in a protected manner, allowing the user to focus their protection on the noisier unprotected operations.

In Chapter 3, we examine how to tailor error-correcting codes and fault-tolerant quantum circuits in the presence of dephasing biased noise, where dephasing errors are far more common than bit-flip errors. By using an appropriately asymmetric code, we demonstrate the ability to improve the amount of error reduction and decrease the physical resources required for error correction.

In Chapter 4, we analyze a variety of protocols for distilling magic states, which enable universal quantum computation, in the presence of faulty Clifford operations. Here again there is a hierarchy of noise levels, with a fixed error rate for faulty gates, and a second rate for errors in the distilled states which decreases as the states are distilled to better quality. The interplay of of these different rates sets limits on the achievable distillation and how quickly states converge to that limit.

An arithmetical theorem for partially ordered sets

The simplest multiplicative systems in which arithmetical ideas can be defined are semigroups. For such systems irreducible (prime) elements can be introduced and conditions under which the fundamental theorem of arithmetic holds have been investigated (Clifford (3)). After identifying associates, the elements of the semigroup form a partially ordered set with respect to the ordinary division relation. This suggests the possibility of an analogous arithmetical result for abstract partially ordered sets. Although nothing corresponding to product exists in a partially ordered set, there is a notion similar to g.c.d. This is the meet operation, defined as greatest lower bound. Thus irreducible elements, namely those elements not expressible as meets of proper divisors can be introduced. The assumption of the ascending chain condition then implies that each element is representable as a reduced meet of irreducibles. The central problem of this thesis is to determine conditions on the structure of the partially ordered set in order that each element have a unique such representation.

Part I contains preliminary results and introduces the principal tools of the investigation. In the second part, basic properties of the lattice of ideals and the connection between its structure and the irreducible decompositions of elements are developed. The proofs of these results are identical with the corresponding ones for the lattice case (Dilworth (2)). The last part contains those results whose proofs are peculiar to partially ordered sets and also contains the proof of the main theorem.

Smooth sets for borel equivalence relations and the covering property for σ-ideals of compact sets

This thesis is divided into three chapters. In the first chapter we study the smooth sets with respect to a Borel equivalence realtion E on a Polish space X. The collection of smooth sets forms σ-ideal. We think of smooth sets as analogs of countable sets and we show that an analog of the perfect set theorem for Σ¹₁ sets holds in the context of smooth sets. We also show that the collection of Σ¹₁ smooth sets is ∏¹₁ on the codes. The analogs of thin sets are called sparse sets. We prove that there is a largest ∏¹₁ sparse set and we give a characterization of it. We show that in L there is a ∏¹₁ sparse set which is not smooth. These results are analogs of the results known for the ideal of countable sets, but it remains open to determine if large cardinal axioms imply that ∏¹₁ sparse sets are smooth. Some more specific results are proved for the case of a countable Borel equivalence relation. We also study I(E), the σ-ideal of closed E-smooth sets. Among other things we prove that E is smooth iff I(E) is Borel.

In chapter 2 we study σ-ideals of compact sets. We are interested in the relationship between some descriptive set theoretic properties like thinness, strong calibration and the covering property. We also study products of σ-ideals from the same point of view. In chapter 3 we show that if a σ-ideal I has the covering property (which is an abstract version of the perfect set theorem for Σ¹₁ sets), then there is a largest ∏¹₁ set in I^int (i.e., every closed subset of it is in I). For σ-ideals on 2^ω we present a characterization of this set in a similar way as for C₁, the largest thin ∏¹₁ set. As a corollary we get that if there are only countable many reals in L, then the covering property holds for Σ¹₂ sets.

Some central limit theorems for doubly restricted partitions

Let P_{K, L}(N) be the number of unordered partitions of a positive integer N into K or fewer positive integer parts, each part not exceeding L. A distribution of the form

Ʃ/N≤x P_K,L(N)

is considered first. For any fixed K, this distribution approaches a piecewise polynomial function as L increases to infinity. As both K and L approach infinity, this distribution is asymptotically normal. These results are proved by studying the convergence of the characteristic function.

The main result is the asymptotic behavior of P_K,K(N) itself, for certain large K and N. This is obtained by studying a contour integral of the generating function taken along the unit circle. The bulk of the estimate comes from integrating along a small arc near the point 1. Diophantine approximation is used to show that the integral along the rest of the circle is much smaller.

A generalized Hausdorff dimension for functions and sets

Let E be a compact subset of the n-dimensional unit cube, 1_n, and let C be a collection of convex bodies, all of positive n-dimensional Lebesgue measure, such that C contains bodies with arbitrarily small measure. The dimension of E with respect to the covering class C is defined to be the number

d_C(E) = sup(β:H_{β, C}(E) > 0),

where H_{β, C} is the outer measure

inf(Ʃm(C_i)^β:UC_i Ↄ E, C_i ϵ C) .

Only the one and two-dimensional cases are studied. Moreover, the covering classes considered are those consisting of intervals and rectangles, parallel to the coordinate axes, and those closed under translations. A covering class is identified with a set of points in the left-open portion, 1’_n, of 1_n, whose closure intersects 1_n - 1’_n. For n = 2, the outer measure H_{β, C} is adopted in place of the usual:

Inf(Ʃ(diam. (C_i))^β: UC_i Ↄ E, C_i ϵ C),

for the purpose of studying the influence of the shape of the covering sets on the dimension d_C(E).

If E is a closed set in 1₁, let M(E) be the class of all non-decreasing functions μ(x), supported on E with μ(x) = 0, x ≤ 0 and μ(x) = 1, x ≥ 1. Define for each μ ϵ M(E),

d_C(μ) = lim/c → inf/0 log ∆μ(c)/log c , (c ϵ C)

where ∆μ(c) = v/x (μ(x+c) – μ(x)). It is shown that

d_C(E) = sup (d_C(μ):μ ϵ M(E)).

This notion of dimension is extended to a certain class Ӻ of sub-additive functions, and the problem of studying the behavior of d_C(E) as a function of the covering class C is reduced to the study of d_C(f) where f ϵ Ӻ. Specifically, the set of points in 1₁,

(*) {d_B(F), d_C(f)): f ϵ Ӻ}

is characterized by a comparison of the relative positions of the points of B and C. A region of the form (*) is always closed and doubly-starred with respect to the points (0, 0) and (1, 1). Conversely, given any closed region in 1₂, doubly-starred with respect to (0, 0) and (1, 1), there are covering classes B and C such that (*) is exactly that region. All of the results are shown to apply to the dimension of closed sets E. Similar results can be obtained when a finite number of covering classes are considered.

In two dimensions, the notion of dimension is extended to the class M, of functions f(x, y), non-decreasing in x and y, supported on 1₂ with f(x, y) = 0 for x · y = 0 and f(1, 1) = 1, by the formula

d_C(f) = lim/s · t → inf/0 log ∆f(s, t)/log s · t , (s, t) ϵ C

where

∆f(s, t) = V/x, y (f(x+s, y+t) – f(x+s, y) – f(x, y+t) + f(x, t)).

A characterization of the equivalence d_C1(f) = d_C2(f) for all f ϵ M, is given by comparison of the gaps in the sets of products s · t and quotients s/t, (s, t) ϵ C_i (I = 1, 2).

Computational Microscopy: Breaking the Limit of Conventional Optics

Computational imaging is flourishing thanks to the recent advancement in array photodetectors and image processing algorithms. This thesis presents Fourier ptychography, which is a computational imaging technique implemented in microscopy to break the limit of conventional optics. With the implementation of Fourier ptychography, the resolution of the imaging system can surpass the diffraction limit of the objective lens's numerical aperture; the quantitative phase information of a sample can be reconstructed from intensity-only measurements; and the aberration of a microscope system can be characterized and computationally corrected. This computational microscopy technique enhances the performance of conventional optical systems and expands the scope of their applications.