TY - JOUR T1 - Optimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation Y1 - 2020 A1 - Andrew N. Glaudell A1 - Neil J. Ross A1 - J. M. Taylor AB -

We study two-qubit circuits over the Clifford+CS gate set which consists of Clifford gates together with the controlled-phase gate CS=diag(1,1,1,i). The Clifford+CS gate set is universal for quantum computation and its elements can be implemented fault-tolerantly in most error-correcting schemes with magic state distillation. However, since non-Clifford gates are typically more expensive to perform in a fault-tolerant manner, it is desirable to construct circuits that use few CS gates. In the present paper, we introduce an algorithm to construct optimal circuits for two-qubit Clifford+CS operators. Our algorithm inputs a Clifford+CS operator U and efficiently produces a Clifford+CS circuit for U using the least possible number of CS gates. Because our algorithm is deterministic, the circuit it associates to a Clifford+CS operator can be viewed as a normal form for the operator. We give a formal description of these normal forms as walks over certain graphs and use this description to derive an asymptotic lower bound of 5log(1/epsilon)+O(1) on the number CS gates required to epsilon-approximate any 4x4 unitary matrix. 

UR - https://arxiv.org/abs/2001.05997 ER - TY - JOUR T1 - Canonical forms for single-qutrit Clifford+T operators JF - Annals of Physics Y1 - 2019 A1 - Andrew N. Glaudell A1 - Neil J. Ross A1 - J. M. Taylor AB -

We introduce canonical forms for single qutrit Clifford+T circuits and prove that every single-qutrit Clifford+T operator admits a unique such canonical form. We show that our canonical forms are T-optimal in the sense that among all the single-qutrit Clifford+T circuits implementing a given operator our canonical form uses the least number of T gates. Finally, we provide an algorithm which inputs the description of an operator (as a matrix or a circuit) and constructs the canonical form for this operator. The algorithm runs in time linear in the number of T gates. Our results provide a higher-dimensional generalization of prior work by Matsumoto and Amano who introduced similar canonical forms for single-qubit Clifford+T circuits. 

VL - 406 U4 - 54-70 UR - https://arxiv.org/abs/1803.05047 U5 - https://doi.org/10.1016/j.aop.2019.04.001 ER - TY - JOUR T1 - Graphical Methods in Device-Independent Quantum Cryptography JF - Quantum Y1 - 2019 A1 - Spencer Breiner A1 - Carl Miller A1 - Neil J. Ross AB -

We introduce a framework for graphical security proofs in device-independent quantum cryptography using the methods of categorical quantum mechanics. We are optimistic that this approach will make some of the highly complex proofs in quantum cryptography more accessible, facilitate the discovery of new proofs, and enable automated proof verification. As an example of our framework, we reprove a recent result from device-independent quantum cryptography: any linear randomness expansion protocol can be converted into an unbounded randomness expansion protocol. We give a graphical exposition of a proof of this result and implement parts of it in the Globular proof assistant.

VL - 3 UR - https://arxiv.org/abs/1705.09213 CP - 146 U5 - https://doi.org/10.22331/q-2019-05-27-146 ER - TY - JOUR T1 - Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits Y1 - 2019 A1 - Matthew Amy A1 - Andrew N. Glaudell A1 - Neil J. Ross AB -

Kliuchnikov, Maslov, and Mosca proved in 2012 that a 2×2 unitary matrix V can be exactly represented by a single-qubit Clifford+T circuit if and only if the entries of V belong to the ring Z[1/2–√,i]. Later that year, Giles and Selinger showed that the same restriction applies to matrices that can be exactly represented by a multi-qubit Clifford+T circuit. These number-theoretic characterizations shed new light upon the structure of Clifford+T circuits and led to remarkable developments in the field of quantum compiling. In the present paper, we provide number-theoretic characterizations for certain restricted Clifford+T circuits by considering unitary matrices over subrings of Z[1/2–√,i]. We focus on the subrings Z[1/2], Z[1/2–√], Z[1/-2−−√], and Z[1/2,i], and we prove that unitary matrices with entries in these rings correspond to circuits over well-known universal gate sets. In each case, the desired gate set is obtained by extending the set of classical reversible gates {X,CX,CCX} with an analogue of the Hadamard gate and an optional phase gate.

UR - https://arxiv.org/abs/1908.06076 ER - TY - JOUR T1 - Automated optimization of large quantum circuits with continuous parameters JF - npj:Quantum Information Y1 - 2018 A1 - Yunseong Nam A1 - Neil J. Ross A1 - Yuan Su A1 - Andrew M. Childs A1 - Dmitri Maslov AB -

We develop and implement automated methods for optimizing quantum circuits of the size and type expected in quantum computations that outperform classical computers. We show how to handle continuous gate parameters and report a collection of fast algorithms capable of optimizing large-scale quantum circuits. For the suite of benchmarks considered, we obtain substantial reductions in gate counts. In particular, we provide better optimization in significantly less time than previous approaches, while making minimal structural changes so as to preserve the basic layout of the underlying quantum algorithms. Our results help bridge the gap between the computations that can be run on existing hardware and those that are expected to outperform classical computers. 

VL - 4 UR - https://arxiv.org/abs/1710.07345 CP - 23 U5 - https://doi.org/10.1038/s41534-018-0072-4 ER - TY - JOUR T1 - Toward the first quantum simulation with quantum speedup JF - Proceedings of the National Academy of Sciences Y1 - 2018 A1 - Andrew M. Childs A1 - Dmitri Maslov A1 - Yunseong Nam A1 - Neil J. Ross A1 - Yuan Su AB -

