boofun.analysis.query_complexity

Query complexity measures for Boolean functions.

This module implements various query complexity measures as described in Scott Aaronson’s Boolean Function Wizard and related literature.

Query complexity measures how many queries to the input bits are needed to compute a Boolean function under different computational models:

D(f): Deterministic query complexity (worst-case)
R0(f): Zero-error randomized query complexity
R2(f): Two-sided-error (bounded-error) randomized query complexity
Q(f): Bounded-error quantum query complexity

Also includes related measures: - Ambainis complexity (quantum lower bound) - Various degree measures (approximate, nondeterministic)

References: - Aaronson, “Algorithms for Boolean Function Query Measures” (2000) - Buhrman & de Wolf, “Complexity Measures and Decision Tree Complexity” (2002) - O’Donnell, “Analysis of Boolean Functions” (2014)

Functions

`ambainis_complexity`(f)	Compute the Ambainis adversary bound, a lower bound for Q2(f).
`approximate_degree`(f[, epsilon])	Estimate the approximate degree deg_epsilon(f).
`average_deterministic_complexity`(f)	Compute D_avg(f), the average-case deterministic query complexity.
`average_everywhere_sensitivity`(f[, value])	Compute esu(f), the average everywhere sensitivity.
`block_sensitivity_lower_bound`(f)	Compute lower bound on D(f) from block sensitivity.
`bounded_error_randomized_complexity`(f[, error])	Compute R2(f), the bounded-error randomized query complexity.
`certificate_lower_bound`(f)	Compute lower bound on D(f) from certificate complexity.
`deterministic_query_complexity`(f)	Compute D(f), the deterministic query complexity (worst-case).
`everywhere_sensitivity`(f)	Compute es(f), the everywhere sensitivity.
`exact_quantum_complexity`(f)	Estimate QE(f), the exact quantum query complexity.
`general_adversary_bound`(f)	Estimate the general (negative-weight) adversary bound for Q2(f).
`nondeterministic_complexity`(f[, side])	Compute NR(f), the nondeterministic query complexity.
`nondeterministic_degree`(f[, side])	Estimate ndeg(f), the nondeterministic degree.
`one_sided_approximate_degree`(f[, side, epsilon])	Estimate deg1(f), the one-sided approximate degree.
`one_sided_randomized_complexity`(f[, side])	Compute R1(f), the one-sided-error randomized query complexity.
`polynomial_method_bound`(f)	Compute lower bound on Q2(f) via the polynomial method.
`quantum_query_complexity`(f)	Estimate Q2(f), the bounded-error quantum query complexity.
`sensitivity_lower_bound`(f)	Compute lower bound on D(f) from sensitivity.
`spectral_adversary_bound`(f)	Compute the spectral adversary bound for Q2(f).
`strong_nondeterministic_degree`(f)	Estimate degs(f), the strong nondeterministic degree.
`threshold_degree`(f)	Compute the threshold degree of f (degree as a sign-polynomial).
`weak_nondeterministic_degree`(f)	Estimate degw(f), the weak nondeterministic degree.
`zero_error_randomized_complexity`(f)	Compute R0(f), the zero-error randomized query complexity.

Classes

QueryComplexityProfile(f)

Compute and store query complexity measures for a Boolean function.

boofun.analysis.query_complexity.deterministic_query_complexity(f: BooleanFunction) → int[source]

Compute D(f), the deterministic query complexity (worst-case).

This is the minimum depth of a decision tree that computes f. Same as decision_tree_depth() from complexity.py.

Parameters:: f – BooleanFunction to analyze
Returns:: Worst-case number of queries needed

boofun.analysis.query_complexity.average_deterministic_complexity(f: BooleanFunction) → float[source]

Compute D_avg(f), the average-case deterministic query complexity.

This is the expected number of queries under the uniform distribution on inputs, using an optimal decision tree.

Parameters:: f – BooleanFunction to analyze
Returns:: Average number of queries needed

boofun.analysis.query_complexity.zero_error_randomized_complexity(f: BooleanFunction) → float[source]

Compute R0(f), the zero-error randomized query complexity.

This is the expected number of queries needed by the best randomized algorithm that always outputs the correct answer (Las Vegas).

Satisfies: R0(f) >= sqrt(D(f)) and R0(f) <= D(f)

Parameters:: f – BooleanFunction to analyze
Returns:: Expected number of queries for zero-error randomized computation

Note

This is an approximation; the exact computation requires solving a linear program over all possible randomized protocols.

boofun.analysis.query_complexity.bounded_error_randomized_complexity(f: BooleanFunction, error: float = 0.3333333333333333) → float[source]

Compute R2(f), the bounded-error randomized query complexity.

This is the minimum expected queries for a randomized algorithm that outputs the correct answer with probability >= 1 - error.

Satisfies: R2(f) = Omega(sqrt(bs(f))) and R2(f) = O(D(f))

Parameters:

f – BooleanFunction to analyze
error – Maximum error probability (default 1/3)

Returns:

