betaFeedback

WorksPhysics and Astronomy

Classical dissipative search of unstructured database

Abstract

We propose a physical realization of the unstructured database search that works via classical, dissipative model of spherical spins. The database is implemented via spin-spin couplings, where the selected coupling refers to a larger ferromagnetic interaction between two selected spins. The low-temperature equilibrium of this model leads to magnetization strongly concentrated on the selected spins, which means that the search is complete. The search time refers to the relaxation time to equilibrium from a homogeneous initial state, and is described via Langevin equations. This time scales as O(Ma){\cal O}(M^a) with a<1/2a<1/2, where MM is the database volume. This is faster than Grover's search, showing how a dissipative, classical analog computer can overcome the quantum unitary computer.

Analog computers operate via continuous variables (e.g., magnetization or optical intensity) and encode the information directly, whereas usual digital computers work with discrete representations [1, 2]. Analog computers closely relate to the structure of the system they intend to simulate: they connect the computational model and the computing substrate. For centuries, analog computers were the only form of computation [2]. Starting from 1960s, digital computers drove them out, mostly because analog computers are not general-purpose. Nowadays, with the increased importance of computational speed and energy saving, analog computers are actively studied again via quantum computation [3], neuromorphic computation, and other approaches [4]. None of them will replace digital computers in the near future. However, studying analog computers is important, since they can be combined with digital ones, improving their speed and/or energy consumption; e.g., noisy, intermediate-scale quantum computers are considered from this perspective [5]. The major drawback of quantum computers is their strong sensitivity to noise (decoherence) [3, 5], which combines with other drawbacks of quantum computers (e.g., non-scalability) [6].

The unstructured database search is one of the main hallmarks of quantum computation, because the unitary quantum computers can perform this task much faster than classical digital computers [9, 10, 11]. In the simplest version, the unstructured database consists of M≫1M \gg1 elements, where M−1M-1 elements are identical, and one is selected. Once the database is unstructured, the classical digital computer should check one element after another, which makes, on average, (M+1)/2=O(M)(M+1)/2 = O(M) checking steps. A reformulation of this result highlights biophysical applications of the unstructured database search, where a target (selected) molecule should be found in a cell, or a target channel should be found in a membrane [7, 8]. Assume that the database consists of MM molecules (balls of size aa) homogeneously distributed in the cell; one of them is a selected target, which should be reached by a random walker (e.g., a protein). The characteristic of reaching the target is ∼M/(nDa)=O(M)\sim M/(nDa) = O(M), where nn is the concentration of molecules, and DD is the diffusion constant of the random walker in the cell [7]. The phenomenon of facilitated diffusion refers to introducing structural features into the database [7].

A quantum, unitary computer completes searches the unstructured database within M\sqrt{M} steps [9, 11] (Grover’s search), and this is the best possible result for such computers [10, 12]; cf. [13]. The analog implementation of Grover’s search looks for an MM-level quantum system, where one (selected) energy level has energy ΔE\Delta E, whereas all other energy levels have energy zero [11]. The quantum search time here amounts to running the Schroedinger dynamics for the MM-level system [11]. Grover’s search was generalized to classical waves with the same conclusion on the search time ∼M\sim\sqrt{M} [15, 16, 17].

We work out a classical, dissipative, long-range interacting many-body model for unstructured database search, where the search time scales as O(Ma)O(M^a) with a<1/2a < 1/2, i.e. it is better than Grover’s search. The advantage of this model is that it does not involve quantum coherence, hence it is not susceptible to the main source of noise (decoherence) that plagues standard quantum computers. Here, the computation process amounts to spontaneous relaxation towards equilibrium; i.e., there is no need to isolate the computer from its environment and thereby maintain a unitary evolution, or any other specific control operation. Thus, the search works via free energy minimization. In that sense, it is similar to dissipative physical devices performing various computational tasks; see [18] for a review.

Our model for unstructured database search is based on the spherical spin model, where the database is implemented via inter-spin interactions with one selected (ferromagnetic) interaction; see below. The final result is read off via magnetization measurements, which is concentrated on the two spins that interact via the selected interaction. These measurements take a shorter time than the relaxation, provided that the concentration is sufficiently strong. The drawback of this and all other classical search models is that the database is implemented via O(M)O(\sqrt{M}) classical spins. In the quantum situation, one needs O(ln⁡M)O(\ln M) quantum spins due to the tensor-product structure of composite quantum states [9– 11].

The spherical model relates to the Heisenberg O(n)O(n) spin model in the limit n≫1n \gg1 [19]. Due to its flexibility and solvability, the spherical model was applied to a wide range of problems, and led to a better understanding of new areas of statistical physics: phase-transition [20, 21]; spin-glass physics [22, 23, 24]; quantum critical systems [25]; etc. We show that it elucidates as well capabilities of classical dissipative computers.

The database and its selected element. The Hamiltonian HH of the spherical model is defined over NN real variables (spherical spins) SIS_I, where II is the space-index:

H=−12∑I≠J=1NJIJSISJ−ϵ∑I=1NhISI,(1)H=-\frac{1}{2}\sum_{I\ne J=1}^{N}\mathcal{J}_{IJ}S_IS_J-\epsilon\sum_{I=1}^{N}h_IS_I, \tag*{(1)}

where JIJ\mathcal{J}_{IJ} is the interaction matrix, and ϵhI\epsilon h_I are external fields (ϵ>0\epsilon>0). Eq. (1) is supplemented with the mean spherical constraint ∑I=1NSI2=N\sum_{I=1}^{N}S_I^2=N. It bounds energy HH and magnetization ∑I=1NSI\sum_{I=1}^{N}S_I and ensures well-defined equilibrium states.

For the interaction matrix J\mathcal{J} in (1) we assume that one among its M=N(N−1)/2M=N(N-1)/2 elements is selected, while all other elements are equivalent; e.g.,

J12=J21=R,JI≠J,I≥3=JI≠J,J≥3=JN−3,(2)\mathcal{J}_{12}=\mathcal{J}_{21}=R,\qquad\mathcal{J}_{I\ne J,I\ge3}=\mathcal{J}_{I\ne J,J\ge3}=\frac{J}{N-3}, \tag*{(2)}

where the spherical spins S1S_1 and S2S_2 interact via R=O(1)>0R=O(1)>0, while all other interactions go via JN−3\frac{J}{N-3} with J=O(1)J=O(1). This choice of RR and JJ ensures that the energy HH is O(N)O(N) for N≫1N\gg1. A selected interaction means a selected pair of spins; i.e., S1S_1 and S2S_2 for (2). The selected pair in the Hamiltonian (1) is unknown to us, though we know the values of RR and JJ. We want that in the equilibrium state generated by (1), the mean magnetization {SI‾}I=1N\{\overline{S_I}\}_{I=1}^{N} concentrates on I=1,2I=1,2. The maximal value allowed by the spherical constraint is S1‾=S2‾=O(N)\overline{S_1}=\overline{S_2}=O(\sqrt{N}), and we want this value to be much larger than the collective magnetization of all other (nonselected) spins ∑I≥3SI‾\sum_{I\ge3}\overline{S_I}. The concentration is sufficiently large to ensure that the selected spins can be found via O(ln⁡N)O(\ln N) finite-accuracy magnetization measurements; see below and also section 1 of Supplementary Material (SM).

Note that to get SI‾≠0\overline{S_I}\ne0, we need to have external fields in (1). These fields also should not know which interaction is selected. The search time is the relaxation to the equilibrium starting from some state that also does not know about the selected interaction. We see below that there is a trade-off: a larger S1‾=S2‾\overline{S_1}=\overline{S_2} requires longer relaxation time. But the search time O(Ma)O(M^a) with a<1/2a<1/2 is smaller than Grover’s search time.

Relaxation dynamics. The model is described via overdamped Langevin equations, where each spin SIS_I feels the conservative force −∂SIH-\partial_{S_I}H, friction force from the bath, and random noise [26, 27]. The inertia ∝S¨I\propto\ddot{S}_I is neglected assuming that the friction is strong. Recall that the Langevin equations are derived from system-bath Hamiltonian models, where the bath has an infinite number of degrees of freedom [27]. We use ket (bra) notations for column (row) vectors: ⟨S∣=(S1,…,SN)\langle S|=(S_1,\ldots,S_N), ⟨h∣=(h1,…,hN)\langle h|=(h_1,\ldots,h_N), and ⟨I∣=(0,…,1,…,0)\langle I|=(0,\ldots,1,\ldots,0), where the single 11 in ⟨I∣\langle I| is located at the IIth place. Langevin’s dynamics reads [26]:

ddt∣S(t)⟩=(J−z(t)I)∣S(t)⟩+ϵ∣h⟩+∣η(t)⟩,(3)\frac{d}{dt}|S(t)\rangle=(\mathcal{J}-z(t)\mathcal{I})|S(t)\rangle+\epsilon|h\rangle+|\eta(t)\rangle, \tag*{(3)}
⟨η∣=(η1,…,ηN),ηI(t)ηJ(t′)‾=2TδIJδ(t−t′),(4)\langle\eta|=(\eta_1,\ldots,\eta_N),\qquad\overline{\eta_I(t)\eta_J(t')}=2T\delta_{IJ}\delta(t-t'), \tag*{(4)}

where ∣η⟩|\eta\rangle is the random white noise with zero mean, η‾=0\overline{\eta}=0, TT is the temperature, z(t)z(t) is the Lagrange multiplier ensuring the mean spherical constraint ⟨S∣S⟩=N\langle S|S\rangle=N, and where the friction constant is 1. Eqs. (3), (4) is solved via the eigenresolution of the symmetric matrix J\mathcal{J}:

J∣λ⟩=λ∣λ⟩,⟨λ∣λ′⟩=δλλ′,λ,λ′=1,…,N,(5)\mathcal{J}|\lambda\rangle=\lambda|\lambda\rangle,\qquad\langle\lambda|\lambda'\rangle=\delta_{\lambda\lambda'},\qquad\lambda,\lambda'=1,\ldots,N, \tag*{(5)}
⟨λ∣S(t)⟩=eλt−z^(t)⟨λ∣S(0)⟩+ϵ⟨λ∣h⟩eλt−z^(t)×∫0tds e−λs+z^(s)+ϵeλt−z^(t)∫0tds e−λs+z^(s)⟨λ∣η(s)⟩,(6)\langle\lambda|S(t)\rangle=e^{\lambda t-\widehat{z}(t)}\langle\lambda|S(0)\rangle+\epsilon\langle\lambda|h\rangle e^{\lambda t-\widehat{z}(t)}\times \int_{0}^{t}ds\,e^{-\lambda s+\widehat{z}(s)}+\epsilon e^{\lambda t-\widehat{z}(t)}\int_{0}^{t}ds\,e^{-\lambda s+\widehat{z}(s)}\langle\lambda|\eta(s)\rangle, \tag*{(6)}
z^(t)=∫0tds z(s),⟨λ∣η(t)⟩‾=0,(7)\widehat{z}(t)=\int_{0}^{t}ds\,z(s),\qquad\overline{\langle\lambda|\eta(t)\rangle}=0, \tag*{(7)}
⟨λ∣η(t)⟩⟨λ′∣η(s)⟩‾=2Tδλλ′δ(t−s).(8)\overline{\langle\lambda|\eta(t)\rangle\langle\lambda'|\eta(s)\rangle}=2T\delta_{\lambda\lambda'}\delta(t-s). \tag*{(8)}

⟨λ∣S(0)⟩\langle\lambda|S(0)\rangle does not depend on ⟨λ∣η(t)⟩\langle\lambda|\eta(t)\rangle. The spherical constraint ⟨S∣S⟩=∑λ⟨λ∣S(t)⟩2=N\langle S|S\rangle=\sum_\lambda\langle\lambda|S(t)\rangle^2=N produces from (6) a non-linear integral equation for ez^(t)e^{\widehat{z}(t)}, which is solved for a large tt via [24]

ez^(t)≃e(σ+λ1)t,σ>0,(9)e^{\widehat{z}(t)}\simeq e^{(\sigma+\lambda_1)t},\qquad\sigma>0, \tag*{(9)}

where λ1\lambda_1 is the largest eigenvalue of J\mathcal{J}, and where the terms neglected in (9) are exponentially small for long times. Eqs. (6), (9) show that each ⟨λ∣S(t)⟩\langle\lambda|S(t)\rangle relaxes with its own relaxation time, but ⟨λ1∣S(t)⟩\langle\lambda_1|S(t)\rangle has the largest relaxation time 1/σ1/\sigma. Putting (9) into (6), using (7), and taking the large tt limit, we get in the stationary state

1=TN∑λ1σ+λ1−λ+ϵ2N⟨h∣[σ+λ1−J]−2∣h⟩,(10)1=\frac{T}{N}\sum_{\lambda}\frac{1}{\sigma+\lambda_1-\lambda}+\frac{\epsilon^2}{N}\langle h|[\sigma+\lambda_1-\mathcal{J}]^{-2}|h\rangle, \tag*{(10)}
SI‾=ϵ⟨I∣[σ+λ1−J]−1∣h⟩,(11)\overline{S_I}=\epsilon\langle I|[\sigma+\lambda_1-\mathcal{J}]^{-1}|h\rangle, \tag*{(11)}

where (10) comes from ⟨S∣S⟩=N\langle S|S\rangle=N and determines σ>0\sigma>0. Eq. (11) shows that SI‾→0\overline{S_I}\to0 if ϵ→0\epsilon\to0 for all other parameters being fixed. This follows from SI→SIS_I\to S_I symmetry of H∣ϵ→0H|_{\epsilon\to0} in (1). Eqs. (10), (11) are found as well from the equilibrium Gibbs distribution based on (1); see section 2 of SM. There σ\sigma relates to the Lagrange multiplier enforcing ⟨S∣S⟩=N\langle S|S\rangle=N.

The stationary state. Eqs. (10), (11) contain the eigenresolution of J\mathcal{J}, which reads from (1, 2):

J=∑k=13λk∣λk⟩⟨λk∣−JN−3ΠN−3,(12)\mathcal{J}=\sum_{k=1}^{3}\lambda_k\lvert\lambda_k\rangle\langle\lambda_k\rvert-\frac{J}{N-3}\Pi_{N-3}, \tag*{(12)}
λk=12[R+J±(R−J)2+8J2(N−2)(N−3)2],(13)\lambda_k=\frac{1}{2}\left[R+J\pm\sqrt{(R-J)^2+\frac{8J^2(N-2)}{(N-3)^2}}\right], \tag*{(13)}
⟨λk∣=12c2(λk)+N−2[c(λk),c(λk),1,1,…,1],(14)\langle\lambda_k\rvert=\frac{1}{\sqrt{2c^2(\lambda_k)+N-2}}[c(\lambda_k),c(\lambda_k),1,1,\ldots,1], \tag*{(14)}
c(λ)=J(N−2)(N−3)(λ−R),k=1,2,(15)c(\lambda)=\frac{J(N-2)}{(N-3)(\lambda-R)},\qquad k=1,2, \tag*{(15)}
λ3=−R,⟨λ3∣=12[1,−1,0,0,…,0],(16)\lambda_3=-R,\qquad\langle\lambda_3\rvert=\frac{1}{\sqrt{2}}[1,-1,0,0,\ldots,0], \tag*{(16)}

and where ΠN−3\Pi_{N-3} is a projector on the N−3N-3 dimensional subspace: [0,0,c3,…,cN][0,0,c_3,\ldots,c_N] with ∑k=3Nck=0\sum_{k=3}^{N}c_k=0:

