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
> <[email protected] <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 [email protected] <javascript:>.
> To post to this group, send email to [email protected]
> <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 [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
