%0 Journal Article %J Quantum Information and Computation %D 2016 %T Optimal ancilla-free Clifford+T approximation of z-rotations %A Neil J. Ross %A Peter Selinger %X

We consider the problem of decomposing arbitrary single-qubit z-rotations into ancilla-free Clifford+T circuits, up to given epsilon. We present a new efficient algorithm for solving this problem optimally, i.e., for finding the shortest possible circuit whatsoever for the given problem instance. The algorithm requires a factoring oracle (such as a quantum computer). Even in the absence of a factoring oracle, the algorithm is still near-optimal: In this case, it finds a solution of T-count m + O(log(log(1/epsilon))), where m is the T-count of the second-to-optimal solution. In the typical case, this yields circuit decompositions of T-count 3log_2(1/epsilon) + O(log(log(1/epsilon))).

%B Quantum Information and Computation %V 16 %P 901-953 %G eng %U http://arxiv.org/abs/1403.2975v2 %N 11-12 %0 Journal Article %J Communications of the ACM %D 2015 %T Programming the Quantum Future %A D. Scott Alexander %A Neil J. Ross %A Peter Selinger %A Jonathan M. Smith %A Benoît Valiron %X The earliest computers, like the ENIAC, were rare and heroically difficult to program. That difficulty stemmed from the requirement that algorithms be expressed in a "vocabulary" suited to the particular hardware available, ranging from function tables for the ENIAC to more conventional arithmetic and movement operations on later machines. Introduction of symbolic programming languages, exemplified by FORTRAN, solved a major difficulty for the next generation of computing devices by enabling specification of an algorithm in a form more suitable for human understanding, then translating this specification to a form executable by the machine. The "programming language" used for such specification bridged a semantic gap between the human and the computing device. It provided two important features: high-level abstractions, taking care of automated bookkeeping, and modularity, making it easier to reason about sub-parts of programs. %B Communications of the ACM %V 58 %P 52-61 %8 2015/08/01 %G eng %U http://cacm.acm.org/magazines/2015/8/189851-programming-the-quantum-future/fulltext#comments %N 8 %R 10.1145/2699415 %0 Journal Article %D 2014 %T Quipper: Concrete Resource Estimation in Quantum Algorithms %A Jonathan M. Smith %A Neil J. Ross %A Peter Selinger %A Benoît Valiron %X

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 done at the level of complexity analysis, but actual concrete numbers (of quantum gates, qubits, etc.) can differ by orders of magnitude. The line of work we present here is a formal framework to write, and reason about, quantum algorithms. Specifically, we designed a language, Quipper, with scalability in mind, and we are able to report actual resource counts for seven non-trivial algorithms found in the quantum computer science literature.

%8 2014/12/01 %G eng %U http://arxiv.org/abs/1412.0625v1 %0 Journal Article %J Lecture Notes in Computer Science %D 2013 %T An Introduction to Quantum Programming in Quipper %A Alexander S. Green %A Peter LeFanu Lumsdaine %A Neil J. Ross %A Peter Selinger %A Benoît Valiron %X 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 how to make use of some of its key features. We illustrate many of Quipper's language features by developing a few well known examples of Quantum computation, including quantum teleportation, the quantum Fourier transform, and a quantum circuit for addition. %B Lecture Notes in Computer Science %V 7948 %P 110-124 %8 2013/07/05 %@ 978-3-642-38986-3 %G eng %U http://arxiv.org/abs/1304.5485v1 %! Lecture Notes in Computer Science 7948:110-124 %R 10.1007/978-3-642-38986-3_10 %0 Journal Article %J ACM SIGPLAN Notices %D 2013 %T Quipper: A Scalable Quantum Programming Language %A Alexander S. Green %A Peter LeFanu Lumsdaine %A Neil J. Ross %A Peter Selinger %A Benoît Valiron %X

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 level of toy problems. We address this issue by introducing Quipper, a scalable, expressive, functional, higher-order quantum programming language. Quipper has been used to program a diverse set of non-trivial quantum algorithms, and can generate quantum gate representations using trillions of gates. It is geared towards a model of computation that uses a classical computer to control a quantum device, but is not dependent on any particular model of quantum hardware. Quipper has proven effective and easy to use, and opens the door towards using formal methods to analyze quantum algorithms.

%B ACM SIGPLAN Notices %V 48 %P 333-342 %8 2013/06/23 %G eng %U http://arxiv.org/abs/1304.3390v1 %N 6 %! SIGPLAN Not. %R 10.1145/2499370.2462177