We study the quantum version of the random K -satisfiability problem in the presence of an external magnetic field Gamma applied in the transverse direction. We derive the replica-symmetric free-energy functional within the static approximation and the saddle-point equation for the order parameter: the distribution P[h(m)] of functions of magnetizations. The order parameter is interpreted as the histogram of probability distributions of individual magnetizations. In the limit of zero temperature and small transverse fields, to leading order in Gamma magnetizations m approximately 0 become relevant in addition to purely classical values of m approximately +/-1 . Self-consistency equations for the order parameter are solved numerically using a quasi-Monte Carlo method for K=3 . It is shown that for an arbitrarily small Gamma quantum fluctuations destroy the phase transition present in the classical limit Gamma=0 , replacing it with a smooth crossover transition. The implications of this result with respect to the expected performance of quantum optimization algorithms via adiabatic evolution are discussed. The replica-symmetric solution of the classical random K -satisfiability problem is briefly reexamined. It is shown that the phase transition at T=0 predicted by the replica-symmetric theory is of continuous type with atypical critical exponents.
Using the quantum cavity method, we present an analytical study of the phase diagram of a random optimization problem in a transverse field, in the thermodynamic limit and for a uniformly random distribution of instances. We include the effect of replica symmetry breaking, and unveil the occurrence of a first-order quantum phase transition. We back up our results with Quantum Monte Carlo and Exact Diagonalization methods, and provide evidence that the gap vanishes exponentially with the system size at the transition. This suggests that the Quantum Adiabatic Algorithm requires an exponential time to find the ground state of such problems.
I describe one quantum approach to solving 3-satisfiability (3-SAT), the well known problem in computer science. The approach is based on repeatedly measuring the truth value of the clauses forming the 3-SAT proposition using a non-orthogonal basis. If the basis slowly evolves then there is a strong analogy to adiabatic quantum computing, although the approach is entirely circuit-based. To solve a 3-SAT problem of n variables requires a quantum register of
n qubits, or more precisely rebits i.e. qubits whose phase need only be real. For cases of up to n=26 qubits numerical simulations indicate that the algorithm runs fast, outperforming Grover's algorithm and having a scaling with n that is superior to the best reported classical algorithms. There are indications that the approach has an inherent robustness versus imperfections in the elementary operations.
The discrete formulation of adiabatic quantum computing is compared with other search methods, classical and quantum, for random satisfiability (SAT) problems. With the number of steps growing only as the cube of the number of variables, the adiabatic method gives solution probabilities close to 1 for problem sizes feasible to evaluate via simulation on current computers. However, for these sizes the minimum energy gaps of most instances are fairly large, so the good performance scaling seen for small problems may not reflect asymptotic behavior where costs are dominated by tiny gaps. Moreover, the resulting search costs are much higher than for other methods. Variants of the quantum algorithm that do not match the adiabatic limit give lower costs, on average, and slower growth than the conventional GSAT heuristic method.
Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.
The random k-SAT instances undergo a "phase transition" from being generally satisfiable to unsatisfiable as the clause number m passes a critical threshold,
rkn. This causes a drastic reduction in the number of satisfying assignments, shifting the problem from being generally solvable on classical computers to typically insolvable. Beyond this threshold, it is challenging to comprehend the computational complexity of random k-SAT. In quantum computing, Grover's search still yields exponential time requirements due to the neglect of structural information. Leveraging the structure inherent in search problems, we propose the k-local quantum search algorithm, which extends quantum search to structured scenarios. Grover's search, by contrast, addresses the unstructured case where k=n. Given that the search algorithm necessitates the presence of a target, we specifically focus on the problem of searching the interpretation of satisfiable instances of k-SAT, denoted as max-k-SSAT. If this problem is solvable in polynomial time, then k-SAT can also be solved within the same complexity. We demonstrate that, for small
k≥3, any small
ε>0 and sufficiently large n:
⋅ k-local quantum search achieves general efficiency on random instances of max-k-SSAT with
m=Ω(n2+δ+ε) using
O(n) iterations, and
⋅ k-local adiabatic quantum search enhances the bound to
m=Ω(n1+δ+ε) within an evolution time of
O(n2). In both cases, the circuit complexity of each iteration is
O(nk), and the efficiency is assured with overwhelming probability
1−O(erfc(nδ/2)). By modifying this algorithm capable of solving all instances of max-k-SSAT, we further prove that max-k-SSAT is polynomial on average when
m=Ω(n2+ε) based on the average-case complexity theory.