Oracle separation of BQP and pH

Ran Raz, Avishay Tal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

We present a distribution D over inputs in (±1)2N , such that: (1) There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time O(log N), that distinguishes between D and the uniform distribution with advantage Ω(1/log N). (2) No Boolean circuit of quasipoly(N) size and constant depth distinguishes between D and the uniform distribution with advantage better than polylog(N)/N. By well known reductions, this gives a separation of the classes Promise-BQP and Promise-PH in the black-box model and implies an oracle O relative to which BQPO ⊈ PHO.

Original languageEnglish (US)
Title of host publicationSTOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
EditorsMoses Charikar, Edith Cohen
PublisherAssociation for Computing Machinery
Pages13-23
Number of pages11
ISBN (Electronic)9781450367059
DOIs
StatePublished - Jun 23 2019
Event51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States
Duration: Jun 23 2019Jun 26 2019

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
CountryUnited States
CityPhoenix
Period6/23/196/26/19

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • BQP
  • Bounded depth circuits
  • Oracle separation
  • Polynomial hierarchy

Fingerprint Dive into the research topics of 'Oracle separation of BQP and pH'. Together they form a unique fingerprint.

Cite this