10-03-2011, 10:52 AM
Presented By:
Abhijit Doley
Ranjan Phukan
Rekhamoni Morang
[attachment=9918]
Evolution of Quantum Automata
• Quantum events cannot be simulated in classical computers in feasible time.
• So it was needed to formalize the quantum computers.
• Quantum automata are the basic model for the quantum computers.
• Quantum automata are built due to the problems of classical computers with certain mathematical problems.
Classical Computational Unit (Bits)
• A building block of classical computational devices is a two-state system.
0 and 1
• Indeed, any system with a finite set of discrete, stable states, with controlled transitions between them will do.
Quantum Computational Unit (Qubits)
• The basic unit of information in quantum computing is called the qubit.
• Two states are labeled as |0> and |1>.
• An object enclosed using the notation |> can be called a state, a vector or a ket.
• A qubit can exist in the state |0> or the state |1>.
• Can also exist in a state that is a linear combination of the states |0> and |1>
▫ Superposition State.
• A superposition state is written as
|ψ> = α|0> + β|1 >
▫ Here α, β are complex numbers.
• When a qubit is measured, it is only found to be in the state |0> or the state |1>.
• |α|²: probability of finding |ψ> in state |0>.
• |β|²: probability of finding |ψ> in state |1>.
• Example:
|ψ >=1/√3 |0> +√(2/3) |1>
probability of finding |ψ> in state |0> = | 1/√3 |²=1/3
probability of finding |ψ> in state |1> = | √2/√3 |²=2/3
• Alphabet, Strings & Languages
• Alphabet(∑): Finite non-empty set of symbols.
Example:{0,1} is the binary alphabet.
• String: Finite sequence of symbols chosen from some alphabet.
Example: 1011 is string from the alphabet {0,1}.
∑* denotes the set of all strings over alphabet ∑.
Language: A set of strings all of which are chosen from some ∑*.
Example: The set of even numbers.
Finite Automata
• Collection of three things:
▫ A finite set of states
One of them is the start state and
Some (or none) are final states.
▫ An alphabet set (∑) containing symbols to construct input strings .
▫ A finite set of transitions denoting the states it goes next on accepting each letter.
• Languages accepted by FA are called regular languages.
Deterministic Finite Automata(DFA)
• DFA is a 5-tuple (K, S, d, q0, F) where
▫ K is a finite set of states,
▫ S is a finite set of input symbols,
▫ q0 is the initial state,
▫ F is the set of final states,
▫ d is the transition function mapping from K * S à K, d(q1,a)= q2 means when we are in state q1 and read ‘a’ , we move to state q2.
Deterministic Finite Automata(DFA)
• Non-deterministic Finite Automata(NFA)
• NFA is a 5-tuple (Q, S, d, q0, F) where
▫ Q is a finite set of states,
▫ S is a finite set of input symbols,
▫ q0 is the initial state,
▫ F is the set of final states,
▫ d is the transition function mapping from Q * S à 2Q.
• Non-deterministic Finite Automata(NFA)
Transition Matrix
• A Transition Matrix M of an alphabet in S accepted by a DFA with Q states is a |Q| *|Q| matrix with entries 0 or 1.
• Ma(i,j) = 1, if (qj, a) ® qi
= 0, otherwise; a is an element of S.
• Transition Matrix (Example)
• Probabilistic Automata
• We obtain probabilistic automata if we allow fractional values in transition matrix.
• Each columns adds up to 1.
• Probabilistic Automata accepts regular language.
• Example:
• Language Accepted
• A probabilistic automaton A accepts a language L with certainty if
Quantum Automata
• Quantum automata are obtained by letting the transition matrices have complex entries.
• We also require each of the matrices to be unitary.
• Example: Transition Matrix
Acceptance Probabilities
• Let q1 is the starting state of the automaton, Mw|q> is a vector describing a superposition of states.
• If the jth entry in the vector is αj then αj is the probability that the automaton reaches state qj .
• | αj |2 is the probability that a measurement will result in state qj .
• | ∑ qj єF αj |2 is the probability that the automaton accepts the string w.
Quantum finite-state automata
• A QFA is a 6-tuple M =(Q, ∑, V, q0,Qacc,Qrej) where
▫ Q is a finite set of states.
▫ ∑ is an input alphabet.
▫ V is a transition function.
▫ q0∈Q is a starting state.
▫ Qacc⊆Q are accepting states.
▫ Qrej⊆Q are sets of and rejecting states (Qacc∩Qrej=∅).
▫ Qacc and Qrej, are called halting states.
▫ Qnon=Q−(Qacc∪Qrej) are called non-halting states.
States of M
• The state of M can be any superposition of states in Q.
• It means any linear combination of them with complex coefficients.
• We use |q> to denote the superposition consisting of state q only.
• l2(Q) denotes the linear combination consisting of all superpositions with l2-distance.
Endmarkers
• We use κ and $ as the left and the right endmarker respectively.
• They do not belong to ∑.
• We call Γ= ∑ ∪ {κ; $} the working alphabet of M.
• Transition function
• The transition function V is a mapping from Γ×l2(Q) to l2(Q) such that, for every a∈ Γ, the function Va : l2(Q)→l2(Q) defined by Va(x)=V(a, x) is a unitary transformation.