Quantum Automata and Languages
#1

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.
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page
Popular Searches: sutrupura thuimaii katturair in tamil languages, freshers party in different languages, www scienceproject com in gujarati languages, automata compiler design viva questions, quantum dot cellular automata ppt, teaching kids programming languages, abstract cellular automata,

[-]
Quick Reply
Message
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  QUANTUM CRYPTOGRAPHY- MAKING CODE UNBREAKABLE seminar class 2 2,435 11-07-2013, 02:07 PM
Last Post: computer topic
  A survey of usage of Data Mining and Data Warehousing in Academic Institution and Lib seminar class 1 2,118 29-11-2012, 12:56 PM
Last Post: seminar details
  Intelligent Electronic Devices (IEDs) and Supervisory Control and Data Acquisition computer girl 0 1,140 09-06-2012, 06:01 PM
Last Post: computer girl
  The 8051 Microcontroller and Embedded Systems Using Assembly and C computer girl 0 1,035 04-06-2012, 05:41 PM
Last Post: computer girl
Brick Categorization of Programming Languages computer science crazy 1 1,861 14-02-2012, 01:43 PM
Last Post: seminar paper
  Quantum dot lasers computer science crazy 1 1,727 04-02-2012, 10:02 AM
Last Post: seminar addict
  Quantum Cryptography computer science crazy 5 6,910 19-01-2012, 11:05 AM
Last Post: seminar addict
  Seminar Report On QUANTUM CRYPTOGRAPHY Computer Science Clay 4 8,295 19-01-2012, 11:04 AM
Last Post: seminar addict
  quantum computing full report project report tiger 4 7,021 13-05-2011, 10:35 PM
Last Post: shocksharker
  Lean and Zoom: Proximity-Aware User Interface and Content Magnification seminar class 0 927 05-05-2011, 02:39 PM
Last Post: seminar class

Forum Jump: