0
$\begingroup$

I found this paper: https://arxiv.org/abs/1606.08764

There, it is said "We realize constant-space quantum computation by measure-many two-way quantum finite automata"

What are "finite automata"? Are there infinite automata?

Also, I don't know if that means that this model is a quantum continuous (in space, time...etc) cellular automata/game of life

Improve this question
$\endgroup$
1
$\begingroup$

Cellular automata are well explained in their Wikipedia page. Most work on cellular automata is concentrated on systems where each cell can have a finite number of states; it is possible to consider systems with an infinite number of states, but this introduces all sorts of additional complications into the theory and it kind of defeats the whole point of cellular automata (which is, basically, that you can get very complex behaviour by chaining together simple finite systems with simple interactions; if you allow for infinite states then the complex behaviour isn't all that surprising).

The paper you link to considers quantum cellular automata, where the number of states of each cell is replaced by the Hilbert-space dimension of the state space associated with each cell; the paper is thus requiring that that dimension be finite.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Gràcies! And what about my second question? When it says "We realize constant-space quantum computation by measure-many two-way quantum finite automata" does it mean that this cellular automata can do quantum continuous processes/behaviour/equations? (With continuous time, continuous space...etc)? $\endgroup$ – user199226 Jul 5 '18 at 12:44
  • $\begingroup$ I shouldn't think so - like all discrete models of quantum computation, it's likely to be universal in the sense that it can approximate to arbitrary precision any arbitrary unitary, but it might struggle getting to the exact continuous behaviour. $\endgroup$ – Emilio Pisanty Jul 5 '18 at 14:02
  • $\begingroup$ and do you know of any quantum continuous cellular automata? could 't Hooft's cellular automata based in string theory do quantum continuous processes? math.columbia.edu/~woit/wordpress/?p=5022; or maybe some version of a continuous spatial automaton could do it? en.wikipedia.org/wiki/Continuous_spatial_automaton $\endgroup$ – user199226 Jul 5 '18 at 15:19
  • $\begingroup$ Normally this type of back-and-forth should be conducted in chat. But no, neither continuous cellular automata nor infinite-dimension-per-site automata (which are not the same thing!) seem particularly interesting to me, and I don't know much about them. $\endgroup$ – Emilio Pisanty Jul 5 '18 at 15:21
  • $\begingroup$ (Since I read you are from Barcelona, I suppose you speak spanish. Would you like to talk in spanish?) And what about hybrid quantum cellular automata (like this: pdfs.semanticscholar.org/d358/…). I read that hybrid cellular automata combine discrete and continuous processes. And with a quantum hybrid cellular automata, I suppose that quantum continuous processes could be produced, isn't it? Also, could a hybrid cellular automata be programmed to produce only the continuous ones? @EmilioPisanty $\endgroup$ – user199226 Jul 5 '18 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy