Number Partitioning With Grover’s Algorithm in Central Spin Systems

Numerous conceptually important quantum algorithms rely on a blackbox device known as an oracle, which is typically difficult to construct without knowing the answer to the problem that the algorithm is intended to solve. A notable example is Grover’s search algorithm. Here we propose a Grover search for solutions to a class of NP-complete decision problems known as subset sum problems, including the special case of number partitioning. Each problem instance is encoded in the couplings of a set of qubits to a central spin or boson, which enables a realization of the oracle without knowledge of the solution. The algorithm provides a quantum speedup across a known phase transition in the computational complexity of the partition problem, and we identify signatures of the phase transition in the simulated performance. Whereas the naive implementation of our algorithm requires a spectral resolution that scales exponentially with system size for NP-complete problems, we also present a recursive algorithm that enables scalability. We propose and analyze implementation schemes with cold atoms, including Rydberg-atom and cavity-QED platforms.

Popular Summary

Grover’s algorithm—a textbook result in the field of quantum information—theoretically allows a quantum computer to search through an unstructured list in a time scaling as the square root of the number of entries, a speedup over the best classical counterpart. A challenge in applying the algorithm is that it relies on a blackbox subroutine known as an oracle that is typically difficult to construct without knowing the answer to the search problem. Here we propose an application of Grover’s algorithm to speed up the search for solutions to the hard computational problem of number partitioning: given a set of objects with integer weights, is there a way of partitioning the objects into two subsets whose weights are perfectly balanced? Our proposal offers a natural way of encoding the problem—without knowing the solution—in the interactions of a set of spins representing the objects with one central spin that acts as the oracle. Such central spin models can be realized in several experimental platforms, for example, in systems of laser-cooled atoms.

Previous studies of number partitioning using concepts of statistical mechanics have shown that the problem exhibits a phase transition in computational complexity, being either easy or hard depending on the dynamic range of the integer weights. We calculate the quantum speedup attainable throughout this phase diagram and find that it peaks at the phase transition. Our analysis sheds light on the physical manifestations of computational complexity.

Figure 1

(a) Sketch of Grover’s algorithm, showing the amplitude of each basis state $|x⟩$ in the system state $|\psi ⟩$. One iteration consists of the oracle $U$ marking the solution states (red) with a $\pi$ phase shift, followed by inversion about the average $V$. (b) Number partitioning: a set of weighted spins is partitioned, if possible, into two sets of equal total weight. (c) Phase shift ${\mathrm{\Phi }}_{\gamma }(S_z)$ applied by generalized oracle with step width $\gamma$. (d) The weights $w_i$ are encoded by couplings of system spins (red) to an ancilla (blue), which can be either (i) a central spin (e.g., Rydberg atom); or (ii) a bosonic mode (e.g., cavity).

Figure 2

Visualization of Grover’s algorithm and generalized oracle. (a) Grover’s algorithm with ideal oracle for $N=2^{10}$ and $N_{\mathcal{A}}=1$. Over repeated iterations (blue), the state $|{\psi }_0⟩$ (red) approaches the solution state $|A⟩$. (b) Grover’s algorithm with naive application of the generalized oracle for $ϵ=0.25$. (c) The spin-echo sequence compensates for the imperfection of the oracle, allowing similar performance to the ideal case.

Figure 3

Number partitioning with generalized oracle of step width $\gamma =2^{-k}$. (a) Success probability $P_T$ for $n=8$, $k=4,8,12$ (blue squares, orange circles, and green diamonds). Shading indicates standard deviation over 5000 instances of the weights. (b.i) Optimal number of iterations $T_{\mathrm{opt}}$ versus $(n,k)$. (b.ii) $T_{\mathrm{opt}}$ for $n=k$, grouped by number of solutions $N_A=2,4,6$ (red triangles, green circles, and yellow stars) and compared with asymptotic theory $T_{\mathrm{opt}}\propto \sqrt{N}$ (dashed lines). Black squares show average over all instances. Dotted gray line indicates linear scaling $T_{\mathrm{opt}}\propto N$. Blue diamonds show median speedup ${\left[Q\right]}_{0.5}$ for $n=k$, with error bars indicating interquartile range. (c) Probability $P_{\mathrm{opt}}$ versus $(n,k)$. Black line shows critical bit depth $k_c(n)$.

