Oracle Separation of BQP and PH

Ran Raz, Avishay Tal

Research output: Contribution to journalArticlepeer-review

3 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 languageEnglish (US)
Article number30
JournalJournal of the ACM
Volume69
Issue number4
DOIs
StatePublished - Aug 31 2022
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Oracle Separation of BQP and PH'. Together they form a unique fingerprint.

Cite this