The power of quantum Fourier sampling

How powerful are Quantum Computers? Despite the prevailing belief that Quantum Computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's famous factoring algorithm [Shor97] gives an example of a problem that can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring, however, is unlikely to be NP-Hard, meaning that few unexpected formal consequences would arise, should such a classical algorithm be discovered. Could it then be the case that any quantum algorithm can be simulated efficiently classically? Likewise, could it be the case that Quantum Computers can quickly solve problems much harder than factoring? If so, where does this power come from, and what classical computational resources do we need to solve the hardest problems for which there exist efficient quantum algorithms?

We make progress toward understanding these questions through studying the relationship between classical nondeterminism and quantum computing. In particular, is there a problem that can be solved efficiently on a Quantum Computer that cannot be efficiently solved using nondeterminism? In this thesis we address this problem from the perspective of sampling problems. Namely, we give evidence that approximately sampling the Quantum Fourier Transform of an efficiently computable function, while easy quantumly, is hard for any classical machine in the Polynomial Time Hierarchy. In particular, we prove the existence of a class of distributions that can be sampled efficiently by a Quantum Computer, that likely cannot be approximately sampled in randomized polynomial time with an oracle for the Polynomial Time Hierarchy.

Our work complements and generalizes the evidence given in Aaronson and Arkhipov's work [AA2013] where a different distribution with the same computational properties was given. Our result is more general than theirs, but requires a more powerful quantum sampler.

Band Engineering in Thermoelectric Materials Using Optical, Electronic, and Ab-Initio Computed Properties

Thermoelectric materials have demanded a significant amount of attention for their ability to convert waste heat directly to electricity with no moving parts. A resurgence in thermoelectrics research has led to significant enhancements in the thermoelectric figure of merit, zT, even for materials that were already well studied. This thesis approaches thermoelectric zT optimization by developing a detailed understanding of the electronic structure using a combination of electronic/thermoelectric properties, optical properties, and ab-initio computed electronic band structures. This is accomplished by applying these techniques to three important classes of thermoelectric materials: IV-VI materials (the lead chalcogenides), Half-Heusler’s (XNiSn where X=Zr, Ti, Hf), and CoSb₃ skutterudites.

In the IV-VI materials (PbTe, PbSe, PbS) I present a shifting temperature-dependent optical absorption edge which correlates well to the computed ab-initio molecular dynamics result. Contrary to prior literature that suggests convergence of the primary and secondary bands at 400 K, I suggest a higher convergence temperature of 700, 900, and 1000 K for PbTe, PbSe, and PbS, respectively. This finding can help guide electronic properties modelling by providing a concrete value for the band gap and valence band offset as a function of temperature.

Another important thermoelectric material, ZrNiSn (half-Heusler), is analyzed for both its optical and electronic properties; transport properties indicate a largely different band gap depending on whether the material is doped n-type or p-type. By measuring and reporting the optical band gap value of 0.13 eV, I resolve the discrepancy in the gap calculated from electronic properties (maximum Seebeck and resistivity) by correlating these estimates to the electron-to-hole weighted mobility ratio, A, in narrow gap materials (A is found to be approximately 5.0 in ZrNiSn).

I also show that CoSb₃ contains multiple conduction bands that contribute to the thermoelectric properties. These bands are also observed to shift towards each other with temperature, eventually reaching effective convergence for T>500 K. This implies that the electronic structure in CoSb₃ is critically important (and possibly engineerable) with regards to its high thermoelectric figure of merit.

Robust Control of Evolutionary Dynamics

The application of principles from evolutionary biology has long been used to gain new insights into the progression and clinical control of both infectious diseases and neoplasms. This iterative evolutionary process consists of expansion, diversification and selection within an adaptive landscape - species are subject to random genetic or epigenetic alterations that result in variations; genetic information is inherited through asexual reproduction and strong selective pressures such as therapeutic intervention can lead to the adaptation and expansion of resistant variants. These principles lie at the center of modern evolutionary synthesis and constitute the primary reasons for the development of resistance and therapeutic failure, but also provide a framework that allows for more effective control.

A model system for studying the evolution of resistance and control of therapeutic failure is the treatment of chronic HIV-1 infection by broadly neutralizing antibody (bNAb) therapy. A relatively recent discovery is that a minority of HIV-infected individuals can produce broadly neutralizing antibodies, that is, antibodies that inhibit infection by many strains of HIV. Passive transfer of human antibodies for the prevention and treatment of HIV-1 infection is increasingly being considered as an alternative to a conventional vaccine. However, recent evolution studies have uncovered that antibody treatment can exert selective pressure on virus that results in the rapid evolution of resistance. In certain cases, complete resistance to an antibody is conferred with a single amino acid substitution on the viral envelope of HIV.

The challenges in uncovering resistance mechanisms and designing effective combination strategies to control evolutionary processes and prevent therapeutic failure apply more broadly. We are motivated by two questions: Can we predict the evolution to resistance by characterizing genetic alterations that contribute to modified phenotypic fitness? Given an evolutionary landscape and a set of candidate therapies, can we computationally synthesize treatment strategies that control evolution to resistance?

To address the first question, we propose a mathematical framework to reason about evolutionary dynamics of HIV from computationally derived Gibbs energy fitness landscapes -- expanding the theoretical concept of an evolutionary landscape originally conceived by Sewall Wright to a computable, quantifiable, multidimensional, structurally defined fitness surface upon which to study complex HIV evolutionary outcomes.

To design combination treatment strategies that control evolution to resistance, we propose a methodology that solves for optimal combinations and concentrations of candidate therapies, and allows for the ability to quantifiably explore tradeoffs in treatment design, such as limiting the number of candidate therapies in the combination, dosage constraints and robustness to error. Our algorithm is based on the application of recent results in optimal control to an HIV evolutionary dynamics model and is constructed from experimentally derived antibody resistant phenotypes and their single antibody pharmacodynamics. This method represents a first step towards integrating principled engineering techniques with an experimentally based mathematical model in the rational design of combination treatment strategies and offers predictive understanding of the effects of combination therapies of evolutionary dynamics and resistance of HIV. Preliminary in vitro studies suggest that the combination antibody therapies predicted by our algorithm can neutralize heterogeneous viral populations despite containing resistant mutations.