From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-1.2 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,HTML_MESSAGE,MAILING_LIST_MULTI, RCVD_IN_DNSWL_NONE autolearn=ham autolearn_force=no version=3.4.2 Received: from mail-yw1-xc3b.google.com (mail-yw1-xc3b.google.com [IPv6:2607:f8b0:4864:20::c3b]) by inbox.vuxu.org (OpenSMTPD) with ESMTP id 109d0952 for ; Sat, 12 Jan 2019 03:22:37 +0000 (UTC) Received: by mail-yw1-xc3b.google.com with SMTP id 201sf8955375ywp.13 for ; Fri, 11 Jan 2019 19:22:37 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1547263356; cv=pass; d=google.com; s=arc-20160816; b=Sjtvzauy+CigftXA1NUHPd/RB3frxqjBoX1mvNfa0IQbwTEnDIF7iO/4xpCOYIYUSM nl7OMGobf9qHpiHXWo6RlgaawJhN2WM0x+DMRsFAazTxyhFZm6bsZCkdO7Xk8s5q7Kue 6HH4uoh69K2ouCYDkw3Hgf9a3z2N6JCp+ktg3851JJwBuDYWP0hHfr5H/RZ9TBZTC+P1 ptJ8eu3qhUVhPXJD47tSnyFtD1N0n7tA7Qth4t5uw+2BwNsJ4lrK4z+a8U6E7kfy9Ntd 7A1ZSS5DGLTGc89H/oGQyqCBdSAxdvrYUjISEculc+h+qRYgizIQJOX2OwWJJWz39q/S af3g== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-unsubscribe:list-archive:list-help:list-post:list-id :mailing-list:precedence:to:subject:message-id:date:from :mime-version:sender:dkim-signature:dkim-signature; bh=g85NYTRUCMqpiiwXowoF1xZCqbjcxQcudgMZii5Sy0M=; b=kP+t9A2E37b23BXIUDRrqclBxK5ZwHsePPHlXxHfGOmwCRZf0lchBvIAutLtiIJfKZ 1syRFZcSDck4rwvdbRj/TYj+3hb9beGcOWjUPg02uNQWgwuY+z75z7yipHs/0MiKwqPc +rliBgSJhO9JpZNFHy2jqZ85sKDBYFm26t0oHrDa2wC3/cwGJDLxICALVyt8exeNaEpN Ek3O7hKl+9P70GRsh9t+vwiMaP2TjbkD9y/b1KZBPuia2Ooc6UX6wrq3CtMyaSCEqvQ0 RPfsRUvQ+z7N/mz09g7c2sxY9K2XBky5AzwGIDKFEiRmtPL+q2VkQuY1E51bq3lnLJQ0 DGfg== ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=XOi0qqcb; spf=pass (google.com: domain of josephcmac@gmail.com designates 2607:f8b0:4864:20::134 as permitted sender) smtp.mailfrom=josephcmac@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20161025; h=sender:mime-version:from:date:message-id:subject:to :x-original-sender:x-original-authentication-results:precedence :mailing-list:list-id:list-post:list-help:list-archive :list-unsubscribe; bh=g85NYTRUCMqpiiwXowoF1xZCqbjcxQcudgMZii5Sy0M=; b=PdcRtjj0M58K4Y3Dx0wakAo8+5C4LZktz+54nDzOi5IUyCF7T7dkM8gr+6uCsXMZeC ChyGz2f4GIOvahMjjhnKZFmBf6kRoJ2xRmyhdXwm3SUVKkvW7lGRVVVglFWJEejKjO71 97ereY5o/F4phrCwNAFEfMd+Ah/17FicPsafl4L+53xY6Zlv+qLLDSAhpCdfD/adCrIg vBs68Rkga+cuwkC79DLJMhZxelo4kBeFSbrPb+0wE/TUdBUEvC2ODhDvBKwgx2ItsJfk TU4Kcj8cownUL5pLNpV2ES9vn+20thYoggnPLL4xAaaJ3USz2qaJCBj8BnSG2uiKzFV4 E8pw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to:x-original-sender :x-original-authentication-results:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-unsubscribe; bh=g85NYTRUCMqpiiwXowoF1xZCqbjcxQcudgMZii5Sy0M=; b=a76AjUkhPUeqMUHnWHo3pnNOkYx0H5j0wTYhgzALBJqu/ZrQmDBJszNwe+9/gy6vGJ oXqW/JBTz89mbiZHxD6C3KXucRwrrJ5jwIWvYScfe5Na2b2mH92bFS43Een1FmCPthgE TeMDQEpVLgHnWRGyluAW32BKgSnW0ENG1kUjcdG08XA/vIgA0hYWaRjiO6ePADGt70z7 5xm4/zU2jETYtPNotD/qX2kdViCNg28dAfUc+6xISD2S75w69JRfx4uoviOgOqwdBciR 4TVFCFCj7jd3pEhEvunwGJ3kDfRTdy43RNZSUKCGqRU5Rw0MNtIgxFZG1JRqxZku2v0D FWlQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=sender:x-gm-message-state:mime-version:from:date:message-id:subject :to:x-original-sender:x-original-authentication-results:precedence :mailing-list:list-id:x-spam-checked-in-group:list-post:list-help :list-archive:list-unsubscribe; bh=g85NYTRUCMqpiiwXowoF1xZCqbjcxQcudgMZii5Sy0M=; b=bcJnLSgNFSFcJSpx8f0PZdQCeLiNbRIKDT1egThyvrM2uJoXIUgapjDtIuRAwQx77Z IjKqEUsrLyVcUp2LTIxV0oeJEEUNum0+Bcr9p7b4abZUm7rP6ZQTA4JDIcPNSdoDhhoQ EZ+XUsbb5gfFmmsD1VN+K0QwyCu1eFv7DPnGkDV+Gb18nmWDXjq/T+F2MTj2sbHdpkaB SaimUHiCNjR5yu660GT0aw15sDDLqP2MLvYbg14R8klwDTZZIv63cRl8NmcJh3/LQNIQ ZIoY/ivaUTlTKcIwNgbPfKjcDbgbQAwUl+3FxEoXfkke9mtmvF0+hBbk5+cM8Qv1Km3P p1bg== Sender: homotopytypetheory@googlegroups.com X-Gm-Message-State: AJcUukdVjw9HxHtstNgP7TjxoauFHUFlpoHewFVgof85NgtT4s7wchj2 Z+hBEBnu51GGTcRIPGBGBn0= X-Google-Smtp-Source: ALg8bN6cKlJqfvaPyYY6x95yjp2rUlnqxm6EA8oaIm83Lfx/tzgJxOmBab9/f/VWm6UmzRIY6dwehQ== X-Received: by 2002:a25:378a:: with SMTP id e132mr19181yba.0.1547263356569; Fri, 11 Jan 2019 19:22:36 -0800 (PST) X-BeenThere: homotopytypetheory@googlegroups.com Received: by 2002:a0d:dd81:: with SMTP id g123ls6937513ywe.10.gmail; Fri, 11 Jan 2019 19:22:36 -0800 (PST) X-Received: by 2002:a81:7207:: with SMTP id n7mr1701847ywc.11.1547263356141; Fri, 11 Jan 2019 19:22:36 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1547263356; cv=none; d=google.com; s=arc-20160816; b=ShHpAHPclWRC+2Dcbw5/602j/sCY7HGxZO3y1O0JAsAS09DN08vCgFaFGEHX7wZO0W qoonidqZ6B7TfpRguyjwIcYVq768LZECCMUGs81lEBGiz9HlAl6LJ3//b9ZReRR4C1Xn 51G2OG7Ca7GdHkANaztEfW4Q4HRa2axqGqGqUwCnhxPq6pH4vnN7FEfjU96PFEsfkVzO 3Lq5LjHanjmZ1KAKgIsx6UiT0Cc98s7asClQQ/hdxf9Og4Lu7nxUDla5yxDmywa+Kpfx SIAj6OdqQwrJtKwKWPjEopXeYYdGE6Rbdq7fRkcCloDCIIKfm9W/PRmg6AwcPGedtxfP yQ/g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:subject:message-id:date:from:mime-version:dkim-signature; bh=1dR+1ZMPRRcuWEvr0226zaadZGLAvWnVzkPOkOfWyqs=; b=r1DTB3itYL0EG2HreFd0wOwBFsTzGfw9EPY0950ZGAGijczj8Zi/3Zv5C1CW50BfVo p3U1h1VOeBHG0uSEmFR6WzklBHWuz3xDYmZIu5jr15orImN1zMtBexD5fPi7/MgIOLOp 67akFkcUYfsYerLqEhE1PBe9sPHhMn0QUy3o4YhhcKp4FiQCqC6Hzc80xYS9woDlMuCJ jgNQrsRN05SAdxMCbbogJ5H4i6j6zChJt2lO2pF+GeeyvagTwSwwQcJMY2yDqOUGXwko iJKJau9dt8v0ir7hTZIcYiMF28vIormZi7rdGjS7xw3xSG8FSKqigS02D4H9tXuBxBOZ i6bQ== ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=XOi0qqcb; spf=pass (google.com: domain of josephcmac@gmail.com designates 2607:f8b0:4864:20::134 as permitted sender) smtp.mailfrom=josephcmac@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: from mail-it1-x134.google.com (mail-it1-x134.google.com. [2607:f8b0:4864:20::134]) by gmr-mx.google.com with ESMTPS id i1si4562666ywg.5.2019.01.11.19.22.36 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 11 Jan 2019 19:22:36 -0800 (PST) Received-SPF: pass (google.com: domain of josephcmac@gmail.com designates 2607:f8b0:4864:20::134 as permitted sender) client-ip=2607:f8b0:4864:20::134; Received: by mail-it1-x134.google.com with SMTP id z7so5874587iti.0 for ; Fri, 11 Jan 2019 19:22:36 -0800 (PST) X-Received: by 2002:a24:55d4:: with SMTP id e203mr2844543itb.36.1547263355425; Fri, 11 Jan 2019 19:22:35 -0800 (PST) MIME-Version: 1.0 From: =?UTF-8?Q?Jos=C3=A9_Manuel_Rodriguez_Caballero?= Date: Fri, 11 Jan 2019 22:22:24 -0500 Message-ID: Subject: [HoTT] HoTT as a classical equivalent of quantum programming (was: What is knot in HOTT?) To: HomotopyTypeTheory@googlegroups.com Content-Type: multipart/alternative; boundary="000000000000ac9b9c057f3a5276" X-Original-Sender: josephcmac@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=XOi0qqcb; spf=pass (google.com: domain of josephcmac@gmail.com designates 2607:f8b0:4864:20::134 as permitted sender) smtp.mailfrom=josephcmac@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Precedence: list Mailing-list: list HomotopyTypeTheory@googlegroups.com; contact HomotopyTypeTheory+owners@googlegroups.com List-ID: X-Google-Group-Id: 1041266174716 List-Post: , List-Help: , List-Archive: , --000000000000ac9b9c057f3a5276 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hello, This is just a possible application of the conclusions in the previous discussion entitled: "[HoTT] What is knot in HOTT?" First, I recall from the previous discussion that Andr=C3=A9 Joyal wrote: > Of course, braids, knots and tangles can be constructed algebraically > using braided monoidal categories. The only practical quantum algorithms in order to solve decision problems belong to the class BQP (bounded-error quantum polynomial time). Indeed, a quantum algorithm which is quantum exponential in time is as useless in practice as an exponential algorithm in classical exponential time. There is an interesting theorem [2, 3, 4] which guarantees that we only need one quantum algorithm in (quantum) polynomial time in order to solve all the BQP problems. This algorithm is the numerical evaluation of the Jones polynomial [1] of a knot at a root of unity. Indeed, any input of a BQP can be transformed into a knot in classical polynomial time, and this knot determines the solution of the original BQP problem by means of the numerical evaluation of the Jones polynomial at a root of unity. The argument above suggests that, in place using a quantum programming language in order to solve a problem by means of an algorithm in quantum polynomial time, it is enough to focus on a classical programming language in order to transform an input into a knot in classical polynomial time and to have a fixed quantum hardware (black box) just to evaluate the Jones polynomial. I guess that such a classical programming language may be HoTT, using the Curry-Howard-Lambek correspondence (proof =3D algorithm =3D categ= ory theory). It would be nice to know some opinions about this reduction and if it is useful in practice. Kind Regards, Jos=C3=A9 M. References: [1] Jones polynomial: https://math.berkeley.edu/~vfr/jones.pdf [2] Aharonov, Dorit, Vaughan Jones, and Zeph Landau. "A polynomial quantum algorithm for approximating the Jones polynomial." *Algorithmica* 55.3 (2009): 395-421. https://arxiv.org/pdf/quant-ph/0511096.pdf [3] Freedman, Michael H., Alexei Kitaev, and Zhenghan Wang. "Simulation of topological field theories=C2=B6 by quantum computers." *Communications in Mathematical Physics* 227.3 (2002): 587-603. https://arxiv.org/pdf/quant-ph/0001071.pdf [4] outline: https://prezi.com/r6w-yyxlispj/view/ --=20 You received this message because you are subscribed to the Google Groups "= Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to HomotopyTypeTheory+unsubscribe@googlegroups.com. For more options, visit https://groups.google.com/d/optout. --000000000000ac9b9c057f3a5276 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hello,
This is just a possible application of the = conclusions in the previous discussion entitled: "[HoTT] What is knot = in HOTT?"

