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