Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > FBQP:
Reports tagged with FBQP:
TR10-128 | 15th August 2010
Scott Aaronson

#### The Equivalence of Sampling and Searching

Revisions: 1

In a sampling problem, we are given an input $x\in\left\{0,1\right\} ^{n}$, and asked to sample approximately from a probability
distribution $D_{x}$ over poly(n)-bit strings. In a search problem, we are given an input
$x\in\left\{ 0,1\right\} ^{n}$, and asked to find a member of a nonempty set
$A_{x}$ with high probability. ... more >>>

ISSN 1433-8092 | Imprint