Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

A decision procedure for well-formed linear quantum cellular automata

Christoph Dürr, Huong Lê Thanh, Miklós Sántha

Published Jan 1, 1996• 21 citations
Publisher
DOI
10.1007/3-540-60922-9_24

Related papers

Algebraic Characterizations of Unitary Linear Quantum Cellular Automata

Pablo J. Arrighi

Lecture notes in computer science•Jan 1, 2006•9 citations

A decision procedure for well-formed linear quantum cellular automata

Christoph Dürr, Huong LêThanh, Miklós Sántha

In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since it enables us to define the probability of a configuration in an observation as the squared magnitude of its amplitude. We give an efficient algorithm which decides if a linear quantum cellular automaton is well-formed. The complexity of the algorithm is $O(n^2)$ in the algebraic model of computation if the input automaton has continuous neighborhood.

arXiv:cs/9906024•Jun 23, 1999•4 citations

Classification of Quantum Cellular Automata

Michael Freedman, Matthew B. Hastings

arXiv:1902.10285•Communications in Mathematical Physics•Apr 6, 2020•74 citations

Structures in quantum cellular automata

Gerhard Grössing, Anton Zeilinger

Physica B+C•Jul 1, 1988•31 citations

A decision procedure for well-formed linear quantum cellular automata

Christoph Dürr, Huong L�Thanh, Miklós Sántha

In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since it enables us to define the probability of a configuration in an observation as the squared magnitude of its amplitude. We give an efficient algorithm which decides if a linear quantum cellular automaton is well-formed. The complexity of the algorithm is O(n2) in the algebraic model of computation if the input automaton has continuous neighborhood. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11, 381–394 (1997)

Random Structures and Algorithms•Dec 1, 1997•25 citations

An overview of quantum cellular automata

Pablo J. Arrighi

Natural Computing•Sep 20, 2019•133 citations
In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since it enables us to define the probability of a configuration in an observation as the squared magnitude of its amplitude. We give an efficient algorithm which decides if a linear quantum cellular automaton is well-formed. The complexity of the algorithm is O(n2)O(n^2)O(n2) in the algebraic model of computation if the input automaton has continuous neighborhood.
In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since it enables us to define the probability of a configuration in an observation as the squared magnitude of its amplitude. We give an efficient algorithm which decides if a linear quantum cellular automaton is well-formed. The complexity of the algorithm is O(n2) in the algebraic model of computation if the input automaton has continuous neighborhood. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11, 381–394 (1997)