From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/7782 Path: news.gmane.org!not-for-mail From: selinger@mathstat.dal.ca (Peter Selinger) Newsgroups: gmane.science.mathematics.categories Subject: RE: Quipper: a quantum programming language Date: Thu, 20 Jun 2013 21:23:27 -0300 (ADT) Message-ID: References: Reply-To: selinger@mathstat.dal.ca (Peter Selinger) NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1371821682 11883 80.91.229.3 (21 Jun 2013 13:34:42 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 21 Jun 2013 13:34:42 +0000 (UTC) Cc: categories@mta.ca (Categories List) To: joyal.andre@uqam.ca Original-X-From: majordomo@mlist.mta.ca Fri Jun 21 15:34:43 2013 Return-path: Envelope-to: gsmc-categories@m.gmane.org Original-Received: from smtp3.mta.ca ([138.73.1.186]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Uq1U9-0007QO-W8 for gsmc-categories@m.gmane.org; Fri, 21 Jun 2013 15:34:42 +0200 Original-Received: from mlist.mta.ca ([138.73.1.63]:36386) by smtp3.mta.ca with esmtp (Exim 4.80) (envelope-from ) id 1Uq1Ss-000264-Cc; Fri, 21 Jun 2013 10:33:22 -0300 Original-Received: from majordomo by mlist.mta.ca with local (Exim 4.71) (envelope-from ) id 1Uq1Sr-00026d-Ff for categories-list@mlist.mta.ca; Fri, 21 Jun 2013 10:33:21 -0300 In-Reply-To: X-Mailer: ELM [version 2.5 PL8] Precedence: bulk Xref: news.gmane.org gmane.science.mathematics.categories:7782 Archived-At: Dear Andre, yes, you are right. Quantum computers can be simulated on classical computers, but not efficiently. The simulation can be done in exponential time (or more specifically, polynomial space). Quipper includes such a simulator (but it is only intended for testing small components, not to actually run whole programs). It is an interesting fact that there are subclasses of quantum computing that *can* be efficiently simulated. Consider the monoidal category U of finite dimensional Hilbert spaces and unitary maps. Consider a 2-dimensional Hilbert space V, and consider the full subcategory U' with objects {1, V, V*V, V*V*V, ...}; here "*" denotes tensor product. It is this monoidal category in which quantum computation usually "takes place". More precisely, one usually considers a set of generators, for example, some finite set of maps A,B,C :: V -> V and another finite set of maps D,E,F :: V*V -> V*V. Let U'' be the smallest monoidal subcategory of U' that contains these given maps. For almost all choices of A...F, U'' will be dense in U'. In the setting of quantum computing, the generators A...F are called "gates"; the morphisms of the free monoidal category generated by A...F are called "circuits", and each circuit of course defines a morphism of U''. Somehow quantum computing is concerned with how to write certain interesting unitary maps in terms of the given generators. This is quite analogous to classical (boolean) circuits, where "programming" means to decompose a given boolean function of interest into elementary gates (usually and, or, not, and a fanout gate). From the point of view, the difference between classical and quantum computation is that boolean circuit form a cartesian, rather than monoidal, category. To get back to the issue of simulation: Consider the generators X,Y,Z,H,S and CNOT, where X,Y,Z are the Pauli matrices, H is the Hadamard gate, S is the phase gate, and CNOT :: V*V -> V*V is the controlled not gate. Their matrices are: X Y Z H S 0 1 0 -i 1 0 s s 1 0 1 0 i 0 0 -1 s -s 0 i CNOT 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 where s = 1 / sqrt(2). The monoidal category U'' spanned by these generators is the so-called Clifford groupoid. Interestingly, U'' is not at all dense in U'; moreover, it is a (non-trivial) theorem that quantum computations using only gates from the Clifford groupoid can be efficiently simulated on a classical computer. It follows, as a corollary, that any interesting quantum computation must use at least one non-Clifford gate. Sorry, this was probably a much longer answer than you asked for. I'm indulging myself because I think, as a category theorist, this way of looking at quantum computation is appealing. Best, -- Peter Joyal, Andr?? wrote: > > Dear Peter, > > I thank you for your answer. > > Is it possible to "simulate" quantum > computing on ordinary computers? > Operator algebra is matrix algebra. > Surely, there will be a loss of efficiency. > But it might help understanding > the nature of quantum computations. > > Best wishes, > -Andr?? > [For admin and other information see: http://www.mta.ca/~cat-dist/ ]