Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs.

Antares Chen Neng Huang Kunal Marwaha

Published in: CoRR (2023)

Keyphrases

high dimensional
computational cost
worst case
optimization problems
data sets
learning algorithm
data structure
search space
significant improvement
constraint satisfaction problems
orders of magnitude
depth map
soft constraints