* [HoTT] HoTT as a classical equivalent of quantum programming (was: What is knot in HOTT?)
@ 2019-01-12 3:22 José Manuel Rodriguez Caballero
0 siblings, 0 replies; 1+ messages in thread
From: José Manuel Rodriguez Caballero @ 2019-01-12 3:22 UTC (permalink / raw)
[-- Attachment #1: Type: text/plain, Size: 2681 bytes --]
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
It would be nice to know some opinions about this reduction and if it is
useful in practice.
 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.
 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 HomotopyTypeTheoryfirstname.lastname@example.org.
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 index
Thread 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:
AGPL code for this site: git clone https://public-inbox.org/ public-inbox