ENS de Lyon > LIP > MC2 > Dr Jonathan Grattage > Publications
European Research Fellow
Dr Jonathan GRATTAGE - Publications
Most of my publications can be found on the arXiv. Below is a collection of my work, including extended abstracts, posters, my PhD thesis, and unpublished drafts.
Quantum Cellular Automata
A Quantum Game of Life
Pablo Arrigh and Jonathan Grattage, Journées Automates Cellulaires (JAC 2010), Turku, Finland, December 2010. HAL:hal-00542373. [BibTeX]
- Companion website
- This research describes a three dimensional quantum cellular automaton (QCA) which can simulate all other 3D QCA. This intrinsically universal QCA belongs to the simplest subclass of QCA: Partitioned QCA (PQCA). PQCA are QCA of a particular form, where incoming information is scattered by a fixed unitary U before being redistributed and rescattered. Our construction is minimal amongst PQCA, having block size 2 x 2 x 2 and cell dimension 2. Signals, wires and gates emerge in an elegant fashion.
Intrinsically Universal n-Dimensional Quantum Cellular Automata
Pablo Arrigh and Jonathan Grattage [BibTeX]
- ArXiv: 0907.3827
- There have been several non-axiomatic approaches taken to define Quantum Cellular Automata (QCA). Partitioned QCA (PQCA) are the most canonical of these non-axiomatic definitions. In this work we first show that any QCA can be put into the form of a PQCA. Our construction reconciles all the non-axiomatic definitions of QCA, showing that they can all simulate one another, and hence that they are all equivalent to the axiomatic definition. Next, we describe a simple n-dimensional QCA capable of simulating all others, in that the initial configuration and the forward evolution of any n-dimensional QCA can be encoded within the initial configuration of the intrinsically universal QCA, and that several steps of the intrinsically universal QCA then correspond to one step of the simulated QCA. Both results are made formal by defining generalised n-dimensional intrinsic simulation, i.e. a notion of simulation which preserves the topology in the sense that each cell of the simulated QCA is encoded as a group of adjacent cells in the universal QCA. We argue that this notion brings the computer science based concepts of simulation and universality one step closer to theoretical physics.
- This is a journal paper incorporating material from the two publications below, 1010.2335 and 1002.1015
A Simple n-Dimensional Intrinsically Universal Quantum Cellular Automaton
Pablo Arrigh and Jonathan Grattage, Language
and Automata Theory and Applications (LATA 2010), Lecture Notes in Computer Science, Vol: 6031. [BibTeX]
- DOI: 10.1007/978-3-642-13089-2
- ArXiv: 1002.1015
- There have been several non-axiomatic approaches taken to define Quantum Cellular Automata (QCA). Partitioned QCA (PQCA) are the most canonical of these non-axiomatic definitions. In this work we show that any QCA can be put into the form of a PQCA. Our construction reconciles all the non-axiomatic definitions of QCA, showing that they can all simulate one another, and hence that they are all equivalent to the axiomatic definition. This is achieved by defining generalised n-dimensional intrinsic simulation, which brings the computer science based concepts of simulation and universality closer to theoretical physics. The result is not only an important simplification of the QCA model, it also plays a key role in the identification of a minimal n-dimensional intrinsically universal QCA.
Partitioned Quantum Cellular Automata are Intrinsically Universal
Pablo Arrigh and Jonathan Grattage, Physics and Computation 2009, to appear (2010). [BibTeX]
- ArXiv: 1010.2335
- There have been several non-axiomatic approaches taken to define Quantum Cellular Automata (QCA). Partitioned QCA (PQCA) are the most canonical of these non-axiomatic definitions. In this work we show that any QCA can be put into the form of a PQCA. Our construction reconciles all the non-axiomatic definitions of QCA, showing that they can all simulate one another, and hence that they are all equivalent to the axiomatic definition. This is achieved by defining generalised n-dimensional intrinsic simulation, which brings the computer science based concepts of simulation and universality closer to theoretical physics. The result is not only an important simplification of the QCA model, it also plays a key role in the identification of a minimal n-dimensional intrinsically universal QCA.
A compiler for a quantum language
A compiler for QML, written in Haskell (including a Happy parser and lexer), with full instructions and example programs, is available from the QML compiler website.An Overview of QML with a Concrete Implementation in Haskell
Jonathan Grattage, Development of Computational Models (DCM IV), Electronic Notes in Theoretical Computer Science, Volume 270, Issue 1, 10 February 2011, Pages 59-74. [BibTeX]
- DOI: 10.1016/j.entcs.2011.01.015
- ArXiv: 0806.2735
- This paper gives an introduction to and overview of the functional quantum programming language QML. The syntax of this language is defined and explained, along with a new QML definition of the quantum teleport algorithm. The categorical operational semantics of QML is also briefly introduced, in the form of annotated quantum circuits. This definition leads to a denotational semantics, given in terms of superoperators. Finally, an implementation in Haskell of the semantics for QML is presented as a compiler. The compiler takes QML programs as input, which are parsed into a Haskell datatype. The output from the compiler is either a quantum circuit (operational), an isometry (pure denotational) or a superoperator (impure denotational). Orthogonality judgements and problems with coproducts in QML are also discussed.
Measurements and Confluence in Quantum Lambda Calculi with Explicit Qubits
Alejandro Díaz-Caro, Pablo Arrighi, Manuel Gadella, and Jonathan Grattage, Quantum Physics and Logic (QPL V), Electronic Notes in Theoretical Computer Science, Volume 270, Issue 1, 10 February 2011, Pages 59-74. [BibTeX]
- DOI: 10.1016/j.entcs.2011.01.006
- ArXiv: 0806.2447
- This paper demonstrates how to add a measurement operator to quantum lambda-calculi. A proof of the consistency of the semantics is given through a proof of confluence presented in a sufficiently general way to allow this technique to be used for other languages. The method described here may be applied to probabilistic rewrite systems in general, and to add measurement to more complex languages such as QML or Lineal, which is the subject of further research.
An Algebra of Pure Quantum Programming
Thorsten Altenkirch, Jonathan Grattage, Juliana K. Vizzotto and Amr Sabry, Quantum Programming Languages workshop (QPL 2005), ENTCS Vol: 170, March 2007, Pp. 23-47. [BibTeX]
- DOI: 10.1016/j.entcs.2006.12.010
- ArXiv: quant-ph/0506012
- We develop a sound and complete equational theory for the functional quantum programming language QML. The soundness and completeness of the theory are with respect to the previously-developed denotational semantics of QML. The completeness proof also gives rise to a normalisation algorithm following the normalisation by evaluation approach. The current work focuses on the pure fragment of QML omitting measurements.
A Functional Quantum Programming Language
Thorsten Altenkirch and Jonathan Grattage, 20th Annual IEEE Symposium on Logic In Computer Science (LICS 2005), June 2005, Pp. 249-258. [BibTeX]
- DOI: 10.1109/LICS.2005.1
- ArXiv: quant-ph/0409065
- We introduce the language QML, a functional language for quantum computations on finite types. Its design is guided by its categorical semantics: QML programs are interpreted by morphisms in the category FQC of finite quantum computations, which provides a constructive semantics of irreversible quantum computations realisable as quantum gates. QML integrates reversible and irreversible quantum computations in one language, using first order strict linear logic to make weakenings explicit. Strict programs are free from decoherence and hence preserve superpositions and entanglement - which is essential for quantum parallelism.
- Note: The content of this paper has been revised and superseded by my thesis.
QML: A Functional Quantum Programming Language
Jonathan Grattage. Viva: September 2006, Graduated: July 2007 [BibTeX]
- QML Website
- This PhD thesis contains a complete rewrite of QML, replacing the definition given in the original LICS paper above. It also formalises, using category theory and the category FQC of Finite Quantum Computation, the quantum circuit model, and gives an operational semantics for QML in terms of quantum circuits. A denotational semantics for QML, using Selinger's superoperator category Q, is also given. It also contains an introduction to reversible classical computation, quantum computation (and its history), and an implementation in Haskell of all the main ideas discussed. The appendix contains a full discussion of Shor's factoring algorithm.
An Overview of QML
PLUME, ENS de Lyon, 2010
- Slides
- This is an invited talk I prepared for the PLUME team at ENS de Lyon, giving an overview of QML taken from my thesis and subsequent work.
A Simple n-Dimensional Intrinsically Universal QCA
LATA 2010, Trier
- Slides
- Quicktime movie
- The presentation accompanying the paper of the same name, above. The QuickTime version of this talk includes animated examples of the QCA tiles which implement universal quantum computation.
An introduction to QML, a functional quantum language
CAPP Café seminar, LIG, Grenoble
- Slides
- An introduction to most aspects of QML (the language, motivations, semantics, algebra, etc), and contains an updated version of talks I have given previously (LICS '05, BCTCS), as well as some new information. All information in this presentation is from my thesis and the paper "An Algebra of Pure Quantum Programming" above.
Contact Details
- (GPG Key)
- Tel: 04 26 23 38 10
- Fax: 04 26 23 38 20
Address
Updated: February 2011
Ens de Lyon
15 parvis René Descartes - BP 7000 69342 Lyon Cedex 07 - FRANCE
Tel. : Site René Descartes (siège) : +33 (0) 4 37 37 60 00 / Site Jacques Monod : +33 (0) 4 72 72 80 00