A Short History of Computational Complexity

National Science Foundation (CCR-998310); Army Research Office (DAAD19-02-1-0058)

Small Depth Quantum Circuits

Small depth quantum circuits have proved to be unexpectedly powerful in comparison to their classical counterparts. We survey some of the recent work on this and present some open problems.

Universal Quantum Circuits

We define and construct efficient depth universal and almost size universal quantum circuits. Such circuits can be viewed as general purpose simulators for central classes of quantum circuits and can be used to capture the computational power of the circuit class being simulated. For depth we construct universal circuits whose depth is the same order as the circuits being simulated. For size, there is a log factor blow-up in the universal circuits constructed here. We prove that this construction is nearly optimal. Our results apply to a number of well-studied quantum circuit classes.

Non-Uniform Reductions

We study properties of non-uniform reductions and related completeness notions. We strengthen several results of Hitchcock and Pavan and give a trade-off between the amount of advice needed for a reduction and its honesty on NEXP. We construct an oracle relative to which this trade-off is optimal. We show, in a more systematic study of non-uniform reductions, that among other things non-uniformity can be removed at the cost of more queries. In line with Post's program for complexity theory we connect such 'uniformization' properties to the separation of complexity classes.

On Finding Sensitivity of Quantum and Classical Gates

We consider a fault model of Boolean gates, both classical and quantum, where some of the inputs may not be connected to the actual gate hardware. This model is somewhat similar to the stuck-at model which is a very popular model in testing Boolean circuits. We consider the problem of detecting such faults; the detection algorithm can query the faulty gate and its complexity is the number of such queries. This problem is related to determining the sensitivity of Boolean functions. We show how quantum parallelism can be used to detect such faults. Specifically, we show that a quantum algorithm can detect such faults more efficiently than a classical algorithm for a Parity gate and an AND gate. We give explicit constructions of quantum detector algorithms and show lower bounds for classical algorithms. We show that the model for detecting such faults is similar to algebraic decision trees and extend some known results from quantum query complexity to prove some of our results.

Determining Acceptance Possibility for a Quantum Computation is Hard for PH

It is shown that determining whether a quantum computation has a non-zero probability of accepting is at least as hard as the polynomial time hierarchy. This hardness result also applies to determining in general whether a given quantum basis state appears with nonzero amplitude in a superposition, or whether a given quantum bit has positive expectation value at the end of a quantum computation.

Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy

It is shown that determining whether a quantum computation has a non-zero probability of accepting is at least as hard as the polynomial time hierarchy. This hardness result also applies to determining in general whether a given quantum basis state appears with nonzero amplitude in a superposition, or whether a given quantum bit has positive expectation value at the end of a quantum computation. This result is achieved by showing that the complexity class NQP of Adleman, Demarrais, and Huang, a quantum analog of NP, is equal to the counting class coC=P.

On the Complexity of Quantum ACC

For any q > 1, let MOD_q be a quantum gate that determines if the number of 1's in the input is divisible by q. We show that for any q,t > 1, MOD_q is equivalent to MOD_t (up to constant depth). Based on the case q=2, Moore has shown that quantum analogs of AC^(0), ACC[q], and ACC, denoted QAC^(0)_wf, QACC[2], QACC respectively, define the same class of operators, leaving q > 2 as an open question. Our result resolves this question, implying that QAC^(0)_wf = QACC[q] = QACC for all q. We also prove the first upper bounds for QACC in terms of related language classes. We define classes of languages EQACC, NQACC (both for arbitrary complex amplitudes) and BQACC (for rational number amplitudes) and show that they are all contained in TC^(0). To do this, we show that a TC^(0) circuit can keep track of the amplitudes of the state resulting from the application of a QACC operator using a constant width polynomial size tensor sum. In order to accomplish this, we also show that TC^(0) can perform iterated addition and multiplication in certain field extensions.

Inhibition of pulmonary fibrosis in mice by CXCL10 requires glycosaminoglycan binding and syndecan-4.

