Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_2$ Lattice
Gauge Theory
- URL: http://arxiv.org/abs/2202.08817v1
- Date: Thu, 17 Feb 2022 18:39:42 GMT
- Title: Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_2$ Lattice
Gauge Theory
- Authors: Xiaopeng Cui, Yu Shi
- Abstract summary: The Hamiltonian cycle (HC) problem in graph theory is a well-known NP-complete problem.
We present an approach in terms of $mathbbZ$ lattice gauge theory defined on the lattice with the graph as its dual.
For some random samples of small graphs, we demonstrate that the dependence of the average value of $g_c$ on $sqrtN_hc$, $N_hc$ being the number of HCs, and that of the average value of $frac1g_c$ on $N
- Score: 9.83302372715731
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Hamiltonian cycle (HC) problem in graph theory is a well-known
NP-complete problem. We present an approach in terms of $\mathbb{Z}_2$ lattice
gauge theory (LGT) defined on the lattice with the graph as its dual. When the
coupling parameter $g$ is less than the critical value $g_c$, the ground state
is a superposition of all configurations with closed strings of spins in a same
single-spin state, which can be obtained by using an adiabatic quantum
algorithm with time complexity $O(\frac{1}{g_c^2} \sqrt{ \frac{1}{\varepsilon}
N_e^{3/2}(N_v^3 + \frac{N_e}{g_c}}))$, where $N_v$ and $N_e$ are the numbers of
vertices and edges of the graph respectively. A subsequent search for a HC
among those closed-strings solves the HC problem. For some random samples of
small graphs, we demonstrate that the dependence of the average value of $g_c$
on $\sqrt{N_{hc}}$, $N_{hc}$ being the number of HCs, and that of the average
value of $\frac{1}{g_c}$ on $N_e$ are both linear. It is thus suggested that
for some graphs, the HC problem may be solved in polynomial time. A possible
quantum algorithm using $g_c$ to infer $N_{hc}$ is also discussed.
Related papers
- Efficient Sampling on Riemannian Manifolds via Langevin MCMC [51.825900634131486]
We study the task efficiently sampling from a Gibbs distribution $d pi* = eh d vol_g$ over aian manifold $M$ via (geometric) Langevin MCMC.
Our results apply to general settings where $pi*$ can be non exponential and $Mh$ can have negative Ricci curvature.
arXiv Detail & Related papers (2024-02-15T22:59:14Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously.
Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples.
We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
arXiv Detail & Related papers (2023-09-25T17:54:19Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
We give a quantum approximation scheme for the classical $k$-means clustering problem in the QRAM model.
Our quantum algorithm runs in time $tildeO left( 2tildeO(frackvarepsilon) eta2 dright)$.
Unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines.
arXiv Detail & Related papers (2023-08-16T06:46:37Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem.
We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph.
Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
arXiv Detail & Related papers (2023-04-17T10:38:08Z) - The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits [0.0]
We give an algorithm to perform pattern matching in quantum circuits for many patterns simultaneously.
In the case of quantum circuits, we can express the bound obtained in terms of the maximum number of qubits.
arXiv Detail & Related papers (2023-02-13T22:09:02Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis.
We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$.
Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
arXiv Detail & Related papers (2022-08-19T18:00:34Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized
Optimization [77.57736777744934]
This paper revisits and extends the widely used accelerated gradient tracking.
Our complexities improve significantly on the ones of $cal O(frac1epsilon5/7)$ and $cal O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$.
arXiv Detail & Related papers (2021-04-06T15:34:14Z) - Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
We show that the exponential dependence on the dimension dimension $d in the celebrated fast multipole method of Greengard and Rokhlin cannot be improved.
This is the first formal limitation proven about fast multipole methods.
arXiv Detail & Related papers (2020-11-04T18:35:02Z) - Convergence of Graph Laplacian with kNN Self-tuned Kernels [14.645468999921961]
Self-tuned kernel adaptively sets a $sigma_i$ at each point $x_i$ by the $k$-nearest neighbor (kNN) distance.
This paper proves the convergence of graph Laplacian operator $L_N$ to manifold (weighted-)Laplacian for a new family of kNN self-tuned kernels.
arXiv Detail & Related papers (2020-11-03T04:55:33Z) - Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language [1.0118253437732931]
We study the quantum query complexity of two problems.
We consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing.
By embedding the "balanced parentheses" problem into the grid, we show a lower bound of $Omega(n1.5-epsilon)$ for the directed 2D grid and $Omega(n2-epsilon)$ for the undirected 2D grid.
arXiv Detail & Related papers (2020-07-06T09:51:41Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
We study the fixed-support Wasserstein barycenter problem (FS-WBP)
We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
arXiv Detail & Related papers (2020-02-12T03:40:52Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.