Re: Fwd: "Finally, A Problem That Only Quantum Computers Will Ev
The upshot is that with forrelation equivalent to the BPQ problem a match
occurs with few oracles that with PH. An oracle is a sort of hypercomputing
system outside the Church-Turing thesis or λ-calculus. If BPQ requires
fewer oracle inputs it means it is a closer approximation to a hyper-Turing
machine or the Löbian machine. This is a different domain in the theory of
computation.
LC
On Thursday, June 21, 2018 at 8:20:35 PM UTC-5, cdemorsella wrote:
>
> The birth of a fundamentally distinct new class of problems.
>
> BQP has carved out a realm of its own... beyond the reach of the combined
> set PH = {P, NP}
>
> Chris
>
> On Thu, Jun 21, 2018 at 3:52 PM, Brent Meeker
> > wrote:
>
>
>
> Forwarded Message
>
>
>
> https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/
> ref: https://eccc.weizmann.ac.il/report/2018/107/
> ...
>
> *Here’s the problem. Imagine you have two random number generators, each
> producing a sequence of digits. The question for your computer is this: Are
> the two sequences completely independent from each other, or are they
> related in a hidden way (where one sequence is the “Fourier transform” of
> the other)? Aaronson introduced this “forrelation” problem in 2009 and
> proved that it belongs to BQP. That left the harder, second step — to prove
> that forrelation is not in PH.*
>
> *Which is what Raz and Tal have done, in a particular sense. Their paper
> achieves what is called “oracle” (or “black box”) separation between BQP
> and PH. This is a common kind of result in computer science and one that
> researchers resort to when the thing they’d really like to prove is beyond
> their reach.*
>
> *The actual best way to distinguish between complexity classes like BQP
> and PH is to measure the computational time required to solve a problem in
> each. But computer scientists “don’t have a very sophisticated
> understanding of, or ability to measure, actual computation time,” said
> Henry Yuen, a computer scientist at the University of Toronto.*
>
> *So instead, computer scientists measure something else that they hope
> will provide insight into the computation times they can’t measure: They
> work out the number of times a computer needs to consult an “oracle” in
> order to come back with an answer. An oracle is like a hint-giver. You
> don’t know how it comes up with its hints, but you do know they’re
> reliable.*
>
> *If your problem is to figure out whether two random number generators are
> secretly related, you can ask the oracle questions such as “What’s the
> sixth number from each generator?” Then you compare computational power
> based on the number of hints each type of computer needs to solve the
> problem. The computer that needs more hints is slower.*
>
> *“In some sense we understand this model much better. It talks more about
> information than computation,” said Tal.*
>
> *The new paper by Raz and Tal proves that a quantum computer needs far
> fewer hints than a classical computer to solve the forrelation problem. In
> fact, a quantum computer needs just one hint, while even with unlimited
> hints, there’s no algorithm in PH that can solve the problem. “This means
> there is a very efficient quantum algorithm that solves that problem,” said
> Raz. “But if you only consider classical algorithms, even if you go to very
> high classes of classical algorithms, they cannot.” This establishes that
> with an oracle, forrelation is a problem that is in BQP but not in PH.*
>
> --
> You received this message because you are subscribed to the Google Groups
> "Everything List" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to everything-li...@googlegroups.com .
> To post to this group, send email to everyth...@googlegroups.com
> .
> Visit this group at https://groups.google.com/group/everything-list.
> For more options, visit https://groups.google.com/d/optout.
>
>
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
Re: Fwd: "Finally, A Problem That Only Quantum Computers Will Ev
True, but as you mentioned, and we are in agreement this is a fundamentally new
class of problem. Whether it turns out to be of practical utility or remains as
an interesting oddball is yet to be determined.Chris
Sent from Yahoo Mail on Android
On Fri, Jun 22, 2018 at 1:42 PM, John Clark wrote: On
Thu, Jun 21, 2018 at 9:20 PM, 'Chris de Morsella' via Everything List
wrote:
> The birth of a fundamentally distinct new class of problems.BQP has carved
out a realm of its own... beyond the reach of the combined set PH = {P, NP}
This new result does not prove a quantum computer could solve all
nondeterministic polynomial time problem s in polynomial time but it does
prove that even if P=NP and even if we had an algorithm that could solve NP
problems on a conventional computer in polynomial time there would still be a
class of problems a conventional computer couldn’t solve efficiently but a
quantum computer could. This class of very exotic problems may be of
fundamental interest in themselves or they may be interesting for no reason
other than that a conventional computer can’t solve them.
John K Clark
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
Re: Fwd: "Finally, A Problem That Only Quantum Computers Will Ev
On Thu, Jun 21, 2018 at 9:20 PM, 'Chris de Morsella' via Everything List <
everything-list@googlegroups.com> wrote:
>
> The birth of a fundamentally distinct new class of problems.
> BQP has carved out a realm of its own... beyond the reach of the combined
> set PH = {P, NP}
>
This new result does not prove a quantum computer could solve all
nondeterministic polynomial time problem s in polynomial time but it does
prove that even if P=NP and even if we had an algorithm that could solve NP
problems on a conventional computer in polynomial time there would still be
a class of problems a conventional computer couldn’t solve efficiently but
a quantum computer could. This class of very exotic problems may be of
fundamental interest in themselves or they may be interesting for no reason
other than that a conventional computer can’t solve them.
John K Clark
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
Re: Fwd: "Finally, A Problem That Only Quantum Computers Will Ev
The birth of a fundamentally distinct new class of problems.
BQP has carved out a realm of its own... beyond the reach of the combined set
PH = {P, NP}
Chris
On Thu, Jun 21, 2018 at 3:52 PM, Brent Meeker wrote:
Forwarded Message
https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/
ref: https://eccc.weizmann.ac.il/report/2018/107/ ...
Here’s the problem. Imagine you have two random number generators, each
producing a sequence of digits. The question for your computer is this: Are the
two sequences completely independent from each other, or are they related in a
hidden way (where one sequence is the “Fourier transform” of the other)?
Aaronson introduced this “forrelation” problem in 2009 and proved that it
belongs to BQP. That left the harder, second step — to prove that forrelation
is not in PH.
Which is what Raz and Tal have done, in a particular sense. Their paper
achieves what is called “oracle” (or “black box”) separation between BQP and
PH. This is a common kind of result in computer science and one that
researchers resort to when the thing they’d really like to prove is beyond
their reach.
The actual best way to distinguish between complexity classes like BQP and PH
is to measure the computational time required to solve a problem in each. But
computer scientists “don’t have a very sophisticated understanding of, or
ability to measure, actual computation time,” said Henry Yuen, a computer
scientist at the University of Toronto.
So instead, computer scientists measure something else that they hope will
provide insight into the computation times they can’t measure: They work out
the number of times a computer needs to consult an “oracle” in order to come
back with an answer. An oracle is like a hint-giver. You don’t know how it
comes up with its hints, but you do know they’re reliable.
If your problem is to figure out whether two random number generators are
secretly related, you can ask the oracle questions such as “What’s the sixth
number from each generator?” Then you compare computational power based on the
number of hints each type of computer needs to solve the problem. The computer
that needs more hints is slower.
“In some sense we understand this model much better. It talks more about
information than computation,” said Tal.
The new paper by Raz and Tal proves that a quantum computer needs far fewer
hints than a classical computer to solve the forrelation problem. In fact, a
quantum computer needs just one hint, while even with unlimited hints, there’s
no algorithm in PH that can solve the problem. “This means there is a very
efficient quantum algorithm that solves that problem,” said Raz. “But if you
only consider classical algorithms, even if you go to very high classes of
classical algorithms, they cannot.” This establishes that with an oracle,
forrelation is a problem that is in BQP but not in PH.
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
