Quantum Query Complexity and Span Programs from Pre-Geometry
quant-ph
Submitted: 2026-10-02
Updated: 2026-10-02
Terminology
Sources
- Separations in query complexity using cheat sheets
- A Simple Proof that Toffoli and Hadamard are Quantum Universal
- Reconfiguration of basis pairs in regular matroids
- Ported Tutte Functions of Extensors and Oriented Matroids
- Quantum algorithms through graph composition
- Scalar Solvability of Network Computation Problems and Representable Matroids
- Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
- An Optimal Separation of Randomized and Quantum Query Complexity
- Answer Partitions and Oracle Access Determine Quantum Query Complexity
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- A quasiparticle-protected superconducting qubit
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians