*[HoTT] HoTT as a classical equivalent of quantum programming (was: What is knot in HOTT?)@ 2019-01-12 3:22 José Manuel Rodriguez Caballero0 siblings, 0 replies; 1+ messages in thread From: José Manuel Rodriguez Caballero @ 2019-01-12 3:22 UTC (permalink / raw) To: HomotopyTypeTheory [-- Attachment #1: Type: text/plain, Size: 2681 bytes --] 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é 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 = algorithm = category theory). It would be nice to know some opinions about this reduction and if it is useful in practice. Kind Regards, José 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¶ 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/ -- 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 email to HomotopyTypeTheory+unsubscribe@googlegroups.com. For more options, visit https://groups.google.com/d/optout. [-- Attachment #2: Type: text/html, Size: 4311 bytes --] ^ permalink raw reply [flat|nested] 1+ messages in thread

only message in thread, back to indexThread overview:(only message) (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-01-12 3:22 [HoTT] HoTT as a classical equivalent of quantum programming (was: What is knot in HOTT?) José Manuel Rodriguez Caballero

Discussion of Homotopy Type Theory and Univalent Foundations Archives are clonable: git clone --mirror http://inbox.vuxu.org/hott Newsgroup available over NNTP: nntp://inbox.vuxu.org/vuxu.archive.hott AGPL code for this site: git clone https://public-inbox.org/ public-inbox