Subject: RE: [hackers-il] quantum computers - summary [rather long]

From: "Ofir Carny" <[email-masked]>
Date: Wed, 10 Apr 2002 06:30:01 -0000

AFAIR, basically Turing compatibility means that machine X can simulate a given turing machine and that said turing machine can simulate machine X, so that the overhead of both simulation can be bounded by a polynom based on the time it would take to the unsimulated program to run.

That's basically what P means - everything a turing machine can calculate in polynomial time (based on input).
NP means (altough I heard several definitions for that) - something which can be verified to be true in  polynomial time given a piece of information to verify that it is true (e.g. to check that a number is not prime if given an alleged divisor, to show that there is a solution to a set of equation by being given it - verifing the solution).

That means that all NP problems can be solved by a turing machine in exponential time - you can check all possible pieces of information if exponential time. What we dont know is whether it can be done in polynomial time (the P?=NP question).

AFAIR, Roughly speaking, the program/data interchangability is fundemental to turing machines, so its basically the same model. That's how you can construct a turing machine to simulate all turing machines given their representation.

-----Original Message-----
From: Oleg Goldshmidt [mailto:[email-masked]]
Sent: Tuesday, April 09, 2002 9:19 PM
To: [email-masked]
Subject: Re: [hackers-il] quantum computers - summary [rather long]

"Nadav Har'El" <[email-masked]> writes:

> What you explained is why Quantum computers are *at least stronger* than
> a Turing machine, not why they are the same thing as Turing machines. Using
> a quantum machine you can do some things in polynomial time that you we
> don't know how to do in polynomial time in a deterministic Turing machine -
> hence they may be really stronger. (Note: I'm saying "don't know how to do"
> instead of "can't do", because nobody even knows if P!=NP, for
> example).

I am missing something conceptual here. I thought that the idea of
Turing machines was to separate computable problems from
non-computable ones. The question of efficiency or complexity is that
of an algorithm used, and is quite separate in my mind.

In particular, the usual statement is that having multiple Turing
machines (a finite number of those) working in parallel makes no
difference in principle, since the computation can be performed
sequentially by a single Turing machine. Since - OK, let me be
cautious - I have not seen anything that would contradict the
statement that there is nothing in any single thread of parallel
quantum computation that is not computable by a classical Turing
machine, I conclude that anything a quantum computer can do, a
classical computer can also do. It may take the classical computer
more than Hubble time, but that's immaterial as far as
Turing-equivalency is concerned.

I am a bit (a qubit?) confused (and need to do much more reading) with
the universal quantum gate representation as well. It seems that a set of
1-bit rotations plus a 2-bit XOR can perform any quantum computation
(phase shifts are irrelevant) - cf.

http://xxx.lanl.gov/abs/quant-ph/9503016

- I have not yet read it, just glanced through very quickly.

I suspect that each of those individually can be performed by a
(probably exponential but) finite number of classical gates. This will
prove that any quantum computation can be performed by a set of
classical gates, albeit much less efficiently. What bothers me here is
that rotations for arbitrary angles are needed, and there is an
infinite number of those, seemingly, which is problematic. On the
other hand, a quantum computation of a finite number of operations
will need a finite number of rotations to perform. Yet another angle
is the data which is also quantum. On top of that, we are familiar
with computational models that do not distinguish between programs and
data... Forget it, it's silly to apply common sense to technical
aspects of the quantum world. I need more time to read and think.

> So I guess we were both right in some sense, we just misunderstood each
> other ;) 

I suspect that the mutual misunderstanding stems from the different
understanding of the definition of Turing machine - stopping or
complexity.

> But I think I better shut-up on this issue after this posting,
> because I am really not a quantum computing expert 

And I even lack the benefit of formal CS education, so my email
account should be revoked ;-) My understanding of turing machines
might differ from what is taught in a modern CS course at the
Technion, and I should certainly defer to that authority.

> (I think we have 2 other people on this list who are!),

I guess Eran Tromer is one - why didn't he (and the other one) stop me
in time? ;-)

> it's better to be thought a fool than to open your mouth 
> and remove all doubt

Too late for me... ;-)

Is that the difference between mathematicians and physicists? The
latter consider only one question stupid, "May I ask a stupid question?"

> If we ever prove P!=NP, is it possible that we might still find that quantum
> computers (without oracles) can't calculate in polynomial time anything more
> than P? That would be unfortunate, and make quantum computers absolutely
> useless...

Not necessarily. Grover's search is considered pretty useful,
apparently. ;-)

> > [3] E. Bernstein, U. Vazirani, 1997, Quantum Complexity theory,
> >     http://epubs.siam.org/sam-bin/getfile/SICOMP/articles/30092.pdf
> >     (Unfortunately, one needs a SIAM account to get this, so I
> >      have not read the paper - OG)
> 
> I put a copy of this in http://nadav.harel.org.il/pub/30092.pdf

Thanks! More stuff to study...

-- 
Oleg Goldshmidt | [email-masked] 
If it aint't broken it hasn't got enough features yet.

To unsubscribe from this group, send an email to:
[email-masked]

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

---

From: Adeyemo oluseyi <[email-masked]>
Date: Wed, 10 Apr 2002 17:18:26 -0700 (PDT)

Hi There,
      I want to have full understanding on how to
hack.
E.G CREDIT CARD, SITES, PASSWORD AND BANK.
   Thaat was my main purpose of joining you site and i
want to tell you that someone Hack my password and
deleated all my confidential message even he even
clear off my credit card information.If there is any
way you can use to help me to get another card and
also to strike back,i will be very glad to read from
you.
Thanks
Richard oluseyi

--- Ofir Carny <[email-masked]> wrote:
> AFAIR, basically Turing compatibility means that
> machine X can simulate a given turing machine and
> that said turing machine can simulate machine X, so
> that the overhead of both simulation can be bounded
> by a polynom based on the time it would take to the
> unsimulated program to run.
> 
> That's basically what P means - everything a turing
> machine can calculate in polynomial time (based on
> input).
> NP means (altough I heard several definitions for
> that) - something which can be verified to be true
> in  polynomial time given a piece of information to
> verify that it is true (e.g. to check that a number
> is not prime if given an alleged divisor, to show
> that there is a solution to a set of equation by
> being given it - verifing the solution).
> 
> That means that all NP problems can be solved by a
> turing machine in exponential time - you can check
> all possible pieces of information if exponential
> time. What we dont know is whether it can be done in
> polynomial time (the P?=NP question).
> 
> AFAIR, Roughly speaking, the program/data
> interchangability is fundemental to turing machines,
> so its basically the same model. That's how you can
> construct a turing machine to simulate all turing
> machines given their representation.
> 
> Thanks! More stuff to study...
=== message truncated ===

__________________________________________________
Do You Yahoo!?
Yahoo! Tax Center - online filing with TurboTax
http://taxes.yahoo.com/