Quantum computing of 3-SAT problems using Rydberg atom arrays

Seeking a quantum computation method for solving nondeterministic polynomial time (NP)-complete problems is of central interest in quantum information science. The 3-satisfiability problem (3-SAT) is one of the best-known NP-complete problems which cannot be solved time-effectively (i.e. in a polynomial time) unless P=NP. Here we present a proof-of-principle experimental demonstration of quantum mechanical computing for a set of instances of the 3-SAT (Satisfiability) problem. We use three-dimensional optical tweezer arrays to implement Rydberg atom graphs, which are Rydberg data atoms coupled by Rydberg quantum wires [1], in which the data atoms and wires are used for variables and complemented pairs of 3-SAT clauses. And their many-body ground states which are the maximal independent sets of the given graphs are reduced to the 3-SAT solutions. The experimental result shows that two-clause 3-SAT satisfiable probabilities, i.e., whether instance of the given graphs are satisfiable or not, are measured to be $87.1%$, $95.0%$ and $84.7%$, for one-, two- and three- inter-clause connections, respectively. This proof-of-principle experiment of 3-SAT suggests that an NP-complete problem can be efficiently solvable through a reduction among NP-complete problems.