ΠN−3=diag⁡[0,0,1,…,1]−1N−2∣e3⟩⟨e3∣,(17)\Pi_{N-3}=\operatorname{diag}[0,0,1,\ldots,1]-\frac{1}{N-2}\lvert e_3\rangle\langle e_3\rvert, \tag*{(17)}
⟨e3∣=(0,0,1,…,1).(18)\langle e_3\rvert=(0,0,1,\ldots,1). \tag*{(18)}

The orthogonality and normalization of the eigenvectors are seen from (12–15). Making natural assumptions

N≫1,R>J,J2N−1(R−J)−2≪1,(19)N\gg1,\qquad R>J,\qquad J^2N^{-1}(R-J)^{-2}\ll1, \tag*{(19)}

we get from (12–15):

λ1=R+2J2N(R−J),λ2=J−2J2N(R−J),(20)\lambda_1=R+\frac{2J^2}{N(R-J)},\qquad\lambda_2=J-\frac{2J^2}{N(R-J)}, \tag*{(20)}
⟨λ1∣=12(1,1,2JN(R−J),…,2JN(R−J)),(21)\langle\lambda_1\rvert=\frac{1}{\sqrt{2}}\left(1,1,\frac{2J}{N(R-J)},\ldots,\frac{2J}{N(R-J)}\right), \tag*{(21)}
⟨λ2∣=1N(JJ−R,JJ−R,1,…,1).(22)\langle\lambda_2\rvert=\frac{1}{\sqrt{N}}\left(\frac{J}{J-R},\frac{J}{J-R},1,\ldots,1\right). \tag*{(22)}

Figure 1 shows that for N≫1N\gg1 and weak external fields ϵ≪1\epsilon\ll1, the model described by (10, 11, 20–22) undergoes a phase-transition at T=RT=R, where the mean selected spins S‾1\overline{S}_1 and S‾2\overline{S}_2 start to grow. For T≤RT\leq R, the inverse relaxation time σ\sigma is small. Both σ\sigma and the mean non-selected spin S‾3\overline{S}_3 (and S‾I>3\overline{S}_{I>3}) are weakly-dependent on TT for T≤RT\leq R. Hence, we shall analytically study the regime of low temperatures T≪RT\ll R, where S‾1\overline{S}_1 and S‾2\overline{S}_2 maximize.

Image not extracted

Figure 1. For the spherical model [1, 10, 11, 20, 21, 22] we show the mean of the selected spin S‾1/200\overline{S}_1/200 (green), the mean of a nonselected spin S‾3\overline{S}_3 (red) and the inverse relaxation time σ\sigma as a function of temperature for N=104N=10^4, R=1R=1, J=0.2J=0.2, ϵ=0.05\epsilon=0.05 (weak fields). The external fields {hI}I=1N\{h_I\}_{I=1}^{N} are random Gaussian variables with w=1.54w=1.54, h1=0.33h_1=0.33, and h2=2.77h_2=2.77; see [25, 26, 27, 28]. T=RT=R is the phase-transition point, where S‾1\overline{S}_1 starts to increase from a nearly zero value to S‾1∝N\overline{S}_1\propto\sqrt{N} for T→0T\to0. σ\sigma monotonically decreases, assumes small values for T<RT<R, but does not decrease much for T<RT<R. S‾3\overline{S}_3 is nearly constant. For details of the plots see section 3 of SM.

Low temperatures. Eq. (10) simplifies in the limit T→0T\to0 (i.e., T≪RT\ll R). Now the terms ∝T\propto T in (10) can be neglected, and (10) is solved by noting that the inverse relaxation time σ\sigma tends for T→0T\to0 to a constant, σ=O(ϵN−1/2)\sigma=O(\epsilon N^{-1/2}), as confirmed in (23), and seen in Figure 1. Hence we can neglect σ\sigma everywhere besides the term λ=λ1\lambda=\lambda_1 in (10). The solution of (10) reads

ϵ∣⟨h∣λ1⟩∣σN=1−ϵ21N⟨h∣λ2⟩2(R−J)2−ϵ21N⟨h∣ΠN−3∣h⟩R2,(23)\frac{\epsilon\lvert\langle h\vert\lambda_1\rangle\rvert}{\sigma\sqrt{N}}=\sqrt{1-\frac{\epsilon^2\frac{1}{N}\langle h\vert\lambda_2\rangle^2}{(R-J)^2}-\frac{\epsilon^2\frac{1}{N}\langle h\vert\Pi_{N-3}\vert h\rangle}{R^2}}, \tag*{(23)}

where the term ∝1N⟨h∣λ3⟩2=O(1N)\propto\frac{1}{N}\langle h\vert\lambda_3\rangle^2=O\left(\frac{1}{N}\right) was neglected in (23); cf. (16). Note that ϵ\epsilon has to be sufficiently small for σ>0\sigma>0 in (23).

σ>0\sigma>0 in (23). Eq. (11) reads with the same approximation that led to (23):

S‾I=N⟨I∣λ1⟩sign⁡[⟨h∣λ1⟩]×1−ϵ21N⟨h∣λ2⟩2(R−J)2−ϵ21N⟨h∣ΠN−3∣h⟩R2+ϵ⟨I∣λ2⟩⟨λ2∣h⟩R−J+ϵ⟨I∣λ3⟩⟨λ3∣h⟩2R+ϵ⟨I∣ΠN−3∣h⟩R.(24)\overline{S}_I=\sqrt{N}\langle I\vert\lambda_1\rangle\operatorname{sign}[\langle h\vert\lambda_1\rangle]\times\sqrt{1-\frac{\epsilon^2\frac{1}{N}\langle h\vert\lambda_2\rangle^2}{(R-J)^2}-\frac{\epsilon^2\frac{1}{N}\langle h\vert\Pi_{N-3}\vert h\rangle}{R^2}}+\frac{\epsilon\langle I\vert\lambda_2\rangle\langle\lambda_2\vert h\rangle}{R-J}+\frac{\epsilon\langle I\vert\lambda_3\rangle\langle\lambda_3\vert h\rangle}{2R}+\frac{\epsilon\langle I\vert\Pi_{N-3}\vert h\rangle}{R}. \tag*{(24)}

Note that S‾I2=S‾12\overline{S}_I^2=\overline{S}_1^2, as expected for T=0T=0.

Random external fields. In (24) we can assume that the external fields {hI}I=1N\{h_I\}_{I=1}^{N} in (1) are homogeneous: hk=1h_k=1. This assumption leads to the same scaling 1/σ=O(N)=O(M)1/\sigma=O(N)=O(\sqrt{M}) of the relaxation time as in Grover’s search; see SM section 1. Instead, we assume that each hkh_k in ∣h⟩=(h1,…,hN)\lvert h\rangle=(h_1,\ldots,h_N) is Gaussian random variables with zero mean and dispersion 1. Recall that {hI}I=1N\{h_I\}_{I=1}^{N} should not know about selected spins 1 and 2. We show that random external fields do not influence the magnetization of the selected spins, while the magnetization of nonselected spins is suppressed. We consider only a single realization of random variables {hI}I=1N\{h_I\}_{I=1}^{N}. Eqs. (17–22) imply

⟨e3∣h⟩=∑k=3Nhk=wN,(25)\langle e_3\vert h\rangle=\sum_{k=3}^{N}h_k=w\sqrt{N}, \tag*{(25)}
1N⟨h∣ΠN−3∣h⟩=1+O(1N),(26)\frac{1}{N}\langle h\vert\Pi_{N-3}\vert h\rangle=1+O\left(\frac{1}{\sqrt{N}}\right), \tag*{(26)}
⟨h∣λ2⟩=w+h1+h2NJJ−R=w+O(1N),(27)\langle h\vert\lambda_2\rangle=w+\frac{h_1+h_2}{\sqrt{N}}\frac{J}{J-R}=w+O\left(\frac{1}{\sqrt{N}}\right), \tag*{(27)}
⟨I∣ΠN−3∣h⟩=[hI−⟨e3∣h⟩N−2]δI≥3,(28)\langle I\vert\Pi_{N-3}\vert h\rangle=\left[h_I-\frac{\langle e_3\vert h\rangle}{N-2}\right]\delta_{I\geq3}, \tag*{(28)}

where ww is a Gaussian random variable with zero mean and dispersion 1. Using (25–28) in (24) we get

S‾I=1,2=N2sign⁡[h1+h2]1−ϵ2R2(29)\overline{S}_{I=1,2}=\sqrt{\frac{N}{2}}\operatorname{sign}[h_1+h_2]\sqrt{1-\frac{\epsilon^2}{R^2}} \tag*{(29)}
+ϵ(h1−h2)(δI1−δI2)4R−ϵNJ(δI1+δI2)⟨λ2∣h⟩(R−J)2,(30)+\frac{\epsilon(h_1-h_2)(\delta_{I1}-\delta_{I2})}{4R}-\frac{\epsilon}{\sqrt{N}}\frac{J(\delta_{I1}+\delta_{I2})\langle\lambda_2\mid h\rangle}{(R-J)^2}, \tag*{(30)}
S‾I≥3=N2JR−Jsign⁡[h1+h2]1−ϵ2R2(31)\overline{S}_{I\geq3}=\sqrt{\frac{N}{2}}\frac{J}{R-J}\operatorname{sign}[h_1+h_2]\sqrt{1-\frac{\epsilon^2}{R^2}} \tag*{(31)}
+ϵ⟨λ2∣h⟩(R−J)N+ϵ[hI−ϵ3hN−2]R.(32)+\frac{\epsilon\langle\lambda_2\mid h\rangle}{(R-J)\sqrt{N}}+\frac{\epsilon\left[h_I-\frac{\epsilon_3 h}{N-2}\right]}{R}. \tag*{(32)}

The first term ∝Nsign⁡[h1+h2]\propto\sqrt{N}\operatorname{sign}[h_1+h_2] is the RHS of (29) is the amplification of S‾I=1,2\overline{S}_{I=1,2} due to R>JR>J. The sign (but not magnitude) of S‾I=1,2\overline{S}_{I=1,2} is random and it depends on the sign of the total field h1+h2h_1+h_2 acting on the two selected spins. The term ∝J\propto J in (31) is induced by the coupling to the selected spins.

We want to show that the selected spins S1S_1 and S2S_2 can be found in O(ln⁡[N])O(\ln[N]) steps via measuring the mean magnetization of properly defined subsets of {I≥1}\{I\geq1\}. Eqs. (29)–(32) are sufficient for this purpose, since they show that S‾1=S‾2=O(N)\overline{S}_1=\overline{S}_2=O(\sqrt{N}) have the same order of magnitude as ∑I≥3S‾I\sum_{I\geq3}\overline{S}_I. But to make our reasoning more transparent, we consider a sufficiently small JJ so that the term ∝J\propto J in (31) can be neglected. Retaining this term does not alter our main conclusions; see section 4 of SM. We intend to show that in any generic subset of spins containing spins S1S_1 and/or S2S_2, the collective magnetization of the subset, is dominated by S‾1\overline{S}_1 and/or S‾2\overline{S}_2, and is larger than in any subset not containing them. Here, generic means chosen in a way that is not correlated with the distribution of {hI}I≥1\{h_I\}_{I\geq1}. Let KK be such a KK-spin subset of {I≥3}\{I\geq3\}. We get from (27, 32) (neglecting (31)):

∑I∈KS‾I=KϵwK(R−J)N+ϵRNKN(NKwK−w),(33)\sum_{I\in K}\overline{S}_I=\frac{K\epsilon w_K}{(R-J)\sqrt{N}}+\frac{\epsilon}{R\sqrt{N}}\frac{K}{N}\left(\sqrt{\frac{N}{K}}w_K-w\right), \tag*{(33)}

where wK=1K∑I∈KhIw_K=\frac{1}{\sqrt{K}}\sum_{I\in K}h_I is a Gaussian with mean zero and variance 1. ww and wKw_K are correlated random variables. The maximal value of (33) is reached for K∼NK\sim N and scales as O(ϵN)O(\epsilon\sqrt{N}). Comparing this with the dominant term ∝Nsign⁡[h1+h2]\propto\sqrt{N}\operatorname{sign}[h_1+h_2] in (29), we see that for ϵ=O(N−ζ)\epsilon=O(N^{-\zeta}) (with ζ>0\zeta>0), the two selected spins S‾I=1,2\overline{S}_{I=1,2} will dominate the behavior of any generic subset of {I≥1}\{I\geq1\}, which includes S‾I=1\overline{S}_{I=1} or S‾I=2\overline{S}_{I=2}. If such a set does contain neither S1S_1, nor S2S_2, then its mean magnetization will be much smaller than for a set containing S1S_1 or S2S_2. Eq. (33) can be much larger than O(N−ζ+1/2)O(N^{-\zeta+1/2}) only due to e.g. ∣w∣≫1|w|\gg1. Such events are very rare and can be neglected.

Likewise, with ϵ=O(N−ζ)\epsilon=O(N^{-\zeta}) we find from (23, 27, 28) for the relaxation time: 1/σ=O(Nζ+0.5)1/\sigma=O(N^{\zeta+0.5}). For 0<ζ<1/20<\zeta<1/2 this search time is shorter than the Grover search time O(N)O(N).

The above concentration feature means that the selected spins S1S_1 and S2S_2 can be found recursively: the total set of {I≥1}\{I\geq1\} spins is divided into two (not necessarily strictly equal) generic subsets and their (mean) magnetizations re measured. If one of the subsets contains at least one selected spin, its magnetization will be O(N0.5)O(N^{0.5}). Otherwise, the magnetization will be at best O(N0.5−ζ)O(N^{0.5-\zeta}). The relative error of distinguishing such subsets from each other goes to zero for N→∞N\to\infty. Then the target subset is divided into generic subsubsets, etc. It should be clear that the number of steps for identifying both selected spins will then scale O(ln⁡[N])O(\ln[N]), which is much smaller than the relaxation time needed to amplify the selected spins.

Conclusion

We studied the unstructured database search problem via tools and models of classical statistical mechanics. This is a relevant strategy in view of biophysical applications of the database search: the protein folding problem, the performance optimization of small heat-engines [28], the target reaching problem in cell biology [7] (c.f. the introduction), etc. We studied the classical two-body interacting spherical model for illustrating the ideas of classical dissipative search, since this model is solvable starting from three Langevin equations. Other models (e.g., multi-body interacting spherical model [23, 29]) might show a better performance as search engines.

The HESC of Armenia supported us under grants 24FP-1F030 and 21AG-1C038. We thank Y. Mamasakhlisov and V. Stepanyan for discussions. unstructured database search, where even smaller search times are possible. However, the framework of [14] is phenomenological and does not involve explicit microscopic mechanisms. This major drawback is corrected here on the classical level.

Description: This Supplementary Material consists of the following sections. Section 1 discusses our basic assumptions: the accuracy of magnetization measurements is finite in the thermodynamic limit. This is exemplified for the spherical model under the homogeneous external field. It shown in detail why the search time here has the same order of magnitude as for Grover’s search. Section 2 discusses the partition function of the equilibrium spherical model. The presentation here is standard and follows [20, 21]. The purpose of section 2 is to confirm that Eqs. (10), (11) of the main text that were deduced in the main text from the Langevin equations can also be recovered from the equilibrium analysis. Section 3 addresses the ferromagnetic phase-transition and shows parameters and settings of Figure 1 in the main text. Section 4 provides the details of the derivation presented after Eq. (33) of the main text. The formulas in this Supplementary Material are written as (S1, S2, ...). Usual formulas refer to the main text and are indicated explicitly, e.g.: Eq. (1) of the main text.

Finite-accuracy magnetization measurements and the spherical model under homogeneous external field

We consider the homogeneous external field: ∣h⟩=(1,1,…,1)\lvert h\rangle= (1,1,\ldots,1). Using Eqs. (12)–(15) of the main text, ⟨R∣h⟩=0\langle R\lvert h\rangle= 0 and ΠN−3∣h⟩=0\Pi_{N-3}\lvert h\rangle= 0, we get from Eq. (24) of the main text:

σ=ϵN2RR−J(1−ϵ2(R−J)2)−1/2,(34)\sigma= \frac{\epsilon}{\sqrt{N}}\frac{\sqrt{2}R}{R-J}\left(1-\frac{\epsilon^2}{(R-J)^2}\right)^{-1/2}, \tag*{(34)}
S‾I=N[⟨I∣λ1⟩(1−ϵ2(R−J)2)1/2+ϵR−J⟨I∣λ2⟩],(35)\overline{S}_I = \sqrt{N}\left[\langle I\lvert\lambda_1\rangle\left(1-\frac{\epsilon^2}{(R-J)^2}\right)^{1/2}+\frac{\epsilon}{R-J}\langle I\lvert\lambda_2\rangle\right], \tag*{(35)}
S‾I=1,2=N2(1−ϵ2(R−J)2)1/2−ϵJ(R−J)2,(36)\overline{S}_{I=1,2} = \sqrt{\frac{N}{2}}\left(1-\frac{\epsilon^2}{(R-J)^2}\right)^{1/2}-\frac{\epsilon J}{(R-J)^2}, \tag*{(36)}
S‾I≥3=ϵR−J+2N(1−ϵ2(R−J)2)1/2JR−J,(37)\overline{S}_{I\geq3} = \frac{\epsilon}{R-J}+\sqrt{\frac{2}{N}}\left(1-\frac{\epsilon^2}{(R-J)^2}\right)^{1/2}\frac{J}{R-J}, \tag*{(37)}

where ⟨I∣λ1⟩\langle I\lvert\lambda_1\rangle and ⟨I∣λ2⟩\langle I\lvert\lambda_2\rangle in (S1) and (S2) are deduced from Eq. (21) and Eq. (22) of the main text, respectively.

Now (S1) provides the inverse relaxation time, while (S2, S3, S4) describe magnetizations. The spatial distribution of S‾I\overline{S}_I concentrates on those two spherical spins S‾1\overline{S}_1 and S‾2\overline{S}_2 that interact via the biased bond with the strength RR. When this concentration is strong enough for our purposes?

We want to find the selected spins S1S_1 and S2S_2 by dividing the spins into two equal-size groups. Assume for simplicity that the two selected spins are in the first group. First, assume that ϵ=O(1)\epsilon= O(1) in (S3, S4). Then the mean magnetization of the first and the second group are, respectively [see (S3, S4)],

ϵNR−J+2N(1−ϵ2(R−J)2)1/2andϵNR−J.(38)\frac{\epsilon N}{R-J}+\sqrt{2N}\left(1-\frac{\epsilon^2}{(R-J)^2}\right)^{1/2} \quad\text{and}\quad \frac{\epsilon N}{R-J}. \tag*{(38)}

To distinguish these two signals from each other, the error (or the inverse accuracy) of the measuring device should be smaller than the relative difference between the two signals, i.e., smaller than O(N−1/2)O(N^{-1/2}), which is negligible in the thermodynamic limit N≫1N\gg1. The same results is found when the selected spins are in different groups.

Hence distinguishing between the signals (S5) demands excessively accurate measurements. We exclude such measurements from our consideration by demanding the measurement accuracy stays finite in the thermodynamic limit N≫1N\gg1. This demand is completely standard and is present as well in all unstructured database problems, which are supposed to operate in the thermodynamic limit (i.e., for large databases).

Instead of ϵ=O(1)\epsilon= O(1), we now assume in (S3, S4) that

ϵ=ϵ^N−1/2,ϵ^=O(1).(39)\epsilon= \hat{\epsilon}N^{-1/2}, \qquad\hat{\epsilon}=O(1). \tag*{(39)}

Instead of (S5), we now find from (S3, S4) for the mean magnetizations of the first and second groups:

2N+ϵ^N+2NJR−Jandϵ^N+2NJR−J.(40)\sqrt{2N}+\frac{\hat{\epsilon}\sqrt{N}+\sqrt{2N}J}{R-J} \quad\text{and}\quad \frac{\hat{\epsilon}\sqrt{N}+\sqrt{2N}J}{R-J}. \tag*{(40)}

Now the relative difference between the signals is O(1)\mathcal{O}(1), i.e., sufficiently accurate (but finite for N≫1N \gg1) measurements can distinguish between the two signals in (S7). Note that this conclusion is based on knowing sufficiently precisely the number of spins in each group. The error in this knowledge should be much smaller than N/2N/2 (the number of elements in each group).

Note from (S1) that ϵ∝N−1/2\epsilon\propto N^{-1/2} means that the relaxation time 1/σ1/\sigma is O(N)\mathcal{O}(N), which is the Grover regime. We conclude that once finite-accuracy measurements are employed, the homogeneous fields do not improve the quantum search time.

Continuing along these lines, we shall reach groups whose size is smaller than O(N)\mathcal{O}(N). For such groups, we find instead of (S5)

ϵKR−J+2N(1−ϵ2(R−J)2)1/2andϵKR−J,(41)\frac{\epsilon K}{R-J}+\sqrt{2N}\left(1-\frac{\epsilon^2}{(R-J)^2}\right)^{1/2} \quad\text{and}\quad \frac{\epsilon K}{R-J}, \tag*{(41)}

where KK is the group size: K≪NK \ll N. Naturally, such two signals are much easier to distinguish than those in (S5).

To close this section, let us discuss why one cannot design an analog search engine with the spherical model, where no inter-spin couplings are involved. To this end, consider

H=−ϵ∑I=1NhISI,(42)H=-\epsilon\sum_{I=1}^{N}h_I S_I, \tag*{(42)}

where ϵhI\epsilon h_I are external fields (ϵ>0\epsilon>0), and where the spherical constraint ∑I=1NSI2‾=N\sum_{I=1}^{N}\overline{S_I^2}=N is assumed. Note that the size of the database is now NN, since the database is constructed via external fields.

Now Eqs. (10, 11) of the main text read:

1=Tσ+ϵ2σ21N⟨h∣h⟩,(43)1=\frac{T}{\sigma}+\frac{\epsilon^2}{\sigma^2}\frac{1}{N}\langle h|h\rangle, \tag*{(43)}
SI‾=ϵhIσ.(44)\overline{S_I}=\frac{\epsilon h_I}{\sigma}. \tag*{(44)}

Eq. (S10) is a quadratic equation for 1/σ1/\sigma, which is solved for T→0T\to0, as

ϵσ=N⟨h∣h⟩.(45)\frac{\epsilon}{\sigma}=\sqrt{\frac{N}{\langle h|h\rangle}}. \tag*{(45)}

Hence, we find from (S11) for T→0T\to0:

SI‾=hIN⟨h∣h⟩,SI‾−SJ‾SI‾=hI−hJhI.(46)\overline{S_I}=h_I\sqrt{\frac{N}{\langle h|h\rangle}},\qquad \frac{\overline{S_I}-\overline{S_J}}{\overline{S_I}}=\frac{h_I-h_J}{h_I}. \tag*{(46)}

It is seen from (S13) that the potential amplification factor N⟨h∣h⟩\sqrt{\frac{N}{\langle h|h\rangle}} is the same for all spins, and the relative spin differences are equal to those of the external fields. Since we evaluate the mean magnetization of various subsets of {I≥1}\{I\ge1\} based on the relative magnetization differences, the usage of the spherical model will not provide any advantage; see (S13).

Gibbsian equilibrium of the spherical model

The statistical sum reads from Hamiltonian

H=−12∑I≠J=1NJIJSISJ−ϵ∑I=1NhISI,(47)H=-\frac{1}{2}\sum_{I\ne J=1}^{N}J_{IJ}S_I S_J-\epsilon\sum_{I=1}^{N}h_I S_I, \tag*{(47)}

and the spherical constraint ∑I=1NSI2=N\sum_{I=1}^{N}S_I^2=N:

Z=∫∏I=1NdSI e−βH[S]δ(∑I=1NSI2−N)=∫∏I=1NdSI∫Reu−i∞Reu+i∞du2πieNu−∑I,J(uδIJ−βJIJ2)SISJ+βϵ∑IhISI(48)Z=\int\prod_{I=1}^{N}dS_I\,e^{-\beta H[S]}\delta\left(\sum_{I=1}^{N}S_I^2-N\right) =\int\prod_{I=1}^{N}dS_I\int_{\mathop{\mathrm{Re}}u-i\infty}^{\mathop{\mathrm{Re}}u+i\infty}\frac{du}{2\pi i}e^{Nu-\sum_{I,J}\left(u\delta_{IJ}-\frac{\beta J_{IJ}}{2}\right)S_I S_J+\beta\epsilon\sum_I h_I S_I} \tag*{(48)}
=πN/2∫Reu−i∞Reu+i∞du2πieNg(u),Reu>βλmax⁡2,(49)=\pi^{N/2}\int_{\mathop{\mathrm{Re}}u-i\infty}^{\mathop{\mathrm{Re}}u+i\infty}\frac{du}{2\pi i}e^{Ng(u)},\qquad\mathop{\mathrm{Re}}u>\frac{\beta\lambda_{\max}}{2}, \tag*{(49)}
g(u)≡u−12N∑λln⁡(u−βλ2)+ϵ2β24N⟨h∣[uI−β2J]−1∣h⟩,(50)g(u)\equiv u-\frac{1}{2N}\sum_{\lambda}\ln\left(u-\frac{\beta\lambda}{2}\right)+\frac{\epsilon^2\beta^2}{4N}\langle h|\left[u\mathcal{I}-\frac{\beta}{2}\mathcal{J}\right]^{-1}|h\rangle, \tag*{(50)}

where I={δIJ}\mathcal{I} = \{\delta_{IJ}\} is the unity matrix, and where in the integration over uu we demand ℜu>βλmax⁡2\Re u > \frac{\beta\lambda_{\max}}{2} with λmax⁡\lambda_{\max} being the maximal eigenvalue of JIJ\mathcal{J}_{IJ}. {λ}\{\lambda\} are eigenvalues of matrix J\mathcal{J}. When going from (S15) to (S16) we changed variables as

∣S′⟩=∣S⟩−βϵ2[uI−β2J]−1∣h⟩,(51)\lvert S'\rangle= \lvert S\rangle- \frac{\beta\epsilon}{2}\left[u\mathcal{I} - \frac{\beta}{2}\mathcal{J}\right]^{-1}\lvert h\rangle, \tag*{(51)}

and took the Gaussian integrals over S′S'. Condition ℜu>βλmax⁡2\Re u > \frac{\beta\lambda_{\max}}{2} is needed for ensuring the convergence of these integrals.

The integral in (S16) is taken via the saddle-point method for N≫1N \gg1. The saddle-point value is determined from

∂g∂u=1−12N∑λ1u−βλ2−ϵ2β24N⟨h∣[u−β2J]−2∣h⟩=0,(52)\frac{\partial g}{\partial u} = 1 - \frac{1}{2N}\sum_{\lambda}\frac{1}{u-\frac{\beta\lambda}{2}}-\frac{\epsilon^{2}\beta^{2}}{4N}\langle h\lvert\left[u-\frac{\beta}{2}\mathcal{J}\right]^{-2}\rvert h\rangle=0, \tag*{(52)}
∂2g∂u2>0,(53)\frac{\partial^{2}g}{\partial u^{2}}>0, \tag*{(53)}

where the last relation means that for real value of uu, g(u)g(u) has to have a minimum, and then for imaginary uu it will have a maximum, and lead to the saddle-point method for N≫1N\gg1. Note that (S17) implies

1β∂g∂ϵ=1N∑I=1NS‾IhI,(54)\frac{1}{\beta}\frac{\partial g}{\partial\epsilon}=\frac{1}{N}\sum_{I=1}^{N}\overline{S}_{I}h_{I}, \tag*{(54)}

where S‾I\overline{S}_{I} means averaging over the Gibbs distribution; see (S15). Now (S19) shows that ∂g∂ϵ=∂g∂ϵ∣u\frac{\partial g}{\partial\epsilon}=\left.\frac{\partial g}{\partial\epsilon}\right|_{u}, i.e. from (S21) we find

1N∑I=1NS‾IhI=ϵβ2N⟨h∣[uI−β2J]−1∣h⟩.(55)\frac{1}{N}\sum_{I=1}^{N}\overline{S}_{I}h_{I}=\frac{\epsilon\beta}{2N}\langle h\lvert\left[u\mathcal{I}-\frac{\beta}{2}\mathcal{J}\right]^{-1}\rvert h\rangle. \tag*{(55)}

Eq. (S22) can be also obtained from (S18). After applying to this equation ∣S′⟩=0\lvert S'\rangle=0 (only Gaussian integrals are involved that symmetric with respect to SI′→−SI′S'_{I}\rightarrow-S'_{I}), we get

∣S‾⟩=βϵ2[uI−β2J]−1∣h⟩=βϵ2∑λ⟨λ∣h⟩u−βλ2∣λ⟩,(56)\lvert\overline{S}\rangle=\frac{\beta\epsilon}{2}\left[u\mathcal{I}-\frac{\beta}{2}\mathcal{J}\right]^{-1}\lvert h\rangle=\frac{\beta\epsilon}{2}\sum_{\lambda}\frac{\langle\lambda\lvert h\rangle}{u-\frac{\beta\lambda}{2}}\lvert\lambda\rangle, \tag*{(56)}

where uu is determined from (S19).

Let S^λ\hat{S}_{\lambda} be the normal modes obtained after the diagonalizing orthogonal transformation in (S15, S18):

SI′=∑λ⟨I∣λ⟩S^λ,S^λ=∑I⟨λ∣I⟩SI′(57)S'_{I}=\sum_{\lambda}\langle I\lvert\lambda\rangle\hat{S}_{\lambda},\qquad\hat{S}_{\lambda}=\sum_{I}\langle\lambda\lvert I\rangle S'_{I} \tag*{(57)}

Using (S15) we get

S^λ2‾=12(u−βλ2),SI′2‾=12∑λ⟨λ∣I⟩2u−βλ2,SI′‾=0.(58)\overline{\hat{S}_{\lambda}^{2}}=\frac{1}{2\left(u-\frac{\beta\lambda}{2}\right)},\qquad\overline{S'_{I}{}^{2}}=\frac{1}{2}\sum_{\lambda}\frac{\langle\lambda\lvert I\rangle^{2}}{u-\frac{\beta\lambda}{2}},\qquad\overline{S'_{I}}=0. \tag*{(58)}

Eqs. (S25), (11), (S18) imply

SI2‾=12∑λ⟨λ∣I⟩2u−βλ2+β2ϵ24⟨I∣[u−β2J]−1∣h⟩2.(59)\overline{S_{I}^{2}}=\frac{1}{2}\sum_{\lambda}\frac{\langle\lambda\lvert I\rangle^{2}}{u-\frac{\beta\lambda}{2}}+\frac{\beta^{2}\epsilon^{2}}{4}\langle I\lvert\left[u-\frac{\beta}{2}\mathcal{J}\right]^{-1}\rvert h\rangle^{2}. \tag*{(59)}

Now summing (S26) over II we revert to the spherical constraint (S19), which clarifies its physical meaning. In the same way, we calculate the mean energy from (1, S17, S19):

1NH‾=T(1−2u)2−ϵ2β4N⟨h∣[u−β2J]−1∣h⟩.(60)\frac{1}{N}\overline{H}=\frac{T(1-2u)}{2}-\frac{\epsilon^{2}\beta}{4N}\langle h\lvert\left[u-\frac{\beta}{2}\mathcal{J}\right]^{-1}\rvert h\rangle. \tag*{(60)}

The general concept of phase-transitions in the spherical model is that for sufficiently low temperatures, the saddle-point solution uu in (S19) approaches for ϵ→0\epsilon\to0 to its limiting value βλmax⁡2\frac{\beta\lambda_{\max}}{2}. Further clarifications of the phase-transition scenario demand understanding the eigen-structure of J\mathcal{J}. On regular lattices, the eigenvalues of J\mathcal{J} converge (in the thermodynamic limit N≫1N \gg1) to a well-defined distribution [20, 21]. Hence, (S19, S22) do not depend on NN and can be studied directly in the thermodynamic limit [20, 21].

The parameter (Lagrange multiplier) uu obeying (S19) relates to the parameter σ\sigma used in the main text:

σ=2uT−λ1,(61)\sigma= 2uT-\lambda_1, \tag*{(61)}

where λ1\lambda_1 is the maximal eigenvalue of the matrix J\mathcal{J} in (S15).

Finite temperatures and phase-transition in the spherical model

Here we explain details of Figure 1. Let us first note more detailed versions of Eqs. (25)–(28) of the main text:

⟨e3∣h⟩=∑k=3Nhk=wN,(62)\langle e_3|h\rangle= \sum_{k=3}^{N}h_k = w\sqrt{N}, \tag*{(62)}
1N⟨h∣ΠN−3∣h⟩=1N∑k=3Nhk2−⟨e3∣h⟩2N(N−2)=1+1N∑k=3N(hk2−1)+O(1N)=1+w1N+O(1N),(63)\frac{1}{N}\langle h|\Pi_{N-3}|h\rangle= \frac{1}{N}\sum_{k=3}^{N}h_k^2-\frac{\langle e_3|h\rangle^2}{N(N-2)} = 1+\frac{1}{N}\sum_{k=3}^{N}(h_k^2-1)+O\left(\frac{1}{N}\right)=1+\frac{w_1}{\sqrt{N}}+O\left(\frac{1}{N}\right), \tag*{(63)}
⟨h∣λ1⟩=h1+h22+2JwN(R−J)=h1+h22+O(1N),(64)\langle h|\lambda_1\rangle= \frac{h_1+h_2}{\sqrt{2}}+\frac{2Jw}{\sqrt{N}(R-J)}=\frac{h_1+h_2}{\sqrt{2}}+O\left(\frac{1}{\sqrt{N}}\right), \tag*{(64)}
⟨h∣λ2⟩=w+h1+h2NJJ−R=w+O(1N),(65)\langle h|\lambda_2\rangle= w+\frac{h_1+h_2}{\sqrt{N}}\frac{J}{J-R}=w+O\left(\frac{1}{\sqrt{N}}\right), \tag*{(65)}
⟨h∣λ3⟩=h1−h22,(66)\langle h|\lambda_3\rangle= \frac{h_1-h_2}{\sqrt{2}}, \tag*{(66)}
⟨I∣ΠN−3∣h⟩=[hI−⟨e3∣h⟩N−2]δI≥3,(67)\langle I|\Pi_{N-3}|h\rangle= \left[h_I-\frac{\langle e_3|h\rangle}{N-2}\right]\delta_{I\geq3}, \tag*{(67)}

where ww is a Gaussian random variable with zero mean and dispersion 1; for N≫1N\gg1, w1w_1 also converges to a Gaussian random variable with zero mean and dispersion 1.

We obtain from (S29–S34) and Eqs. (10), (11) of the main text:

0=−1+TN[1σ+1σ+R−J+1σ+2R+Nσ+R]+ϵ2N[⟨h∣λ1⟩2σ2+⟨h∣λ2⟩2(σ+R−J)2+⟨h∣λ3⟩2(σ+2R)2+N+w1N(σ+R)2],(68)0=-1+\frac{T}{N}\left[\frac{1}{\sigma}+\frac{1}{\sigma+R-J}+\frac{1}{\sigma+2R}+\frac{N}{\sigma+R}\right]+\frac{\epsilon^2}{N}\left[\frac{\langle h|\lambda_1\rangle^2}{\sigma^2}+\frac{\langle h|\lambda_2\rangle^2}{(\sigma+R-J)^2}+\frac{\langle h|\lambda_3\rangle^2}{(\sigma+2R)^2}+\frac{N+w_1\sqrt{N}}{(\sigma+R)^2}\right], \tag*{(68)}
S‾1=ϵ⟨h∣λ1⟩2σ+ϵ⟨h∣λ2⟩N(J−R)(σ+R−J)+ϵ⟨h∣λ3⟩2(σ+2R),(69)\overline{S}_1=\frac{\epsilon\langle h|\lambda_1\rangle}{\sqrt{2\sigma}}+\frac{\epsilon\langle h|\lambda_2\rangle}{\sqrt{N(J-R)(\sigma+R-J)}}+\frac{\epsilon\langle h|\lambda_3\rangle}{\sqrt{2(\sigma+2R)}}, \tag*{(69)}
S‾3=2ϵJ⟨h∣λ1⟩N(R−J)σ+ϵ⟨h∣λ2⟩N(σ+R−J)+ϵ(h3−wN)σ+R.(70)\overline{S}_3=\frac{\sqrt{2\epsilon J}\langle h|\lambda_1\rangle}{N(R-J)\sigma}+\frac{\epsilon\langle h|\lambda_2\rangle}{\sqrt{N}(\sigma+R-J)}+\frac{\epsilon\left(h_3-\frac{w}{\sqrt{N}}\right)}{\sigma+R}. \tag*{(70)}

Figure 1 is contructed via (S35–S37), where we have put w1→0w_1\to0 for simplicity.

Further details on the derivation after Eq. (33) of the main text

We noted after Eqs. (29)–(32) of the main text that S‾1=O(N)\overline{S}_1=O(\sqrt{N}) and S‾2=O(N)\overline{S}_2=O(\sqrt{N}). After Eq. (33) of the main text we argued that provided that ϵ=O(N−ζ)\epsilon=O(N^{-\zeta}) with 0<ζ<1/20<\zeta<1/2, we ensure the relaxation time 1/σ=O(Nζ+0.5)1/\sigma=O(N^{\zeta+0.5}), and we achieve the mean magnetization O(N0.5−ζ)O(N^{0.5-\zeta}) for subsets of {I≥1}\{I\geq1\} that contain O(N)O(N) spins and do not contain the two selected spins S1S_1 and S2S_2. However, these conclusions was obtained after neglecting the term given by Eq. (31) of the main text. Now we retain this term. The reasoning here is similar to that in section 1. We repeat it for clarity and completeness.

Let K\mathcal{K} be a generic KK-spin subset of {I≥3}\{I\geq3\}, i.e., K\mathcal{K} does not contain the selected spins S1S_1 and S2S_2. Here generic means chosen in a way that is not correlated with the distribution of {hI}I≥1\{h_I\}_{I\geq1}. We get from Eqs. (27), (32) of the main text:

∑I∈KS‾I=f(K)+2NJKR−Jsign⁡[h1+h2]1−ϵ2R2,(71)\sum_{I\in\mathcal{K}}\overline{S}_I=f(\mathcal{K})+\sqrt{\frac{2}{N}}\frac{JK}{R-J}\operatorname{sign}[h_1+h_2]\sqrt{1-\frac{\epsilon^2}{R^2}}, \tag*{(71)}
f(K)≡Kϵw(R−J)N+ϵRKN(NKwK−w),wK=1K∑I∈KhI.(72)f(\mathcal{K})\equiv\frac{K\epsilon w}{(R-J)\sqrt{N}}+\frac{\epsilon}{R}\frac{K}{\sqrt{N}}\left(\sqrt{\frac{N}{K}}w_{\mathcal{K}}-w\right),\qquad w_{\mathcal{K}}=\frac{1}{\sqrt{K}}\sum_{I\in\mathcal{K}}h_I. \tag*{(72)}

