In this paper we propose an approach to quantum λ-calculi. The “quantum data-classical control” paradigm is considered. Starting from a measurement-free untyped quantum λ–calculus called Q, we will study standard properties such as confluence and subject reduction and some good quantum properties. We will focus on the expressive power, analyzing the relationship with other quantum computational models. Successively, we will add an explicit measurement operator to Q. On the resulting calculus, called Q∗, we will propose a complete study of reduction sequences regardless of their finiteness, proving confluence results. Moreover, since the stronger motivation behind quantum computing is the research of new results in computational complexity, we will also propose a calculus which captures the three classes of quantum polytime complexity, showing an ICC-like approach in the quantum setting.

On Quantum Lambda Calculi: a Foundational Perspective

ZORZI, Margherita
2016-01-01

Abstract

In this paper we propose an approach to quantum λ-calculi. The “quantum data-classical control” paradigm is considered. Starting from a measurement-free untyped quantum λ–calculus called Q, we will study standard properties such as confluence and subject reduction and some good quantum properties. We will focus on the expressive power, analyzing the relationship with other quantum computational models. Successively, we will add an explicit measurement operator to Q. On the resulting calculus, called Q∗, we will propose a complete study of reduction sequences regardless of their finiteness, proving confluence results. Moreover, since the stronger motivation behind quantum computing is the research of new results in computational complexity, we will also propose a calculus which captures the three classes of quantum polytime complexity, showing an ICC-like approach in the quantum setting.
2016
Lambda calculus; Quantum Computing; Implicit computational complexity; computability
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/685561
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 22
social impact