Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ORACLE SEPARATION:
Reports tagged with oracle separation:
TR03-065 | 19th June 2003
Wee, Hoeteck

#### Compressibility Lower Bounds in Oracle Settings

A source is compressible if we can efficiently compute short
descriptions of strings in the support and efficiently
recover the strings from the descriptions. In this paper, we
present a technique for proving lower bounds on
compressibility in an oracle setting, which yields the
following results:

- We ... more >>>

TR04-026 | 17th February 2004
Scott Aaronson

#### Limitations of Quantum Advice and One-Way Communication

Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones.
First, we show that BQP/qpoly is contained in ... more >>>

TR14-181 | 19th December 2014
Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee

#### The space "just above" BQP

We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the ... more >>>

TR18-107 | 31st May 2018
Ran Raz, Avishay Tal

#### Oracle Separation of BQP and PH

We present a distribution $D$ over inputs in $\{-1,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 $\Omega(1/\log N)$.
(2) No Boolean circuit of $\mathrm{quasipoly}(N)$ ... more >>>

TR18-202 | 1st December 2018
Xinyu Wu

#### A stochastic calculus approach to the oracle separation of BQP and PH

After presentations of the oracle separation of BQP and PH result by Raz and Tal [ECCC TR18-107], several people
(e.g. Ryan O’Donnell, James Lee, Avishay Tal) suggested that the proof may be simplified by
stochastic calculus. In this short note, we describe such a simplification.

more >>>

TR19-062 | 18th April 2019
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler

#### Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

This paper proves new limitations on the power of quantum computers to solve approximate counting---that is, multiplicatively estimating the size of a nonempty set $S\subseteq [N]$.

Given only a membership oracle for $S$, it is well known that approximate counting takes $\Theta(\sqrt{N/|S|})$ quantum queries. But what if a quantum algorithm ... more >>>

ISSN 1433-8092 | Imprint