01590nas a2200133 4500008004100000245008000041210006900121260001400190520115200204100002501356700001901381700001901400856003701419 2020 eng d00aOptimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation0 aOptimal TwoQubit Circuits for Universal FaultTolerant Quantum Co c1/16/20203 a

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. 

1 aGlaudell, Andrew, N.1 aRoss, Neil, J.1 aTaylor, J., M. uhttps://arxiv.org/abs/2001.0599701389nas a2200157 4500008004100000245005900041210005700100260001400157300001000171490000800181520094200189100002501131700001901156700001901175856003701194 2019 eng d00aCanonical forms for single-qutrit Clifford+T operators0 aCanonical forms for singlequtrit CliffordT operators c8/19/2019 a54-700 v4063 a

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. 

1 aGlaudell, Andrew, N.1 aRoss, Neil, J.1 aTaylor, J., M. uhttps://arxiv.org/abs/1803.0504701242nas a2200145 4500008004100000245006500041210006400106260001500170490000600185520081100191100002101002700001701023700001901040856003701059 2019 eng d00aGraphical Methods in Device-Independent Quantum Cryptography0 aGraphical Methods in DeviceIndependent Quantum Cryptography c05/20/20190 v33 a

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.

1 aBreiner, Spencer1 aMiller, Carl1 aRoss, Neil, J. uhttps://arxiv.org/abs/1705.0921301571nas a2200133 4500008004100000245007800041210006900119260001400188520113700202100001701339700002501356700001901381856003701400 2019 eng d00aNumber-Theoretic Characterizations of Some Restricted Clifford+T Circuits0 aNumberTheoretic Characterizations of Some Restricted CliffordT C c8/16/20193 a

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.

1 aAmy, Matthew1 aGlaudell, Andrew, N.1 aRoss, Neil, J. uhttps://arxiv.org/abs/1908.0607601295nas a2200169 4500008004100000245008000041210006900121260001500190490000600205520078500211100001800996700001901014700001301033700002301046700001901069856003701088 2018 eng d00aAutomated optimization of large quantum circuits with continuous parameters0 aAutomated optimization of large quantum circuits with continuous c2017/10/190 v43 a

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. 

1 aNam, Yunseong1 aRoss, Neil, J.1 aSu, Yuan1 aChilds, Andrew, M.1 aMaslov, Dmitri uhttps://arxiv.org/abs/1710.0734501648nas a2200169 4500008004100000245006100041210006100102300001400163490000900177520116300186100002301349700001901372700001801391700001901409700001301428856003701441 2018 eng d00aToward the first quantum simulation with quantum speedup0 aToward the first quantum simulation with quantum speedup a9456-94610 v115 3 a

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.

1 aChilds, Andrew, M.1 aMaslov, Dmitri1 aNam, Yunseong1 aRoss, Neil, J.1 aSu, Yuan uhttps://arxiv.org/abs/1711.1098001044nas a2200133 4500008004100000245005300041210005000094260001500144520066000159100001700819700001800836700001900854856003700873 2016 eng d00aA finite presentation of CNOT-dihedral operators0 afinite presentation of CNOTdihedral operators c2016/12/313 a

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.

1 aAmy, Matthew1 aChen, Jianxin1 aRoss, Neil, J. uhttps://arxiv.org/abs/1701.0014001100nas a2200133 4500008004100000245006500041210006200106300001200168490000700180520070300187100001900890700002000909856003700929 2016 eng d00aOptimal ancilla-free Clifford+T approximation of z-rotations0 aOptimal ancillafree CliffordT approximation of zrotations a901-9530 v163 a

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

1 aRoss, Neil, J.1 aSelinger, Peter uhttp://arxiv.org/abs/1403.2975v201270nas a2200133 4500008004100000245006500041210006200106260001500168300001200183490000700195520087800202100001901080856003701099 2015 eng d00aOptimal ancilla-free Clifford+V approximation of z-rotations0 aOptimal ancillafree CliffordV approximation of zrotations c2015/03/06 a932-9500 v153 a 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. 1 aRoss, Neil, J. uhttp://arxiv.org/abs/1409.4355v201473nas a2200181 4500008004100000245003500041210003500076260001500111300001000126490000700136520094600143100002101089700001901110700002001129700002401149700002101173856009701194 2015 eng d00aProgramming the Quantum Future0 aProgramming the Quantum Future c2015/08/01 a52-610 v583 aThe 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.1 aAlexander, Scott1 aRoss, Neil, J.1 aSelinger, Peter1 aSmith, Jonathan, M.1 aValiron, Benoît uhttp://cacm.acm.org/magazines/2015/8/189851-programming-the-quantum-future/fulltext#comments01088nas a2200145 4500008004100000245006400041210006300105260001500168520063800183100002400821700001900845700002000864700002100884856003700905 2014 eng d00aQuipper: Concrete Resource Estimation in Quantum Algorithms0 aQuipper Concrete Resource Estimation in Quantum Algorithms c2014/12/013 a

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.

1 aSmith, Jonathan, M.1 aRoss, Neil, J.1 aSelinger, Peter1 aValiron, Benoît uhttp://arxiv.org/abs/1412.0625v101002nas a2200193 4500008004100000020002200041245005400063210005100117260001500168300001200183490000900195520045300204100002500657700002900682700001900711700002000730700002100750856003700771 2013 eng d a978-3-642-38986-300aAn Introduction to Quantum Programming in Quipper0 aIntroduction to Quantum Programming in Quipper c2013/07/05 a110-1240 v79483 a 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. 1 aGreen, Alexander, S.1 aLumsdaine, Peter, LeFanu1 aRoss, Neil, J.1 aSelinger, Peter1 aValiron, Benoît uhttp://arxiv.org/abs/1304.5485v101302nas a2200181 4500008004100000245005300041210005200094260001500146300001200161490000700173520078900180100002500969700002900994700001901023700002001042700002101062856003701083 2013 eng d00aQuipper: A Scalable Quantum Programming Language0 aQuipper A Scalable Quantum Programming Language c2013/06/23 a333-3420 v483 a

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.

1 aGreen, Alexander, S.1 aLumsdaine, Peter, LeFanu1 aRoss, Neil, J.1 aSelinger, Peter1 aValiron, Benoît uhttp://arxiv.org/abs/1304.3390v101302nas a2200145 4500008004100000245008300041210006900124260001500193300001200208490000900220520081500229100001901044700001901063856007401082 2012 eng d00aFull Abstraction for Set-Based Models of the Symmetric Interaction Combinators0 aFull Abstraction for SetBased Models of the Symmetric Interactio c2012/01/01 a316-3300 v72133 aThe 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.1 aMazza, Damiano1 aRoss, Neil, J. uhttps://lipn.univ-paris13.fr/~mazza/papers/CombSetSem-FOSSACS2012.pdf