- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Mirek Dobsicek <m.dobsicek.domain.name.hidden>

Date: Mon, 19 Jan 2009 23:18:05 +0100

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

Date: Mon, 19 Jan 2009 23:18:05 +0100

Hi Bruno,

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.

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

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

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:15 PST
*