With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, using diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically infeasible instances of factoring and quantum chemistry, bringing practical quantum computation closer to reality.

VL - 115 U4 - 9456-9461 UR - https://arxiv.org/abs/1711.10980 U5 - https://doi.org/10.1073/pnas.1801723115 ER - TY - JOUR T1 - A finite presentation of CNOT-dihedral operators Y1 - 2016 A1 - Matthew Amy A1 - Jianxin Chen A1 - Neil J. Ross AB -

We give a finite presentation by generators and relations of unitary operators expressible over the {CNOT, T, X} gate set, also known as CNOT-dihedral operators. To this end, we introduce a notion of normal form for CNOT-dihedral circuits and prove that every CNOT-dihedral operator admits a unique normal form. Moreover, we show that in the presence of certain structural rules only finitely many circuit identities are required to reduce an arbitrary CNOT-dihedral circuit to its normal form. By appropriately restricting our relations, we obtain a finite presentation of unitary operators expressible over the {CNOT, T } gate set as a corollary.

UR - https://arxiv.org/abs/1701.00140 ER - TY - JOUR T1 - Optimal ancilla-free Clifford+T approximation of z-rotations JF - Quantum Information and Computation Y1 - 2016 A1 - Neil J. Ross A1 - Peter Selinger AB -

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))).

VL - 16 U4 - 901-953 UR - http://arxiv.org/abs/1403.2975v2 CP - 11-12 ER - TY - JOUR T1 - Optimal ancilla-free Clifford+V approximation of z-rotations JF - Quantum Information and Computation Y1 - 2015 A1 - Neil J. Ross AB - We describe a new efficient algorithm to approximate z-rotations by ancilla-free Clifford+V circuits, up to a given precision epsilon. Our algorithm is optimal in the presence of an oracle for integer factoring: it outputs the shortest Clifford+V circuit solving the given problem instance. In the absence of such an oracle, our algorithm is still near-optimal, producing circuits of V-count m + O(log(log(1/epsilon))), where m is the V-count of the third-to-optimal solution. A restricted version of the algorithm approximates z-rotations in the Pauli+V gate set. Our method is based on previous work by the author and Selinger on the optimal ancilla-free approximation of z-rotations using Clifford+T gates and on previous work by Bocharov, Gurevich, and Svore on the asymptotically optimal ancilla-free approximation of z-rotations using Clifford+V gates. VL - 15 U4 - 932-950 UR - http://arxiv.org/abs/1409.4355v2 CP - 11-12 ER - TY - JOUR T1 - Programming the Quantum Future JF - Communications of the ACM Y1 - 2015 A1 - D. Scott Alexander A1 - Neil J. Ross A1 - Peter Selinger A1 - Jonathan M. Smith A1 - Benoît Valiron AB - 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. VL - 58 U4 - 52-61 UR - http://cacm.acm.org/magazines/2015/8/189851-programming-the-quantum-future/fulltext#comments CP - 8 U5 - 10.1145/2699415 ER - TY - JOUR T1 - Quipper: Concrete Resource Estimation in Quantum Algorithms Y1 - 2014 A1 - Jonathan M. Smith A1 - Neil J. Ross A1 - Peter Selinger A1 - Benoît Valiron AB -

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.

UR - http://arxiv.org/abs/1412.0625v1 ER - TY - JOUR T1 - An Introduction to Quantum Programming in Quipper JF - Lecture Notes in Computer Science Y1 - 2013 A1 - Alexander S. Green A1 - Peter LeFanu Lumsdaine A1 - Neil J. Ross A1 - Peter Selinger A1 - Benoît Valiron AB - 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. VL - 7948 U4 - 110-124 SN - 978-3-642-38986-3 UR - http://arxiv.org/abs/1304.5485v1 J1 - Lecture Notes in Computer Science 7948:110-124 U5 - 10.1007/978-3-642-38986-3_10 ER - TY - JOUR T1 - Quipper: A Scalable Quantum Programming Language JF - ACM SIGPLAN Notices Y1 - 2013 A1 - Alexander S. Green A1 - Peter LeFanu Lumsdaine A1 - Neil J. Ross A1 - Peter Selinger A1 - Benoît Valiron AB -

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.

VL - 48 U4 - 333-342 UR - http://arxiv.org/abs/1304.3390v1 CP - 6 J1 - SIGPLAN Not. U5 - 10.1145/2499370.2462177 ER - TY - JOUR T1 - Full Abstraction for Set-Based Models of the Symmetric Interaction Combinators JF - Proceedings of the 15th International Conference on Foundations of Software Science and Computation Structures Y1 - 2012 A1 - Damiano Mazza A1 - Neil J. Ross AB - The symmetric interaction combinators are a model of distributed and deterministic computation based on Lafont’s interaction nets, a special form of graph rewriting. The interest of the symmetric interaction combinators lies in their universality, that is, the fact that they may encode all other interaction net systems; for instance, several implementations of the lambda-calculus in the symmetric interaction combinators exist, related to Lamping’s sharing graphs for optimal reduction. A certain number of observational equivalences were introduced for this system, by Lafont, Fernandez and Mackie, and the first author. In this paper, we study the problem of full abstraction with respect to one of these equivalences, using a class of very simple denotational models based on pointed sets. VL - 7213 U4 - 316-330 UR - https://lipn.univ-paris13.fr/~mazza/papers/CombSetSem-FOSSACS2012.pdf ER -