Quantum Lower Bounds for Approximate Counting via Laurent Polynomials.

Scott Aaronson Robin Kothari William Kretschmer Justin Thaler

Published in: CoRR (2019)

Keyphrases

lower bound
upper bound
exact solution
exact and approximate
objective function
branch and bound
branch and bound algorithm
np hard
hermite transform
lower and upper bounds
worst case
lower bounding
optimal solution
quantum computing
optimal cost
vc dimension
max sat
provide an upper bound