Beyond the n/2 Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions
quant-ph, cs.CC
Submitted: 2026-11-06
Updated: 2026-11-06
Terminology
Sources
- Quantum Lower Bounds by Polynomials
- Quantum Amplitude Amplification and Estimation
- On Quantum Versions of the Yao Principle
- Sum-of-squares hierarchy lower bounds for symmetric formulations
- On the sum-of-squares degree of symmetric quadratic functions
- Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science
- Symmetric chains, Gelfand-Tsetlin chains, and the Terwilliger algebra of the binary Hamming scheme
- Quantum Oracle Interrogation: Getting all information for almost half the price
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements