Quantum computers = Turing machine?
Dale Hurliman
machine? And would a quantum computer have any implications for
Church's Thesis (Anything which can be computed can be computed by a
Turing machine in finite time)?
Davin C. Enigl
I don't think so. . . Read David Deutsch's The Fabric of Reality for
a good discussion on this.
Bill Taylor
|> >machine? And would a quantum computer have any implications for
|> >Church's Thesis (Anything which can be computed can be computed by a
|> >Turing machine in finite time)?
|> I don't think so. . . Read David Deutsch's The Fabric of Reality for
|> a good discussion on this.
Or any quomping book.
The answer is definitely no. There *would* however be an effect on
whether various types of complicated (in the P/NP sense) functions could
be calculated in very quick (Q-real) time.
It would not, however, change the actual status of the P/NP classifications
themselves, as that is an abstract matter, not a physical one.
It is in this area that the distinctions ABSTRACT:PHYSICAL::MATH:SCIENCE
have most relevance! Yet another great bi-dichotomy there!!
------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
------------------------------------------------------------------------------
The nature of light is "?"
The upper part denotes the wave aspect, the lower part the particle aspect.
------------------------------------------------------------------------------
Alias
When light changes its nature between " " and ?, must there be a
corresponding associated quantum event, even though not observed? I
hope this question is meaningful. If not, ignore me. I won't mind. I'm
poorly qualified to be here anyway.
Alias
tc...@lsa.umich.edu
Bill Taylor <mat...@math.canterbury.ac.nz> wrote:
<|> >Would a quantum computer (when one is built) be homologous to a Turing
<|> >machine? And would a quantum computer have any implications for
<|> >Church's Thesis (Anything which can be computed can be computed by a
<|> >Turing machine in finite time)?
<|> I don't think so. . . Read David Deutsch's The Fabric of Reality for
<|> a good discussion on this.
<
<Or any quomping book.
<
<The answer is definitely no.
But see the following preprints, which suggest that the answer is yes.
http://arxiv.org/abs/quant-ph/0112087
http://arxiv.org/abs/quant-ph/0110136
Seems pretty far-fetched to me, but I don't know enough physics to be able
to follow the argument in detail.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
Bill Taylor
|> > The answer is definitely no.
|> But see the following preprints, which suggest that the answer is yes.
Thanks for the refs, but I doubt I'll check them out.
Life is too short, and I've read many similar-looking things in the past.
However, Tim, if you would be so kind as to summarize them here, I'll
certainly give it serious consideration, and explain any flaws.
|> Seems pretty far-fetched to me,
I'm sure you're right! :)
|> but I don't know enough physics to be able to follow the argument in detail.
You don't need to know very much physics to be able to detect or pinpoint
an argument conflating the terms in my sig-motto...
------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
------------------------------------------------------------------------------
ABSTRACT : PHYSICAL :: MATH : SCIENCE
------------------------------------------------------------------------------
Dale Hurliman
Alias wrote:
> mat...@math.canterbury.ac.nz (Bill Taylor) wrote in message news:<a37r1v$apu$2...@cantuc.canterbury.ac.nz>...
>
>>|> > Would a quantum computer (when one is built) be homologous to a Turing
>>|> >machine? And would a quantum computer have any implications for
>>|> >Church's Thesis (Anything which can be computed can be computed by a
>>|> >Turing machine in finite time)?
>>|> I don't think so. . . Read David Deutsch's The Fabric of Reality for
>>|> a good discussion on this.
>>
>>Or any quomping book.
>>
>>The answer is definitely no.
If that is true, then could quantum computers compute functions which a
Turing machine could not? If so what sorts of functions? (And I am not
thinking of questions of polynomial _vs_ non polynomial time. Time
does not enter into consideration of Turing machines.) And if true, this
must have implications for Church's Thesis. What are they? Is it now
invalid? Can it be revised somehow ?
<snip>
Dale
tc...@lsa.umich.edu
Bill Taylor <mat...@math.canterbury.ac.nz> wrote:
>However, Tim, if you would be so kind as to summarize them here, I'll
>certainly give it serious consideration, and explain any flaws.
Here's what I understand of http://arxiv.org/abs/quant-ph/0110136
Suppose we're given a polynomial p(x_1, ..., x_n) with integer coefficients.
We want to find the minimum value of |p(x_1, ..., x_n)|^2 as the x_i range
over all integers. This is impossible classically (Hilbert's 10th problem).
Tien D Kieu suggests preparing a physical system whose ground state energy
is the desired minimum value. If we can measure the ground state energy
then we will obtain the solution to the problem.
Two possible objections spring to mind. (1) Measurements in quantum
mechanics are probabilistic, so one can never obtain the desired quantity
with the absolute certainty usually required in classical recursion
theory. I'm not fully decided about this objection, but initially my
feeling is that this is not the crucial point. (2) One cannot actually
prepare the physical system in question. I'm afraid I'm not competent
to evaluate, or even summarize, Kieu's proposal here, but those interested
can read the above paper.
Bill Taylor
|> If that is true, then could quantum computers compute functions which a
|> Turing machine could not?
As presently envisaged, (remember we don't actually *have* any yet!),
no they could not.
|> (And I am not
|> thinking of questions of polynomial _vs_ non polynomial time.
Naturally - it is well-known that they can transcend PTime and PSpace limits.
|> Time does not enter into consideration of Turing machines.
You are absolutely correct; but you will have a hard time impressing that
point on a lot of popularizers and their readers!
|> must have implications for Church's Thesis. What are they?
No such functions, so no implications.
|> Is it now invalid?
So this has been covered. But it does suggest a further query.
Insofar as Church's thesis is treated as a formal matter, it doesn't
say a lot, and is true (and easily provable). As an informal matter,
it's hard to pin down exactly what it says, but it's something to do with:
"ANY kind of machine or procedure that we would (inter-subjectively)
recognize as doing computations which were understandable in detail,
even if too complex in total for us to follow."
Opinions will differ on how much of that quoted phrase should apply
or how worded. But something like that. So, involving subjectivity
and vagueness as it does, it seems to leave open a chink of space
for the following scenario.
Somone builds a machine that they aren't fully capable of convincing us
how/that it works, but it seems to, and we can check in detail how (and that)
it works for finite calculations. We can also verify that it gets the
right answers in an incredibly short time, to problems which would take
ordinary computers, even quantum ones, centuries and millenia. Huge
advances are made in number theory and math proofs generally. But the maker
also claims it can execute an infinite sequence of (checkable in detail)
steps in a finite time. A classic "infinite task" machine, in fact.
Any that can be checked against known theorems are checked and always found
true. Any that are set moving and stopped "before infinite completion"
are also found to be correct, (and found were done by operations checkable
in detail). The only thing it can do that we can't yet, is check an
infinite sequence of (programmatically similar) cases, and relay back
whether (say) any came to zero. This is, of course, enough to determine
the result of any sigma_1 or pi_1 numerical statement, including halting
problems and so forth. If the machines can be cascaded (internally or
externally), it can determine the truth of ANY PA-statement.
What would we say about such a machine? Would we put all its invariable
successes down to "mere luck"? Would we rigidly insist that it proved
nothing new, merely perhaps that it gave "good evidence" for certain new
alleged facts? I don't know. And would it have any effect on the (informal)
Church's thesis??? I still don't know.
Perhaps others might care to speculate on these points.
------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
------------------------------------------------------------------------------
Kleeneness is next to Godelness.
------------------------------------------------------------------------------
David Moews
|In article <a3aivl$5ti$4...@cantuc.canterbury.ac.nz>,
|Bill Taylor <mat...@math.canterbury.ac.nz> wrote:
|>However, Tim, if you would be so kind as to summarize them here, I'll
|>certainly give it serious consideration, and explain any flaws.
|
|Here's what I understand of http://arxiv.org/abs/quant-ph/0110136
|
|Suppose we're given a polynomial p(x_1, ..., x_n) with integer coefficients.
|We want to find the minimum value of |p(x_1, ..., x_n)|^2 as the x_i range
|over all integers. This is impossible classically (Hilbert's 10th problem).
|
|Tien D Kieu suggests preparing a physical system whose ground state energy
|is the desired minimum value. If we can measure the ground state energy
|then we will obtain the solution to the problem.
I looked at this paper. I see nothing specifically quantum-mechanical about
this suggestion. We could equally well say that we will prepare a classical
system that will be in equilibrium only when |p(x_1, ..., x_n)|^2 is
minimum. Then we simply sit down and wait for the system to reach
equilibrium. I think the problems are the following.
(1) The physical system may break down for large values of x_i. For
example, if x_i is the number of photons in a certain mode in
a cavity, and the system tries to drive itself to x_i=10^(10^10),
it will probably either blow up or run out of photons.
(2) The time taken to reach equilibrium, or the ground state. If
we wait a day and measure |p|^2 = 54756, how do we know we have
waited long enough for |p|^2 to drop to its minimum? If the wait
time becomes infinite as max_i |x_i| in the solution becomes infinite
(as seems very likely), the method does not differ qualitatively from
exhaustive search on a conventional computer.
--
David Moews dmo...@xraysgi.ims.uconn.edu
Bill Taylor
|> Here's what I understand of http://arxiv.org/abs/quant-ph/0110136
|>
|> Suppose we're given a polynomial p(x_1, ..., x_n) with integer coefficients.
|> We want to find the minimum value of |p(x_1, ..., x_n)|^2 as the x_i range
|> over all integers. This is impossible classically (Hilbert's 10th problem).
|>
|> Tien D Kieu suggests preparing a physical system whose ground state energy
|> is the desired minimum value. If we can measure the ground state energy
|> then we will obtain the solution to the problem.
Thanks for posting this summary Tim - it's exactly what I was after!
It reminds me somewhat of a Martin Gardner column, where he described
various analogue solvers to certain problems, that might be quicker at
solving them than a digital computer. One was, find the longest pencil
in a bunch of n. The usual digital method takes time n. The method of
holding them all bunched together and tapping them onto a table, using
gravity, and eyeballing the tallest, was alleged to be better and do it
in time c, constant. I thought this was a really, really, silly thing.
The alleged "method" bypasses such a huge number of practical problems
(like holding a million, or 100 million, pencils in your hand), that it
can't be considered more than a bad joke.
There were various others - finding the C of G of a bunch of planar weights
by means of strings and pulleys, I think was one. They were all of similar
stupifdity, in that they all glossed over equally disrupting practicalities.
It was rather difficult to see what the "essential method" really amounted
to in math terms. The whole thing was very disappointing, though fun.
And they seem to be similar to the case above...
|> Two possible objections spring to mind. (1) Measurements in quantum
|> mechanics are probabilistic, so one can never obtain the desired quantity
|> with the absolute certainty
That is cetrainly a valid objection, though one doesn't need QM to make it.
Ordinary classical randomness due to imperfect experimental technique
is more than sufficient.
|> (2) One cannot actually prepare the physical system in question.
I would guess this is also valid. After all, we need to be able to handle
inputs of the order of 1- or 100-million data points... where on earth are
you going to be able to prepare *any* analogue system in such a state to
the desired accuracy... it is absurd. The whole point of digital computing
is to remove small variations in analogue states by rendering them bitwise
digital, so the "real physics" doesn't apply, just basic organizational
physics... computer engineering. To compare calculations done thuswise with
those done by "analogue preparations" like the above, or like the pencils
earlier, is the height of absurdity - amounting to a category mistake, in fact.
I had hoped the alleged experiemnt was going to be something rather more
digital and many-worldly... pity.
------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
------------------------------------------------------------------------------
How many universes can dance on the head of a photomultiplier?
------------------------------------------------------------------------------
Keith Ramsay
mat...@math.canterbury.ac.nz (Bill Taylor) writes:
||> (And I am not
||> thinking of questions of polynomial _vs_ non polynomial time.
|
|Naturally - it is well-known that they can transcend PTime and PSpace limits.
Careful, it's not known.
There are problems (e.g. factorization) that have polynomial "quantum
algorithms" but no _known_ polynomial time algorithm, but we don't
know that polynomial time algorithms for them don't exist. I'm pretty
sure that none of them are even known to be NP-complete or NP-hard,
and that even assuming standard conjectures like P<>NP isn't known to
imply that polynomial time algorithms for them don't exist.
A polynomial-time bounded quantum computer can be simulated in
polynomial-bounded space by a Turing machine. One way to do the
simulation is basically to have the Turing machine to do a path sum,
computing amplitudes and phases for each "path" that the quantum
computation takes, and keeping a running total. It requires that the
Turing machine be able to store an entire "history" of a calculation
on the quantum computer, maintaining a sufficiently precise running
sum of the amplitudes/phases it's obtained. This all can be done in
polynomial-bounded space.
I don't see how to adapt it to an general "quantum polynomial space"
machine, and I suppose it seems a bit doubtful that one gets exactly
the same thing. On the other hand, does anybody know of a particular
problem (aside from "simulate a quantum computer having a polynomial
space bound") that in theory could be solved in quantum polynomial
space but not by a Turing machine with a polynomial space bound? I
suspect it's not known whether PSPACE and "quantum PSPACE" are the
same, even assuming P<>PSPACE, and if it is known, surely it's that
there actually is some clever way to do the simulation that I don't
know about.
Keith Ramsay
tc...@lsa.umich.edu
Keith Ramsay <kra...@aol.commangled> wrote:
>There are problems (e.g. factorization) that have polynomial "quantum
>algorithms" but no _known_ polynomial time algorithm, but we don't
>know that polynomial time algorithms for them don't exist. I'm pretty
>sure that none of them are even known to be NP-complete or NP-hard,
That's correct. It would be a major result to show that BQP contains NP.
>and that even assuming standard conjectures like P<>NP isn't known to
>imply that polynomial time algorithms for them don't exist.
Also correct.
>I don't see how to adapt it to an general "quantum polynomial space"
>machine, and I suppose it seems a bit doubtful that one gets exactly
>the same thing. On the other hand, does anybody know of a particular
>problem (aside from "simulate a quantum computer having a polynomial
>space bound") that in theory could be solved in quantum polynomial
>space but not by a Turing machine with a polynomial space bound? I
>suspect it's not known whether PSPACE and "quantum PSPACE" are the
>same, even assuming P<>PSPACE, and if it is known, surely it's that
>there actually is some clever way to do the simulation that I don't
>know about.
I seem to recall that
BQSpace(s(n)) <= PrSpace(c*s(n)) <= DSpace(c'*s(n)^2),
where c and c' are constants, i.e., that bounded-error quantum space
can be simulated using a classical probabilistic Turing machine with
unbounded error and that the latter can be simulated using a deterministic
Turing machine with a quadratic increase in space. If this is right then
BQPSpace = PSpace.
tc...@lsa.umich.edu
David Moews <dmo...@xraysgi.ims.uconn.edu> wrote:
>In article <a3bs53$dra$1...@galois.mit.edu>, <tc...@lsa.umich.edu> wrote:
>|
>|Here's what I understand of http://arxiv.org/abs/quant-ph/0110136
>I think the problems are the following.
>
>(1) The physical system may break down for large values of x_i. For
> example, if x_i is the number of photons in a certain mode in
> a cavity, and the system tries to drive itself to x_i=10^(10^10),
> it will probably either blow up or run out of photons.
This sounds right to me.
>(2) The time taken to reach equilibrium, or the ground state. If
> we wait a day and measure |p|^2 = 54756, how do we know we have
> waited long enough for |p|^2 to drop to its minimum? If the wait
> time becomes infinite as max_i |x_i| in the solution becomes infinite
> (as seems very likely), the method does not differ qualitatively from
> exhaustive search on a conventional computer.
It seems that Kieu tries to address this issue. I don't fully understand
what he's saying, but it looks like he's claiming that Tarski's algorithm
allows one to compute an upper bound for the waiting time. If this is
right, then this would meet objection (2).