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.

Coding for information storage

Storage systems are widely used and have played a crucial rule in both consumer and industrial products, for example, personal computers, data centers, and embedded systems. However, such system suffers from issues of cost, restricted-lifetime, and reliability with the emergence of new systems and devices, such as distributed storage and flash memory, respectively. Information theory, on the other hand, provides fundamental bounds and solutions to fully utilize resources such as data density, information I/O and network bandwidth. This thesis bridges these two topics, and proposes to solve challenges in data storage using a variety of coding techniques, so that storage becomes faster, more affordable, and more reliable.

We consider the system level and study the integration of RAID schemes and distributed storage. Erasure-correcting codes are the basis of the ubiquitous RAID schemes for storage systems, where disks correspond to symbols in the code and are located in a (distributed) network. Specifically, RAID schemes are based on MDS (maximum distance separable) array codes that enable optimal storage and efficient encoding and decoding algorithms. With r redundancy symbols an MDS code can sustain r erasures. For example, consider an MDS code that can correct two erasures. It is clear that when two symbols are erased, one needs to access and transmit all the remaining information to rebuild the erasures. However, an interesting and practical question is: What is the smallest fraction of information that one needs to access and transmit in order to correct a single erasure? In Part I we will show that the lower bound of 1/2 is achievable and that the result can be generalized to codes with arbitrary number of parities and optimal rebuilding.

We consider the device level and study coding and modulation techniques for emerging non-volatile memories such as flash memory. In particular, rank modulation is a novel data representation scheme proposed by Jiang et al. for multi-level flash memory cells, in which a set of n cells stores information in the permutation induced by the different charge levels of the individual cells. It eliminates the need for discrete cell levels, as well as overshoot errors, when programming cells. In order to decrease the decoding complexity, we propose two variations of this scheme in Part II: bounded rank modulation where only small sliding windows of cells are sorted to generated permutations, and partial rank modulation where only part of the n cells are used to represent data. We study limits on the capacity of bounded rank modulation and propose encoding and decoding algorithms. We show that overlaps between windows will increase capacity. We present Gray codes spanning all possible partial-rank states and using only ``push-to-the-top'' operations. These Gray codes turn out to solve an open combinatorial problem called universal cycle, which is a sequence of integers generating all possible partial permutations.

Gene enrichment using antibodies to DNA/RNA hybrids : mapping the ribosomal DNA of slime mold and rat

A novel method for gene enrichment has been developed and applied to mapping the rRNA genes of two eucaryotic organisms. The method makes use of antibodies to DNA/RNA hybrids prepared by injecting rabbits with the synthetic hybrid poly(rA)•poly(dT). Antibodies which cross-react with non-hybrid nucleic acids were removed from the purified IgG fraction by adsorption on columns of DNA-Sepharose, oligo(dT)-cellulose, and poly(rA)-Sepharose. Subsequent purification of the specific DNA/RNA hybrid antibody was carried out on a column of oligo(dT)-cellulose to which poly(rA) was hybridized. Attachment of these antibodies to CNBr-activated Sepharose produced an affinity resin which specifically binds DNA/RNA hybrids.

In order to map the rDNA of the slime mold Dictyostelium discoideum, R-loops were formed using unsheared nuclear DNA and the 178 and 268 rRNAs of this organism. This mixture was passed through a column containing the affinity resin, and bound molecules containing R- loops were eluted by high salt. This purified rDN A was observed directly in the electron microscope. Evidence was obtained that there is a physical end to Dictyostelium rDN A molecules approximately 10 kilobase pairs (kbp) from the region which codes for the 268 rRNA. This finding is consistent with reports of other investigators that the rRNA genes exist as inverse repeats on extra-chromosomal molecules of DNA unattached to the remainder of the nuclear DNA in this organism.

The same general procedure was used to map the rRNA genes of the rat. Molecules of DNA which contained R-loops formed with the 188 and 288 rRNAs were enriched approximately 150- fold from total genomal rat DNA by two cycles of purification on the affinity column. Electron microscopic measurements of these molecules enabled the construction of an R-loop map of rat rDNA. Eleven of the observed molecules contained three or four R-loops or else two R-loops separated by a long spacer. These observations indicated that the rat rRNA genes are arranged as tandem repeats. The mean length of the repeating units was 37.2 kbp with a standard deviation of 1.3 kbp. These eleven molecules may represent repeating units of exactly the same length within the errors of the measurements, although a certain degree of length heterogeneity cannot be ruled out. If significantly shorter or longer repeating units exist, they are probably much less common than the 37.2 kbp unit.

The last section of the thesis describes the production of antibodies to non-histone chromosomal proteins which have been exposed to the ionic detergent sodium dodecyl sulfate (SDS). The presence of low concentrations of SDS did not seem to affect either production of antibodies or their general specificity. Also, a technique is described for the in situ immunofluorescent detection of protein antigens in polyacrylamide gels.