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 [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---
