Strong Selective and List-Decoding Direct Product Theorems for Quantum Query Complexity

arXiv:2609.26678 · cs.CC, quant-ph · Submitted 2026-09-22 · Read on arXiv

cs.CC, quant-ph

Submitted: 2026-09-22

Updated: 2026-09-30

Terminology

• Multiplicative Adversary Method — 53× in this paper · explained in 2 episodes
• Query Complexity — 47× in this paper · explained in 2 episodes
• Trace — 13× in this paper · explained in 2 episodes
• Generalization — 9× in this paper · explained in 13 episodes
• Ancillary Qubits — 2× in this paper · explained in 1 episode
• Chebyshev Polynomials — 1× in this paper · explained in 2 episodes
• Combinatorial Optimization — 1× in this paper · explained in 2 episodes
• Core — 1× in this paper · explained in 2 episodes
• Fidelity — 1× in this paper · explained in 2 episodes
• Quantum Circuits — 1× in this paper · explained in 2 episodes

Sources

• Tight Quantum Time-Space Tradeoffs for Permutation Inversion
• Symmetry-assisted adversaries for quantum state generation
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments

Related papers

• Parameterized Hardness of Zonotope Containment and Neural Network Verification
• Hardware-Algorithm Co-Optimization of Early-Exit Neural Networks for Multi-Core Edge Accelerators
• Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM
• Strassen's support functionals coincide with the quantum functionals
• Exponential Quantum Advantage in Numbers-on-Forehead Communication
• Rational degree is polynomially related to degree