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
> <meek...@verizon.net <javascript:>> 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 <javascript:>.
> To post to this group, send email to everyth...@googlegroups.com
> <javascript:>.
> 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.
