Quantum algorithms for satisfiability

• Various approaches have been developed which provide hope that the NP-complete boolean satisfiability problem can be solved in polynomial time. It is not clear that any of the published techniques will be effective. Some of the methods seem to require either exponential space/hardware (e.g., bulk spin resonance via NMR) or exponential measurement precision. This is a very active area of current research.

  One algorithm which has been well analyzed is Grover's search algorithm. It gives quadratic speedup of solving satisfiability, but in its general form can do no better than that, and hence does not give the exponential speedup needed to get P=NP.

• Following is an outline of Grover's general search algorithm. If P(x) is a boolean function for $0 \le x < N$, classical search algorithms take on the order of $\frac{N}{2}$ operations to find an item x₀ for which P(x₀) = 1. Grover's algorithm takes on the order of $\sqrt{N}$ operations. Grover's algorithm has been shown to be optimal for the general search problem. This is not an exponential speedup, but it is an improvement over the classical algorithms. However, problems such as satisfiability have additional structure which can make them easier to solve.

• Grover's algorithm consists of the following steps:

  1.

  Let n be such that $2^n \geq N$, and prepare a register containing a superposition of all $x_i\in [0\dots 2^n-1]$.

  2.

  Apply a unitary transformation that computes P(x_i) on this register:
  

  $$U_P: \frac{1}{\sqrt{2^n}}\sum_{x=0}^{n-1}\vert{x, 0}\rangle \to \frac{1}{\sqrt{2^n}}\sum_{x=0}^{n-1}\vert{x, P(x)}\rangle.$$

  
  

  For any x₀ such that P(x₀) is true, $\vert{x_0, 1}\rangle$ will be part of the resulting superposition, but since its amplitude is $\frac{1}{\sqrt{2^n}}$, the probability that a measurement produces x₀ is only 2^-n.

  3.

  Change amplitude a_j to -a_j for all x_j such that P(x_j)=1.

  4.

  Apply inversion about the average to increase amplitude of x_j with P(x_j)=1 and decrease other amplitudes.

  5.

  Repeat steps 2 through 4 $\frac{\pi}{4}\sqrt{2^n}$ times.

  6.

  Measure the last qubit of the quantum state, representing P(x). Because of the amplitude change, there is a high probability that the result will be 1. If this is the case, the measurement has projected the state onto the subspace $\frac{1}{\sqrt{2^k}}\sum_{i=1}^{k}\vert{x_i, 1}\rangle$ where k is the number of solutions. Further measurement of the remaining bits will provide one of these solutions.

• An interesting feature of this algorithm is that repeating steps 2 through 4 $\frac{\pi}{4}\sqrt{2^n}$ times is optimal. In particular, if the process is repeated more times, the probability of a successful measurement decreases back toward zero ...

• An alternative approach builds the unitary transformation for the boolean expression, applies the transformation to molecules in solution, then uses bulk spin resonance analysis via NMR to measure the expected values of the spins, and thus solves the satisfiability problem. However, realistic implementations seem to require an exponentially large NMR sample.
• The general estimate is that if n is the number of qubits, and M is the number of molecules in the sample, then n2ⁿ < M. For a typical sample, $M \approx 10^{23} \approx 2^{76}$ and so n < 70. For an upper limit, a reasonable estimate of the number of elementary particles in the accessible universe is $\approx 10^{80} \approx 2^{265}$ which corresponds with $\approx 256$ qubits ...