Showing 1–8 of 8 results for author: Grattage

A Quantum Game of Life

Authors: Pablo Arrighi, Jonathan Grattage

Abstract: 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… ▽ More 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. △ Less

Submitted 12 November, 2010; v1 submitted 15 October, 2010; originally announced October 2010.

Comments: 13 pages, 10 figures. Final version, accepted by Journées Automates Cellulaires (JAC 2010).

Partitioned quantum cellular automata are intrinsically universal

Authors: Pablo Arrighi, Jonathan Grattage

Abstract: 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 equi… ▽ More 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. △ Less

Submitted 12 October, 2010; originally announced October 2010.

Comments: 16 pages, 7 figures. 2009 Physics and Computation workshop, special issue. Journal version: arXiv:0907.3827

A Simple n-Dimensional Intrinsically Universal Quantum Cellular Automaton

Authors: Pablo Arrighi, Jonathan Grattage

Abstract: We describe a simple n-dimensional quantum cellular automaton (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. Several steps of the intrinsically universal QCA then correspond to one step of the simulated QCA. The simulation preserves the t… ▽ More We describe a simple n-dimensional quantum cellular automaton (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. Several steps of the intrinsically universal QCA then correspond to one step of the simulated QCA. The simulation 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. △ Less

Submitted 12 October, 2010; v1 submitted 4 February, 2010; originally announced February 2010.

Comments: 13 pages, 7 figures. In Proceedings of the 4th International Conference on Language and Automata Theory and Applications (LATA 2010), Lecture Notes in Computer Science (LNCS). Journal version: arXiv:0907.3827

Journal ref: Lecture Notes in Computer Science 6031 (2010) 70-81

Intrinsically universal n-dimensional quantum cellular automata

Authors: Pablo Arrighi, Jonathan Grattage

Abstract: 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 al… ▽ More 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. △ Less

Submitted 13 October, 2010; v1 submitted 22 July, 2009; originally announced July 2009.

Comments: 26 pages, 15 figures. Journal paper incorporating arXiv:0907.3827 and arXiv:1002.1015

An overview of QML with a concrete implementation in Haskell

Authors: Jonathan Grattage

Abstract: 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… ▽ More 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. △ Less

Submitted 21 July, 2008; v1 submitted 17 June, 2008; originally announced June 2008.

Comments: 9 pages, final conference version (Quantum Physics and Logic 2008)

Journal ref: ENTCS: Proceedings of QPL V - DCV IV, 157-165, Reykjavik, Iceland, 2008

Measurements and confluence in quantum lambda calculi with explicit qubits

Authors: Alejandro Díaz-Caro, Pablo Arrighi, Manuel Gadella, Jonathan Grattage

Abstract: 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… ▽ More 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. △ Less

Submitted 4 January, 2010; v1 submitted 15 June, 2008; originally announced June 2008.

Comments: 15 pages. Minor changes: final proceedings version. To appear ENTCS: Proceedings of QPL V - DCV IV, Reykjavik, Iceland, 2008

Journal ref: Electronic Notes in Theoretical Computer Science, 270(1):59-74, 2011. Proceedings of the Joint 5th International Workshop on Quantum Physics and Logic and 4th Workshop on Developments in Computational Models (QPL/DCM 2008)

An Algebra of Pure Quantum Programming

Authors: Thorsten Altenkirch, Jonathan Grattage, Juliana K. Vizzotto, Amr Sabry

Abstract: 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 o… ▽ More 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. △ Less

Submitted 1 June, 2005; originally announced June 2005.

Comments: To appear in ENTCS, 3rd International Workshop on Quantum Programming Languages, 2005. 21 Pages

Journal ref: Electronic Notes in Theoretical Computer Science, Volume 170, 6 March 2007, Pages 23-47

A functional quantum programming language

Authors: Thorsten Altenkirch, Jonathan Grattage

Abstract: 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 c… ▽ More 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. △ Less

Submitted 19 April, 2005; v1 submitted 11 September, 2004; originally announced September 2004.

Comments: 15 pages. Final version, to appear in Logic in Computer Science 2005

Journal ref: Logic in Computer Science, 2005. Proceedings. 20th Annual IEEE Symposium on, 26-29 June 2005 Page(s):249 - 258