### 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 BQP^{O} ⊈ PH^{O}.

Original language | English (US) |
---|---|

Title of host publication | STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Moses Charikar, Edith Cohen |

Publisher | Association for Computing Machinery |

Pages | 13-23 |

Number of pages | 11 |

ISBN (Electronic) | 9781450367059 |

DOIs | |

State | Published - Jun 23 2019 |

Event | 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States Duration: Jun 23 2019 → Jun 26 2019 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Conference

Conference | 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 |
---|---|

Country | United States |

City | Phoenix |

Period | 6/23/19 → 6/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

Raz, R., & Tal, A. (2019). Oracle separation of BQP and pH. In M. Charikar, & E. Cohen (Eds.),

*STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing*(pp. 13-23). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3313276.3316315