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]> 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].
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.
--
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.
