boofun.quantum_complexity

Classical estimation of quantum query complexity bounds for Boolean functions.

Warning

Experimental — NOT part of the stable public API

This module is not exported from the top-level boofun package. Import it explicitly if you want to use it:

from boofun.quantum_complexity import QuantumComplexityAnalyzer

It is an exploratory sandbox for thinking about quantum query complexity in the context of Boolean function analysis. It is not a finished feature. The API is unstable, the scope is still being figured out, and everything here may be reorganized, expanded, or removed in a future release.

Everything runs on a classical CPU. There is no quantum hardware or quantum simulator involved. The functions compute closed-form formulas from textbooks (Grover iteration counts, quantum walk hitting times, etc.) — useful for building intuition, but not a substitute for actual quantum simulation.

What’s here today:

Grover complexity bounds — closed-form O(√(N/M)) formulas.
Quantum walk complexity bounds — analytical Szegedy walk estimates on the Boolean hypercube.
Element distinctness analysis — classical collision enumeration plus the known O(N^{2/3}) quantum upper bound.
Oracle circuit construction — a Qiskit QuantumCircuit that implements the standard phase oracle (if Qiskit is installed). The circuit is built but never executed.

What we’re thinking about for v2.0.0 (see ROADMAP.md):

A lightweight statevector simulator so Grover / walk results come from actual simulated quantum dynamics, not just formulas.
Optional Qiskit/Cirq backends for larger simulations.
Genuine quantum property testers (BLR, monotonicity, junta).
Comparing simulated vs. analytical results side by side.

If you have ideas about what would be most useful here, we’d love to hear them — see CONTRIBUTING.md.

The boofun.analysis.query_complexity module provides the complementary quantum lower bounds (Ambainis adversary, spectral adversary, polynomial method). Those are mature, well-tested, and correctly named.

What was removed (v1.3.0): The previous quantum module contained classical algorithms with misleading quantum_ prefixes (Fourier analysis, influence estimation, property testing) that duplicated SpectralAnalyzer and PropertyTester. Use those instead:

analyzer = SpectralAnalyzer(f)
analyzer.fourier_expansion()   # was quantum_fourier_analysis()
analyzer.influences()          # was quantum_influence_estimation()

tester = PropertyTester(f)
tester.blr_linearity_test()    # was _quantum_linearity_test()
tester.monotonicity_test()     # was _quantum_monotonicity_test()
tester.junta_test(k)           # was _quantum_junta_test()

Module Attributes

`QuantumBooleanFunction`	Deprecated alias.
`create_quantum_boolean_function`(...)	Deprecated alias.
`quantum_walk_analysis`(f)	Deprecated alias.
`quantum_walk_search`(f[, num_iterations])	Deprecated alias.

Functions

`create_complexity_analyzer`(classical_function)	Create a quantum complexity analyzer from a classical Boolean function.
`create_quantum_boolean_function`(...)	Deprecated alias.
`element_distinctness_analysis`(f)	Analyze element distinctness structure of a Boolean function.
`grover_speedup`(f)	Convenience function: compute Grover speedup bounds for a Boolean function.
`quantum_walk_analysis`(f)	Deprecated alias.
`quantum_walk_bounds`(f)	Compute quantum walk complexity bounds on the Boolean hypercube (closed-form).
`quantum_walk_search`(f[, num_iterations])	Deprecated alias.
`quantum_walk_search_bounds`(f[, num_iterations])	Compute quantum walk search success probabilities analytically.

Classes

`QuantumBooleanFunction`	Deprecated alias.
`QuantumComplexityAnalyzer`(boolean_function)	Compute quantum complexity bounds for a Boolean function.

class boofun.quantum_complexity.QuantumComplexityAnalyzer(boolean_function: BooleanFunction)[source]

Compute quantum complexity bounds for a Boolean function.

Warning

Experimental — this class is part of BooFun’s quantum complexity playground. The API may change in future releases.

This is a classical analyzer that plugs numbers into closed-form formulas from quantum query complexity theory. It does not simulate quantum circuits or run quantum algorithms.

Useful for building intuition about questions like:

“How many Grover iterations would be optimal for this function?”
“What is the quantum walk hitting time on the hypercube?”
“What does the Grover amplitude evolution look like analytically?”

For Fourier analysis, influences, or property testing, use SpectralAnalyzer and PropertyTester — those are mature and well-tested.

Example:

import boofun as bf
from boofun.quantum_complexity import QuantumComplexityAnalyzer

f = bf.AND(6)
qca = QuantumComplexityAnalyzer(f)
result = qca.grover_analysis()
print(f"Grover speedup: {result['speedup']:.1f}x")

__init__(boolean_function: BooleanFunction)[source]

Initialize the analyzer.

Parameters:: boolean_function – Classical Boolean function to analyze

create_quantum_oracle() → Any | None[source]

Create a Qiskit quantum oracle circuit for the Boolean function.

This builds a valid QuantumCircuit implementing the standard phase-oracle construction (enumerate satisfying inputs, apply multi-controlled-X). The circuit is not executed — it is returned as a data structure.

Requires pip install qiskit.

Returns:: Qiskit QuantumCircuit, or None if Qiskit is not installed.

grover_analysis() → Dict[str, Any][source]

Compute Grover’s algorithm complexity bounds (closed-form).

Given a function f : {0,1}^n -> {0,1} with M satisfying assignments out of N = 2^n total inputs:

Classical expected queries: N / M
Grover queries: (pi/4) * sqrt(N / M)
Optimal iterations: floor(pi/4 * sqrt(N / M))

These are standard textbook formulas (Grover 1996, Boyer et al. 1998). No quantum circuit is built or simulated.

Returns:: Dict with num_solutions, classical_queries, grover_queries, speedup, optimal_iterations, has_solutions, solution_density.

grover_amplitude_analysis() → Dict[str, Any][source]

Compute Grover amplitude evolution analytically (closed-form).

Uses the exact formulas for amplitude amplification:

theta = arcsin(sqrt(M / N))
After k iterations: solution_amplitude = sin((2k+1) * theta)
Success probability = sin^2((2k+1) * theta)

No statevector simulation — these are the known analytical results (Grover 1996, Boyer et al. 1998).

Returns:: Dict with num_solutions, theta, optimal_iterations, evolution (list of per-iteration amplitudes), max_success_prob.

boofun.quantum_complexity.create_complexity_analyzer(classical_function: BooleanFunction) → QuantumComplexityAnalyzer[source]

Create a quantum complexity analyzer from a classical Boolean function.

Parameters:: classical_function – Classical Boolean function
Returns:: QuantumComplexityAnalyzer instance

boofun.quantum_complexity.grover_speedup(f: BooleanFunction) → Dict[str, Any][source]

Convenience function: compute Grover speedup bounds for a Boolean function.

Returns the same dict as QuantumComplexityAnalyzer(f).grover_analysis().

boofun.quantum_complexity.quantum_walk_bounds(f: BooleanFunction) → Dict[str, Any][source]

Compute quantum walk complexity bounds on the Boolean hypercube (closed-form).

Estimates the Szegedy quantum walk parameters for searching marked vertices (where f(x) = 1) on the n-dimensional hypercube {0,1}^n.

Formulas used (Szegedy 2004, Magniez et al. 2011): - Spectral gap of hypercube walk: 2/n - Classical mixing time: n * log(N) / 2 - Classical hitting time: N / M - Quantum hitting time: sqrt(classical_hitting * mixing) - Quantum walk complexity: sqrt(N/M) * sqrt(mixing_time)

No walk is simulated — these are plugged-in analytical formulas.

Parameters:: f – Boolean function (marked vertices are where f(x) = 1)
Returns:: Dict with spectral_gap, mixing_time, hitting times, speedup, etc.

boofun.quantum_complexity.element_distinctness_analysis(f: BooleanFunction) → Dict[str, Any][source]

Analyze element distinctness structure of a Boolean function.

Performs classical enumeration to find collision pairs, then reports the known quantum upper bound O(N^{2/3}) from Ambainis (2007).

The collision structure is computed classically by exhaustive evaluation. The quantum complexity is the known theoretical bound, not a simulated result.

Parameters:: f – Boolean function (viewed as function from [N] to some range)
Returns:: Dict with collision info, classical_complexity, quantum_complexity, speedup.

boofun.quantum_complexity.quantum_walk_search_bounds(f: BooleanFunction, num_iterations: int | None = None) → Dict[str, Any][source]

Compute quantum walk search success probabilities analytically.

Uses the same closed-form Grover-like formulas: - theta = arcsin(sqrt(M / N)) - Success probability after t steps: sin^2((2t+1) * theta)

This is the analytical result, not a simulation. The connection is mathematically valid: quantum walk search on the complete graph reduces to Grover’s algorithm (Szegedy 2004).

Parameters:

f – Boolean function (marked vertices are where f(x) = 1)
num_iterations – Number of walk iterations (default: optimal)

Returns:

Dict with marked_vertices, success probabilities, evolution, speedup.

boofun.quantum_complexity.QuantumBooleanFunction: Deprecated alias. Use QuantumComplexityAnalyzer instead.

boofun.quantum_complexity.create_quantum_boolean_function(classical_function: BooleanFunction) → QuantumComplexityAnalyzer: Deprecated alias. Use create_complexity_analyzer() instead.

boofun.quantum_complexity.quantum_walk_analysis(f: BooleanFunction) → Dict[str, Any]: Deprecated alias. Use quantum_walk_bounds() instead.

boofun.quantum_complexity.quantum_walk_search(f: BooleanFunction, num_iterations: int | None = None) → Dict[str, Any]: Deprecated alias. Use quantum_walk_search_bounds() instead.