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)

Guarantees

Every public function in this module is classified as one of:

• exact: the returned value is the measure itself.

• certified lower bound: the exact value of an explicit feasible witness; the true quantity is >= the returned value.

• estimate: a heuristic point value, clamped into a provably valid interval where one is stated.

Adversary values are lower bounds on the (general) adversary bound ADV+-(f), which characterizes Q2(f) up to constant factors (Q2(f) = Theta(ADV+-(f))). Because those constants are below 1, an adversary value may numerically exceed Q2(f) (e.g. ADV(PARITY_n) = n while Q2 = ceil(n/2)); adversary values must not be compared directly against D(f) or Q2 estimates. For exact ADV+- values computed by SDP, see the pinned quantum-query-optimizer fixtures under tests/cross_validation/.

Functions

ambainis_complexity(f)	Compute a certified Ambainis adversary lower bound on ADV(f).
approximate_degree(f[, epsilon])	Compute deg_epsilon(f), the approximate degree (exact, via LP).
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)	Compute a certified lower bound on the general adversary bound ADV+-(f).
nondeterministic_complexity(f[, side])	Compute NR(f), the nondeterministic query complexity.
nondeterministic_degree(f[, side])	Compute ndeg(f), the nondeterministic degree (exact).
one_sided_approximate_degree(f[, side, epsilon])	Compute deg1(f), the one-sided approximate degree (exact, via LP).
one_sided_randomized_complexity(f[, side])	Compute R1(f), the one-sided-error randomized query complexity.
polynomial_method_bound(f)	Compute a 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 a certified spectral adversary lower bound on ADV(f).
strong_nondeterministic_degree(f)	Estimate degs(f), the strong nondeterministic degree.
threshold_degree(f)	Compute the threshold degree of f (exact, via LP).
weak_nondeterministic_degree(f)	Compute 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.

class boofun.analysis.query_complexity.QueryComplexityProfile(f: BooleanFunction)

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) → None

Initialize query complexity profile.

Parameters:

f – BooleanFunction to analyze

compute() → dict[str, float]

Compute all query complexity measures.

Returns:

Dictionary of complexity measures

summary() → str

Return a human-readable summary in BFW style.

check_known_relations() → dict[str, bool]

Verify known relationships between complexity measures.

Returns:

Dictionary of relationship checks

boofun.analysis.query_complexity.ambainis_complexity(f: BooleanFunction) → float

Compute a certified Ambainis adversary lower bound on ADV(f).

Ambainis’s theorem: choose X subset f^-1(0), Y subset f^-1(1) and a relation R subset X x Y such that every x in X is related to at least m elements of Y and every y in Y to at least m’ elements of X. With l = max_{x,i} |{y : (x,y) in R, x_i != y_i}| and l’ defined dually,

ADV(f) >= sqrt(m * m’ / (l * l’))

This implementation evaluates that bound exactly for the canonical sensitive-edge relation: R = pairs at Hamming distance 1 with different f-values, with X and Y restricted to inputs that have at least one sensitive neighbor. For that relation l = l’ = 1, so the bound is sqrt(m * m’) with m, m’ the minimum sensitive-edge counts on each side. Examples: AND_n gives sqrt(n); PARITY_n gives n.

Status: certified lower bound on ADV(f) (and hence on ADV+-(f)) via an explicit feasible relation; not the optimum over all relations, which is hard in general. Deterministic (the previous implementation sampled pairs with an unseeded RNG). Since Q2(f) = Theta(ADV+-(f)) with constants below 1, this value is NOT claimed to be numerically <= Q2(f); see the module docstring.

Parameters:

f – BooleanFunction to analyze

Returns:

Exact value of the sensitive-edge Ambainis bound

References

• Ambainis, “Quantum lower bounds by quantum arguments” (2002)

boofun.analysis.query_complexity.approximate_degree(f: BooleanFunction, epsilon: float = 0.3333333333333333) → int

Compute deg_epsilon(f), the approximate degree (exact, via LP).

The approximate degree is the minimum degree of a real polynomial p such that |p(x) - f(x)| <= epsilon for all x in {0,1}^n, with f valued in {0, 1}. Computed exactly by solving one Chebyshev-style linear program per candidate degree (scipy linprog/HiGHS).

Status: exact (for n <= 12; raises ValueError above).

Parameters:

• f – BooleanFunction to analyze

• epsilon – Approximation parameter, in [0, 1/2) (default 1/3; epsilon = 0 gives the exact real degree)

Returns:

The exact approximate degree (an integer)

Raises:

ValueError – if epsilon is outside [0, 1/2) or n exceeds the LP size cap.

boofun.analysis.query_complexity.average_deterministic_complexity(f: BooleanFunction) → float

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.

In any decision tree the variables queried on input x’s path form a certificate for x, so cert(x) <= depth(x) pointwise and the average certificate complexity is a true lower bound on the average depth of every (in particular the optimal) decision tree.

Status: certified lower bound on the average-case deterministic query complexity (returns the average certificate complexity).

Parameters:

f – BooleanFunction to analyze

Returns:

Average certificate complexity (lower bound on average queries)

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

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.block_sensitivity_lower_bound(f: BooleanFunction) → int

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.bounded_error_randomized_complexity(f: BooleanFunction, error: float = 0.3333333333333333) → float

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.

Status: estimate. The point value sqrt(s * bs) is clamped into the certified interval [bs/3, D]: R2(f) >= bs(f)/3 (Nisan 1991) and R2(f) <= D(f) trivially.

Parameters:

• f – BooleanFunction to analyze

• error – Maximum error probability (default 1/3)

Returns:

Estimated expected queries for bounded-error randomized computation

boofun.analysis.query_complexity.certificate_lower_bound(f: BooleanFunction) → int

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.deterministic_query_complexity(f: BooleanFunction) → int

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.everywhere_sensitivity(f: BooleanFunction) → int

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.exact_quantum_complexity(f: BooleanFunction) → float

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)

Status: estimate. The point value is clamped into the certified interval [deg(f)/2, D]: the exact polynomial method gives QE >= deg(f)/2 with deg the real (Fourier) degree (Beals et al. 2001; a previous implementation incorrectly used the GF(2) degree), and QE <= D trivially.

Parameters:

f – BooleanFunction to analyze

Returns:

Estimated exact quantum query complexity

boofun.analysis.query_complexity.general_adversary_bound(f: BooleanFunction) → float

Compute a certified lower bound on the general adversary bound ADV+-(f).

The general (negative-weight) adversary bound characterizes bounded-error quantum query complexity for total Boolean functions: Q2(f) = Theta(ADV+-(f)) (Hoyer-Lee-Spalek 2007; Reichardt 2011). Computing ADV+-(f) exactly requires a semidefinite program, which this library deliberately does not ship; for exact values see the pinned quantum-query-optimizer fixtures in tests/cross_validation/.

This function returns the best certified positive-weight witness we evaluate exactly: max(spectral_adversary_bound, ambainis_complexity). Both are feasible-solution values for ADV(f) <= ADV+-(f), so the result is a true lower bound on ADV+-(f), never an overestimate.

Status: certified lower bound on ADV+-(f). Deterministic.

Parameters:

f – BooleanFunction to analyze

Returns:

Certified lower bound on ADV+-(f)

Raises:

ValueError – if n exceeds the dense-matrix size cap (n <= 12).

References

• Hoyer, Lee, Spalek, “Negative weights make adversaries stronger” (2007)

• Reichardt, “Reflections for quantum query algorithms” (2011)

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

Compute NR(f), the nondeterministic query complexity.

A nondeterministic algorithm “guesses” a certificate and verifies it; it must succeed on every input with f(x) = side, so its cost is the certificate complexity C_side(f) = max over those inputs of the minimal certificate size. (A previous implementation returned the minimum certificate over side inputs, which only accounts for the easiest input and is not the standard measure.)

Status: exact. NR(f) = C_side(f) is a standard identity.

Parameters:

• f – BooleanFunction to analyze

• side – Which value to compute NR for (0 or 1, default 1)

Returns:

Nondeterministic query complexity (= C_side(f))

boofun.analysis.query_complexity.nondeterministic_degree(f: BooleanFunction, side: int = 1) → int

Compute ndeg(f), the nondeterministic degree (exact).

This is the minimum degree of a real polynomial p with p(x) != 0 exactly when f(x) = side (de Wolf’s nondeterministic polynomial). A previous implementation returned the minimum certificate size, which is a different measure.

Method: for each candidate degree d, the polynomials of degree <= d vanishing on all off-side inputs form a linear subspace V (null space of the evaluation matrix). A valid witness exists iff no side input y is annihilated by all of V: the bad polynomials for each y form a proper subspace, and a generic combination of a null-space basis avoids every one of finitely many proper subspaces over the reals.

Status: exact (floating-point rank computation; n <= 12, raises ValueError above). Examples: ndeg(OR_n, side=1) = 1; ndeg(AND_n, side=1) = n.

Parameters:

• f – BooleanFunction to analyze

• side – Which side must be exactly the support of p (0 or 1)

Returns:

The exact nondeterministic degree (an integer)

Raises:

ValueError – if n exceeds the size cap.

References

• de Wolf, “Nondeterministic Quantum Query and Communication Complexities” (2003)

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

Compute deg1(f), the one-sided approximate degree (exact, via LP).

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

Each candidate degree is an LP feasibility problem over the character basis, solved exactly (HiGHS).

Status: exact for the definition above (n <= 12; raises ValueError above). Conventions for “one-sided approximate degree” vary in the literature (some authors additionally require p(x) >= 0 on the off side); this function implements exactly the constraints listed.

Parameters:

• f – BooleanFunction to analyze

• side – Which side to approximate (0 or 1, default 1)

• epsilon – Approximation parameter, in [0, 1/2)

Returns:

The exact one-sided approximate degree (an integer)

Raises:

ValueError – if epsilon is outside [0, 1/2) or n exceeds the LP size cap.

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

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)

Status: estimate. The point value sqrt(C_side * C_other) is clamped into the certified interval [bs/3, D] (R1 >= R2 >= bs/3; R1 <= D).

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.polynomial_method_bound(f: BooleanFunction) → float

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

A quantum algorithm making T queries induces acceptance-probability polynomials of degree at most 2T, so Q2(f) >= deg_{1/3}(f) / 2 (Beals et al. 2001). Since approximate_degree is computed exactly by LP, this is a certified lower bound, not an estimate.

Status: certified lower bound on Q2(f) (for n <= 12).

Parameters:

f – BooleanFunction to analyze

Returns:

Polynomial-method lower bound for bounded-error 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.quantum_query_complexity(f: BooleanFunction) → float

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

Status: estimate. The point value sqrt(D) (Grover-style behavior, exact up to constants for OR-like functions) is clamped into the certified interval [deg_{1/3}(f)/2, D]: the polynomial method gives Q2 >= deg_{1/3}/2 (Beals et al. 2001) and Q2 <= D trivially. Note that adversary values from this module are lower bounds on ADV+-, not on Q2 numerically, so they are deliberately not used here.

For exact Q2 characterization one needs the ADV+- semidefinite program; see the quantum-query-optimizer fixtures in tests/cross_validation/.

Parameters:

f – BooleanFunction to analyze

Returns:

Estimated bounded-error quantum query complexity

Raises:

ValueError – if n exceeds the LP size cap (n <= 12).

boofun.analysis.query_complexity.sensitivity_lower_bound(f: BooleanFunction) → int

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.spectral_adversary_bound(f: BooleanFunction) → float

Compute a certified spectral adversary lower bound on ADV(f).

Uses the spectral formulation of the positive-weight adversary method (Barnum-Saks-Szegedy): for any nonnegative symmetric matrix Gamma supported on pairs with f(x) != f(y),

ADV(f) >= ||Gamma|| / max_i ||Gamma o D_i||

where D_i[x, y] = 1 iff x_i != y_i. This implementation evaluates that ratio exactly for one canonical witness: Gamma = the adjacency matrix of the bipartite sensitivity graph (pairs at Hamming distance 1 with different f-values). For that Gamma each Gamma o D_i is a partial matching, so ||Gamma o D_i|| = 1 and the bound is exactly the largest singular value of the bipartite sensitivity matrix.

Status: certified lower bound on ADV(f) (and hence on ADV+-(f)); not the optimal spectral adversary, which requires an SDP. Deterministic. Since Q2(f) = Theta(ADV+-(f)) with constants below 1, this value is NOT claimed to be numerically <= Q2(f); see the module docstring.

Parameters:

f – BooleanFunction to analyze

Returns:

Exact value of the canonical spectral-adversary witness

Raises:

ValueError – if n exceeds the dense-matrix size cap (n <= 12).

References

• Barnum, Saks, Szegedy, “Quantum query complexity and semi-definite programming” (2003)

boofun.analysis.query_complexity.strong_nondeterministic_degree(f: BooleanFunction) → float

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

Status: estimate, reported as max(ndeg0(f), ndeg1(f)) where the one-sided nondeterministic degrees are exact. Any strong polynomial is in particular a nondeterministic polynomial for side 1, so degs(f) >= ndeg1(f) is certified; the max with ndeg0 is heuristic.

Parameters:

f – BooleanFunction to analyze

Returns:

Estimated strong nondeterministic degree

boofun.analysis.query_complexity.threshold_degree(f: BooleanFunction) → int

Compute the threshold degree of f (exact, via LP).

The threshold degree is the minimum degree d of a real polynomial p with sign(p(x)) = (-1)^{f(x)} for all x (equivalently, p sign- represents f). For example, every linear threshold function (AND, OR, majority) has threshold degree 1, while parity on n variables has threshold degree n.

Status: exact (for n <= 12; raises ValueError above).

Parameters:

f – BooleanFunction to analyze

Returns:

The exact threshold degree (an integer)

Raises:

ValueError – if n exceeds the LP size cap.

boofun.analysis.query_complexity.weak_nondeterministic_degree(f: BooleanFunction) → float

Compute degw(f), the weak nondeterministic degree.

This is min(ndeg0(f), ndeg1(f)), the cheaper of the two one-sided nondeterministic degrees.

Status: exact for this definition (the one-sided values are exact).

Parameters:

f – BooleanFunction to analyze

Returns:

Weak nondeterministic degree

boofun.analysis.query_complexity.zero_error_randomized_complexity(f: BooleanFunction) → float

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).

Status: estimate. The point value sqrt(C0 * C1) is clamped into the certified interval [max(sqrt(D), bs/3), D]: R0 <= D trivially, R0 >= sqrt(D) because D(f) <= R0(f)^2, and R0 >= R2 >= bs/3 (Nisan).

Parameters:

f – BooleanFunction to analyze

Returns:

Estimated expected queries for zero-error randomized computation

Note

Exact computation requires optimizing over all randomized protocols; no library computes this exactly.