Figure 4

(a) Step width as capture range. (a.i) Normalized probability distribution $\tilde{P}(S_z)$ versus $\gamma$, for $n=k=6$ with no postselection. White lines indicate contours of $\tilde{P}(S_z)$=0.5. (a.ii) Step width $\gamma$ required to obtain $P_{\mathrm{opt}}=[0.4,0.6,0.8]$, shaded from lighter to darker. Results are plotted versus $min(k_c,k)$, with markers showing average over all $(n,k)$ with $3\le n,k\le 16$. Gray line shows ${\gamma }_c=2^{-min(k_c,k)}$. (b) Quantum speedup in the decision and optimization problems. (b.i) Median speedup ${\left[Q\right]}_{0.5}$ versus $(n,k)$ for the decision problem at step width ${\gamma }_c$. Lines denote $k=k_c$ (solid black), $k=n$ (dotted blue), and fixed problem size $nk=72$ (dashed red). (b.ii) Cuts of $Q$ along $n=k$ for different quantiles $q=[0.01,0.25,0.5,0.75,0.99]$, shaded from lightest to darkest. Lines denote $\sqrt{N}$ scaling. (b.iii) Cuts of $Q$ at $nk=72$ [red dashed line in (b.i)] for different quantiles, as in (b.ii). Lines are a guide to the eye. (b.iv) Median speedup ${\left[Q\right]}_{0.5}$ versus $n$ and $k_{\mathrm{eff}}=-{\log }_2\gamma$ for the optimization problem with machine-precision weights, approximating the large-$k$ limit. Black line shows $-{\log }_2\gamma =k_c$.

Figure 5

Effects of dissipation. (a) Median speedup ${\left[Q\right]}_{0.5}$ versus $(n,k)$ in the presence of decay with interaction-to-decay ratio $\rho ={10}^3$. Solid black line denotes $k=k_c$. (b) Median speedup ${\left[Q\right]}_{0.5}$ versus $\rho$ for $n=k=(4,6,8,10)$ denoted by dark blue to light green shaded lines. The shading denotes the interquartile range. Black solid line denotes scaling $Q\sim {\rho }^{1/3}$. Dashed lines show maximum achievable $Q$ for each system size $n$. (c) Amplification versus step width $\gamma$ for $T=1$. Solid curves show average amplification in large-$N$ limit for finite cavity cooperativity $\eta ={10}^1,3\times {10}^1,{10}^2,3\times {10}^2,\dots ,{10}^5$ (purple to yellow) and for unitary evolution (red dashed). Dark red circles show simulated amplification at $n=k=12$ with no dissipation; error bars denote standard deviation. Inset shows optimal amplification (red circles) and step width (orange diamonds) versus $\eta$ for $n=k=12$, matching the prediction for large $N$ (solid curves).

Figure 6

Sketch of the scalable algorithm, showing amplitudes of basis states versus $S_z$. Each layer $\ell$ of the algorithm consists of $T_{\ell }$ amplification cycles, each comprising the modular oracle $U_{\ell }$ and recursive inversion operator $V_{\ell }$. The modular oracle acts on states spaced in energy by $J_{\max }$ with a spectral resolution $\gamma J_{\max }$ illustrated by the shaded blue curves. The operator $V_{\ell }$ inverts the amplitudes of the states amplified by the previous layer of the algorithm about their average (dashed purple line). Implementing $V_{\ell }$ requires recursion to the lower layers of the algorithm. In the final layer $\ell =k/m$, the standard nonmodular oracle is used.

Figure 7

Comparison of the recursive and standard algorithms. (a) Physical time $T_{\mathrm{total}}/\gamma$ to implement all $T_{\mathrm{total}}$ queries of the oracle at fixed $J_{\max }$, plotted versus $n=k$. Blue circles show the standard algorithm with $\gamma ={\gamma }_c$. Orange squares show recursive algorithm with $m=6$ and $\gamma =2^{-m-1}$. Lines denote scalings $2^{\alpha n}$, with $\alpha =1.5$ for the standard algorithm and $\alpha =0.5+0.65/m$ for the recursive algorithm. (b) Speedup $Q$ versus $n=k$ for standard algorithm (open markers) and recursive algorithm (solid markers) at interaction-to-decay ratios $\rho ={10}^3$ (green diamonds), $\rho ={10}^4$ (purple squares), and $\rho ={10}^5$ (red triangles).

Figure 8

Comparison of speedups $Q$ between two diffusion operator methods: $Q$ versus the interaction-to-decay ratio $\rho$ for the perfect diffusion operator (full lines) and the diffusion operator using the generalized oracle (dashed lines) for $n=k=(4,6,8,10)$, shaded from darkest to lightest.

Figure 9

Speedup scaling over all $(n,k)$, shown by plotting median total Grover iterations versus memoryless search trials required to reach $\mathcal{P}=0.99$ probability of success. Each point represents a particular $(n,k)$, where $n$ and $k$ each take values over the range $[3,16]$. Black and red lines denote linear and square root dependences, respectively.

Figure 10

Top: Amplification factor $G$ after one Grover iteration for a single representative instance of weights at $n$=$k$=12. Fits with the Lorentzian model of Eq. (E1) are shown as solid lines. Offset $B$ is the sole free fit parameter, which is related to $A$ by Eq. (E7). Bottom: Initial $S_z$ probability density distribution for $n=k=12$, averaged over ${10}^4$ instances (yellow points with shading). Expected initial distribution, a Gaussian with ${\sigma }_{S_z}=1$, shown as a solid orange line.

Figure 11

Comparison of the standard (blue circles) and recursive (orange squares) algorithms. (a) Success probability $P$ versus number of oracle queries $T$ for a single instance of number partitioning at $n=k=12$. Recursive algorithm is performed with $m=4$ and $\gamma =2^{-m-1}$. The physical time per query (at fixed $J_{\max }$) is longer by a factor of $2^{k-m-1}=2^7$ for the standard algorithm than for the recursive algorithm. (b) Median speedup ${\left[Q\right]}_{0.5}$ in query complexity, plotted versus $n=k$ for the standard algorithm with $\gamma ={\gamma }_c$ and the recursive algorithm with $m=6$ and $\gamma =2^{-m-1}$. Lines denote the $2^{0.5n}$ scaling for the standard algorithm and $2^{(0.5-0.65/m)n}$ scaling for the recursive algorithm. (c) Speedup ${\left[Q\right]}_{0.5}\gamma$ in physical runtime at fixed $J_{\max }$, plotted vs. $n=k$ for the standard algorithm with $\gamma ={\gamma }_c$ and the recursive algorithm with $m=6$ and $\gamma =2^{-m-1}$. Lines denote the $2^{-0.5n}$ scaling for the standard algorithm and $2^{(0.5-0.65/m)n}$ scaling for the recursive algorithm.

Figure 12

(a) Ratio of optimal step width $\gamma$ to critical step width ${\gamma }_c$ versus the interaction-to-decay ratio $\rho$ for $n=k=(4,6,8,10)$ denoted by markers shaded from darkest to lightest. (b) Optimal number of Grover iterations $T_{\mathrm{opt}}$ versus the interaction-to-decay ratio $\rho$ for $n=k=(4,6,8,10)$ denoted by markers shaded from darkest to lightest. Dashed lines represent the number of iterations $T_{\mathrm{opt}}$ at which the speedup is maximized in the ideal Grover’s algorithm.

Figure 13

(a) Central spin model realized by Rydberg-dressed atoms (red) interacting with ancilla qubit encoded on a ground-to-Rydberg transition (blue). (b) Central boson model realized by driving one-sided cavity coupled to system spins and heralding on photodetection.