Cálculo lambda quântico

35

Classicamente, existem três maneiras populares de pensar sobre computação: máquina de Turing, circuitos e cálculo lambda (eu uso isso como uma captura para a maioria das visualizações funcionais). Todas as três foram formas proveitosas de pensar sobre diferentes tipos de problemas, e campos diferentes usam formulações diferentes por esse motivo.

Quando trabalho com computação quântica, no entanto, só penso no modelo de circuito. Originalmente, QC foi definido em termos de máquinas quânticas de Turing, mas até onde eu entendi, essa definição (embora equivalente a circuitos quânticos, se ambos forem formulados com cuidado) não foi tão proveitosa. A terceira formulação (em termos de cálculo lambda ou configurações funcionais semelhantes) não estou familiarizada. Daí minhas perguntas:

  • Quais são as definições úteis do cálculo lambda quântico (ou outros paradigmas funcionais)?

  • Quais subcampos do QIP obtêm uma visão mais profunda do uso dessa formulação em vez do modelo de circuito?

Notas

Estou ciente de que estou ignorando muitos outros formalismos populares como autômatos celulares, modelos de RAM etc. Eu os excluo principalmente porque não tenho experiência com o pensamento clássico em termos desses modelos, e muito menos em termos quantitativos .

Também estou ciente de que existem alternativas populares no cenário quântico, como as baseadas em medições, topológicas e adiabáticas. Não os discuto porque não conheço os colegas clássicos.

lambda-calculus quantum-computing reference-request computation-models Artem Kaznatcheev
fonte
4
Eu acho que isso também ficaria bem na Ciência da Computação Teórica . :)
Kaveh
11
@Kaveh Estou muito confuso sobre onde perguntar entre cstheory e CS.SE :(. Decidi não perguntar sobre cstheory porque me deparei com uma tese recente que fala sobre programação funcional quântica (na seção 2.2), mas não o fiz. . tido tempo para pensar cuidadosamente sobre isso Então eu pensei: hey, eu vou fazer uma pergunta cozido meia.
Artem Kaznatcheev
11
Espero que isso leve a uma pergunta complicada para a história. :)
Kaveh
11
Você pode dar uma olhada no LPQL , uma linguagem de programação quântica funcional linear desenvolvida em Calgary.
jmite

Respostas:

17

eis uma resposta incompleta: sei que Ugo Dal Lago, da Universidade de Bolonha, estuda o cálculo quântico lambda. Você pode conferir as publicações dele e, talvez, esta em particular:

Complexidade computacional implícita quântica por U. Dal Lago, A. Masini, M. Zorzi.

Estou dizendo que é uma resposta incompleta, porque não tive chance de ler nenhum de seus trabalhos.

Alessandro Cosentino
fonte
12

Pedimos desculpas antecipadamente pelo plugue descarado, mas há um artigo meu sobre um cálculo quântico lambda que você pode achar interessante. É chamado de The Dagger Lambda Calculus e fornece uma representação de ordem superior para os circuitos diagramáticos que a escola categórica da computação quântica introduziu:

http://arxiv.org/abs/1406.1633

Você também pode conferir minha palestra no YouTube para mais informações:

https://www.youtube.com/watch?v=2pDPVd1BukI

Outros trabalhos na área incluem o cálculo quântico lambda de Selinger-Valiron e o cálculo lambda de Andre van Tonder: [ Sel04a ], [ Sel04b ], [ vTD03 ], [ vT04 ], [ SV04 ], [ SV08 ], [ SV10 ] .

Philip Atz
fonte