Квантовое лямбда-исчисление

35

Классически, есть 3 популярных способа думать о вычислениях: машина Тьюринга, схемы и лямбда-исчисление (я использую это как ловушку для большинства функциональных представлений). Все 3 были плодотворными способами думать о различных типах проблем, и разные области используют разные формулировки по этой причине.

Однако когда я работаю с квантовыми вычислениями, я всегда думаю только о схемотехнической модели. Первоначально КК определялся в терминах квантовых машин Тьюринга, но, насколько я понимаю, это определение (хотя и эквивалентное квантовым цепям, если обе они сформулированы тщательно) не было столь же плодотворным. Третья формулировка (с точки зрения лямбда-исчисления или аналогичных функциональных параметров) мне совершенно незнакома. Отсюда и мои вопросы:

  • Каковы полезные определения квантового лямбда-исчисления (или других функциональных парадигм)?

  • Какие подполя QIP получают более глубокое понимание от использования этой формулировки вместо схемной модели?

Заметки

Мне известно, что я игнорирую многие другие популярные формализмы, такие как клеточные автоматы, RAM-модели и т. Д. Я исключаю их главным образом потому, что у меня нет опыта мышления в терминах этих моделей классически, не говоря уже о квантовом .

Мне также известно, что в квантовой обстановке существуют популярные альтернативы, такие как основанные на измерениях, топологические и адиабатические. Я не обсуждаю их, потому что я не знаком с классическими аналогами.

lambda-calculus quantum-computing reference-request computation-models Артем Казнатчеев
источник
4
Я думаю, что это будет хорошо и для теоретической информатики . :)
Kaveh
1
@Kaveh Я очень смущен тем, где спрашивать между cstheory и CS.SE :(. Я решил не спрашивать о cstheory, потому что наткнулся на недавний тезис, в котором говорится о квантовом функциональном программировании (в разделе 2.2), но не у меня было время тщательно обдумать это. Поэтому я подумал: эй, я задам недоделанный вопрос.
Артем Казнатчеев
1
Надеюсь, это приведет к запутанному вопросу о теории. :)
Kaveh
1
Возможно, вы захотите взглянуть на LPQL , язык линейного функционального квантового программирования, разработанный в Калгари.
15:00

Ответы:

17

вот недоделанный ответ: я знаю, что Уго Дал Лаго из Болонского университета изучал квантовое лямбда-исчисление. Вы можете проверить его публикации и, возможно, этот, в частности:

Квантовая неявная вычислительная сложность У. Даля Лаго, А. Масини, М. Зорзи.

Я говорю, что это недоделанный ответ, потому что у меня не было возможности прочитать ни одну из его работ.

Алессандро Косентино
источник
12

Заранее извиняюсь за бесстыдную пробку, но есть моя статья о квантовом лямбда-исчислении, которая может вас заинтересовать. Он называется лямбда-исчислением Кинжала и предоставляет представление более высокого порядка для диаграммных схем, которые ввела категориальная школа квантовых вычислений:

http://arxiv.org/abs/1406.1633

Вы также можете проверить мой доклад на YouTube для получения дополнительной информации:

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

Другие работы в этой области включают в себя квантовое лямбда-исчисление Селинджера-Валирона и лямбда-исчисление Андре ван Тондера: [ Sel04a ], [ Sel04b ], [ vTD03 ], [ vT04 ], [ SV04 ], [ SV08 ], [ SV10 ] ,

Филип Ац
источник