PaperlayerView exact revision on arXiv

Source-linked AI summary

Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function

Ben W. Reichardt

arXiv:0904.2759v1quant-phcs.CC

TL;DR

The paper asks whether the general adversary SDP lower bound can be converted into a nearly matching quantum query upper bound for every boolean function. It constructs optimal span programs through an SDP and gives a quantum algorithm for evaluating them with logarithmic overhead, making the bound nearly tight and extending span programs beyond formula evaluation.

  • Problem

    The paper investigates whether span-program witness size equals the general adversary bound and whether span programs can yield quantum algorithms beyond formula evaluation.

  • Method

    The paper uses an SDP to construct a span program with optimal witness size, then evaluates span programs with a quantum algorithm based on a spectral-gap analysis.

  • Results

    For every boolean function, the optimal span-program witness size equals Adv±, and span-program evaluation requires only logarithmic query overhead, making Adv± tight up to that factor.

  • Takeaways & Limitations

    Span programs become a nearly universal model for quantum query algorithms and support optimal quantum evaluation of formulas over any finite boolean gate set.

  • Takeaways & Limitations

    The paper addresses query complexity rather than time complexity, leaving tradeoffs between query-optimal and nearly time-optimal span programs beyond its scope.

Abstract

from arXiv · show

The general adversary bound is a semi-definite program (SDP) that lower-bounds the quantum query complexity of a function. We turn this lower bound into an upper bound, by giving a quantum walk algorithm based on the dual SDP that has query complexity at most the general adversary bound, up to a logarithmic factor. In more detail, the proof has two steps, each based on "span programs," a certain linear-algebraic model of computation. First, we give an SDP that outputs for any boolean function a span program computing it that has optimal "witness size." The optimal witness size is shown to coincide with the general adversary lower bound. Second, we give a quantum algorithm for evaluating span programs with only a logarithmic query overhead on the witness size. The first result is motivated by a quantum algorithm for evaluating composed span programs. The algorithm is known to be optimal for evaluating a large class of formulas. The allowed gates include all constant-size functions for which there is an optimal span program. So far, good span programs have been found in an ad hoc manner, and the SDP automates this procedure. Surprisingly, the SDP's value equals the general adversary bound. A corollary is an optimal quantum algorithm for evaluating "balanced" formulas over any finite boolean gate set. The second result extends span programs' applicability beyond the formula evaluation problem. A strong universality result for span programs follows. A good quantum query algorithm for a problem implies a good span program, and vice versa. Although nearly tight, this equivalence is nontrivial. Span programs are a promising model for developing more quantum algorithms.

1 Introduction

The paper resolves longstanding questions about span programs by matching optimal witness size to the general adversary bound and showing that span programs can be evaluated quantumly with logarithmic overhead. Together, these results make the general adversary bound nearly tight for every boolean function and extend optimal formula evaluation to any finite gate set.

  • Motivation: The paper addresses whether formula-evaluation gate sets can be extended, whether witness size matches adversary bounds, and whether span programs yield algorithms beyond formulas.These questions arise because optimal span programs had previously been found mainly through ad hoc methods.
  • First result: For every boolean function f, an optimal span program has witness size equal to the general adversary bound Adv±(f).An SDP characterizes this optimal witness size, and its infimum is achieved.
  • Span-program evaluation: A quantum algorithm evaluates arbitrary span programs with only a logarithmic query overhead on witness size.The analysis uses an effective spectral gap around zero derived from properties of eigenvalue-zero eigenvectors.
  • Overall consequence: Combining the two results makes Adv± tight up to a logarithmic factor for every boolean function and establishes near-equivalence between quantum query algorithms and span programs.The paper also presents a new formulation of the adversary SDP as an SDP for quantum query complexity up to logarithmic overhead.
  • Formula evaluation: The result extends optimal quantum formula evaluation from previously known gate families to formulas over any finite boolean gate set.The factor lost depends on the gates and is constant for a finite gate set.

2 Definitions

The section defines span programs, witness size, and adversary bounds, then states their key relationships to quantum query complexity and composition.

  • Span programs: A span program specifies a Boolean function using a target vector and input vectors grouped by variables and bit labels.The function evaluates to 1 when the target lies in the span of the available input vectors.
  • Witness size: Witness size measures the minimum cost-weighted squared length of these witnesses, with nonuniform costs supporting unbalanced formulas.Uniform costs give the standard witness size, while free input vectors are excluded from the query-cost contribution.
  • Witnesses: For an input evaluating to 1, a witness represents coefficients that combine available input vectors to reach the target.For an input evaluating to 0, a witness is a vector separating the target from the available-input span.
  • Adversary bounds: The general adversary bound is a lower bound on bounded-error quantum query complexity and composes multiplicatively under matching input costs.The section contrasts it with the nonnegative adversary bound, which has certificate and property-testing limitations.
  • Span programs and adversary bounds: Every span program has witness size at least the general adversary bound, while the paper later establishes equality for optimal span programs.This connects span-program complexity to the stronger adversary formulation Adv±.

3 Example: Span programs based on one-sided-error quantum query algorithms

This section constructs span programs from one-sided-error quantum query algorithms by encoding their time evolution, yielding witness size proportional to query complexity.

  • Construction: A q-query quantum algorithm with bounded one-sided error on false inputs induces a span program computing the same function.The construction alternates input-independent unitaries with phase-flip oracle queries and embeds the resulting evolution into the span program.
  • Construction: The construction uses a time-indexed space, a target connecting the initial and final states, free vectors at odd steps, and input-labeled vectors at even steps.Available vectors depend on the input bits through the phase-flip oracle.
  • Witness analysis: On true inputs, the constructed span program has a positive witness with size at most q.The witness follows the algorithm’s state trajectory and uses a telescoping relation across time steps.
  • Witness analysis: On false inputs, the constructed span program has a negative witness with size at most 4q/(1 − ϵ)^2.Here ϵ is the algorithm’s bounded error on false inputs.
  • Consequence: After rescaling the target, the construction gives wsize(P) ≤ 2q/(1 − ϵ), and therefore infP:fP=f wsize(P) = O(Q1(f)).The result relates span-program witness size to one-sided-error quantum query complexity.

4 Span program manipulations

This section develops complementation, composition, and simplification techniques for span programs. Dualization preserves negation and witness size, while composition preserves computability with controlled witness-size growth.

  • Complementation: Span programs can be complemented freely, which supports composing programs for non-monotone functions.
  • Complementation: Dualization produces a span program for ¬fP with exactly the same witness size on every input.The construction follows an earlier dual-span-program approach chosen because it preserves witness size.
  • Composition: For composed functions g(x)=f(f1(x),…,fn(x)), tensor-product and direct-sum constructions each yield a span program computing g.The constructions use the outer program’s input structure together with inner programs selected by the corresponding input values.
  • Composition: The composed witness size is at most the outer witness size multiplied by the largest inner witness size.In particular, wsizes(Q) ≤ wsize(P) maxj∈[n] wsizes(Pj).
  • Composition: Tensor-product, direct-sum, and reduced-tensor-product compositions offer different tradeoffs for designing efficient formula-evaluation algorithms.The reduced-tensor-product construction is suggested as potentially useful for faster AND-OR formula evaluation.
  • Composition: When input span programs are optimal and the component functions depend on disjoint input sets, the composed span program is optimal.

5 Canonical span programs

Canonical span programs restrict the search space without worsening witness size. Every span program can be converted to an equivalent canonical form, with equality on zero-valued inputs and preservation of monotonicity and reality.

  • Canonical form: For any cost vector, a span program can be converted into a canonical program computing the same function without increasing witness size.
  • Structure: Real span programs can likewise be obtained without increasing witness size, completing the reduction to real canonical programs.
  • Canonical form: Canonical span programs use the zero-input set as their inner-product space, with basis vectors indexed by inputs where the function equals zero.Their target vector is the sum of those basis vectors.
  • Witness size: On inputs where the function is zero, the canonical basis vector itself is an optimal witness and witness size is preserved exactly.
  • Structure: The conversion preserves the input-vector index sets, so monotonicity and real-valued structure are retained.
  • Caveat: Canonicalization depends on the chosen cost vector, unlike strict span-program simplification, which preserves witness size for all cost vectors.

6 Span program witness size and the general adversary bound

The paper formulates optimal span-program witness size as an SDP and shows that its optimum equals the general adversary bound. This establishes an exact correspondence between the two measures for arbitrary finite-domain functions with boolean output.

  • Main equivalence: An SDP computes the optimal witness size of a span program, and its value is exactly the general adversary bound Adv±(f).The infimum over span programs agreeing with f is achieved.
  • Context: The SDP correspondence is surprising because earlier optimal span programs were known mainly for functions satisfying Adv(f)=Adv±(f).
  • Scope: The result applies to functions on any D⊆B^n with boolean output and arbitrary nonnegative cost vectors.
  • Dual characterization: The SDP’s dual can be expressed using adversary matrices supported only on pairs of inputs with different function values.For boolean inputs or boolean outputs, the matrix constraints reduce to operator-norm bounds on coordinate-restricted adversary matrices.
  • Proof strategy: The optimal-witness SDP is connected to the adversary formulation through a Cholesky decomposition of the SDP solution.
  • Representation: An optimal span program can be chosen with bounded index-set size determined by the rank of an optimal adversary SDP solution.If the optimal solution has rank k, the construction uses |Ij,b|=k for every j and b.

7 Consequences of the SDP for optimal witness size

The SDP characterization yields compositional and algorithmic consequences: adversary bounds compose multiplicatively, balanced formulas over finite gate sets admit efficient quantum evaluation, and repeated self-composition has asymptotic query rate Adv±(f).

  • Algorithmic consequences: Every boolean function has a span program whose witness size is bounded above by its bounded-error quantum query complexity.
  • Open issue: The paper notes that deriving the span-program upper bound directly from a quantum query algorithm remains an interesting open problem.
  • Composition: The general adversary bound composes multiplicatively for boolean functions, so the composition inequality is an equality.
  • Iterated composition: For a function composed with itself to depth k, the asymptotic kth-root quantum query complexity equals Adv±(f).The lower bound follows from adversary composition, while the upper bound uses optimal span programs and formula evaluation.
  • Sign-degree: The result gives an upper bound on the sign-degree of iterated self-compositions and consequently on the sign-degree of the original function.
  • Formula evaluation: Adversary-balanced formulas over any finite boolean gate set can be evaluated using O(Adv±(ϕ)) input queries.After preprocessing, the running time is Adv±(ϕ)(log Adv±(ϕ))^O(1) with coherent access to the preprocessed string.

8 Correspondence between span programs and bipartite graphs

The section translates span programs into weighted bipartite graphs and relates graph spectra near zero to witness size, enabling quantum evaluation. Its main theorem establishes the spectral properties needed for this connection while identifying limitations for query- and time-efficient applications.

  • Graph correspondence: Span programs are represented by weighted bipartite graphs whose spectral quantities are linked to span-program witness size.The correspondence generalizes earlier constructions and centers on eigenvalues near zero and eigenvectors supported on the output vertex.
  • Main spectral theorem: The analysis combines eigenvalue-zero structure with an effective spectral-gap argument to support quantum phase estimation.The second step is novel and relates zero-eigenvalue eigenvectors of weighted bipartite graphs to effective spectral gaps.
  • Extension beyond prior work: The small-eigenvalue analysis extends earlier results beyond constant-size, strictly balanced span programs to general span programs.For general span programs, spectral gaps cannot be lower-bounded solely by witness size, whereas the new analysis yields a simpler and broader proof framework.
  • Main spectral theorem: Theorem 8.3 constructs an equivalent span program whose graph has eigenvalue-zero and small-eigenvalue properties controlled by witness size.For positive inputs, the graph has an eigenvalue-zero eigenvector; for negative inputs, the output vertex has limited support on sufficiently small eigenvalues.
  • Limitations: Applying Theorem 8.3 as a black box can introduce an O(log n) query overhead because the constructed adjacency matrix need not have constant norm.The theorem is therefore unsuitable for preserving logarithmic factors in some query applications and does not directly optimize time complexity.
  • Limitations: Time-efficient algorithms depend on adjacency-matrix properties beyond norm, including maximum vertex degree, which this article does not optimize.The paper identifies query-optimal versus nearly time-optimal span-program design as an open research direction.

9 Quantum algorithm for evaluating span programs

The paper evaluates span programs by converting their graph representations into quantum-walk or phase-estimation procedures. One algorithm achieves norm-dependent query complexity, while the general procedure tolerates unknown norms at a logarithmic overhead.

  • Spectral evaluation framework: Theorem 9.1 evaluates functions from graph spectral conditions: positive inputs have an output-vertex-overlapping zero eigenvector, while negative inputs have limited small-eigenvalue support.The algorithm starts at the output vertex and tests whether the measured phase is zero.
  • Query bounds: Without a useful norm bound, phase estimation gives a query complexity of ˜O(1/Λ), incurring a logarithmic overhead.The method applies phase estimation to eiAG(x), with logarithmic tolerance for the adjacency-matrix norm.
  • Application to span programs: Theorem 9.2 converts span-program witness size into a bounded-error quantum query algorithm with logarithmic overhead.The construction applies the spectral theorems to the graph associated with a span program.
  • Query bounds: When the absolute adjacency-matrix norm is controlled, the query complexity is O(∥abs(AG)∥/Λ).This bound follows from the specialized quantum-walk algorithm.
  • Spectral evaluation framework: Szegedy’s correspondence relates the spectrum of the input-dependent adjacency matrix to a discrete-time coined quantum walk unitary.This spectral-to-walk connection is the key technical ingredient behind the query algorithm.
  • Correctness: The two algorithms obtain constant completeness-soundness gaps that can be amplified to bounded error.For the general procedure, the final gap remains constant after simulation error is accounted for.

