computation, algebra, logic

Question

So a really simple way of describing a digital computer is to say that it is a device for performing boolean operations. You feed it a bunch of bit strings, which is a description of the problem and its parameters in binary, the computer performs a bunch of boolean operations like $\wedge$, $\vee$, $\neg$ and gives you back another bit string which hopefully is the encoded version of the answer you were looking for. From this description it is not hard to see the connection of classical computation to discrete dynamical systems and classical logic, the operations provide the dynamics by flipping bits around in a controlled fashion and since we restrict the operations to a certain subset we get classical logic. My question is about analog and quantum computation. Is there a simple description of a quantum computer or an analog computer that makes the connection of that notion of computation to the other branches of mathematics a little more obvious? What is the most basic kind of enconding of a problem that can be fed into a quantum or analog computer and what are the most basic operations performed on this encoding?

Edit: Downvotes should come with comments so I know what to change in order to make my question clearer. Being a novice I'm just trying to piece together some themes about computation, logic and algebra.

Edit: alpheccar provided a link to a paper by John Baez and Mike Stay that pretty much answers my question and even puts it in a much wider context. Here's the link alpheccar provided.

Answer 1

From this description it is not hard to see the connection of classical computation to discrete dynamical systems and classical logic, the operations provide the dynamics by flipping bits around in a controlled fashion and since we restrict the operations to a certain subset we get classical logic.

Careful -- this observation only works for purely finite-state systems! If your idealized model of a digital computer can handle potentially unbounded quantities of input, then the connection to classical logic is lost. Happily, it fails in a way that reveals connections to topology, and explains why topological models of intuitionistic logic exist.

The basic idea is that we view a computer as realizing a function $f$. Then for any input value (from the input set $A$), if it returns an answer in a finite amount of time, it can have observed at most a finite amount of information about the input. This means that we can equip our input set with a topology in the following way: suppose our basic observations are a collection of predicates on $A$. Then we get the topological structure from the following fact: we can only take finite intersections because we can only make finitely many observations, and so can only conclude the conjunction of finitely many predicates. We can take infinite unions (i.e., existentials) because we can "get lucky" and guess the correct branch of the union (i.e., witness to the existential).

Then, amazingly, we can use continuity as a stand-in for computability! This is pretty much the idea Dana Scott had when he invented domain theory (which gets a different name because the topologies that we get this way are "weird" -- e.g., they're typically not Hausdorff -- and so the theorems you want develop a bit differently).

Answer 2

The basic step of a quantum computation is the application of a unitary matrix to the qubits. Thus, a quantum computing consists in iterating this unitary matrix.

One can view the quantum computation as built up from gates, not classical logic gates, but rather, quantum gates, each represented by a unitary matrix. One interesting difference with classical computation gates is that these quantum gates are necessarily reversible, and so quantum computations are in principle reversible. (There are also classical reversible gates, such as the Toffoli gate, that suffice for classical computation.)

Solovay and Kitaev provided a set of universal quantum gates.