Circuit Width Estimation via Effect Typing and Linear Dependency (Extended Abstract)
Circuit description languages are a class of quantum programming languages in which programs are classical and produce a description of a quantum computation, in the form of a quantum circuit. Since these programs can leverage all the expressive power of high-level classical languages, circuit description languages have been successfully used to describe complex and practical quantum algorithms, whose circuits, however, may involve many more qubits and gate applications than current quantum architectures can actually muster. In this paper, we present Proto-Quipper-R, a circuit description language endowed with a linear dependent type-and-effect system capable of deriving parametric upper bounds on the width of the circuits produced by a program. We prove both the standard type safety results and that the resulting resource analysis is correct with respect to a big-step operational semantics. We also show that our approach is expressive enough to verify realistic quantum algorithms.
Sat 20 JanDisplayed time zone: London change
09:00 - 10:30 | |||
09:00 45mKeynote | Monoidal Adventures PLanQC Conor McBride University of Strathclyde | ||
09:45 22mTalk | Introducing BRAT PLanQC Ross Duncan Quantinuum, Mark Koch Quantinuum, Alan Lawrence Quantinuum, Conor McBride University of Strathclyde, Craig Roy Quantinuum File Attached | ||
10:07 22mTalk | Circuit Width Estimation via Effect Typing and Linear Dependency (Extended Abstract) PLanQC Andrea Colledan University of Bologna & INRIA Sophia Antipolis, Ugo Dal Lago University of Bologna & INRIA Sophia Antipolis |