REVIEW 5 cited by
Beating the random assignment on constraint satisfaction problems of bounded degree
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac{1}{2} + \Omega(1/\sqrt{D})$ fraction of constraints, where $D$ is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a \emph{quantum} algorithm to find an assignment satisfying a $\frac{1}{2} + \Omega(D^{-3/4})$ fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a $\mu + \Omega(1/\sqrt{D})$ fraction of constraints, where $\mu$ is the fraction that would be satisfied by a uniformly random assignment.
Forward citations
Cited by 5 Pith papers
-
Weak Poincar\'e Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick Model
Approximate stochastic localization plus conductance transfers yield a weak Poincaré inequality for the SK model at β < 1/2, enabling efficient Glauber sampling from a warm start.
-
Classical State Preparation for Variational Quantum Algorithms via Reinforcement Learning
CRiSP uses neural-guided MCTS and curriculum learning to insert Clifford prefixes before parameterized rotations in VQAs, yielding mean 3.17x and max 45x gains in energy accuracy on 22-qubit QAOA benchmarks versus pri...
-
A comprehensive benchmark of an Ising machine on the Max-Cut problem
The Digital Annealer finds better Max-Cut solutions than selected classical heuristics on a majority of medium-to-large instances, but its advantage depends on instance size and numeric precision.
-
Quantum Approximate Optimisation Applied to Graph Similarity
A QAOA simulation study of graph similarity through edge overlap finds that a compact encoding with many infeasible states causes QAOA to underperform random sampling as graphs grow.
-
A brief history of quantum vs classical computational advantage
A single-author review of all quantum computational advantage claims to date, their classical refutations, and the progress of quantum error correction.
Discussion (0). Continue with ORCID to comment.