# Quantum Automata

1. Nov 21, 2008

### michinobu

Unlike normal finite automata, which always have one start state, it seems that quantum automata can actually have more than one start state. How would one be able to use this as a real physical computer, if by pressing the power button on your computer it might not start - but, rather morph into a black-hole and suck you along with everyone or everything you care about (joking)?

2. Nov 22, 2008

### feynomite

You would use it for practical joke purposes only

3. Nov 23, 2008

### Coin

I think it wouldn't be so much that a quantum automata has "more than one" start state, but more like the quantum finite automata has a superposition of possibly more than one start state, which isn't exactly the same thing. As for how this would be used "in a real physical computer", as far as I'm aware the idea of preparing a specific start state for a quantum computer is actually kind of difficult.

Are you sure you mean to ask about a "finite automata"? As far as I know most research which treats quantum computers as automata concerns Quantum Turing Machines, although I guess all actual quantum computers are finite and maybe I am missing something.

4. Nov 25, 2008

### michinobu

Well, if you've ever taken an undergrad-level computational course and paid attention, you'd know that finite automata are related to Turing machines. The only thing is that Turing machines have infinite memory because they can go back and forth in their input tape.
Just like how PDA's (Push-Down Automata) are finite automata with stacks for added memory.
Alone, a finite automata wouldn't equate to a physical computer, but the Turing Machine is the mathematical equivalent of a computer. Everything you can do with a physical computer can be done with a Turing Machine, except for the fact that it's something that can only be observed in your head so you couldn't watch you-tube on a Turing Machine. That is, unless you were crazy.

But, I hear that using quantum computer would cut down computational time considerably. For instance, when trying to crack the key to a cipher, you'd have a machine which would have four-state bits instead of the two-state bits that we have (see quantum bits).

I never taken a course on quantum computation, but my professor brought this up in an unrelated class and he told us about this scenario where you have a cat in a box and you fire a gun into it. In the world of quantum mechanics and quantum computation, the cat has four states: dead, alive, neither, or both. It doesn't make sense in real-life, maybe I wasn't paying attention so I missed the big "aha!" part of his little speech. However, I think his story was credible, in that they actually do talk about it in relation to quantum mechanics, because the same same cat-in-the-box scenario was brought up in an anime series (I forget the title) where this little girl is visited by her friends from the future in an alternate dimension.