[HoTT] HoTT as a classical equivalent of quantum programming (was: What is knot in HOTT?)mailto:homotopytypetheory@googlegroups.com2019-06-25T09:09:21ZJosé Manuel Rodriguez Caballerojosephcmac@gmail.com[HoTT] HoTT as a classical equivalent of quantum programming (was: What is knot in HOTT?)2019-01-12T03:22:37Zurn:uuid:dc6cdc6f-6d29-8797-f249-0b5b243c1980
```[-- 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  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).

useful in practice.

Kind Regards,
José M.

References:
 Jones polynomial: https://math.berkeley.edu/~vfr/jones.pdf

 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

 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

 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.