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.

Electron transfer in cytochrome c oxidase : the rate of electron equillibration between cytochrome a and copper A

Intramolecular electron transfer in partially reduced cytochrome c oxidase has been studied by means of perturbed equilibrium techniques. We have prepared a three electron reduced, CO inhibited form of the enzyme in which cytochrome a and copper A are partially reduced an in intramolecular redox equilibrium. When these samples were photolyzed using a nitrogen laser (0.6 µs, 1.0 mJ pulses) changes in absorbance at 598 nm and 830 nm were observed which are consistent with a fast electron from cytochrome a to copper A. The absorbance changes at 598 nm have an apparent rate of 17,200 ± 1,700 s^(-1) (1σ), at pH 7.0 and 25.5 °C. These changes were not observed in either the CO mixed valence or CO inhibited fully reduced forms of the enzyme. The rate is fastest at about pH 8.0, and falls off in either direction, and there is a small, but clear temperature dependence. The process was also observed in the cytochrome c -- cytochrome c oxidase high affinity complex.

This rate is far faster than any rate measured or inferred previously for the cytochrome a -- copper A electron equilibration, but the interpretation of these results is hampered by the fact that the relaxation could only be followed during the time before CO became rebound to the oxygen binding site. The meaning of our our measured rate is discussed, along with other reported rates for this process. In addition, a temperature-jump experiment on the same system is discussed.

We have also prepared a partially reduced, cyanide inhibited form of the enzyme in which cytochrome a, copper A and copper B are partially reduced and in redox equilibrium. Warming these samples produced absorbance changes at 605 nm which indicate that cytochrome a was becoming more oxidized, but there were no parallel changes in absorbance at 830 nm as would be expected if copper A was becoming reduced. We concluded that electrons were being redistributed from cytochrome a to copper B. The kinetics of the absorbance changes at 605 nm were investigated by temperature-jump methods. Although a rate could not be resolved, we concluded that the process must occur with an (apparent) rate larger than 10,000 s^(-1).

During the course of the temperature-jump experiments, we also found that non-redox related, temperature dependent absorbance changes in fully reduced CO inhibited cytochrome c oxidase, and in the cyanide mixed valence enzyme, took place with an (apparent) rate faster that 30,000 s^(-1).

Part I. Kinetics of coarsening of the gamma-prime precipitate in nickel-silicon alloys. Part II. Rate of crystallization of an amorphous Fe-P-C alloy