First, I recall from the previous d= iscussion that

Andr=C3=A9 Joyal wrote:
Of course, braids, knots and tangles = can be constructed algebraically
using braided monoidal categories.
=C2=A0
The only practical quantum algorithms in order to = solve decision problems belong to the class BQP (bounded-error quantum poly= nomial time). Indeed, a quantum algorithm which is quantum exponential in t= ime is as useless in practice as an exponential algorithm in classical expo= nential time.=C2=A0

There is an interesting theorem [2, = 3, 4] which guarantees that we only need one quantum algorithm in (quantum)= polynomial time in order to solve all the BQP problems. This algorithm is = the numerical evaluation of the Jones polynomial [1] of a knot at a root of= unity. Indeed, any input of a BQP can be transformed into a knot in classi= cal polynomial time,=C2=A0 and this knot determines the solution of the ori= ginal BQP problem by means of the numerical evaluation of the Jones polynom= ial at a root of unity.=C2=A0

The argument above s= uggests that, in place using a quantum programming language in order to sol= ve a problem by means of an algorithm in quantum polynomial time, it is eno= ugh to focus on a classical programming language in order to transform an i= nput into a knot in classical polynomial time and to have a fixed quantum h= ardware (black box) just to evaluate the Jones polynomial. I guess that suc= h a classical programming language may be HoTT, using the=C2=A0Curry-Howard= -Lambek correspondence (proof =3D algorithm =3D category theory).

It would be nice to know some opinions about this reduction= and if it is useful in practice.

Kind Regard= s,
Jos=C3=A9 M.

References:
[1] Jones polynomial:=C2=A0https://math.berkeley.edu/~vfr/jones.pdf

[2]=C2=A0Aharonov, Dorit, Vaughan Jones, and Zeph Landau. "A pol= ynomial quantum algorithm for approximating the Jones polynomial."=C2= =A0Algorith= mica=C2=A05= 5.3 (2009): 395-421.=C2=A0https://arxiv.org/pdf/quant= -ph/0511096.pdf

Freedman, Michael H., Alexei Kitaev, and Zhenghan Wang. "Simulation= of topological field theories=C2=B6 by quantum computers."=C2=A0Communications i= n Mathematical Physics=C2=A0227.3 (2002): 587-603.=C2=A0https://ar= xiv.org/pdf/quant-ph/0001071.pdf



--
You received this message because you are subscribed to the Google Groups &= quot;Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to = HomotopyTypeTheory+unsubscribe@googlegroups.com.
For more options, visit http= s://groups.google.com/d/optout.
--000000000000ac9b9c057f3a5276--