Publications (48)
Efficient Clifford+T approximation of single-qubit operators
Peter Selinger
We give an efficient randomized algorithm for approximating an arbitrary element of by a product of Clifford+ operators, up to any given error threshold . Under a…
Paintbucket on graphs is PSPACE-complete
Ethan J. Saunders, Peter Selinger
The game of Paintbucket was recently introduced by Amundsen and Erickson. It is played on a rectangular grid of black and white pixels. The players alternately fill in one of their…
Dependently Typed Folds for Nested Data Types
Peng Fu, Peter Selinger
We present an approach to develop folds for nested data types using dependent types. We call such folds , they have the following properties. (1)…
Presheaf models of quantum computation: an outline
Octavio Malherbe, Philip Scott, Peter Selinger
This paper outlines the construction of categorical models of higher-order quantum computation. We construct a concrete denotational semantics of Selinger and Valiron's quantum lam…
Remarks on Matsumoto and Amano's normal form for single-qubit Clifford+T operators
Brett Giles, Peter Selinger
Matsumoto and Amano (2008) showed that every single-qubit Clifford+T operator can be uniquely written of a particular form, which we call the Matsumoto-Amano normal form. In this m…
A finite alternation result for reversible boolean circuits
Peter Selinger
We say that a reversible boolean function on n bits has alternation depth d if it can be written as the sequential composition of d reversible boolean functions, each of which acts…
Generators and Relations for the Group On(Z[1/2])
Sarah Meng Li, Neil J. Ross, Peter Selinger
We give a finite presentation by generators and relations for the group O_n(Z[1/2]) of n-dimensional orthogonal matrices with entries in Z[1/2]. We then obtain a similar presentati…
Finite dimensional Hilbert spaces are complete for dagger compact closed categories
Peter Selinger
We show that an equation follows from the axioms of dagger compact closed categories if and only if it holds in finite dimensional Hilbert spaces.
Completely positive projections and biproducts
Chris Heunen, Aleks Kissinger, Peter Selinger
The recently introduced CP*-construction unites quantum channels and classical systems, subsuming the earlier CPM-construction in categorical quantum mechanics. We compare this con…
On the combinatorial value of Hex positions
Peter Selinger
We develop a theory of combinatorial games that is appropriate for describing positions in Hex and other monotone set coloring games. We consider two natural conditions on such gam…
Generators and Relations for Un(Z[1/2,i])
Xiaoning Bian, Peter Selinger
Consider the universal gate set for quantum computing consisting of the gates X, CX, CCX, omega^dagger H, and S. All of these gates have matrix entries in the ring Z[1/2,i], the sm…
Proceedings 8th International Workshop on Quantum Physics and Logic
Bart Jacobs, Peter Selinger, Bas Spitters
This volume contains the proceedings of the 8th International Workshop on Quantum Physics and Logic (QPL 2011), which was held October 27-29, 2011 at Radboud University Nijmegen. T…
On Traces in Categories of Contractions
Aaron David Fairbanks, Peter Selinger
Traced monoidal categories are used to model processes that can feed their outputs back to their own inputs, abstracting iteration. The category of finite dimensional Hilbert space…
A lambda calculus for quantum computation with classical control
Peter Selinger, Benoit Valiron
The objective of this paper is to develop a functional programming language for quantum computers. We develop a lambda calculus for the classical control model, following the first…
Longest winning paths in Hex
Peter Selinger
We answer the question: what is the longest winning path on a Hex board of size ?
Applying quantitative semantics to higher-order quantum computing
Michele Pagani, Peter Selinger, Benoît Valiron
Finding a denotational semantics for higher order quantum computation is a long-standing problem in the semantics of quantum programming languages. Most past approaches to this pro…
A tutorial introduction to quantum circuit programming in dependently typed Proto-Quipper
Peng Fu, Kohei Kishida, Neil J. Ross +1
We introduce dependently typed Proto-Quipper, or Proto-Quipper-D for short, an experimental quantum circuit programming language with linear dependent types. We give several exampl…
Quantum circuits of T-depth one
Peter Selinger
We give a Clifford+T representation of the Toffoli gate of T-depth 1, using four ancillas. More generally, we describe a class of circuits whose T-depth can be reduced to 1 by usin…
Generators and Relations for Real Stabilizer Operators
Justin Makary, Neil J. Ross, Peter Selinger
Real stabilizer operators, which are also known as real Clifford operators, are generated, through composition and tensor product, by the Hadamard gate, the Pauli Z gate, and the c…
A Categorical Model for a Quantum Circuit Description Language (Extended Abstract)
Francisco Rios, Peter Selinger
Quipper is a practical programming language for describing families of quantum circuits. In this paper, we formalize a small, but useful fragment of Quipper called Proto-Quipper-M.…
All passable games are realizable as monotone set coloring games
Eric Demer, Peter Selinger, Kyle Wang
The class of passable games was recently introduced by Selinger as a class of combinatorial games that are suitable for modelling monotone set coloring games such as Hex. In a mono…
Exact synthesis of multiqubit Clifford+T circuits
Brett Giles, Peter Selinger
We prove that a unitary matrix has an exact representation over the Clifford+T gate set with local ancillas if and only if its entries are in the ring Z[1/sqrt(2),i]. Moreover, we…
A survey of graphical languages for monoidal categories
Peter Selinger
This article is intended as a reference guide to various notions of monoidal categories and their associated string diagrams. It is hoped that this will be useful not just to mathe…
A linear-non-linear model for a computational call-by-value lambda calculus (extended abstract)
Peter Selinger, Benoît Valiron
We give a categorical semantics for a call-by-value linear lambda calculus. Such a lambda calculus was used by Selinger and Valiron as the backbone of a functional programming lang…
Proceedings of the 15th International Conference on Quantum Physics and Logic
Peter Selinger, Giulio Chiribella
Quantum Physics and Logic is an annual conference that brings together researchers working on mathematical foundations of quantum physics, quantum computing, and related areas, wit…
Reversible k-valued logic circuits are finitely generated for odd k
Peter Selinger
In his 2003 paper "Towards an algebraic theory of Boolean circuits", Lafont notes that the class of reversible circuits over a set of k truth values is finitely generated when k is…
Some improvements to product formula circuits for Hamiltonian simulation
Andre Kornell, Peter Selinger
We provide three improvements to the product formula implementation of the ground state energy estimation algorithm via Trotter-Suzuki decomposition. These consist of smaller circu…
Lecture notes on the lambda calculus
Peter Selinger
This is a set of lecture notes that developed out of courses on the lambda calculus that I taught at the University of Ottawa in 2001 and at Dalhousie University in 2007 and 2013.…
An Introduction to Quantum Programming in Quipper
Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross +2
Quipper is a recently developed programming language for expressing quantum computations. This paper gives a brief tutorial introduction to the language, through a demonstration of…
Proto-Quipper with Reversing and Control
Peng Fu, Kohei Kishida, Neil J. Ross +1
The quantum programming language Quipper supports circuit operations such as reversing and controlling certain quantum circuits. Additionally, Quipper provides a function called wi…
Towards an induction principle for nested data types
Peng Fu, Peter Selinger
A well-known problem in the theory of dependent types is how to handle so-called nested data types. These data types are difficult to program and to reason about in total dependent…
Optimal ancilla-free Clifford+T approximation of z-rotations
Neil J. Ross, Peter Selinger
We consider the problem of approximating arbitrary single-qubit z-rotations by ancilla-free Clifford+T circuits, up to given epsilon. We present a fast new probabilistic algorithm…
Partially traced categories
Octavio Malherbe, Philip J. Scott, Peter Selinger
This paper deals with questions relating to Haghverdi and Scott's notion of partially traced categories. The main result is a representation theorem for such categories: we prove t…
Quipper: Concrete Resource Estimation in Quantum Algorithms
Jonathan M. Smith, Neil J. Ross, Peter Selinger +1
Despite the rich literature on quantum algorithms, there is a surprisingly small amount of coverage of their concrete logical design and implementation. Most resource estimation is…
Quipper: A Scalable Quantum Programming Language
Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross +2
The field of quantum algorithms is vibrant. Still, there is currently a lack of programming languages for describing quantum computation on a practical scale, i.e., not just at the…
On 3-terminal positions in Hex
Eric Demer, Peter Selinger
This paper is about 3-terminal regions in Hex. A 3-terminal region is a region of the Hex board that is completely surrounded by black and white stones, in such a way that the blac…
A Biset-Enriched Categorical Model for Proto-Quipper with Dynamic Lifting
Peng Fu, Kohei Kishida, Neil J. Ross +1
Quipper and Proto-Quipper are a family of quantum programming languages that, by their nature as circuit description languages, involve two runtimes: one at which the program gener…
Generators and Relations for 3-Qubit Clifford+CS Operators
Xiaoning Bian, Peter Selinger
We give a presentation by generators and relations of the group of 3-qubit Clifford+CS operators. The proof roughly consists of two parts: (1) applying the Reidemeister-Schreier th…
On the Lambek embedding and the category of product-preserving presheaves
Peng Fu, Kohei Kishida, Neil J. Ross +1
It is well-known that the category of presheaf functors is complete and cocomplete, and that the Yoneda embedding into the presheaf category preserves products. However, the Yoneda…
Proto-Quipper with dynamic lifting
Peng Fu, Kohei Kishida, Neil J. Ross +1
Quipper is a functional programming language for quantum computing. Proto-Quipper is a family of languages aiming to provide a formal foundation for Quipper. In this paper, we exte…
Proceedings 12th International Workshop on Quantum Physics and Logic
Chris Heunen, Peter Selinger, Jamie Vicary
This volume contains the proceedings of the 12th International Workshop on Quantum Physics and Logic (QPL 2015), which was held July 15-17, 2015 at Oxford University. The goal of t…
Simplicial cycles and the computation of simplicial trees
Massimo Caboara, Sara Faridi, Peter Selinger
We generalize the concept of a cycle from graphs to simplicial complexes. We show that a simplicial cycle is either a sequence of facets connected in the shape of a circle, or is a…
Linear Dependent Type Theory for Quantum Programming Languages
Peng Fu, Kohei Kishida, Peter Selinger
Modern quantum programming languages integrate quantum resources and classical control. They must, on the one hand, be linearly typed to reflect the no-cloning property of quantum…
There are infinitely many monotone games over
Eric Demer, Peter Selinger
A notion of combinatorial game over a partially ordered set of atomic outcomes was recently introduced by Selinger. These games are appropriate for describing the value of position…
Generators and relations for n-qubit Clifford operators
Peter Selinger
We define a normal form for Clifford circuits, and we prove that every Clifford operator has a unique normal form. Moreover, we present a rewrite system by which any Clifford circu…
A construction of the hat tilings by a Markov partition
Sébastien Labbé, Peter Selinger
We present a simple construction of hat tilings. The construction can be carried out by superimposing a triangular grid on a specially colored image and reading off the orientation…
Generators and Relations for 2-Qubit Clifford+T Operators
Xiaoning Bian, Peter Selinger
We give a presentation by generators and relations of the group of Clifford+T operators on two qubits. The proof relies on an application of the Reidemeister-Schreier theorem to an…
On the mathematics of the free-choice paradigm
Peter Selinger, Kristopher Tapp
Chen and Risen pointed out a logical flaw affecting the conclusions of a number of past experiments that used the free-choice paradigm to measure choice-induced attitude change. Th…