1 Replies - 466 Views - Last Post: 05 June 2018 - 08:12 AM

#1 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon

Reputation: 12680
  • View blog
  • Posts: 45,863
  • Joined: 27-December 08

[News] BQP != PH in Relativized Worlds

Posted 04 June 2018 - 09:03 PM

This is a very big deal, and very interesting read.


All of you readers should be familiar with the P v NP question. P is the set of problems efficiently solvable by a deterministic computer. NP are the problems for which there exists a witness that we can verify quickly. The polynomial-time hierarchy (PH) is the constant alternation generalization of NP that has played a major role in computational complexity So why don't we talk about the P vs PH question? That's just equivalent to P vs NP.

BQP is the the class of problem efficiently solved by a quantum computer. Since P sits in BQP which sits in PSPACE we can't prove outright any separations for BQP without separating P from PSPACE. We can though get an understanding of complexity by allowing the machines access to the same oracle and seeing what we can separate. We already knew BQP doesn't sit in NP relative to an oracle. Same was true for BPP (efficient probabilistic computation) but BPP is in PH for all oracles as are constant round interactive proofs. So we might expect we can have BQP in PH, BQP solvable with constant alternations, relative to all oracles. Raz and Tal refute that hypothesis.

Link: https://blog.computa...erarchy-in.html

Scott Aaronson's take on the problem is also a worthwhile read: https://www.scottaar...om/blog/?p=3827

Is This A Good Question/Topic? 2
  • +

Replies To: [News] BQP != PH in Relativized Worlds

#2 modi123_1   User is offline

  • Suitor #2
  • member icon

Reputation: 15434
  • View blog
  • Posts: 61,848
  • Joined: 12-June 08

Re: [News] BQP != PH in Relativized Worlds

Posted 05 June 2018 - 08:12 AM


Posted Image

Posted Image


PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.



an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain decision problems in a single operation.

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1