Oracle Separation of BQP and PH

Ran Raz; Avishay Tal

doi:10.1145/3530258

Oracle Separation of BQP and PH

Ran Raz
, Avishay Tal

Research output: Contribution to journal › Article › peer-review

15 Scopus citations

Abstract

We present a distribution over inputs in ± 12N, 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 and the uniform distribution with advantage ω (1/log N).(2)No Boolean circuit of quasi-polynomial size and constant depth distinguishes between 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 relative to which BQP is not contained in PH.

Original language	English (US)
Article number	30
Journal	Journal of the ACM
Volume	69
Issue number	4
DOIs	https://doi.org/10.1145/3530258
State	Published - Aug 31 2022
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Keywords

BQP
bounded depth circuits
oracle separation
polynomial hierarchy

Access to Document

10.1145/3530258

Cite this

@article{06153ae317504ea99f9542e8eaee2283,

title = "Oracle Separation of BQP and PH",

abstract = "We present a distribution over inputs in ± 12N, 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 and the uniform distribution with advantage ω (1/log N).(2)No Boolean circuit of quasi-polynomial size and constant depth distinguishes between 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 relative to which BQP is not contained in PH.",

keywords = "BQP, bounded depth circuits, oracle separation, polynomial hierarchy",

author = "Ran Raz and Avishay Tal",

note = "Publisher Copyright: Copyright {\textcopyright} 2022 held by the owner/author(s).",

year = "2022",

month = aug,

day = "31",

doi = "10.1145/3530258",

language = "English (US)",

volume = "69",

journal = "Journal of the ACM",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "4",

}

TY - JOUR

T1 - Oracle Separation of BQP and PH

AU - Raz, Ran

AU - Tal, Avishay

PY - 2022/8/31

Y1 - 2022/8/31

N2 - We present a distribution over inputs in ± 12N, 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 and the uniform distribution with advantage ω (1/log N).(2)No Boolean circuit of quasi-polynomial size and constant depth distinguishes between 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 relative to which BQP is not contained in PH.

AB - We present a distribution over inputs in ± 12N, 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 and the uniform distribution with advantage ω (1/log N).(2)No Boolean circuit of quasi-polynomial size and constant depth distinguishes between 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 relative to which BQP is not contained in PH.

KW - BQP

KW - bounded depth circuits

KW - oracle separation

KW - polynomial hierarchy

UR - https://www.scopus.com/pages/publications/85139185847

UR - https://www.scopus.com/pages/publications/85139185847#tab=citedBy

U2 - 10.1145/3530258

DO - 10.1145/3530258

M3 - Article

AN - SCOPUS:85139185847

SN - 0004-5411

VL - 69

JO - Journal of the ACM

JF - Journal of the ACM

IS - 4

M1 - 30

ER -

Oracle Separation of BQP and PH

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this