Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations

Details Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations

2002-04-15

arxiv.org/abs/quant-ph/0204075v1

Physics

Quantum Physics

11 pages and 5 figures

Scientific paper

The main purpose of this paper is to show that we can exploit the difference ($l_1$-norm and $l_2$-norm) in the probability calculation between quantum and probabilistic computations to claim the difference in their space efficiencies. It is shown that there is a finite language $L$ which contains sentences of length up to $O(n^{c+1})$ such that: ($i$) There is a one-way quantum finite automaton (qfa) of $O(n^{c+4})$ states which recognizes $L$. ($ii$) However, if we try to simulate this qfa by a probabilistic finite automaton (pfa) \textit{using the same algorithm}, then it needs $\Omega(n^{2c+4})$ states. It should be noted that we do not prove real lower bounds for pfa's but show that if pfa's and qfa's use exactly the same algorithm, then qfa's need much less states.

Affiliated with

Also associated with

No associations

Rating

Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-383753