Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn explicit vector algorithm for high-girth MaxCut
71
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We give an approximation algorithm for MaxCut and provide guarantees on the average fraction of edges cut on $d$-regular graphs of girth $geq 2k$. For every $d geq 3$ and $k geq 4$, our approximation guarantees are better than those of all other classical and quantum algorithms known to the authors. Our algorithm constructs an explicit vector solution to the standard semidefinite relaxation of MaxCut and applies hyperplane rounding. It may be viewed as a simplification of the previously best known technique, which approximates Gaussian wave processes on the infinite $d$-regular tree.
rate research
Read More
We study the performance of local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) for the maximum cut problem, and their relationship to that of classical algorithms. (1) We prove that every (quantum or classical) one-local algorithm achieves on $D$-regular graphs of girth $> 5$ a maximum cut of at most $1/2 + C/sqrt{D}$ for $C=1/sqrt{2} approx 0.7071$. This is the first such result showing that one-local algorithms achieve a value bounded away from the true optimum for random graphs, which is $1/2 + P_*/sqrt{D} + o(1/sqrt{D})$ for $P_* approx 0.7632$. (2) We show that there is a classical $k$-local algorithm that achieves a value of $1/2 + C/sqrt{D} - O(1/sqrt{k})$ for $D$-regular graphs of girth $> 2k+1$, where $C = 2/pi approx 0.6366$. This is an algorithmic version of the existential bound of Lyons and is related to the algorithm of Aizenman, Lebowitz, and Ruelle (ALR) for the Sherrington-Kirkpatrick model. This bound is better than that achieved by the one-local and two-loc
We propose a simple iterative (SI) algorithm for the maxcut problem through fully using an equivalent continuous formulation. It does not need rounding at all and has advantages that all subproblems have explicit analytic solutions, the cut values are monotonically updated and the iteration points converge to a local optima in finite steps via an appropriate subgradient selection. Numerical experiments on G-set demonstrate the performance. In particular, the ratios between the best cut values achieved by SI and the best known ones are at least $0.986$ and can be further improved to at least $0.997$ by a preliminary attempt to break out of local optima.
The $p$-stage Quantum Approximate Optimization Algorithm (QAOA$_p$) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum (NISQ) devices, but its theoretical behavior is not well understood beyond $p=1$. We analyze QAOA$_2$ for the maximum cut problem (MAX-CUT), deriving a graph-size-independent expression for the expected cut fraction on any $D$-regular graph of girth $> 5$ (i.e. without triangles, squares, or pentagons). We show that for all degrees $D ge 2$ and every $D$-regular graph $G$ of girth $> 5$, QAOA$_2$ has a larger expected cut fraction than QAOA$_1$ on $G$. However, we also show that there exists a $2$-local randomized classical algorithm $A$ such that $A$ has a larger expected cut fraction than QAOA$_2$ on all $G$. This supports our conjecture that for every constant $p$, there exists a local classical MAX-CUT algorithm that performs as well as QAOA$_p$ on all graphs.
We propose a Markov chain Monte Carlo (MCMC) algorithm based on third-order Langevin dynamics for sampling from distributions with log-concave and smooth densities. The higher-order dynamics allow for more flexible discretization schemes, and we develop a specific method that combines splitting with more accurate integration. For a broad class of $d$-dimensional distributions arising from generalized linear models, we prove that the resulting third-order algorithm produces samples from a distribution that is at most $varepsilon > 0$ in Wasserstein distance from the target distribution in $Oleft(frac{d^{1/4}}{ varepsilon^{1/2}} right)$ steps. This result requires only Lipschitz conditions on the gradient. For general strongly convex potentials with $alpha$-th order smoothness, we prove that the mixing time scales as $O left(frac{d^{1/4}}{varepsilon^{1/2}} + frac{d^{1/2}}{varepsilon^{1/(alpha - 1)}} right)$.
The Systematic Normal Form (SysNF) is a canonical form of lattices introduced in [Eldar,Shor 16], in which the basis entries satisfy a certain co-primality condition. Using a smooth analysis of lattices by SysNF lattices we design a quantum algorithm that can efficiently solve the following variant of the bounded-distance-decoding problem: given a lattice L, a vector v, and numbers b = {lambda}_1(L)/n^{17}, a = {lambda}_1(L)/n^{13} decide if vs distance from L is in the range [a/2, a] or at most b, where {lambda}_1(L) is the length of Ls shortest non-zero vector. Improving these parameters to a = b = {lambda}_1(L)/sqrt{n} would invalidate one of the security assumptions of the Learning-with-Errors (LWE) cryptosystem against quantum attacks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
