Approximating random quantum optimization problems

We report a cluster of results regarding the difficulty of finding approximate ground states to typical instances of the quantum satisfiability problem $k$-body quantum satisfiability ($k$-QSAT) on large random graphs. As an approximation strategy, we optimize the solution space over “classical” product states, which in turn introduces a novel autonomous classical optimization problem, PSAT, over a space of continuous degrees of freedom rather than discrete bits. Our central results are (i) the derivation of a set of bounds and approximations in various limits of the problem, several of which we believe may be amenable to a rigorous treatment; (ii) a demonstration that an approximation based on a greedy algorithm borrowed from the study of frustrated magnetism performs well over a wide range in parameter space, and its performance reflects the structure of the solution space of random $k$-QSAT. Simulated annealing exhibits metastability in similar “hard” regions of parameter space; and (iii) a generalization of belief propagation algorithms introduced for classical problems to the case of continuous spins. This yields both approximate solutions, as well as insights into the free energy “landscape” of the approximation problem, including a so-called dynamical transition near the satisfiability threshold. Taken together, these results allow us to elucidate the phase diagram of random $k$-QSAT in a two-dimensional energy-density–clause-density space.

Figure 1

Heuristic “hardness” phase diagram from approximating random QSAT. PS regions have product state witnesses, C have classical nonproduct, and Q have only quantum witnesses. “Easy” and “Hard” refer to conjectural algorithm-dependent hardness transitions for finding such witnesses.

Figure 2

Finite energy density phase diagram for 3-QSAT extracted from various numerical methods. Dark blue is the QSAT inaccessible region, as estimated by exact diagonalization for size $N=20$. The medium blue region is the PSAT inaccessible region, as estimated by local quench for size $N=100$. The light blue region indicates where the cavity analysis of PSAT exhibits a dynamical instability. The cavity analysis and simulated annealing data for $N=80$ roughly agree. More details regarding the numerical techniques and averaging are in the main text.

Figure 3

Product state ground state energy found by greedy local quench near critical region ${\alpha }_{\text{ps}}\approx 0.92$ at finite-size $N=100$. Error bars indicate instance-to-instance fluctuations over $N_{\mathrm{samp}}\approx 3–400$ instances per density $\alpha$. Inset: Semilogarithmic scatter plot of the same data.

Figure 4

Typical energy traces as a function of time for ten independent sweeps of the greedy quench algorithm in a typical instance at each of $\alpha =0.88,0.90,1.0$ ($N=100$). The curve in the left panel continues to fall exponentially (linearly on the log scale) to machine precision (${10}^{-16}$).

Figure 5

Simulated annealing quality and the step size dependence of the best found PSAT energy for $k=3$ and $N=16$. The step size controls the maximum change of a single component of the wave function per update trial. In the PRODSAT phase reducing the step size leads to a monotonically decreasing energy. In the UNPRODSAT phase the behavior is irregular.

Figure 6

The definition of the cavity distributions on a locally treelike interaction graph. Squares indicate clauses, labeled by letters, and spheres the spinor variables, labeled by integers.

Figure 7

Cavity estimate of the internal energy of PSAT as a function of temperature with $N_{\text{disk}}=24$ states per Bloch sphere. Error bars reflect sampling error in calculating $E$ from the converged population. Solid lines indicate the high-temperature expansion of the energy to fourth order. Solid (hollow) markers indicate data in the replica-symmetric (broken) phase. Inset: Zoomed in at low temperature of the same data, including results for both $N_{\text{disk}}=24$ states ($\blacksquare$) and $N_{\text{disk}}=12$ states ($•$). Solid (dashed) lines indicate $T$-linear fits to the $N_{\text{disk}}=24$ ($N_{\text{k}}=12$) data.

Figure 8

The free energy $F/N$ as a function of $\alpha ,T$ for qubits that have been discretized into 24 states. Point labeling is the same as in Fig. 7 and likewise, hollow points indicate data collected ignoring the dynamical replica instability. Inset: As a function of $\beta$, we show the fit to the high-temperature (small $\beta$) approximation for the free energy [cf. Eqs. (22, 23, 24)].

Figure 9

Inset: The sum-of-squares difference between two populations as a function of time in the population dynamics for $N_{\text{disk}}=36$ states and $\beta =100$. From bottom to top in the inset, we show data for $\alpha =1.26,1.28$, and $1.29$. We observed a transition in $\alpha$ between when the populations converge or diverge over time. This boundary is plotted in the main figure. Main: The location of the dynamical instability phase boundary extracted from the Lyapunov exponents of the population dynamics. As the discretization of the Bloch sphere increases, the dynamical instability appears to converge to a finite temperature phase boundary. As $T\to 0$, the instability line appears to terminate in the PRODSAT transition at $\alpha \simeq 0.91$.