Exact Quantum Algorithms for Composed Boolean Functions
cs.CC, quant-ph
Submitted: 2026-11-12
Updated: 2026-11-12
Terminology
Sources
- Separations in query complexity using cheat sheets
- Monte Carlo to Las Vegas for Recursively Composed Functions
- Superlinear advantage for exact quantum algorithms
- Separations in Query Complexity Based on Pointer Functions
- Separations in communication complexity using cheat sheets and information complexity
- Quantum Lower Bounds by Polynomials
- Quantum Amplitude Amplification and Estimation
- Communication Complexity Lower Bounds by Polynomials
- Quantum vs. Classical Communication and Computation
- Bounds for Small-Error and Zero-Error Quantum Algorithms
- Query-to-Communication Lifting Using Low-Discrepancy Gadgets
- A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions
- Composition limits and separating examples for some Boolean function complexity measures
- Exact quantum query complexity for total Boolean functions
- A General Composition Theorem for Approximate Degree
- Reflections for quantum query algorithms
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?