[HoTT] HoTT as a classical equivalent of quantum programming (was: What is knot in HOTT?)

["José Manuel Rodriguez Caballero" <josephcmac@gmail.com>]

[-- 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 --]