PaperlayerView exact revision on arXiv

Source-linked AI summary

The Equivalence of Sampling and Searching

Scott Aaronson

arXiv:1009.5104v1quant-phcs.CC

TL;DR

The paper asks how the Extended Church-Turing Thesis applies across different problem types. Using Kolmogorov complexity and algorithmic information theory, it establishes an equivalence between sampling and search. It derives a classical–quantum class equivalence and conditional consequences for Gaussian permanent estimation.

  • Problem

    The paper asks whether the Extended Church-Turing Thesis can hold for some problem types, such as decision, search, or sampling, but fail for others.

    Source: §1 · p. 1, §1.1 · p. 3

  • Method

    The paper uses Kolmogorov complexity and algorithmic information theory to construct a search problem corresponding to each sampling problem.

    Source: §1 · p. 1, §1.2 · p. 4, §1.3 · p. 6

  • Results

    FBPP = FBQP if and only if SampP = SampBQP.

    Source: §1.2 · p. 4

  • Takeaways & Limitations

    The sampling–search equivalence lets consequences about classical sampling of quantum outputs be stated equivalently in terms of classical solution of quantum-search problems.

    Source: §1.2 · p. 4

    The search problem in the main theorem is defined using uncomputable Kolmogorov complexity; making it checkable requires time- or space-bounded complexity and a complexity bound on the solving machine.

    Source: §4.4 · p. 15

Abstract

from arXiv · show

In a sampling problem, we are given an input x, and asked to sample approximately from a probability distribution D_x. In a search problem, we are given an input x, and asked to find a member of a nonempty set A_x with high probability. (An example is finding a Nash equilibrium.) In this paper, we use tools from Kolmogorov complexity and algorithmic information theory to show that sampling and search problems are essentially equivalent. More precisely, for any sampling problem S, there exists a search problem R_S such that, if C is any "reasonable" complexity class, then R_S is in the search version of C if and only if S is in the sampling version. As one application, we show that SampP=SampBQP if and only if FBPP=FBQP: in other words, classical computers can efficiently sample the output distribution of every quantum circuit, if and only if they can efficiently solve every search problem that quantum computers can solve. A second application is that, assuming a plausible conjecture, there exists a search problem R that can be solved using a simple linear-optics experiment, but that cannot be solved efficiently by a classical computer unless the polynomial hierarchy collapses. That application will be described in a forthcoming paper with Alex Arkhipov on the computational complexity of linear optics.

1 Introduction

The paper asks whether the Extended Church-Turing Thesis should apply equally to decision, promise, search, and sampling problems. It develops a sampling–search equivalence and uses it to relate classical and quantum computation.

1 Introduction

  • The paper frames the open ECT question across problem types: whether failure for one type implies failure for others.It notes that quantum computing motivates the work, while the equivalence theorem itself is not specific to quantum computing.Source: §1 · pp. 1–2, §1.1 · p. 3

1.1 Background

  • The background distinguishes decision, promise, search, and sampling questions, noting that finding a Nash equilibrium is a search problem without a known decision- or promise-problem formulation.For promise problems, the paper highlights estimating a quantum circuit's acceptance probability as a task with a natural promise formulation but no known language-decision formulation.Source: §1.1 · pp. 2–3

1.2 Our Results

  • The paper constructs, for any sampling problem S, a search problem R_S that is solvable in a model C exactly when S is samplable in C.The paper presents the result as applying to reasonable computational models.Source: §1.2 · p. 4
  • FBPP = FBQP if and only if SampP = SampBQP, connecting classical solution of quantum-search problems with classical sampling of quantum-circuit outputs.The paper states the equivalence in both directions.Source: §1.2 · p. 4
  • The paper extends Aaronson and Arkhipov’s [1] sampling result to search problems, with a classical-hardness consequence conditional on |GPE|2 being #P-complete.Under that conjecture, the paper states that FBQP ⊆ FBPP^PH cannot hold unless P^#P = PH and the polynomial hierarchy collapses.Source: §1.2 · p. 5
  • Assuming |GPE|2 is #P-complete, FBPP = FBQP would imply |GPE|2 ∈ FBPP^NP; if the polynomial hierarchy is infinite, the paper concludes FBPP ≠ FBQP.The paper also states that the search-problem application rules out FBQP ⊆ FBPP^PH under the same conjecture unless P^#P = PH and the polynomial hierarchy collapses.Source: §1.2 · p. 5

1.3 Proof Overview

  • The proof uses Kolmogorov complexity to require search outputs with near-maximal complexity, so a machine solving the search problem can be used to sample.The proof overview contrasts this with a black-box reduction, which could return a fixed valid element; it also invokes a universal randomness test to handle arbitrary distributions.Source: §1.3 · p. 6
  • For arbitrary distributions, the proof overview invokes a universal randomness test that compares the probability of x under D with its probability under the universal prior.The paper describes this as a direct approach building on the connection between Kolmogorov complexity and Shannon information.Source: §1.3 · p. 6