The coarsening kinetics of Ni₃ Si(γ') precipitate in a binary Ni-Si alloy containing 6.5 wt. % silicon was studied by magnetic techniques and transmission electronmicroscopy. A calibration curve was established to determine the concentration of silicon in the matrix. The variation of the Si content of the Ni-rich matrix as a function of time follows Lifshitz and Wagner theory for diffusion controlled coarsening phenomena. The estimated values of equilibrium solubility of silicon in the matrix represent the true coherent equilibrium solubilities.

The experimental particle-size distributions and average particle size were determined from dark field electron micrographs. The average particle size varies linearly with t^-1/3 as suggested by Lifshitz and Wagner. The experimental distributions of particle sizes differ slightly from the theoretical curve at the early stages of aging, but the agreement is satisfactory at the later stages. The values of diffusion coefficient of silicon, interfacial free energy and activation energy were calculated from the results of coarsening kinetics. The experimental value of effective diffusion coefficient is in satisfactory agreement with the value predicted by the application of irreversible the rmodynamics to the process of volume constrained growth of coherent precipitate during coarsening. The coherent γ' particles in Ni-Sialloy unlike those in Ni-Al and Ni-Ti seem to lose coherency at high temperature. A mechanism for the formation of semi-coherent precipitate is suggested.

Rate and Microstructure Effects on the Dynamics of Carbon Nanotube Foams

Soft hierarchical materials often present unique functional properties that are sensitive to the geometry and organization of their micro- and nano-structural features across different lengthscales. Carbon Nanotube (CNT) foams are hierarchical materials with fibrous morphology that are known for their remarkable physical, chemical and electrical properties. Their complex microstructure has led them to exhibit intriguing mechanical responses at different length-scales and in different loading regimes. Even though these materials have been studied for mechanical behavior over the past few years, their response at high-rate finite deformations and the influence of their microstructure on bulk mechanical behavior and energy dissipative characteristics remain elusive.

In this dissertation, we study the response of aligned CNT foams at the high strain-rate regime of 10² - 10⁴ s^-1. We investigate their bulk dynamic response and the fundamental deformation mechanisms at different lengthscales, and correlate them to the microstructural characteristics of the foams. We develop an experimental platform, with which to study the mechanics of CNT foams in high-rate deformations, that includes direct measurements of the strain and transmitted forces, and allows for a full field visualization of the sample’s deformation through high-speed microscopy.

We synthesize various CNT foams (e.g., vertically aligned CNT (VACNT) foams, helical CNT foams, micro-architectured VACNT foams and VACNT foams with microscale heterogeneities) and show that the bulk functional properties of these materials are highly tunable either by tailoring their microstructure during synthesis or by designing micro-architectures that exploit the principles of structural mechanics. We also develop numerical models to describe the bulk dynamic response using multiscale mass-spring models and identify the mechanical properties at length scales that are smaller than the sample height.

The ability to control the geometry of microstructural features, and their local interactions, allows the creation of novel hierarchical materials with desired functional properties. The fundamental understanding provided by this work on the key structure-function relations that govern the bulk response of CNT foams can be extended to other fibrous, soft and hierarchical materials. The findings can be used to design materials with tailored properties for different engineering applications, like vibration damping, impact mitigation and packaging.

Rewriting Schemes for Flash Memory

Flash memory is a leading storage media with excellent features such as random access and high storage density. However, it also faces significant reliability and endurance challenges. In flash memory, the charge level in the cells can be easily increased, but removing charge requires an expensive erasure operation. In this thesis we study rewriting schemes that enable the data stored in a set of cells to be rewritten by only increasing the charge level in the cells. We consider two types of modulation scheme; a convectional modulation based on the absolute levels of the cells, and a recently-proposed scheme based on the relative cell levels, called rank modulation. The contributions of this thesis to the study of rewriting schemes for rank modulation include the following: we

•propose a new method of rewriting in rank modulation, beyond the previously proposed method of “push-to-the-top”;

•study the limits of rewriting with the newly proposed method, and derive a tight upper bound of 1 bit per cell;

•extend the rank-modulation scheme to support rankings with repetitions, in order to improve the storage density;

•derive a tight upper bound of 2 bits per cell for rewriting in rank modulation with repetitions;

•construct an efficient rewriting scheme that asymptotically approaches the upper bound of 2 bit per cell.

The next part of this thesis studies rewriting schemes for a conventional absolute-levels modulation. The considered model is called “write-once memory” (WOM). We focus on WOM schemes that achieve the capacity of the model. In recent years several capacity-achieving WOM schemes were proposed, based on polar codes and randomness extractors. The contributions of this thesis to the study of WOM scheme include the following: we

•propose a new capacity-achievingWOM scheme based on sparse-graph codes, and show its attractive properties for practical implementation;

•improve the design of polarWOMschemes to remove the reliance on shared randomness and include an error-correction capability.

The last part of the thesis studies the local rank-modulation (LRM) scheme, in which a sliding window going over a sequence of real-valued variables induces a sequence of permutations. The LRM scheme is used to simulate a single conventional multi-level flash cell. The simulated cell is realized by a Gray code traversing all the relative-value states where, physically, the transition between two adjacent states in the Gray code is achieved by using a single “push-to-the-top” operation. The main results of the last part of the thesis are two constructions of Gray codes with asymptotically-optimal rate.

I. The rate and mechanism of the vapor-phase reaction between water and parts-per-million concentrations of nitrogen dioxide. II. The rate and mechanism of the air oxidation of parts-per-million concentrations of nitric oxide in the presence of water vapor.

Part I

A study of the thermal reaction of water vapor and parts-per-million concentrations of nitrogen dioxide was carried out at ambient temperature and at atmospheric pressure. Nitric oxide and nitric acid vapor were the principal products. The initial rate of disappearance of nitrogen dioxide was first order with respect to water vapor and second order with respect to nitrogen dioxide. An initial third-order rate constant of 5.5 (± 0.29) x 10⁴ liter² mole^-2 sec^-1 was found at 25˚C. The rate of reaction decreased with increasing temperature. In the temperature range of 25˚C to 50˚C, an activation energy of -978 (± 20) calories was found.

The reaction did not go to completion. From measurements as the reaction approached equilibrium, the free energy of nitric acid vapor was calculated. This value was -18.58 (± 0.04) kilocalories at 25˚C.

The initial rate of reaction was unaffected by the presence of oxygen and was retarded by the presence of nitric oxide. There were no appreciable effects due to the surface of the reactor. Nitric oxide and nitrogen dioxide were monitored by gas chromatography during the reaction.

Part II

The air oxidation of nitric oxide, and the oxidation of nitric oxide in the presence of water vapor, were studied in a glass reactor at ambient temperatures and at atmospheric pressure. The concentration of nitric oxide was less than 100 parts-per-million. The concentration of nitrogen dioxide was monitored by gas chromatography during the reaction.

For the dry oxidation, the third-order rate constant was 1.46 (± 0.03) x 10⁴ liter² mole^-2 sec^-1 at 25˚C. The activation energy, obtained from measurements between 25˚C and 50˚C, was -1.197 (±0.02) kilocalories.

The presence of water vapor during the oxidation caused the formation of nitrous acid vapor when nitric oxide, nitrogen dioxide and water vapor combined. By measuring the difference between the concentrations of nitrogen dioxide during the wet and dry oxidations, the rate of formation of nitrous acid vapor was found. The third-order rate constant for the formation of nitrous acid vapor was equal to 1.5 (± 0.5) x 10⁵ liter² mole^-2 sec^-1 at 40˚C. The reaction rate did not change measurably when the temperature was increased to 50˚C. The formation of nitric acid vapor was prevented by keeping the concentration of nitrogen dioxide low.

Surface effects were appreciable for the wet tests. Below 35˚C, the rate of appearance of nitrogen dioxide increased with increasing surface. Above 40˚C, the effect of surface was small.

The rate and mechanism of the partial oxidation of acetaldehyde by PPM concentrations of nitrogen dioxide

The thermal reaction between nitrogen dioxide and acetaldehyde in the gas phase was investigated at room temperature and atmospheric pressure. The initial rate of disappearance of nitrogen dioxide was 1.00 ± 0.03 order with respect to nitrogen dioxide and 1.00 ± 0.07 order with respect to acetaldehyde. An initial second order rate constant of (8.596 ± 0.189) x 10^-3 1.mole^-1 sec^-1 was obtained at 22.0 ± 0.1 °C and a total pressure of one atmosphere. The activation energy of the reaction was 12,900 cal/mole in the temperature range between 22°C and 122°C.

The products of the reaction were nitric oxide, carbon dioxide, methyl nitrite, nitromethane and a trace amount of trans-dimeric nitrosomethane. The addition of nitric oxide increased the rate of formation of nitromethane and decreased the rate of formation of methyl nitrite. There were no measurable surface effects due to the addition of glass wool or glass beads to the reactor.

Reactants and products were analyzed by gas chromatography. A mechanism was proposed incorporating the principal features of the reaction.

Decoding cosets of first-order Reed-Muller code

Proper encoding of transmitted information can improve the performance of a communication system. To recover the information at the receiver it is necessary to decode the received signal. For many codes the complexity and slowness of the decoder is so severe that the code is not feasible for practical use. This thesis considers the decoding problem for one such class of codes, the comma-free codes related to the first-order Reed-Muller codes.

A factorization of the code matrix is found which leads to a simple, fast, minimum memory, decoder. The decoder is modular and only n modules are needed to decode a code of length 2ⁿ. The relevant factorization is extended to any code defined by a sequence of Kronecker products.

The problem of monitoring the correct synchronization position is also considered. A general answer seems to depend upon more detailed knowledge of the structure of comma-free codes. However, a technique is presented which gives useful results in many specific cases.

Finite-Element Simulations of Earthquakes

This thesis discusses simulations of earthquake ground motions using prescribed ruptures and dynamic failure. Introducing sliding degrees of freedom led to an innovative technique for numerical modeling of earthquake sources. This technique allows efficient implementation of both prescribed ruptures and dynamic failure on an arbitrarily oriented fault surface. Off the fault surface the solution of the three-dimensional, dynamic elasticity equation uses well known finite-element techniques. We employ parallel processing to efficiently compute the ground motions in domains containing millions of degrees of freedom.

Using prescribed ruptures we study the sensitivity of long-period near-source ground motions to five earthquake source parameters for hypothetical events on a strike-slip fault (M_w 7.0 to 7.1) and a thrust fault (M_w 6.6 to 7.0). The directivity of the ruptures creates large displacement and velocity pulses in the ground motions in the forward direction. We found a good match between the severity of the shaking and the shape of the near-source factor from the 1997 Uniform Building Code for strike-slip faults and thrust faults with surface rupture. However, for blind thrust faults the peak displacement and velocities occur up-dip from the region with the peak near-source factor. We assert that a simple modification to the formulation of the near-source factor improves the match between the severity of the ground motion and the shape of the near-source factor.

For simulations with dynamic failure on a strike-slip fault or a thrust fault, we examine what constraints must be imposed on the coefficient of friction to produce realistic ruptures under the application of reasonable shear and normal stress distributions with depth. We found that variation of the coefficient of friction with the shear modulus and the depth produces realistic rupture behavior in both homogeneous and layered half-spaces. Furthermore, we observed a dependence of the rupture speed on the direction of propagation and fluctuations in the rupture speed and slip rate as the rupture encountered changes in the stress field. Including such behavior in prescribed ruptures would yield more realistic ground motions.

Proton magnetic resonance studies of ribonucleic acid complexes. I. Complexes of biological bases and oligonucleotides with RNA. II. Template recognition and the degeneracy of the genetic code

Part I. Complexes of Biological Bases and Oligonucleotides with RNA

The physical nature of complexes of several biological bases and oligonucleotides with single-stranded ribonucleic acids have been studied by high resolution proton magnetic resonance spectroscopy. The importance of various forces in the stabilization of these complexes is also discussed.

Previous work has shown that purine forms an intercalated complex with single-stranded nucleic acids. This complex formation led to severe and stereospecific broadening of the purine resonances. From the field dependence of the linewidths, T₁ measurements of the purine protons and nuclear Overhauser enhancement experiments, the mechanism for the line broadening was ascertained to be dipole-dipole interactions between the purine protons and the ribose protons of the nucleic acid.

The interactions of ethidium bromide (EB) with several RNA residues have been studied. EB forms vertically stacked aggregates with itself as well as with uridine, 3'-uridine monophosphate and 5'-uridine monophosphate and forms an intercalated complex with uridylyl (3' → 5') uridine and polyuridylic acid (poly U). The geometry of EB in the intercalated complex has also been determined.

The effect of chain length of oligo-A-nucleotides on their mode of interaction with poly U in D₂0 at neutral pD have also been studied. Below room temperatures, ApA and ApApA form a rigid triple-stranded complex involving a stoichiometry of one adenine to two uracil bases, presumably via specific adenine-uracil base pairing and cooperative base stacking of the adenine bases. While no evidence was obtained for the interaction of ApA with poly U above room temperature, ApApA exhibited complex formation of a 1:1 nature with poly U by forming Watson-Crick base pairs. The thermodynamics of these systems are discussed.

Part II. Template Recognition and the Degeneracy of the Genetic Code

The interaction of ApApG and poly U was studied as a model system for the codon-anticodon interaction of tRNA and mRNA in vivo. ApApG was shown to interact with poly U below ~20°C. The interaction was of a 1:1 nature which exhibited the Hoogsteen bonding scheme. The three bases of ApApG are in an anti conformation and the guanosine base appears to be in the lactim tautomeric form in the complex.

Due to the inadequacies of previous models for the degeneracy of the genetic code in explaining the observed interactions of ApApG with poly U, the "tautomeric doublet" model is proposed as a possible explanation of the degenerate interactions of tRNA with mRNA during protein synthesis in vivo.