We analyze several examples, including maximum-weighted independent set on graphs with arbitrary connectivity, quadratic unconstrained binary optimization problems with arbitrary or restricted connectivity, and integer factorization. Numerical simulations on small system sizes indicate that the adiabatic time scale for solving the mapped problems is strongly correlated with that of the original problems. Our work provides a blueprint for using Rydberg atom arrays to solve a wide range of combinatorial optimization problems with arbitrary connectivity, beyond the restrictions imposed by the hardware geometry. Programmable quantum systems offer unique possibilities to test the performance of various quantum optimization algorithms. Some of the main practical limitations in this context are often set by specific hardware restrictions. In particular, the native connectivity of the qubits for a given platform typically restricts the class of problems that can addressed. For instance, Rydberg atom arrays naturally allow encoding maximum independent set problems, but native encodings are restricted to so-called unit disk graphs. In this work we significantly expand the class of problems that can be addressed with Rydberg atom arrays, overcoming the limitations to geometric graphs. We develop a specific encoding scheme to map a variety of problems into arrangements of Rydberg atoms, including maximum weighted independent sets on graphs with arbitrary connectivity, quadratic unconstrained binary optimization problems with arbitrary or restricted connectivity, and integer factorization. Our work thus provides a blueprint for using Rydberg atom arrays to solve a wide range of combinatorial optimization problems, using technology already available in experiments. MWIS representation of some example constraints. Each bit is represented by a corresponding vertex in the MWIS problem graph. The weight of the vertices is indicated by its interior color on a gray scale. For each example, the degenerate MWIS configurations are shown by identifying vertices in a MWIS with a red boundary. The MWISs correspond to the satisfying assignments to the corresponding constraint-satisfaction problem. We would wait for the system to reach an equilibrium, which hopefully would minimize some potential function that measures the distance between our embedding and a unit disk graph.(b) MWIS representation of n 1 n 2 = 0, with the third, unlabeled vertex being an ancillary vertex. I have an idea but it's rather silly: I thought of running a physical simulation in which we place an attractive force on edges between vertices that are far apart, and a repelling force on non-edges between vertices that are close together. "Low distortion Embeddings" is something related but different: There, the goal is that all edges should have similar lengths, whereas in my case I don't care about eliminating short edges. Has this type of thing been studied? In particular, I haven't been able to find an appropriate algorithm for the first item. Hopefully, if the embedding of $G$ is close to a unit disk graph, $A$ will return a good approximation to the $NP$-hard problem. Use the algorithm $A$ to find a solution for the graph.Of course, the resulting graph is probably not going to be a unit disk graph, but hopefully it is close to such a graph in some sense. ![]() Given a graph $G$, first embed it into the plane in such a way that vertex pairs connected by an edge tend to be close together, whereas vertex pairs that aren't connected tend to be farther apart.Let $A$ be an algorithm that solves an $NP$-hard problem in polynomial time in the special case of unit disk graphs. I am interested in designing approximation algorithms by adapting such algorithms to general graphs as follows: Some $NP$-hard problems become solvable in polynomial time for unit disk graphs. A unit disk graph is defined by a collection of $n$ vertices corresponding to $n$ points on the plane, with an edge between any two vertices whose distance is at most $r$.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |