Kwantowy rachunek lambda

35

Klasycznie istnieją 3 popularne sposoby myślenia o obliczeniach: maszyna Turinga, obwody i rachunek lambda (używam tego jako haczyka dla większości widoków funkcjonalnych). Wszystkie 3 były owocnymi sposobami myślenia o różnych typach problemów, a różne dziedziny stosują różne formuły z tego powodu.

Kiedy jednak pracuję z obliczeniami kwantowymi, zawsze myślę tylko o modelu obwodu. Pierwotnie QC zdefiniowano w kategoriach kwantowych maszyn Turinga, ale o ile rozumiem, ta definicja (choć równoważna obwodom kwantowym, jeśli oba są formułowane ostrożnie), nie była tak owocna. Trzecie sformułowanie (pod względem rachunku lambda lub podobnych ustawień funkcjonalnych) jest mi zupełnie nieznane. Stąd moje pytania:

  • Jakie są przydatne definicje kwantowego rachunku lambda (lub innych paradygmatów funkcjonalnych)?

  • Jakie podpola QIP zyskują głębszy wgląd dzięki zastosowaniu tego sformułowania zamiast modelu obwodu?

Notatki

Wiem, że ignoruję wiele innych popularnych formalizmów, takich jak automaty komórkowe, modele pamięci RAM itp. Wykluczam je głównie dlatego, że nie mam doświadczenia w myśleniu o tych modelach klasycznie, a co dopiero kwantowo .

Zdaję sobie również sprawę, że w ustawieniach kwantowych istnieją popularne alternatywy, takie jak oparte na pomiarach, topologiczne i adiabatyczne. Nie omawiam ich, ponieważ nie znam klasycznych odpowiedników.

lambda-calculus quantum-computing reference-request computation-models Artem Kaznatcheev
źródło
4
Myślę, że byłoby to również w porządku w Teoretycznej Informatyki . :)
Kaveh
1
@Kaveh Jestem bardzo zdezorientowany, gdzie zapytać między cstheory a CS.SE :(. Postanowiłem nie pytać o cstheory, ponieważ natknąłem się na ostatnią tezę, która mówi o kwantowym programowaniu funkcjonalnym (w sekcji 2.2), ale nie miałem czas dokładnie się nad tym zastanowić. Pomyślałem więc: hej, zadam na wpół upieczone pytanie
Artem Kaznatcheev
1
Mam nadzieję, że doprowadzi to do upieczonego pytania o cstheory. :)
Kaveh
1
Możesz rzucić okiem na LPQL , liniowy funkcjonalny kwantowy język programowania opracowany w Calgary.
jmite

Odpowiedzi:

17

oto na wpół upieczona odpowiedź: wiem, że Ugo Dal Lago z University of Bologna studiował kwantowy rachunek lambda. Możesz sprawdzić jego publikacje, a może w szczególności tę:

Kwantowa niejawna złożoność obliczeniowa autorstwa U. Dal Lago, A. Masini, M. Zorzi.

Mówię, że to na wpół upieczona odpowiedź, ponieważ nie miałem okazji przeczytać żadnej z jego prac.

Alessandro Cosentino
źródło
12

Z góry przepraszam za bezwstydną wtyczkę, ale na kwantowym rachunku lambda jest mój papier, który może cię zainteresować. Nazywa się on The Dagger Lambda Calculus i zapewnia wyższą reprezentację schematów obwodów, które wprowadziła kategoryczna szkoła obliczeń kwantowych:

http://arxiv.org/abs/1406.1633

Możesz również sprawdzić moją rozmowę na YouTube, aby uzyskać więcej informacji:

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

Inne prace w tym obszarze obejmują kwantowe obliczenia lambda Selingera-Valirona oraz rachunek lambda Andrea van Tondera: [ Sel04a ], [ Sel04b ], [ vTD03 ], [ vT04 ], [ SV04 ], [ SV08 ], [ SV10 ] .

Philip Atz
źródło