Pulmonary fibrosis is a progressive, dysregulated response to injury culminating in compromised lung function due to excess extracellular matrix production. The heparan sulfate proteoglycan syndecan-4 is important in mediating fibroblast-matrix interactions, but its role in pulmonary fibrosis has not been explored. To investigate this issue, we used intratracheal instillation of bleomycin as a model of acute lung injury and fibrosis. We found that bleomycin treatment increased syndecan-4 expression. Moreover, we observed a marked decrease in neutrophil recruitment and an increase in both myofibroblast recruitment and interstitial fibrosis in bleomycin-treated syndecan-4-null (Sdc4-/-) mice. Subsequently, we identified a direct interaction between CXCL10, an antifibrotic chemokine, and syndecan-4 that inhibited primary lung fibroblast migration during fibrosis; mutation of the heparin-binding domain, but not the CXCR3 domain, of CXCL10 diminished this effect. Similarly, migration of fibroblasts from patients with pulmonary fibrosis was inhibited in the presence of CXCL10 protein defective in CXCR3 binding. Furthermore, administration of recombinant CXCL10 protein inhibited fibrosis in WT mice, but not in Sdc4-/- mice. Collectively, these data suggest that the direct interaction of syndecan-4 and CXCL10 in the lung interstitial compartment serves to inhibit fibroblast recruitment and subsequent fibrosis. Thus, administration of CXCL10 protein defective in CXCR3 binding may represent a novel therapy for pulmonary fibrosis.

VERSATILITY IN THE MODERN PERFORMER: THREE DIVERSE OPERA ROLES

This dissertation project consisted of performances of three diverse operatic roles. The goal was to examine the challenges and benefits of performing diverse repertoire (baroque, classical, and romantic opera, in this case) and to observe how vocal and acting techniques might adjust to different styles and voice classifications. On December 3, 5, 11, and 13,2003, I performed a composite role in Fatal Song, directed by Leon Major, in the Robert & Arlene Kogod Theatre. This opera pastiche, premiered in 1996, contains spoken dialogue, and the music originates from famous eighteenth and nineteenth-century operas. I explored the challenges and benefits of playing three different, well-known opera characters within the same opera, performing four different languages within the same opera, and performing spoken dialogue in an opera. My roles in this pastiche of famous opera included Lucia from Lucia di Lammermoor by Gaetano Donizetti, Manon from Manon by Jules Massenet, and Pamina from Die ZauberJlote by W.A. Mozart. On January 28 and 29, 2005, I performed the role of Nice in Eurilla e Alcindo, a serenata by Antonio Vivaldi, in Homer Ulrich Recital Hall; musical direction by Joseph Gascho and stage direction by Kate Vetter Cain. I explored the challenges and benefits of preparing baroque ornamentation, singing without a conductor, performing an unknown work, staging a work that is not traditionally staged, singing with minimal sets and costumes, and singing with period instruments. On April 16,20, and 24,2005, I performed the role of Musetta in Giacomo Puccini's La BohBme, directed by Pat Diamond and conducted by Jeffrey Rink, in the Ina & Jack Kay Theatre. I examined the challenges and benefits of singing with a large orchestra of modem instruments, singing Puccini rubato and coordinating this with the conductor, and singing a role in one of the most well-known operas in today's repertoire. As a result of this investigation, I concluded that singing different styles, and singing outside one's voice classification, within reason, is beneficial. The knowledge, skill, confidence and insight I acquired by becoming more versatile benefited me as a performer and as a teacher.

SELECTED TWENTIETH-CENTURY BRITISH & AMERICAN ENGLISH SONG REPERTOIRE WRITTEN FOR SOPRANO

English language song (both British and American) is influenced by a variety of cultures, races, and musical forms and has produced a broad range of song repertoire. Like songs in all countries and throughout history, these songs can be classified into three categories: imitative songs, experimental songs, and songs of individuality. Music experimentation, necessary and welcome as it is, can hardly command broad international attention. Thus, the songs of this dissertation performance project are chosen from the first and third categories: imitative songs and individual songs in the composer's own unique style. This project concentrates its exploration on twentieth-century solo songs written in English. Although twentieth-century British & American composers also produced solos and chamber music in other languages, this dissertation focuses upon their English repertoire. This performance project consists of three programs: one British repertoire and two American. The first program titled An Evening of British Song examines twentieth-century British song written by Roger Quilter, Peter Warlock, William Walton, Benjamin Britten, Thomas F. Dunhill, Ivor Gurney, and Frank Bridge. It was presented on December 12, 2001, in Homer Ulrich Recital Hall with the collaborative pianist Meriel Owen. The second program titled An Evening of American Song I comprises music written by Dominick Argento, Samuel Barber, Ned Rorem, Leonard Bernstein, and Lee Hoiby. It was presented on October 23, 2002, in Joseph & Alma Gildenhorn Recital Hall with the collaborative pianist R. Timothy McReynolds. The third program titled An Evening of American Song II written by John Duke, John Corigliano, Charles Ives, Richard Hundley, Lori Laitman, Frederick Loewe, George Gershwin, and Jerome Kern was presented on December 18, 2003, again in Joseph & Alma Gildenhorn Recital Hall with the collaborative pianist R. Timothy McReynolds and the flutist Jessica Dunnavant. Each of these three dissertation recitals occurred at the University of Maryland in College Park and was recorded. These CD recordings are held by the Michelle Smith Performing Arts Library at the University of Maryland.

The origin and evolution of synaptic proteins - choanoflagellates lead the way.

The origin of neurons was a key event in evolution, allowing metazoans to evolve rapid behavioral responses to environmental cues. Reconstructing the origin of synaptic proteins promises to reveal their ancestral functions and might shed light on the evolution of the first neuron-like cells in metazoans. By analyzing the genomes of diverse metazoans and their closest relatives, the evolutionary history of diverse presynaptic and postsynaptic proteins has been reconstructed. These analyses revealed that choanoflagellates, the closest relatives of metazoans, possess diverse synaptic protein homologs. Recent studies have now begun to investigate their ancestral functions. A primordial neurosecretory apparatus in choanoflagellates was identified and it was found that the mechanism, by which presynaptic proteins required for secretion of neurotransmitters interact, is conserved in choanoflagellates and metazoans. Moreover, studies on the postsynaptic protein homolog Homer revealed unexpected localization patterns in choanoflagellates and new binding partners, both which are conserved in metazoans. These findings demonstrate that the study of choanoflagellates can uncover ancient and previously undescribed functions of synaptic proteins.

La cultura homérica en la Escenografía del Seiscientos: "Il Greco in Troia" y "La caduta del regno dell´Amazzoni"

Sería imposible hacer una enumeración de festejos, espectáculos y representaciones teatrales, que a lo largo de la época moderna, tuvieron como argumento las historias narradas por la literatura homérica. Incontables, pero todas ellas buscaban el don de la elocuencia que tenían desde que en la Antigüedad empezaron a reeditarse. Apenas un iglo después de la recopilación de relatos orales que quedaron hilvanados bajo los títulos de la Iliada y la Odisea –si se acepta la autoría de ese personaje mítico que fue Homero en torno al siglo VIII antes de Cristo–, tiranos y oligarcas atisbaron de forma visionaria las posibilidades que aportaban las tramas en las que se vieron envueltos dioses y héroes. La mitología olímpica no sólo sirvió al propósito de la unificación panhelénica de la nación de naciones que era Grecia, en torno a un mundo de creencias común en el marco de los grandes santuario, sino que además, las vicisitudes de los principales personajes, como Paris, Aquiles, Héctor, Ulises, Pentesilea, Eneas, Agamenón, Andrómaca, Casandra y Helena, proporcionaron un repertorio de modelos de conducta y un protocolo ceremonial en sociedad extremadamente útil. Piedad, fidelidad, excelencia, belleza, sumisión, virtudes morales que habían de “adornar” por igual a gobernantes y a ciudadanos, garantizaban un nuevo orden en la Hélade, constituyendo asimismo las notas distintivas con respecto a los anquilosados y monolíticos Imperios hegemónicos en la zona de Oriente Próximo, Egipcio y Babilónico o Persa, respectivamente. Se propone el análisis de la incidencia iconológica de tales asuntos a partir de la revisión escenográfica de dos libretos para dos representaciones teatrales italianas de finales del Seicento, de los que se encuentran sendos ejemplares en la Biblioteca Nacional de Madrid: Il Greco in Troia y La caduta del regno dell´amazzone.