Hi Bruno,
> I have finished the reading of the paper I mentioned (Deutsch's
> Universal Quantum Turing Machine revisited) and I see they have very
> similar problems, probably better described.
I finished a rather careful reading of that paper (QTM revisited) too,
http://arxiv.org/pdf/quant-ph/0701108v1
and if I got it right the main authors' point is:
Claims:
1) An Universal Probabilistic Turing Machine (PTM) can simulate the set
of PTMs with computable transition probabilities EXACTLY.
2) An Universal QTM can simulate the set of QTMs with computable
amplitudes only approximately.
Conclusion:
The notion of universality for Quantum TM is not of the same kind that
we have for Determinictic TM and Probabilistic TM.
--------
Well, the first claim is correct and the corresponding algorithm for an
EXACT simulation is very simple. I think you know this well, but for the
sake of having a good reference, see for example Lemma 7.14 in
http://www.cs.princeton.edu/theory/complexity/bppchap.pdf
A tricky point, of course, is that in order to achive an EXACT
simulation your algorithm will potentionally never stop. For example,
trying to achieve ouput probability P=1/3 using UPTM with transitional
probabilities {0,1/2,1} is exact only in the limit.
In practice, such an EXACT simulation is not needed, and people prefer
to say that one machine CAN simulate other machine if properties in
question can be approximated with ARBITRARY accuracy. Yes, and it should
be reasonably fast. Typically the penalty for a better accuracy is
upper-bounded by a polylog factor.
Regarding the second claim, it is not true to my knowledge.
Approximation of amplitudes is a convergent process - set your accuracy,
suffer polylog slowdown factor, done. Wanna go to the limit, you get an
exact simulation.
> The paper mentions (but
> does not tackle) an old problem already described by Shi 2002, which
> made me think at the time that the notion of Universality is a bit
> dubious in the quantum realm.
I don't know which problem do you mean. In the QTM Revisited paper, the
authors do not suply a valid reference, the paper they refer to does not
exist and they don't get right even the first name of Dr. Shi.
Thus I may only assume that you/the authors refer to this paper
http://arxiv.org/pdf/quant-ph/0205115v2
I have read this paper few years ago and after a quick today's scan I'm
not aware of some explicitly described problem. On the contrary, the
message of the paper is that it is 'easy' to find universal set of
quantum gates (given that you start, for better or worse, from classical
universal set of gates).
> To sum up: is there a (never stopping) quantum counting algorithm? I
> think I can build a Quantum UD from it, well in case the Shi problem
> is not too much devastating.
> But here, and now, I got a feeling there is just no quantum counting
> algorithm ...
>
Please be more specific about what do you mean by a quantum counting
algorithm. Sometimes I'm not too bright guy :-)
Is this what you mean?
step 1\ |0>
step 2\ |0> + |1>
step 3\ |0> + |1> + |2>
....
or (a classical machine operated by quantum means)
step 1\ |0>
step 2\ |1>
step 3\ |2>
....
or something different :-)
Best,
mirek
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Mon Jan 19 2009 - 17:18:12 PST