1,721,111 research outputs found
A classification of reversible bit and stabilizer operations
No full textThesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.Cataloged from PDF version of thesis.Includes bibliographical references (pages 63-64).This thesis is an exposition of a classification of classical reversible gates acting on bits in terms of the reversible transformations they generate, which was recently completed by the author, Scott Aaronson, and Luke Schaeffer. In particular, we present those portions of the classification which were the main contributions of the author. Most importantly, this thesis contains the proof that every non-affine gate generates a Fredkin gate, which was one of the main technical hurdles in completing the classification. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical logic from the 1940s, where we allow arbitrary ancilla bits to be used in the computation provided they return to their initial configuration at the end of the computation. It is a step toward the ambitious goal of classifying all possible quantum gate sets acting on qubits. This thesis also gives preliminary results for the classification of stabilizer gates, which have garnered much attention due to their role in unifying many of the known quantum error-correcting codes. In the stabilizer setting, we generalize the classical model to allow the use of arbitrary stabilizer ancillas and show that this leads to several nonintuitive results. In particular, we show that the CNOT and Hadamard gates suffice to generate all stabilizer operations (whereas the phase gate is required in a more group theoretic setting); present a complete classification of the "classical" stabilizer operations; and give exact generating sets for the one-qubit stabilizer operations.by Daniel Grier.S.M
Scott Aaronson, Quantum Computing since Democritus, Cambridge University Press, Cambridge, 2013, pp. 370.
No full textThe article is a review of "Quantum Computing Since Democritus", Scott Aaronson's introductory book on complexity theory. The volume is a first walkthrough in the land of "complexity theory", the branch of computer science tasked with formally characterizing how hard is to solve certain algorithmic problems; particular attention is given to "quantum computation" - Aaronson's main area of expertise - to introduce the reader to the possibilities offered by quantum mechanics. The review leverages the conceptual tools introduced in the book to survey the main open research themes in the field and discuss some of the philosophical arguments put forward by the author.Il contributo presenta una recensione del volume di Scott Aaronson "Quantum Computing Since Democritus". Il saggio è una introduzione alla teoria della complessità, con particolare attenzione alle sfide e alla possibilità offerte dalla “computazione quantistica”, ovvero l’utilizzo di alcune proprietà della meccanica quantistica per costruire nuovi modelli di computazione. La recensione utilizza gli strumenti concettuali messi a disposizione da Aaronson per introdurre i principali temi di ricerca della disciplina e per discutere una serie di argomentazioni
presentate dall’autore. Complessivamente, il terreno concettuale che emerge gradualmente dal volume appare filosoficamente fertile e sicuramente degno di maggiori approfondimenti
Quantum computation with identical bosons
No full textThesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017.Cataloged from PDF version of thesis.Includes bibliographical references (pages 103-106).We investigate the computational complexity of quantum computing with identical noninteracting bosons, such as that in a linear optical system. We explore the challenges in building devices that implement this model and in certifying their correctness. In work done with Scott Aaronson, we introduce BOSONSAMPLING, a computational model of quantum linear optics [1]. We argue that the statistical distribution of outcomes cannot be reproduced by any classical device in a reasonable time span. This gives hands-on evidence of quantum advantage, that there are quantum phenomena are prohibitive to simulate in the classical world. Moreover, this quantum advantage is already present in limited optical systems, suggesting a lower bar to building devices that exhibit super-classical computation. We lay out the computational complexity argument for the classical difficulty of simulating BOSONSAMPLING. An efficient classical simulation would have unlikely complexity consequences for the polynomial hierarchy PH. We look into the difficulties in proving an analogous approximate result, including the conjectures that seem to be needed to push it through. We then discuss experimental implementations of BOSONSAMPLING. The scalability of current implementations is limited by various sources of noise that accumulate as the problem size grows. We prove a result [51 that pertains to the inexactnesses of components that comprise the linear optical network, giving bounds on the tolerances that suffice to obtain an output distribution close to the ideal one. Finally, we look at the challenge of certifying a BOSONSAMPLING device. We show the impossibility of one technique, to use a submatrix whose permanent is so large that its corresponding outcome appears very frequently. Joint work with Aaronson [21 argues that the outputs of a BOSONSAMPLING device can be verified not to come from a uniform distribution. Results on the statistical bunching of bosons obtained with Kuperberg [61 are another approach to certification. We further present a novel certification technique based on classically estimating the distribution of integer combinations of the boson counts.by Aleksandr Arkhipov.Ph. D
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Get PDFWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
Is P versus NP formally independent
No full textThis is a survey about the title question, written for people who (like the author) see logic as forbidding, esoteric, and remote from their usual concerns. Beginning with a crash course on Zermelo-Fraenkel set theory, it discusses oracle independence; natural proofs; independence results of Razborov, Raz, DeMillo-Lipton, Sazanov, and others; and obstacles to proving P vs. NP independent of strong logical theories. It ends with some philosophical musings on when one should expect a mathematical question to have a definite answer.
- …
