Solving satisfiability problems by the ground-state quantum computer

A quantum algorithm is proposed to solve the satisfiability (SAT) problems by the ground-state quantum computer. The scale of the energy gap of the ground-state quantum computer is analyzed for the $3\text{−}\text{bit}$ exact cover problem. The time cost of this algorithm on the general SAT problems is discussed.

Figure 1

The same as Fig. 2 in Ref. 14, this figure shows, in a complicated circuit, how the CNOT gate interacting qubits is modified by inserting teleportation boxes on each qubit’s upstream and downstream part, so that the energy gap is only polynomially small. Each dot represents a row of two quantum dots, label $I$ stands for identical transformation Hamiltonian $h\left(I\right)$, $H$ for Hadamard transformation Hamiltonian $h\left(H\right)$, and $P\left(0\right)$ for projection Hamiltonian $h(\mid 0⟩,\lambda )$.

Figure 2

A six-row single qubit ended with the projection Hamiltonian $h(\mid 0⟩,\lambda )$.

Figure 3

Energy gap $\Delta$ vs $\lambda$ with $h(\mid 0⟩,\lambda )$ applied on the last row of a six-row single qubit, where $h^0=10ϵ(I+\alpha {\sigma }_z-\sqrt{1-{\alpha }^2}{\sigma }_x)$. From top to bottom, lines correspond to $\alpha =0,0.9,0.99,0.999,0.9999,0.99999$.

Figure 4

A filter for the clause $i=0$.

Figure 5

A filter for the clause $i+j=1$.

Figure 6

A GSQC circuit solving the SAT problem with each clause involving several bits. Box labeled “Filter Box” represents filters like Fig. 4 ($1\text{−}\text{bit}$ clause), Fig. 5 ($2\text{−}\text{bit}$ clause) or Fig. 7 ($3\text{−}\text{bit}$ clause).

Figure 7

A filter for the clause $i+j+k=1$. The labels on the lines stand for corresponding Hamiltonians, $I$ for $h\left(I\right)$, CNOT gate for $h\left(\mathrm{CNOT}\right)$, $P\left(1\right)$ for projection $h(\mid 1⟩,\lambda )$, etc. At the final rows, $B∕I$ represents boost Hamiltonian $h(B,\lambda )$ if there is no more clause to be applied to this qubit, otherwise, represents identical transformation Hamiltonian $h\left(I\right)$. There are teleportation boxes, not shown in the figure, inserted on all qubits between two control Hamiltonians. Some dots marked by $X$ or $Y$ are for demonstration convenience in text.