Likewise, let L\mathcal{L} be a generic LL-spin subset of {I≥1}\{I\geq1\} that contains the selected spin S1S_1 and does not contain S2S_2.

(Subsets that contain both selected spins are treated in a similar way.) We have from Eq. (29) of the main text:

∑I∈LS‾I=f(L)+N2sign⁡[h1+h2]1−ϵ2R2+ϵ(h1−h2)4R+O(ϵN)+2NJ(L−1)R−Jsign⁡[h1+h2]1−ϵ2R2.(73)\sum_{I\in\mathcal{L}} \overline{S}_{I}=f(\mathcal{L})+\sqrt{\frac{N}{2}}\operatorname{sign}[h_{1}+h_{2}]\sqrt{1-\frac{\epsilon^{2}}{R^{2}}+\frac{\epsilon(h_{1}-h_{2})}{4R}}+O\left(\frac{\epsilon}{\sqrt{N}}\right)+\sqrt{\frac{2}{N}}\frac{J(L-1)}{R-J}\operatorname{sign}[h_{1}+h_{2}]\sqrt{1-\frac{\epsilon^{2}}{R^{2}}}. \tag*{(73)}

For ϵ=O(N−ζ)\epsilon=O(N^{-\zeta}) with 0<ζ<1/20<\zeta<1/2 we have from (S39)

f(K)=O(KN−0.5−ζ)+O(N−ζ).(74)f(K)=O(KN^{-0.5-\zeta})+O(N^{-\zeta}). \tag*{(74)}

It is seen from (S38, S39, S40) that ∑I∈LS‾I≫∑I∈KS‾I\sum_{I\in\mathcal{L}}\overline{S}_{I}\gg\sum_{I\in\mathcal{K}}\overline{S}_{I} unless K=O(N)K=O(N). If this condition holds, the relative difference between two experimental signals ∑I∈LS‾I\sum_{I\in\mathcal{L}}\overline{S}_{I} and ∑I∈KS‾I\sum_{I\in\mathcal{K}}\overline{S}_{I} reads

∑I∈LS‾I−∑I∈KS‾I∑I∈LS‾I=1−2J(K−L+1)(R−J)N.(75)\frac{\sum_{I\in\mathcal{L}}\overline{S}_{I}-\sum_{I\in\mathcal{K}}\overline{S}_{I}}{\sum_{I\in\mathcal{L}}\overline{S}_{I}}=1-\frac{2J(K-L+1)}{(R-J)N}. \tag*{(75)}

Eq. (75) is of order of 1 for K=O(N)K=O(N). It depends only on known quantities, i.e. sufficiently accurate (but with a finite accuracy for N≫1N\gg1) measurements can distinguish between ∑I∈LS‾I\sum_{I\in\mathcal{L}}\overline{S}_{I} and ∑I∈KS‾I\sum_{I\in\mathcal{K}}\overline{S}_{I}.

References

  1. [1]L.N. de Castro, Fundamentals of natural computing: an overview, Physics of Life Reviews, 4 (2007) 1-36.DOI
  2. [2]B.J. MacLennan, A review of analog computing, Department of Electrical Engineering & Computer Science, University of Tennessee, Technical Report UT-CS-07-601 (2007).
  3. [3]E.G. Rieffel and W.H. Polak, Quantum computing: A gentle introduction (MIT Press, 2011).
  4. [4]Unconventional Computation, in Encyclopedia of Complexity and System Science (Springer, 2008).
  5. [5]J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018).DOI
  6. [6]P. Ball, Major quantum computing strategy suffers serious setbacks, Quanta Magazine, September 19 (2021).
  7. [7]P.C. Bressloff, Stochastic Processes in Cell Biology, Vol. I (Springer Nature Switzerland AG 2021).
  8. [8]O. Benichou and R. Voituriez, Narrow-Escape Time Problem: Time Needed for a Particle to Exit a Confining Domain through a Small Window, Phys. Rev. Lett. 100, 168105 (2008).pubmed.ncbi.nlm.nih.gov/18518253
  9. [9]L.K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79, 325 (1997).DOI
  10. [10]L.K. Grover and A.D. Patel, Quantum Search, in Encyclopedia of Algorithms, ed. by M.-Y. Kao. 1707-1716 (2015).
  11. [11]E. Farhi and S. Gutmann, An Analog Analogue of a Digital Quantum Computation, Phys. Rev. A 57, 2403 (1998).DOI
  12. [12]C. Zalka, Grover’s quantum searching algorithm is optimal, Phys. Rev. A, 60, 2746 (1999).DOI
  13. [13]Ref. [14] proposed a framework for quantum dissipative A. E. Allahverdyan and D. Petrosyan, Dissipative search of an unstructured database, Phys. Rev. A 105, 032447 (2022).DOI
  14. [15]L.K. Grover and A.M. Sengupta, Classical analog of quantum search, Phys. Rev. A, 65, 032319 (2002).DOI
  15. [16]A. Patel, Optimal database search: Waves and catalysis, Int. J. Quant. Inf., 4, 815-825 (2006).arxiv.org/abs/quant-ph/0401154
  16. [17]N. Bhattacharya N, H.V. van den Heuvell, and R.J. Spreeuw, Implementation of quantum search algorithm using classical Fourier optics, Phys. Rev. Lett. 88, 137901 (2002).DOI
  17. [18]S.K. Vadlamani, T.P. Xiao, E. Yablonovitch, Physics successfully implements Lagrange multiplier optimization, Proceedings of the National Academy of Sciences, 117, 26639-50 (2020).arxiv.org/abs/2007.05882
  18. [19]W.K. Thuemann and J.F. Fontanari, Spherical model as the limiting n-vector model in random field, Physica A, 149, 341-357 (1988).DOI
  19. [20]G.S. Joyce, Critical properties of the spherical model, Phase transitions and critical phenomena, 2, 375-442 (1972).
  20. [21]R.J. Baxter, Exactly solved models in statistical mechanics (Elsevier, 2016).
  21. [22]J.M. Kosterlitz, D.J. Thouless, R.C. Jones, Spherical model of a spin-glass, Phys. Rev. Lett. 36, 1217 (1976).
  22. [23]A. Barrat, The p-spin spherical spin glass model, arXiv preprint cond-mat/9701031 (1997).arxiv.org/abs/cond-mat/9701031
  23. [24]L.F. Cugliandolo and D.S. Dean, On the dynamics of a spherical spin-glass in a magnetic field, J. Phys. A, 28, L453-L459 (1995).DOI
  24. [25]Th. M. Nieuwenhuizen, Quantum description of spherical spins, Phys. Rev. Lett. 74, 4293 (1995).DOI
  25. [26]L.D. Landau and E.M. Lifshitz, Statistical Physics, Part 1 (Pergamon Press, 1980).
  26. [27]H.-P. Breuer and F. Petruccione, The Theory of Open Quantum Systems, (Oxford University Press, Oxford, 2002).
  27. [28]A. E. Allahverdyan, K. V. Hovhannisyan, A. V. Melkikh, and S. G. Gevorkian, Carnot Cycle at Finite Power: Attainability of Maximal Efficiency, Phys. Rev. Lett. 111, 050601 (2013).DOI
  28. [29]D. Bolle, Th. M. Nieuwenhuizen, I. Perez Castillo, and T. Verbeiren, A spherical Hopfield model, J. Phys. A, 36, 10269 (2003).DOI

Paper details

vlnc:W_fr3v6nmt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents