Quantum Lower Bounds for Approximate Counting via Laurent Polynomials.
Scott AaronsonRobin KothariWilliam KretschmerJustin ThalerPublished in: Computational Complexity Conference (2020)
Keyphrases
- lower bound
- upper bound
- exact solution
- exact and approximate
- branch and bound algorithm
- branch and bound
- worst case
- quantum computation
- np hard
- objective function
- quantum computing
- lower and upper bounds
- vc dimension
- quantum inspired
- information retrieval
- piecewise linear
- sample size
- online learning
- lower bounding
- quantum mechanics
- randomly generated problems
- linear programming
- set of randomly generated instances
- provide an upper bound