Expected queries for bounded-error randomized computation

Note

This is an approximation based on known lower bounds.

boofun.analysis.query_complexity.one_sided_randomized_complexity(f: BooleanFunction, side: int = 1) → float[source]

Compute R1(f), the one-sided-error randomized query complexity.

A one-sided algorithm never errs on inputs with f(x) = side.

Satisfies: R2(f) <= R1(f) <= R0(f) <= D(f)

Parameters:

f – BooleanFunction to analyze
side – Which side has no error (0 or 1, default 1)

Returns:

Estimated one-sided randomized complexity

boofun.analysis.query_complexity.nondeterministic_complexity(f: BooleanFunction, side: int = 1) → float[source]

Compute NR(f), the nondeterministic query complexity.

This is the minimum certificate complexity over inputs where f(x) = side. Nondeterministic algorithms “guess” the certificate and verify it.

Satisfies: NR(f) <= R1(f)

Parameters:

f – BooleanFunction to analyze
side – Which value to compute NR for (0 or 1, default 1)

Returns:

Nondeterministic query complexity

boofun.analysis.query_complexity.quantum_query_complexity(f: BooleanFunction) → float[source]

Estimate Q2(f), the bounded-error quantum query complexity.

Uses multiple lower bounds: - Ambainis adversary bound - Spectral adversary bound - sqrt(bs(f)) (Grover lower bound)

Q2(f) = Theta(sqrt(D(f))) for many functions by Grover-type algorithms.

Parameters:: f – BooleanFunction to analyze
Returns:: Estimated bounded-error quantum query complexity

boofun.analysis.query_complexity.exact_quantum_complexity(f: BooleanFunction) → float[source]

Estimate QE(f), the exact quantum query complexity.

QE(f) is the minimum queries for a quantum algorithm that always outputs the correct answer (no error allowed).

Satisfies: Q2(f) <= QE(f) <= D(f)

Parameters:: f – BooleanFunction to analyze
Returns:: Estimated exact quantum query complexity

boofun.analysis.query_complexity.everywhere_sensitivity(f: BooleanFunction) → int[source]

Compute es(f), the everywhere sensitivity.

The everywhere sensitivity is the minimum sensitivity over all inputs:: es(f) = min_x s(f, x)

This measures the “easiest” input to compute in terms of sensitivity.

Parameters:: f – BooleanFunction to analyze
Returns:: Minimum sensitivity across all inputs

boofun.analysis.query_complexity.average_everywhere_sensitivity(f: BooleanFunction, value: int | None = None) → float[source]

Compute esu(f), the average everywhere sensitivity.

This is the average of min sensitivity values, optionally restricted to inputs where f(x) = value.

Parameters:

f – BooleanFunction to analyze
value – If specified (0 or 1), only consider inputs where f(x) = value

Returns:

Average of minimum sensitivities

boofun.analysis.query_complexity.ambainis_complexity(f: BooleanFunction) → float[source]

Compute the Ambainis adversary bound, a lower bound for Q2(f).

The Ambainis bound is defined as:

Adv(f) = max_R sqrt(max_x |{y: R(x,y)=1}| * max_y |{x: R(x,y)=1}|): / max_{x,y:R(x,y)=1} |{i: x_i != y_i}|

where R is any binary relation with R(x,y) = 1 only when f(x) != f(y).

Parameters:: f – BooleanFunction to analyze
Returns:: Ambainis adversary lower bound for quantum query complexity

Note

Computing the optimal R is NP-hard in general. This uses a heuristic.

boofun.analysis.query_complexity.spectral_adversary_bound(f: BooleanFunction) → float[source]

Compute the spectral adversary bound for Q2(f).

This is the “positive weights” adversary method, which is sometimes tighter than the basic Ambainis bound.

The spectral bound equals sqrt(λ) where λ is the largest eigenvalue of a certain matrix derived from the function structure.

Parameters:: f – BooleanFunction to analyze
Returns:: Spectral adversary lower bound

boofun.analysis.query_complexity.polynomial_method_bound(f: BooleanFunction) → float[source]

Compute lower bound on Q2(f) via the polynomial method.

The polynomial method shows that quantum algorithms induce low-degree polynomials. Any quantum algorithm making T queries induces polynomials of degree at most 2T representing acceptance probabilities.

Therefore: Q2(f) >= deg~(f)/2, where deg~(f) is the approximate degree.

For symmetric functions, this is often tight.

Parameters:: f – BooleanFunction to analyze
Returns:: Polynomial method lower bound for quantum query complexity

References

Beals et al., “Quantum lower bounds by polynomials” (2001)
Belovs, “A Direct Reduction from Polynomial to Adversary Method” (TQC 2024)

boofun.analysis.query_complexity.general_adversary_bound(f: BooleanFunction) → float[source]

Estimate the general (negative-weight) adversary bound for Q2(f).

The general adversary method with negative weights characterizes bounded-error quantum query complexity for total Boolean functions:

Q2(f) = Θ(ADV±(f))

This is the strongest known quantum lower bound technique.

Parameters:: f – BooleanFunction to analyze
Returns:: Estimated general adversary bound (approximation)

Note

Computing the exact ADV±(f) requires solving a semidefinite program. This implementation provides a heuristic approximation combining multiple lower bound techniques.

References

Reichardt, “Reflections for quantum query algorithms” (2011)
Belovs (TQC 2024): dual polynomials → adversary bounds

boofun.analysis.query_complexity.certificate_lower_bound(f: BooleanFunction) → int[source]

Compute lower bound on D(f) from certificate complexity.

D(f) >= max(C0(f), C1(f))

Parameters:: f – BooleanFunction to analyze
Returns:: Certificate-based lower bound

boofun.analysis.query_complexity.sensitivity_lower_bound(f: BooleanFunction) → int[source]

Compute lower bound on D(f) from sensitivity.

By Huang’s theorem (2019): D(f) >= s(f)

Parameters:: f – BooleanFunction to analyze
Returns:: Sensitivity-based lower bound

boofun.analysis.query_complexity.block_sensitivity_lower_bound(f: BooleanFunction) → int[source]

Compute lower bound on D(f) from block sensitivity.

D(f) >= bs(f)

Also: bs(f) <= D(f) <= bs(f)^2 (the latter is Nisan’s theorem)

Parameters:: f – BooleanFunction to analyze
Returns:: Block sensitivity-based lower bound

boofun.analysis.query_complexity.approximate_degree(f: BooleanFunction, epsilon: float = 0.3333333333333333) → float[source]

Estimate the approximate degree deg_epsilon(f).

The approximate degree is the minimum degree of a polynomial p such that |p(x) - f(x)| <= epsilon for all x in {0,1}^n.

This is a lower bound for R2(f): R2(f) >= deg_1/3(f)

Parameters:

f – BooleanFunction to analyze
epsilon – Approximation parameter

Returns:

Estimated approximate degree

Note

Exact computation requires linear programming. This uses bounds.

boofun.analysis.query_complexity.one_sided_approximate_degree(f: BooleanFunction, side: int = 1, epsilon: float = 0.3333333333333333) → float[source]

Estimate deg1(f), the one-sided approximate degree.

This is the minimum degree of a polynomial p such that: - p(x) >= 1 - epsilon when f(x) = side - p(x) <= epsilon when f(x) != side

Satisfies: deg1(f) >= deg2(f) (two-sided approximate degree)

Parameters:

f – BooleanFunction to analyze
side – Which side to approximate (0 or 1, default 1)
epsilon – Approximation parameter

Returns:

Estimated one-sided approximate degree

boofun.analysis.query_complexity.nondeterministic_degree(f: BooleanFunction, side: int = 1) → float[source]

Estimate ndeg(f), the nondeterministic degree.

This is the minimum degree of a polynomial p such that: - p(x) >= 1 when f(x) = side - p(x) = 0 when f(x) != side

This equals the minimum size of an AND of ORs (DNF width for side=1).

Satisfies: ndeg(f) <= deg1(f)

Parameters:

f – BooleanFunction to analyze
side – Which side to exactly represent (0 or 1, default 1)

Returns:

Estimated nondeterministic degree

boofun.analysis.query_complexity.strong_nondeterministic_degree(f: BooleanFunction) → float[source]

Estimate degs(f), the strong nondeterministic degree.

This is the minimum degree needed for polynomials that: - Are nonnegative on all inputs - Are > 0 exactly when f(x) = 1

Parameters:: f – BooleanFunction to analyze
Returns:: Estimated strong nondeterministic degree

boofun.analysis.query_complexity.weak_nondeterministic_degree(f: BooleanFunction) → float[source]

Estimate degw(f), the weak nondeterministic degree.

This is min(ndeg0(f), ndeg1(f)).

Parameters:: f – BooleanFunction to analyze
Returns:: Estimated weak nondeterministic degree

boofun.analysis.query_complexity.threshold_degree(f: BooleanFunction) → int[source]

Compute the threshold degree of f (degree as a sign-polynomial).

The threshold degree is the minimum degree d such that there exists a polynomial p of degree d with sign(p(x)) = f(x) for all x.

Parameters:: f – BooleanFunction to analyze
Returns:: Threshold degree

Note

This equals the real degree for most Boolean functions.

class boofun.analysis.query_complexity.QueryComplexityProfile(f: BooleanFunction)[source]

Compute and store query complexity measures for a Boolean function.

This class provides a comprehensive analysis similar to Aaronson’s Boolean Function Wizard.

__init__(f: BooleanFunction)[source]

Initialize query complexity profile.

Parameters:: f – BooleanFunction to analyze

compute() → Dict[str, float][source]

Compute all query complexity measures.

Returns:: Dictionary of complexity measures

summary() → str[source]: Return a human-readable summary in BFW style.

check_known_relations() → Dict[str, bool][source]

Verify known relationships between complexity measures.

Returns:: Dictionary of relationship checks