10 The general quantum adversary bound is nearly tight for every boolean function

The paper proves that the general adversary bound characterizes bounded-error quantum query complexity up to a logarithmic factor for Boolean functions. The upper bound follows by constructing an optimal-witness-size span program and then evaluating it quantumly.

  • Main theorem: For every partial Boolean function, the bounded-error quantum query complexity is characterized by the general adversary bound up to a logarithmic factor.The lower bound comes from the adversary method, while the upper bound uses span-program construction and evaluation.
  • Proof strategy: The SDP constructs a span program computing f with witness size equal to Adv±(f), after which Theorem 9.2 supplies the quantum algorithm.This connects the dual SDP optimization directly to the quantum query upper bound.
  • Larger codomains: The adversary-bound result extends to larger output alphabets through binary search and standard error reduction.The reduction repeatedly evaluates binary range divisions and uses composition properties of the adversary bound.
  • Scope: The theorem is stated for binary input alphabets; encoding non-binary inputs may increase Adv±.The paper does not provide a direct result for non-binary input alphabets.

11 Open problems

The paper identifies extensions of its framework beyond the main boolean query-complexity results, while leaving several algorithmic and generalization questions open.

  • The general adversary bound is tight for bounded-error quantum query complexity up to a logarithmic factor.
  • Quantum algorithms and span programs are equivalent computational models for boolean functions up to a logarithmic factor.
  • Adversary-balanced formulas over any finite boolean gate set admit optimal quantum algorithms, including gate sets containing all functions on at most 1000 input bits.
  • The span-program framework does not apply to the nonnegative-weight adversary bound, even when that bound is close to the general adversary bound.
  • Efficient time complexity remains unresolved because further techniques are needed to construct span programs and implement the associated quantum-walk reflections efficiently.
  • The authors leave open extensions to non-binary input alphabets, non-boolean codomains, removal of the logarithmic overhead, and classical-query relationships.

A Optimal span programs for the Hamming-weight threshold functions

The appendix gives explicit span-program constructions for Hamming-weight threshold and interval functions, using symmetry, recursive composition, and adversary-bound comparisons.

  • Optimal span programs are constructed for Hamming-weight threshold functions and for interval functions whose nonnegative-weight and general adversary bounds coincide.
  • Recursive composition of symmetrized span programs is presented as a technique that may support further constructions.
  • The constructions are derived from AND and OR span programs composed symmetrically with optimized weights.
  • The appendix compares witness sizes with adversary bounds by constructing adversary matrices and matching dual solutions.
  • Threshold and interval functions are defined through Hamming weight and conjunctions of threshold conditions on x and its complement.

A.1 Span programs for the threshold functions T n

The threshold-function construction uses recursive span programs whose witness sizes depend on Hamming weight, with separate analyses for true and false inputs and explicit size limitations.

  • Threshold span programs are built recursively by adding tensor-product blocks to lower-threshold constructions.
  • The construction analyzes true inputs with weight at least the threshold and false inputs with weight below it using separate witnesses.
  • For the three-majority function, the recursive construction has size 9 and is not size-optimal despite having optimal witness size.
  • Interval-function constructions combine complementary threshold span programs and analyze the resulting witness size by cases over the input Hamming weight.
  • For symmetric threshold functions, witness size depends only on the input Hamming weight.

B Examples of composed span programs

The appendix illustrates direct-sum, tensor-product, and reduced-tensor-product composition for AND-OR formulas, emphasizing their different graph structures and weight behavior.

  • Three composition methods are illustrated: direct-sum, tensor-product, and reduced-tensor-product composition.
  • Fan-in-two AND and OR span programs are composed according to the formula to obtain a span program computing the full AND-OR formula.
  • Reduced-tensor-product composition changes graph structure locally as gates are added but changes edge weights nonlocally.
  • Direct-sum composition yields a graph closely related to the formula tree, with edge weights determined by ratios of subformula sizes.
Loading 0904.2759v1…