2 Preliminaries

The preliminaries define classical and quantum sampling and search classes, then review Kolmogorov complexity and information-theoretic tools used in the paper.

2.1 Sampling and Search Problems

  • SampP and SampBQP concern approximating input-indexed distributions, while FBPP and FBQP concern finding members of nonempty input-indexed solution sets.Sampling is measured by total variation error; search success is measured by the probability of outputting a valid solution.Source: §2.1 · p. 7

2.2 Algorithmic Information Theory

  • Prefix-free Kolmogorov complexity is defined through the shortest valid program producing a string, with conditional complexity defined given another string.The section also introduces prefix-free sets, in which no member is a prefix of another.Source: §2.2 · p. 7
  • Two lemmas connect Kolmogorov complexity to distributions: one concerns computable distributions, and another is established by a counting argument.The first lemma is tied to Shannon’s noiseless channel coding theorem.Source: §2.2 · pp. 7–8

2.3 Information Theory

  • The information-theory review defines variation distance and KL-divergence, gives a relation between them, and states a KL-divergence proposition for joint distributions and their marginals.The proposition is attributed to Rao.Source: §2.3 · p. 8

3 Main Result

The section constructs a search counterpart for every sampling problem and proves a two-way algorithmic equivalence. It applies this result to show that classical-versus-quantum sampling equality is equivalent to classical-versus-quantum search equality.

3 Main Result

  • The search problem asks for an N-tuple of m-bit strings satisfying a distribution-dependent criterion, with success probability at least 1−δ and runtime polynomial in n and 1/δ.The construction sets N := m/δ^2.1.Source: §3 · p. 9
  • A sampler can be called on independent random inputs to produce a tuple accepted by R_S, yielding a search algorithm.The theorem states that an oracle producing samples close to D_x suffices for R_S to lie in the corresponding search class.Source: §3 · p. 11
  • Conversely, a machine that solves R_S can yield a sample by choosing one tuple coordinate uniformly at random, with the resulting distribution close to D_x.The proof invokes Lemma 19 for the variation-distance bound and handles small m by hardwiring descriptions of D_x.Source: §3 · pp. 11–12
  • Every sampling problem has a constructed search counterpart whose membership is equivalent to sampling membership for below-recursive models with the proof’s closure properties.The equivalence runs in both directions between S ∈ SampP and R_S ∈ FBPP, and likewise between S ∈ SampBQP and R_S ∈ FBQP.Source: §3 · pp. 11–12

3.1 Implication for Quantum Computing

  • SampP = SampBQP if and only if FBPP = FBQP.Thus classical efficient quantum-circuit sampling is equivalent to classical efficient solution of every FBQP search problem.Source: §3.1 · p. 12
  • The quantum-class equivalence relativizes: for every oracle A, SampP^A = SampBQP^A if and only if FBPP^A = FBQP^A.The relativized search counterpart must use Kolmogorov complexity for Turing machines with A-oracles.Source: §3.1 · p. 12

4 Extensions and Open Problems

The extensions examine whether sampling can be related to decision problems, whether Kolmogorov complexity is necessary, and how to reverse or make checkable the sampling-search construction. They establish a qualified search-to-sampling result and a checkable version of the main reduction, while leaving key equivalence questions open.

4.1 Equivalence of Sampling and Decision Problems?

  • The paper leaves open whether a sampling problem can be shown inequivalent to every decision problem under the stated oracle-relative criteria.It also asks whether the oracle in such a criterion can be required to be computable.Source: §4.1 · p. 13
  • Enumeration gives S ∈ SampP iff L_S ∈ P, but avoids reducing S to L_S; unlike Theorem 5, it does not yield one equivalent problem across computational models.The authors note that the theorem's use of large numbers of outputs was essential and that they know no analogous result using a language or promise problem.Source: §4.1 · p. 13

4.2 Was Kolmogorov Complexity Necessary?

  • The paper asks whether the computability assumption in Theorem 5 is necessary, framing the question through oracle-relative separations between sampling and search problems.For the search problem from Theorem 5, the relevant oracle in one direction, if it exists, must be uncomputable.Source: §4.2 · p. 14

4.3 From Search Problems to Sampling Problems

  • Conditioning the universal prior on valid search outputs defines S_R with two-way guarantees, but the reverse direction guarantees only a constant error gap, not arbitrary-ε sampling.An oracle solving S_R yields an FBPP^O solver for R; a probabilistic machine solving R yields sampling within distance 1−η_B for some constant η_B > 0.Source: §4.3 · pp. 14–15

4.4 Making the Search Problem Checkable

  • Replacing Kolmogorov complexity with space-bounded complexity makes membership in A_x decidable, while requiring a complexity bound on the solver for the converse guarantee.Theorem 22 gives oracle transfer from S to R_S, recovers S from a BPTIME(f(n)) solver for R_S, and provides a SPACE-bounded membership algorithm.Source: §4.4 · p. 15
Loading 1009.5104v1…