betaFeedback

WorksPhysics and Astronomy

Quantum adiabatic and diabatic optimization: A Hilbert space engineering strategy with Rydberg arrays

Abstract

Neutral-atom arrays provide a versatile platform for encoding combinatorial optimization problems with arbitrary graph connectivity [Nguyen et al., PRX Quantum 4, 010316 (2023)]. Although the dynamics of individual encoding gadgets has been studied [Bombieri et al., PRX Quantum 6, 020306 (2025)], understanding annealing bottlenecks in larger networks remains challenging. We investigate how engineering the Hilbert-space geometry controls quantum annealing in a family of blockaded-chain models motivated by these encodings. While boundary terms encode the target maximum independent set problem, the bulk geometry induces an auxiliary optimization problem associated with independent sets of cliques. Spectrally, the energetics of the quantum system can be approximated by physically derived clique weights. When the target problem and the auxiliary problems are consistent, the low-energy modes lie predominantly within the target subspace. This spectral structure motivates a diabatic annealing strategy that exploits target-compatible excited states, as tested on the diamond-chain graph family. These results provide a framework for predicting annealing bottlenecks, and demonstrate Hilbert-space engineering as a strategy for improving neutral-atom quantum optimization protocols.

Introduction

Quantum many-body systems can be exploited to solve combinatorial optimization problems. Within these encoding schemes, the optimal solution to the classical problem is mapped to the ground state of the quantum many-body system. One method to search for the ground state of a quantum many-body Hamiltonian in a quantum platform is through quantum annealing algorithm [1, 2]. The system is initialized in a known and easy-to-prepare state, and its parameters are slowly ramped toward the target. In the adiabatic limit, the state follows the instantaneous ground state. Revealing the source of bottleneck encountered in quantum annealing, and subsequently improving the annealing performance typically requires a comprehensive and oftentimes intractable study on the quantum many-body dynamics. Conceptually, departure from the instantaneous ground state need not imply failure to solve the encoded optimization problem. It is thus crucial to identify and utilize the compatibility of excitations with the target solution in the encoding.

Recently, neutral atom arrays have become a promising platform for quantum computing and quantum simulations, due to their rapid and substantial development in theoretical proposals and experimental techniques [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25] [21]. The Rydberg blockade mechanism [26, 27] of neutral atoms provides a natural quantum encoding scheme for a family of combinatorial optimization problems [28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38], including the unweighted maximum independent set problems. The encoding scheme for these problems has been investigated theoretically [34, 36, 38, 39] and experimentally [29, 30, 31, 33, 37]. Recently, a strongly correlated and geometrically localized many-body bound state has been shown to be the major source of annealing bottlenecks within a building block of the network, called gadget. Correspondingly, a strategy controlling the effective shape and boundary conditions of the system has been proposed to alleviate the difficulty [35].

However, the effects of these dynamical bottleneck in more complex networks is yet to be unveiled.

In this work, we elucidate the low-energy dynamics of the Rydberg networks using the effective blockaded-chain models. While the boundary condition encodes the target optimization problem by design, the bulk of the system naturally encodes a pertinent auxiliary optimization problem. Specifically, quantum many-body bound states contribute characteristic energies, allowing competing many-body configurations to be organized through weighted cliques of the graph. In the quantum system, this corresponds to the energetic competition between quantum states lying in macroscopically distinct Hilbert subspaces, and leads to bottleneck in quantum annealing.

Compatibility between the target and auxiliary problems can favor low-energy states with substantial support in the target subspace. This spectral structure suggests that excitation out of the instantaneous ground state need not prevent eventual recovery of the desired target readout. We investigate this possibility through a diabatic annealing protocol on diamond-chain graphs, relating the observed dynamics to competition between target-compatible and suboptimal channels.

This work is structured as follows. Section II introduces the encoding, effective model, and performance diagnostics. § 2, § 3, § 3.1 develop the spectral description, and investigate how geometric constraints and quantum many-body effects like hybridization and binding lead to clique-based quantum states, and how different branches compete. Section VI examines the resulting dynamics on diamond-chain graphs, followed by implementation considerations and conclusions in Sec. VII.

Encoding scheme and Hamiltonian

Introduction to the graph theory problems

The maximum independent set (MIS) problem in graph theory provides a stage for examining quantum computing algorithms. A connected simple graph G=(V,E)\mathcal{G}=(\mathcal{V},\mathcal{E}) consists of a vertex set V\mathcal{V} and an edge set E\mathcal{E} connecting the vertices. Given a graph, a subset of vertices is said to be independent, when no pair of vertices share an edge. The MIS problem thus searches for the independent set with the largest cardinality, see Figure 1(a) for an example. This set, represented by the array σMIS\sigma^{\mathrm{MIS}}, minimizes the loss function

Figure 1. Graph theoretical representation of quantum many-body states and dynamics for quantum annealing. (a) Maximum independent vertex and clique sets (MIS, MICS) of a graph. The two sets are consistent: choosing a vertex from each clique in MICS yields the MIS. (b,c) Schematics associating quantum annealing bottleneck to features of the graph. Along the annealing, the ground state behaves like boundary states representing the logical-zeros state ∣0L⟩\lvert0_L\rangle and the target ∣MIS⟩\lvert\mathrm{MIS}\rangle state in the initial and final stages, respectively. In the intermediate stage, the ground state spreads in the bulk of the system, encoding the solution to the maximum weight independent clique set (MWICS) problem. This solution can be (b) consistent with the MICS problem or (c) not, depending on the graph and the system parameters. Following the ground state (solid arrows) requires traversing narrow gaps and costs long time overheads. (b) Particularly, when MICS and MWICS are consistent, the low-energy quantum many-body spectrum allows a diabatic annealing scheme for reaching the target MIS state while bypassing the bottleneck. (d) The N=3N=3 chain graph and its (red) maximum and (blue) suboptimal independent sets. (e) A realistic implementation using neutral atom arrays subject to Rydberg blockade mechanism for encoding the MIS problem. The filled circles are atoms, and the links between them indicate Rydberg blockade. Three configurations are shown representing (brown) logical-zero, (red) optimal solution, and (blue) suboptimal solution, respectively, in the classical limit. The Rydberg mode (ground mode) of the neutral atoms is occupied when the atom is colored (white). (f) The effective Hamiltonian describing the domain wall states in the low energy sector of the neutral atomic system shown in (e), which motivates our blockaded lattice model. Particularly, the dashed lines highlight the hoppings which are explicitly omitted in our blockaded lattice model. (g) Schematics illustrating the blockaded lattice model encoding the MIS problem on the N=3N=3 chain graph G3,1=P3\mathcal{G}_{3,1}=\mathcal{P}_3, with L=4,d=2L=4,d=2.

H=−σTσ,subject toσTAσ=0,(1)H=-\sigma^{T}\sigma,\qquad\text{subject to}\quad\sigma^{T}\mathcal{A}\sigma=0, \tag*{(1)}

Here, σ=(σ1,…,σN)T\sigma=(\sigma_{1},\ldots,\sigma_{N})^{T} with σn=0,1\sigma_{n}=0,1 denoting the occupancy of vertex nn, and N=∣V∣N=|\mathcal{V}| is the cardinality of the graph. A\mathcal{A} is the adjacency matrix encoding the edges, Am,n=0\mathcal{A}_{m,n}=0 for ⟨m,n⟩∉E\langle m,n\rangle\notin\mathcal{E} and Am,n=1\mathcal{A}_{m,n}=1 for ⟨m,n⟩∈E\langle m,n\rangle\in\mathcal{E}. Generically, the MIS problem is NP-complete, and an exact and generic classical branching algorithm has a complexity scaling exponentially with the size of the graph O(γN)O(\gamma^{N}), with γ≈1.26\gamma\approx1.26 [40].

Neutral atoms are subject to the Rydberg blockade mechanism, which can be effectively described by the PXP model in the hardcore limit [41, 42, 43, 44, 45]. The Rydberg states of two spatially adjacent atoms cannot be occupied simultaneously. This constraint on the quantum device is naturally reminiscent of the graph-theoretical constraint Eq. (1). This correspondence motivates a proposal for encoding the MIS problem on unit-disk graphs using arrays of neutral atoms [28, 31, 46]. Later, the mapping proposed in Ref. [32] generalizes the encoding scheme to graphs with arbitrary connectivity, and eventually motivates the model investigated in this work. Once quantum encoded, the solutions to the classical optimization problem can be read out from the ground states, which are to be solved by quantum annealing algorithms [1, 2]. The performance is determined by the low-energy dynamics of the instantaneous Hamiltonians along the entire annealing process.

In this work, we find that the quantum many-body dynamics can be inferred from a classical indicator, termed maximum weight independent clique set (MWICS), as illustrated in Figure 1(a). A clique K⊆GK\subseteq\mathcal{G} is a fully connected subgraph of cardinality q=∣K∣=∑n=1NσnKq=|K|=\sum_{n=1}^{N}\sigma_{n}^{K}, satisfying (σK)TAσK=q(q−1)(\sigma^{K})^{T}\mathcal{A}\sigma^{K}=q(q-1). Here, the clique is represented by an array σK\sigma^{K} listing a set of vertices S\mathcal{S} inducing the clique, K=G[S]K=\mathcal{G}[\mathcal{S}]. A set of cliques K={K1,K2,…,KR}\mathcal{K}=\{K_{1},K_{2},\ldots,K_{R}\}, is said to be independent, when vertices from these disjoint cliques are not connected by any edge, i.e., (σrK)TσsK=0(\sigma_{r}^{K})^{T}\sigma_{s}^{K}=0, and (σrK)TAσsK=0(\sigma_{r}^{K})^{T}\mathcal{A}\sigma_{s}^{K}=0, r≠sr\ne s. The MWICS problem associates each clique with a weight WrW_{r} depending on its cardinality, and search for the independent clique set (ICS) with the largest weight. It minimizes the loss function

H=−∑r=1RWr,(2)H=-\sum_{r=1}^{R}W_{r}, \tag*{(2)}

subject to

(σrK)TAσsK=(qr2−qr)δr,s.(\sigma_{r}^{K})^{T}\mathcal{A}\sigma_{s}^{K}=(q_{r}^{2}-q_{r})\delta_{r,s}.

In the same spirit, MWICS is reduced to the maximum independent clique set (MICS) problem, by assigning weights Wr=lim⁡ϵ→0+1+qrϵW_{r}=\lim_{\epsilon\to0^{+}}1+q_{r}\epsilon, see Figure 1(a) for an example. MIS and MICS are naturally compatible with each other, and a MIS can be straightforwardly read out from a MICS. In this work, we will show that the annealing difficulty can be alleviated when MWICS is reduced to the MICS, see Figure 1(b,Figure 1c).

The blockaded chain Hamiltonian

We encode the MIS problem in the blockaded chain model,

H(L,d,G)=Π(L,d,G)HLNΠ(L,d,G)(3)H_{(L,d,\mathcal{G})}=\Pi_{(L,d,\mathcal{G})}H_{L}^{N}\Pi_{(L,d,\mathcal{G})} \tag*{(3)}

Here, the bare Hamiltonian HLNH_{L}^{N} describes NN independent chains with nearest-neighbor hopping strength tt and local chemical potentials ϵi,f\epsilon_{i,f} at the two edges.

HLN=∑n=1NhL,n(4)H_{L}^{N}=\sum_{n=1}^{N}h_{L,n} \tag*{(4)}
hL,n=−t∑ℓ=1L−1(∣n,ℓ⟩⟨n,ℓ+1∣+h.c.)−ϵi∣n,1⟩⟨n,1∣−ϵf∣n,L⟩⟨n,L∣(5)h_{L,n}=-t\sum_{\ell=1}^{L-1}\left(|n,\ell\rangle\langle n,\ell+1|+\mathrm{h.c.}\right)-\epsilon_{i}|n,1\rangle\langle n,1|-\epsilon_{f}|n,L\rangle\langle n,L| \tag*{(5)}

This bare Hamiltonian describes NN non-interacting chains of length LL, with lattice sites denoted as ∣n,ℓ⟩|n,\ell\rangle, n=1,…,Nn=1,\ldots,N, ℓ=1,…,L\ell=1,\ldots,L. Notably, it can also be interpreted as an NN-dimensional lattice in the shape of a hypercube, and encodes the MIS problem for a graph consisting of NN unconnected vertices. The projection operator PP encodes the independent set constraint associated to the graph, by projecting out the relevant lattice sites from being occupied,

Π(L,d,G)=∏⟨m,n⟩∈EΠ⟨m,n⟩(6)\Pi_{(L,d,\mathcal{G})}=\prod_{\langle m,n\rangle\in\mathcal{E}}\Pi_{\langle m,n\rangle} \tag*{(6)}
Π⟨m,n⟩=1−∑ℓm,ℓn=d+1L∣m,ℓm⟩∣n,ℓn⟩⟨m,ℓm∣⟨n,ℓn∣(7)\Pi_{\langle m,n\rangle}=\mathbb{1}-\sum_{\ell_{m},\ell_{n}=d+1}^{L}|m,\ell_{m}\rangle|n,\ell_{n}\rangle\langle m,\ell_{m}|\langle n,\ell_{n}| \tag*{(7)}

Particularly, ⟨m,n⟩\langle m,n\rangle refers to an edge between vertices mm and nn in the graph, and the projection operation can be viewed as an interaction between the mmth and nnth chains of infinite strength.

Given a specific graph, LL and dd are the two important control parameters. In this work, we refer to d=L−1d=L-1, L≠2L\ne2 as the hypercube limit, L≫dL\gg d as the indent limit, and L=2L=2, d=1d=1 as the PXP implementation. Particularly, for L≫1L\gg1, the system can be treated as a continuum, and the ratio d/L∈(0,1)d/L\in(0,1) solely determines the shape of the Hilbert space. As an example, the lattice hosting H(L,d,P3)H_{(L,d,\mathcal{P}_3)} is shown in Figure 1(g). Notably, H(L=2,d=1,PN)H_{(L=2,d=1,\mathcal{P}_N)} being chain graphs of NN vertices, is the commonly discussed PXP model [47, 48, 49, 50].

We refer to H(L,d,G)H_{(L,d,\mathcal{G})} as the (L,d,G)(L,d,\mathcal{G})-blockaded lattice model. It is motivated by experimentally relevant neutral atom arrays. A scheme for encoding the MIS problem on a general graph has been proposed in Ref. [32], which utilizes the Rydberg blockade mechanism of neutral atoms for naturally encoding the independent-set constraint on a quantum device. The crucial building blocks are the atom wires representing the graph vertices, and the gadgets lying at the wire crossings representing the connectivity between the two wires. The blockaded-chain model effectively captures the low-energy physics of these Rydberg networks, see Appendix B.

The quantum dynamics within these building blocks has been thoroughly investigated in Ref. [35]. Particularly, the low energy quantum dynamics of the system has been found to be governed by domain walls along the atom wires. For a two-vertex connected graph G2,1=K2\mathcal{G}_{2,1}=\mathcal{K}_2, the domain walls travel on a two-dimensional lattice, where part of the lattice sites are prohibited, forming an L-shaped lattice. A similar treatment for the graph G3,1=P3\mathcal{G}_{3,1}=\mathcal{P}_3 leads to the Rydberg array illustrated in Figure 1(e), and the effective lattice model shown in Fig. 1(f). For simplicity, we impose that the gadget is placed at the same position along each wires, leading to a symmetric implementation. Experimentally, this corresponds to elongating the every wire along both directions at the same proportionality, making the size and detailed structures of the gadgets negligible in comparison to the entire wires. Moreover, hopping terms at the gadgets linking next-nearest-neighbor lattice sites are also omitted. These extra hopping terms have been shown not to exhibit essential contributions to quantum dynamics [35]. Taking all these considerations into account, the H(L,d,K2)H_{(L,d,\mathcal{K}_2)} and H(L,d,P3)H_{(L,d,\mathcal{P}_3)} are achieved, respectively. In Ref. [35], geometric confinement has been found as a substantial source of obstacle for a polynomial scaling of the annealing efficiency with respect to LL in the L-shaped domain associated to the two-vertex graph, K2\mathcal{K}_2. Nevertheless, the quantum annealing performance associated to H(L,d,G)H_{(L,d,\mathcal{G})} for a more general graph G\mathcal{G} is so far not yet explored.

Hilbert space

The blockaded chain model provides a suitable platform for solving the MIS problem in two perspectives. Straightforwardly, the ground states under selected boundary conditions are connected to logical configurations of the graph. When ϵi≫t,ϵf=0\epsilon_i \gg t,\epsilon_f=0, the instantaneous ground state can be interpreted as logical-zero state,

∣0L⟩=⨂n=1N∣n,1⟩;(8)\lvert0_L\rangle= \bigotimes_{n=1}^{N}\lvert n,1\rangle; \tag*{(8)}

while when ϵi=0,ϵf≫t\epsilon_i=0,\epsilon_f\gg t, the quantum state is localized in the vicinity of the lattice site encoding the MIS solution {σnMIS}\{\sigma_n^{\mathrm{MIS}}\},

∣ΨMIS⟩=⨂n=1N∣n,σnMIS×(L−1)+1⟩.(9)\lvert\Psi^{\mathrm{MIS}}\rangle= \bigotimes_{n=1}^{N}\lvert n,\sigma_n^{\mathrm{MIS}}\times(L-1)+1\rangle. \tag*{(9)}

Nevertheless, the blockaded chain model encodes the optimization problem beyond its boundary, and also in its bulk. The compatibility between the boundary and the bulk fundamentally facilitates the quantum annealing processes. To gain a first insight, we inspect the structure of the intact NN-dimensional hypercube lattice ⨂n=1N⨁ℓ=1L∣n,ℓ⟩⟨n,ℓ∣\bigotimes_{n=1}^{N}\bigoplus_{\ell=1}^{L}\lvert n,\ell\rangle\langle n,\ell\rvert projected out by ΠL,d,G\Pi_{L,d,\mathcal{G}} in Eq. (5) from a constructive point of view [51, 52],

ΠL,d,G⨂n=1N⨁ℓ=1L∣n,ℓ⟩⟨n,ℓ∣ΠL,d,G=⋃σ∈{σmIS}(⨂n=1N⨁ℓ=1ℓnL,d∣n,ℓ⟩⟨n,ℓ∣)(10)\Pi_{L,d,\mathcal{G}}\bigotimes_{n=1}^{N}\bigoplus_{\ell=1}^{L}\lvert n,\ell\rangle\langle n,\ell\rvert\Pi_{L,d,\mathcal{G}} = \bigcup_{\sigma\in\{\sigma^{\mathrm{mIS}}\}}\left(\bigotimes_{n=1}^{N}\bigoplus_{\ell=1}^{\ell_n^{L,d}}\lvert n,\ell\rangle\langle n,\ell\rvert\right) \tag*{(10)}

The construction is directly associated to the collection of maximal independent sets (mIS), {σmIS}\{\sigma^{\mathrm{mIS}}\}, of the graph G\mathcal{G}. They are ISs which are not a proper subset of another IS. Given an mIS, ⨂n=1N⨁ℓ=1ℓnL,d∣n,ℓ⟩⟨n,ℓ∣\bigotimes_{n=1}^{N}\bigoplus_{\ell=1}^{\ell_n^{L,d}}\lvert n,\ell\rangle\langle n,\ell\rvert constructs an NN-dimensional hypercube, and its lengths along dimension nn is given by ℓnL,d=d(L)\ell_n^{L,d}=d(L) for σn=0(1)\sigma_n=0(1). The projected Hilbert space can be constructed by merging hypercuboids of different mISs. The structure of the lattice mimics a Daisy cube [53, 54] generated by all mISs of the graph, particularly for the PXP implementation L=2,d=1L=2,d=1.

The structure of the Hilbert space of the blockaded chains alludes to quantum dynamics. A hypercuboid Hilbert subspace acts locally like an integrable system, and admits tractable quantum dynamics. Moreover, the MIS, being the classical optimal solution among all mISs, corresponds to the hypercuboid of the largest volume in this construction. Intuitively, this strongly facilitates the propagation of the quantum state and the annealing process for searching the MIS solution. This effect should be most prominent in the limit L≫dL\gg d.

Logical annealing protocol and performance

The objective of the quantum annealing is to adiabatically evolve the quantum many-body state from the initial state to the target state in an unbiased manner. The unbiasedness requires that (i) the initial state is known and easy to prepare, which is fulfilled by Eq. (6); (ii) the structure and the parameters of the Hamiltonian is not biased toward/against certain solutions, e.g., a sequential ramping of boundary terms associated different vertices is prohibited; (iii) the annealing protocol should not be based on learned, non-universal features associated to a specific graph, e.g. slowing down the annealing for addressing a fine structure of the spectrum of a specific Hamiltonian is prohibited.

The logical annealing protocol proposed in Ref. [35] and shown in Figure 2 meets these criteria. It further provides a tractable arena for investigating the quantum dynamics within the blockaded chain model. In this protocol, the initial boundary chemical potential ϵi\epsilon_i is first linearly turned off, and subsequently the final boundary chemical potential ϵf\epsilon_f is linearly turned on. Particularly, the boundary terms of every chain are ramped simultaneously. Meanwhile, the hopping tt is kept fixed during the whole process, cf. Eq. (4). The logical protocol can be straightforwardly implemented upon the atom network, and allows for an intuitive analysis of quantum dynamics, see Appendix B.

Figure 2. Quantum annealing protocol and list of graphs. (a) The annealing parameters, tt, ϵi\epsilon_i, and ϵf\epsilon_f, as a function of annealing time in the logical protocol. (b) A list of small graphs used as examples for discussions in this work. An exhaustive atlas of small graphs with N≤5N\leq5 vertices is listed in Appendix A.

We characterize quantum annealing performance using complementary spectral and dynamical indicators. Spectrally, quantum adiabatic theorem [55, 56, 57] measures the performance using the minimum gap of the instantaneous Hamiltonians within the dynamically accessible branches. This is most clearly seen when the solution to the MIS problem is unique. In this case, due to the uniqueness of ground state, the annealing performance can be represented by the minimum gap between the instantaneous ground first excited state along the annealing, Δmin⁡=min⁡(E1−E0)\Delta_{\min}=\min(E_1-E_0). However, when the MIS problem has k≥2k \ge2 degenerate solutions, there is no a general rule for assigning a gap for quantifying the performance, and we tentatively employ Δmin⁡=min⁡(Ek−E0)\Delta_{\min}=\min(E_k-E_0) for this purpose. In this work, the spectrum is solved numerically using exact diagonalization of sparse matrices unless specified otherwise.

Dynamically, the quantum annealing performance can be measured by the success rate of the quantum state reaching the target state, or more generically, the target subspace. We propose the dephased density probability in the MIS subspace,

PT=∑μ∣⟨μ∣Ψ⟩∣2⟨μ∣ΠMIS∣μ⟩,(11)P_T=\sum_{\mu}|\langle\mu|\Psi\rangle|^2\langle\mu|\Pi_{\mathrm{MIS}}|\mu\rangle, \tag*{(11)}

where ∣μ⟩|\mu\rangle are the instantaneous eigenmodes. ΠMIS=⨂n∈UΠn(0)\Pi_{\mathrm{MIS}}=\bigotimes_{n\in\mathcal{U}}\Pi_n^{(0)} projects onto (the union of) the logical hypercuboids associated with the MIS (degenerate MISs). Here, U\mathcal{U} contains all vertices that are not in (any of the degenerate) MISs, and Πn(0)=∑ℓ=1d∣ℓ⟩n⟨ℓ∣\Pi_n^{(0)}=\sum_{\ell=1}^{d}|\ell\rangle_n\langle\ell|. Notably, PTP_T measures the weight of the quantum state in the entire MIS subspace, rather than its fidelity to a particular state. It further averages out the phases between different ∣μ⟩|\mu\rangle to account for an average in time in dynamics. Complementary and experimentally relevant information can be further provided by marginal density distribution along a dimension associated to logical-one, see Appendix B.

Quantum annealing performance in hypercube limit

We proceed to investigate the quantum dynamics on the blockaded chain model along the logical protocol. The hypercube limit, d=L−1d=L-1, exhibits a high

degree of connectivity within the Hilbert space. This typically leads to highly delocalized quantum many-body states and improved annealing performance [46]. Counterintuitively, the annealing performance in this limit is fundamentally determined by the quantum dynamics of the PXP implementation, L=2L=2, d=1d=1. Connectivity in Hilbert space configurations alone is therefore insufficient to predict annealing performance.

Along the annealing, the gap exhibits universal behaviors, as depicted for the representative cases in Figure 3. It has one local minimum in the first and second half of the annealing, respectively. Given a specific graph and varying L≥3L\geq3, the gaps as a function of the annealing parameters collapse upon a scaling of L2ΔL~,L~−1,Gmin⁡L^2\Delta^{\min}_{\tilde{L},\tilde{L}-1,\mathcal{G}}. This is shown for the paw graph, G4−3\mathcal{G}_{4-3}, in Figure 3(a).

Figure 3. Performance of quantum annealing in the hypercube limit d=L−1d=L-1. (a) The gap along the annealing for an implementation encoding the MIS problem on the paw graph G4−3\mathcal{G}_{4-3}. The two local minima for L≥3L\geq3 are indicated by arrows. (b) The relation between the minimum gaps for the hypercube limit ΔL~,L~−1min⁡\Delta^{\min}_{\tilde{L},\tilde{L}-1} and the PXP implementation Δ2,1min⁡\Delta^{\min}_{2,1} for all small graphs with N≤7N\leq7 [58]. Results are shown for L=3,4,5,6L=3,4,5,6 (for graphs with N=2,3,4,5N=2,3,4,5), L=3,4,5L=3,4,5 (N=6N=6), or L=3L=3 (N=7N=7). The dashed lines with slopes 22EL−1/π2\sqrt{2}E_{L-1}/\pi are guides to the eyes highlighting the linearity.

The universal behavior can be elucidated through a mapping of HL,L−1,GH_{L,L-1,\mathcal{G}} onto spinor models, see Appendix C for details. The low energy dynamics can effectively be described by three modes along each chain, including two exponential modes, ∣A⟩n∼∑ℓ=1Le−ϵiℓ/t∣n,ℓ⟩|A\rangle_n\sim\sum_{\ell=1}^{L}e^{-\epsilon_i\ell/t}|n,\ell\rangle, ∣C⟩n∼∑ℓ=1Le−ϵf(L−ℓ)/t∣n,ℓ⟩|C\rangle_n\sim\sum_{\ell=1}^{L}e^{-\epsilon_f(L-\ell)/t}|n,\ell\rangle, and a standing-wave mode, ∣B⟩n∼∑ℓ=1Lsin⁡(πℓ/L)∣n,ℓ⟩|B\rangle_n\sim\sum_{\ell=1}^{L}\sin(\pi\ell/L)|n,\ell\rangle. The first minimum lies around ϵi=t\epsilon_i=t, where the system transitions from the localized state ⨂n=1N∣A⟩n\bigotimes_{n=1}^{N}|A\rangle_n to the delocalized state ⨂n=1N∣B⟩n\bigotimes_{n=1}^{N}|B\rangle_n. Since any basis state formed by direct products of ∣A⟩n|A\rangle_n and ∣B⟩n|B\rangle_n is legitimate, the full Hamiltonian projecting onto this basis thus induces the Hamiltonian of a spin-N/2N/2, HL~=2NH^N_{\tilde{L}=2}, with an effective hopping t~=42/π×(1−cos⁡[π/(L+1)])∼1/L2\tilde{t}=4\sqrt{2}/\pi\times(1-\cos[\pi/(L+1)])\sim1/L^2. Similarly for the second local minimum around ϵf=t\epsilon_f=t, projecting HL,L−1,GH_{L,L-1,\mathcal{G}} onto the basis states of ∣B⟩n|B\rangle_n and ∣C⟩n|C\rangle_n leads to the PXP implementation of the same graph, HL~=2,d~=1,GH_{\tilde{L}=2,\tilde{d}=1,\mathcal{G}}. The gap behaviors thus inherit from H2,1,GH_{2,1,\mathcal{G}}. Our mapping can further be confirmed by comparing the minimum gap along protocol between the hypercube limit d=L−1d=L-1 and the PXP implementation L=2L=2, d=1d=1, see Figure 3(b). Consistent with our analysis, a strong correlation can be seen between ΔL,L−1,Gmin⁡\Delta^{\min}_{L,L-1,\mathcal{G}} and Δ2,1,Gmin⁡\Delta^{\min}_{2,1,\mathcal{G}}. During the annealing, the bottleneck of the quantum annealing performance competes between the quantum dynamics of a spin-N/2N/2 system, and that of the PXP implementation based on the graph, with Δspin−N/2min⁡=ΔL,L−1,Gmin⁡≈2t\Delta^{\min}_{\mathrm{spin-}N/2} = \Delta^{\min}_{L,L-1,\mathcal{G}} \approx2t,

ΔL,L−1,Gmin⁡≈t~/t×min⁡(2t,Δ2,1,Gmin⁡).(12)\Delta^{\min}_{L,L-1,\mathcal{G}} \approx\tilde{t}/t \times\min\left(2t,\Delta^{\min}_{2,1,\mathcal{G}}\right). \tag*{(12)}

The quantum annealing performance in the hypercube limit is thus fundamentally determined by the quantum dynamics of the PXP implementation. Increasing Hilbert-space connectivity in the hypercube limit does not remove the graph-dependent PXP bottleneck.

Factorizability of quantum states in indent limit

In stark contrast to the hypercube limit, the indent limit of the blockaded-chain model manifests quantum dynamics distinct from the PXP implementation. Importantly, due to the characteristic structure of the Hilbert space, the quantum dynamics becomes tractable and can be attributed to a product-state ansatz. In the rest of this work, we focus on this implementation, and explore the potential for improvement of quantum annealing performance.

In indent limit, the structure of the Hilbert space as described by Eq. (10) chiefly governs the quantum many-body dynamics. These hypercuboid subspaces can be viewed individually as quasi-integrable subsystems, which are barely coupled with each others, and host independent dynamics. Specifically, in the low energy sector, the quantum many-body states are thus expected to follow the tentative NN-partite ansatz based on a mIS (not necessarily optimal), σMIS\sigma^{\mathrm{MIS}}, of the graph,

∣ΨMIS⟩tentative=∏n=1N∣ψμnσnMIS⟩n.(13)\left|\Psi^{\mathrm{MIS}}\right\rangle_{\mathrm{tentative}} = \prod_{n=1}^{N}\left|\psi_{\mu_n}^{\sigma_n^{\mathrm{MIS}}}\right\rangle_n. \tag*{(13)}

Here, ∣ψμn0⟩n\left|\psi_{\mu_n}^{0}\right\rangle_n (∣ψμn1⟩n\left|\psi_{\mu_n}^{1}\right\rangle_n) are logical zero (one) modes, and corresponds to any vertex with σnMIS=0\sigma_n^{\mathrm{MIS}}=0 (σnMIS=1\sigma_n^{\mathrm{MIS}}=1) in the mIS. They span a one-dimensional lattice of dnd_n (LL) sites along the corresponding dimension nn, and are the NN harmonics of the Hamiltonian h=−t∑ℓ=1d−1(∣ℓ⟩⟨ℓ+1∣+h.c.)−ϵi∣1⟩⟨1∣h=-t\sum_{\ell=1}^{d-1}(\left|\ell\right\rangle\left\langle\ell+1\right|+\mathrm{h.c.})-\epsilon_i\left|1\right\rangle\left\langle1\right| (h=−t∑ℓ=1L−1(∣ℓ⟩⟨ℓ+1∣+h.c.)−ϵf∣L⟩⟨L∣h=-t\sum_{\ell=1}^{L-1}(\left|\ell\right\rangle\left\langle\ell+1\right|+\mathrm{h.c.})-\epsilon_f\left|L\right\rangle\left\langle L\right|).

Surprisingly, this convenient fully factorizable ansatz is already sufficient for describing the low-energy quantum dynamics in models based on a large number of graphs. For instance, it is consistent with the instantaneous ground states of H(30,5,P3)H_{(30,5,\mathcal{P}_3)}, as shown in Figure 4. However, models based on graphs with permutation symmetries tend to host correlated quantum many-body dynamics. In the following, we progressively demonstrate these correlated effects with exact numerical solutions, and demonstrate examples which are fully factorizable, factorizable with quantum many-body bound states, and nontrivially correlated.

Figure 4. Densities of instantaneous ground states at several characteristic time points of the annealing protocol. (a) The lattice sites and boundary terms ϵi\epsilon_i (red) and ϵf\epsilon_f (blue) for the (30,5,P3)(30,5,\mathcal{P}_3)-blockaded chain model. (b-f) Densities of state along the quantum annealing. The majority of the density lies in the “flat” oblate hypercuboid subspace, and abstained from the “chimney” prolate subspace. Therefore, the wavefunction can be formulated as a product state.

Completely factorizable quantum states

We first examine the validity of the tentative ansatz at the homogeneous boundary condition ϵi,f=0\epsilon_{i,f}=0. We mainly focus on the separability of the state and its projected densities along different dimensions. The separability of the quantum states can be quantified by its entanglement entropy. Given many-body state ∣Ψ⟩\left|\Psi\right\rangle based on a lattice of NN dimensions and length LL, its entanglement entropy with respect to a specific dimension nn can be defined as

Sn=−∑ℓ=1Lλℓln⁡λℓ,λℓ∈eig⁡(ρn)(14)S_n=-\sum_{\ell=1}^{L}\lambda_\ell\ln\lambda_\ell,\quad\lambda_\ell\in\operatorname{eig}(\rho_n) \tag*{(14)}

where the reduced density matrix

ρn=tr⁡m≠n∣Ψ⟩⟨Ψ∣(15)\rho_n=\operatorname{tr}_{m\ne n}\left|\Psi\right\rangle\left\langle\Psi\right| \tag*{(15)}

is traced over all N−1N-1 dimensions other than nn. For the case of 3-chain graph P3=G3−1\mathcal{P}_3=\mathcal{G}_3-1, and an implementation with L=30L=30, d=5d=5, we show the entanglement spectrum with respect to the 1st dimension in Figure 5(a). The low-energy sector is indeed dominated by a family of states with zero entanglement, confirming the states are product states. Two arbitrary zero-entanglement excited states are visualized in Figure 5(b,Figure 5c), where their densities apparently exhibit higher harmonics among different dimensions. These states are also characterized by S2/3=ln⁡2S_{2/3}=\ln2 due to (anti)symmetric superposition.

Figure 5. Product-state ansatz with homogeneous boundary. (a) The entanglement spectrum of the system at midpoint of protocol, where the boundary is homogeneous ϵi,f=0\epsilon_{i,f}=0, for graph P3=G3−1P_3=G_{3-1}. The entanglement entropy S1S_1, cf. Eq. (14), is evaluated for each eigenstate. The low energy sector is dominated by a large family of product states with vanishing entanglement entropy, as marked by the orange crosses. (b,c) The densities of two arbitrarily chosen zero-entanglement states, marked by red crosses in panel (a). (d-f) The entanglement spectrum for the paw graph, G4−3G_{4-3}. (g-o) The projection of (g-i) the ground state, (j-l) the first excited state, and (m-o) a low-lying excited state is consistent with the product state ansatz. Along the 3rd and 4th dimensions, the state is either (l,o) a superposition of two harmonics or (i) a bound state.

Intuitively, similar arguments apply straightforwardly to the case of paw graph G4−3G_{4-3}, apart from its ground state.

In Figure 5(d-f), we show the entanglement spectra along different dimensions. Similar to the P3P_3, there is a large family of states with S1=S2=0S_1=S_2=0, and S3=S4=ln⁡2S_3=S_4=\ln2, which confirms that they are product states. This can be further confirmed by the projected densities along different dimensions, as shown in Figure 5(g-o). Along the 1st and 2nd dimensions, the projected densities correspond to the basis states ∣ψμ1⟩n|\psi^{1}_{\mu}\rangle_n and ∣ψμ2⟩n|\psi^{2}_{\mu}\rangle_n, respectively. Particularly, ∣ψμ1⟩n=∑ℓ=1Lsin⁡(μπℓ/L)∣n,ℓ⟩|\psi^{1}_{\mu}\rangle_n=\sum_{\ell=1}^{L}\sin(\mu\pi\ell/L)|n,\ell\rangle and ∣ψμ2⟩n=∑ℓ=1dsin⁡(μπℓ/d)∣n,ℓ⟩|\psi^{2}_{\mu}\rangle_n=\sum_{\ell=1}^{d}\sin(\mu\pi\ell/d)|n,\ell\rangle. Along the 3rd and 4th dimensions, the projected densities indicate that the first excited state [Figure 5(l)] and the low-lying excited state [Figure 5(o)] are superposition states (∣ψμ1⟩3∣ψμ2⟩4±∣ψμ2⟩3∣ψμ1⟩4)/2(|\psi^{1}_{\mu}\rangle_3|\psi^{2}_{\mu}\rangle_4\pm|\psi^{2}_{\mu}\rangle_3|\psi^{1}_{\mu}\rangle_4)/\sqrt{2}.

The ground state, however, can not be fully captured by the tentative ansatz. This is the most obvious in its projected density along the 3rd and 4th dimensions. It resembles the bound state which appears in the model based on the 2-vertex graph P2=G2−1P_2=G_{2-1}, as studied in Ref. [35]. Correspondingly, its entanglement entropy along these two dimensions is 0<S3/4<ln⁡20<S_{3/4}<\ln2 [Figure 5(f)]. This example highlights the broad existence and importance of bound state dynamics in blockaded-chain models.

Clique-based bound states as factor basis states

The bound states are typically associated to complete subgraphs, or cliques. This motivates us to investigate the blockaded chain model based on complete graphs Kq>2K_{q>2}, e.g. G2−1G_{2-1}, G3−2G_{3-2}, G4−6G_{4-6}, G5−21G_{5-21}. Their Hilbert spaces have the shapes of a “claw”, which is composed by a “palm”, [1,d]q[1,d]^q, and qq “fingers”, [1,d]q−1×[d+1,L][1,d]^{q-1}\times[d+1,L]. The logical-zero sector of volume dqd^q acts like a base, and qq logical-one sectors of volume L×dq−1L\times d^{q-1} are hypertubes individually attached to the based. Inherited from the graph, the Hilbert space also has a permutation symmetry of degree qq. Specifically, the two-dimensional case of a LL-shaped lattice has been studied thoroughly in Ref. [35], where a bound state of particularly low energy has been seen and attributed to quantum interference.

With homogeneous boundary, the existence of similar bound states in higher dimensions can be argued using energetic arguments for the ground states ∣Kq⟩\lvert K^q\rangle of HL,d,KqH_{L,d,K_q}. The variational principle for ground states dictates a strictly monotonic decrease in their energies, EqE_q,

Eq−qE0<Eq−1−(q−1)E0<⋯<E2−2E0,(16)E_q-qE_0 < E_{q-1}-(q-1)E_0 < \cdots< E_2-2E_0, \tag*{(16)}

where E0/t=−2cos⁡[π/(d+1)]E_0/t=-2\cos[\pi/(d+1)] is the energy of the first harmonic mode spanning dd sites. This verifies that the ground states of HL,d,KqH_{L,d,K_q} are indeed exponentially decaying along the “fingers”, since Eq−(q−1)E0<E2−E0<−2tE_q-(q-1)E_0 < E_2-E_0 < -2t [35], and localized around the “palm”, i.e., the logical-zero sector. The two-dimensional and three-dimensional bound states, ∣K2⟩\lvert K^2\rangle and ∣K3⟩\lvert K^3\rangle, are visualized in Figure 6.

Figure 6. Quantum bound states associated to cliques. Densities of clique states ∣Kq⟩|K_q\rangle with homogeneous boundary ϵi,f=0\epsilon_{i,f}=0 with L=30L=30, d=5d=5 for q=2,3q=2,3.

The ansatz for the quantum many-body state should thus take these bound states as indivisible factors. For instance, with homogeneous boundary, ϵi,f=0\epsilon_{i,f}=0, we propose the following improved ansatz represented by an independent clique set (ICS), K={Kr}\mathcal{K}=\{K_r\}, and verify its fidelity against the exact quantum many-body ground state,

∣ΨICS⟩=⨂r=1R∣Kqr⟩n∈Kr⊗⨂n∉K∣ψ0⟩n.(17)\lvert\Psi^{\mathrm{ICS}}\rangle=\bigotimes_{r=1}^{R}\lvert K^{q_r}\rangle_{n\in K_r}\otimes\bigotimes_{n\notin\mathcal{K}}\lvert\psi^0\rangle_n. \tag*{(17)}

Here, ∣ψ0⟩n=∑ℓ=1dsin⁡(πℓ/d)∣n,ℓ⟩\lvert\psi^0\rangle_n=\sum_{\ell=1}^{d}\sin(\pi\ell/d)\lvert n,\ell\rangle, ∣K1⟩n=∑ℓ=1Lsin⁡(πℓ/L)∣n,ℓ⟩\lvert K^1\rangle_n=\sum_{\ell=1}^{L}\sin(\pi\ell/L)\lvert n,\ell\rangle, and ∣Kq≥2⟩n1,…,nq\lvert K^{q\geq2}\rangle_{n_1,\ldots,n_q} are the qq-dimensional bound states associated to KMK_M.

We examine the ansatz for all small graphs with N≤5N\leq5 vertices in Figure 7 by computing their sum of single-dimension entropies S=∑n=1NSnS=\sum_{n=1}^{N}S_n and fidelity with respect to the ansatz F=∣⟨ΨGS∣ΨMICS⟩∣F=\lvert\langle\Psi_{\mathrm{GS}}\vert\Psi_{\mathrm{MICS}}\rangle\rvert, for varying LL at fixed d=5d=5. Particularly, when the graph possesses multiple MICSs, the equal-weight superposition is considered, ∣ΨMICS⟩∝∣ΨMICS1⟩+∣ΨMICS2⟩+⋯\lvert\Psi_{\mathrm{MICS}}\rangle\propto\lvert\Psi_{\mathrm{MICS1}}\rangle+\lvert\Psi_{\mathrm{MICS2}}\rangle+\cdots.

Figure 7. Product-state ansatz for small graphs. (a) Total entanglement entropy and (b) fidelity with respect to the MICS-based product-state ansatz, Eq. (23), of the ground state with homogeneous boundary, ϵi,f=0\epsilon_{i,f}=0, for different LL at fixed d=5d=5. A collapse in the behaviors can be observed in both observables. The curves are categorized into five groups according to the properties of the MICSs of the graphs for a clear presentation.

The behaviors of the quantum state is fully consistent with the ansatz when the graph has a unique MICS (blue, orange), or when the graph has multiple MICSs but all the MICSs are composed by single vertices as cliques (red). See Table I in Appendix A for a list of graphs. In these cases, the fidelity converges to 1 for large LL, while the entropy converges to values reflecting the bound states and/or the superposition states. For example, for large LL, S5−1=0S_{5-1}=0 because G5−1\mathcal{G}_{5-1} has a MICS of four individual vertices, S5−2=2SC2S_{5-2}=2S_{\mathcal{C}_2} because G5−2\mathcal{G}_{5-2} has a MICS consisting of a 2-clique, and S4−4=4ln⁡2S_{4-4}=4\ln2 because G4−4\mathcal{G}_{4-4} has a MICS consisting two pairs of equivalent vertices.

However, the quantum states go beyond the MICS product-state ansatz when the graph possesses multiple MICSs consisting of cliques of M≥2M\geq2 vertices. These MICSs can be either equivalent, e.g., G4−2\mathcal{G}_{4-2}, G5−8\mathcal{G}_{5-8}, G5−12\mathcal{G}_{5-12}, and G5−16\mathcal{G}_{5-16}, or inequivalent to each other, G5−6\mathcal{G}_{5-6}, G5−10\mathcal{G}_{5-10}, and G5−17\mathcal{G}_{5-17}. These graphs are characterized by high permutation symmetry, cf. Table I in Appendix A. In the quantum many-body system, this symmetry is inherited in the Hilbert space structure, and induces hybridization and binding effects. This leads to strong quantum correlations beyond the ansatz.

Hybridization and binding

The numerical evidences indicate that the ground state of the system at homogeneous implementation deviates from the tentative product state ansatz, Eq. (13), when the symmetry of the graph is high. We proceed to formally investigate how the interplay between symmetry of the Hilbert space and geometric constraints leads to hybridization and binding of the product states, and induces quantum correlations and potentially bound states.

Binding in the KqK_q graphs

The bound states in complete graphs, KqK_q, constitute the first effects of symmetry. They stem from coordinated enhancement of equivalent scattering channels induced by symmetry. The energy of the logical-zero state, ∣ψ0⟩⊗q\lvert\psi^0\rangle^{\otimes q}, is significantly lowered and becomes the ground state of the system.

The Hamiltonian HKqH_{K_q} couples ∣ψ0⟩⊗q\lvert\psi^0\rangle^{\otimes q} in the “palm” to lattice sites in the “fingers”, H∣ψ0⟩⊗q=qE0∣ψ0⟩⊗q−t~q∣B⟩H\lvert\psi^0\rangle^{\otimes q}=qE_0\lvert\psi^0\rangle^{\otimes q}-\tilde{t}\sqrt{q}\lvert B\rangle, where ∣B⟩=1q∑n=1q∣n,d+1⟩⊗∣ψ0⟩⊗(q−1)\lvert B\rangle=\frac{1}{\sqrt{q}}\sum_{n=1}^{q}\lvert n,d+1\rangle\otimes\lvert\psi^0\rangle^{\otimes(q-1)} is the “border state”, and where t~=tψ0(d)\tilde{t}=t\psi^0(d) is the hopping amplitude on the boundary, with ψ0(d)=2/(d+1)sin⁡[πd/(d+1)]\psi^0(d)=\sqrt{2/(d+1)}\sin[\pi d/(d+1)] the wavefunction on site dd. The border state ∣B⟩\lvert B\rangle thus provides a scattering channel composed symmetrically from qq equivalent and independent channels along the “fingers”.

The scattering channels effectively induce a self energy upon the bare ∣ψ0⟩⊗q\lvert\psi^{0}\rangle^{\otimes q} state,

Σ=(q−1)t~2⟨d+1∣G∣d+1⟩.(18)\Sigma=(q-1)\tilde{t}^{2}\langle d+1|G|d+1\rangle. \tag*{(18)}

Here, G=1/[E−(q−1)E0−h]G=1/[E-(q-1)E_{0}-h] is the propagator along a one-dimensional lattice with Hamiltonian hh and energy shifted by (q−1)E0(q-1)E_{0} due to contribution from the (q−1)(q-1) ∣ψ0⟩\lvert\psi^{0}\rangle factors in ∣B⟩\lvert B\rangle. The propagator further has an overall factor of (q−1)(q-1) instead of qq, which appears as an effective reduction of scattering channels.

The energy of the dressed ∣ψ0⟩⊗q\lvert\psi^{0}\rangle^{\otimes q} state can thus be determined by the self-energy equation as E≈(q−1)E0−2tcosh⁡(παq/(d+1))E\approx(q-1)E_{0}-2t\cosh(\pi\alpha_{q}/(d+1)), with

1+αq2=q−1παq(1−e−2παq).(19)1+\alpha_{q}^{2}=\frac{q-1}{\pi\alpha_{q}}\left(1-e^{-2\pi\alpha_{q}}\right). \tag*{(19)}

Its energy is reduced to below the threshold E<(q−1)E0−2tE<(q-1)E_{0}-2t, and it is thus a bound state with wavefunctions decaying along the one-dimensional lattice.

Bound states are thus correlated quantum many-body states induced by symmetry and geometric constraints. Symmetry induces dressing through scattering channels to the bare logical-zero state, ∣ψ0⟩⊗q\lvert\psi^{0}\rangle^{\otimes q} and significantly lowers its energy, while geometric constraints increase the energy cost for a propagating state. Detailed derivations are available in Appendix D.

Hybridization in the P4\mathcal{P}_{4} graph

Besides coordinated enhancement, symmetry leads to deviation to the product state ansatz through hybridization. The N=4N=4 path graph, P4=G4−2\mathcal{P}_{4}=\mathcal{G}_{4-2}, has two equivalent MICSs, each of them consisting of a vertex and a 2-clique. It provides an example how coherent hybridization between the two symmetry-related MICS product states deforms the constituent pair wavefunctions.

The product state ansatz predicts two basis states related by the reflection symmetry (1,2,3,4)↔(4,3,2,1)(1,2,3,4)\leftrightarrow(4,3,2,1), formally written as ∣Ψ↑⟩=∣A⟩1,2⊗∣B⟩4,3\lvert\Psi_{\uparrow}\rangle=\lvert A\rangle_{1,2}\otimes\lvert B\rangle_{4,3} and ∣Ψ↓⟩=∣B⟩1,2⊗∣A⟩4,3\lvert\Psi_{\downarrow}\rangle=\lvert B\rangle_{1,2}\otimes\lvert A\rangle_{4,3}. Specifically for P4\mathcal{P}_{4}, these components are ∣A⟩m,n=∣ψ0⟩m⊗∣ψ0⟩n\lvert A\rangle_{m,n}=\lvert\psi^{0}\rangle_{m}\otimes\lvert\psi^{0}\rangle_{n} and ∣B⟩m,n=∣K2⟩m,n\lvert B\rangle_{m,n}=\lvert K_{2}\rangle_{m,n}. The basis state ∣Ψ↑⟩\lvert\Psi_{\uparrow}\rangle (∣Ψ↓⟩\lvert\Psi_{\downarrow}\rangle) is an exact eigenstate of the Hamiltonian P2HP4P2P_{2}H_{\mathcal{P}_{4}}P_{2} (P3HP4P3P_{3}H_{\mathcal{P}_{4}}P_{3}), where PnP_{n} projects out the non-MICS lattice sites ∣n,ℓ≥d+1⟩\lvert n,\ell\ge d+1\rangle. Nevertheless, applying the bare Hamiltonian on these states leads to leakage into the non-MICS Hilbert subspace, ∣⟨2/3,ℓ=d+1∣HP4∣Ψ↑/↓⟩∣>0\lvert\langle2/3,\ell=d+1\lvert H_{\mathcal{P}_{4}}\rvert\Psi_{\uparrow/\downarrow}\rangle\rvert>0.

To appreciate the role of the reflection symmetry, we additionally consider the paw graph G4−3\mathcal{G}_{4-3}, which has an extra edge <2,4><2,4> on top of P4\mathcal{P}_{4}. This graph has a single MICS, and ∣Ψ↑⟩\lvert\Psi_{\uparrow}\rangle is the product state ansatz for its unique ground state. This leakage HG4−3∣Ψ↑⟩H_{\mathcal{G}_{4-3}}\lvert\Psi_{\uparrow}\rangle is negligible compared to the energy difference between the MICS state and the suboptimal ICS state, ∣ψ0⟩1∣ψ0⟩2∣ψ0⟩3∣ψ0⟩4\lvert\psi^{0}\rangle_{1}\lvert\psi^{0}\rangle_{2}\lvert\psi^{0}\rangle_{3}\lvert\psi^{0}\rangle_{4}. According to perturbation theory, ∣Ψ↑⟩\lvert\Psi_{\uparrow}\rangle thus serves a good approximation for the ground state in the indent and continuum limit, L≫d≫1L\gg d\gg1.

For P4\mathcal{P}_{4}, however, the reflection symmetry leads to degenerate basis product states. The tiny leakage can potentially induce significant deformation to the ground state while lifting the degeneracy. As a result, the exact ground state behaves differently from the symmetric superposition ∣Ψ+⟩∝∣Ψ↑⟩+∣Ψ↓⟩\lvert\Psi_{+}\rangle\propto\lvert\Psi_{\uparrow}\rangle+\lvert\Psi_{\downarrow}\rangle. We capture the effects of reflection symmetry by expanding the quantum state in the basis,

{Π∣Ψ++⟩, Π(∣Ψ+−⟩+∣Ψ−+⟩)/2, Π∣Ψ−−⟩}.(20)\{\Pi\lvert\Psi_{++}\rangle,\ \Pi(\lvert\Psi_{+-}\rangle+\lvert\Psi_{-+}\rangle)/\sqrt{2},\ \Pi\lvert\Psi_{--}\rangle\}. \tag*{(20)}

Here, Π=P<2,3\Pi=P_{<2,3} [cf. Eq. (5)] describes the geometric constraint between the 2nd and 3rd dimensions. ∣Ψρσ⟩=∣μρ⟩1,2⊗∣μσ⟩4,3\lvert\Psi_{\rho\sigma}\rangle=\lvert\mu_{\rho}\rangle_{1,2}\otimes\lvert\mu_{\sigma}\rangle_{4,3}, with ρ,σ=±\rho,\sigma=\pm. The basis ∣μ±⟩m,n=∣A⟩m,n±∣B⟩m,n2(1±s)\lvert\mu_{\pm}\rangle_{m,n}=\frac{\lvert A\rangle_{m,n}\pm\lvert B\rangle_{m,n}}{\sqrt{2(1\pm s)}} with s=⟨A∣B⟩s=\langle A|B\rangle. This basis is chosen, because the non-projected wavefunctions ∣Ψμν⟩\lvert\Psi_{\mu\nu}\rangle are orthonormal and nearly resonant with each other. The antisymmetric superposition ∣Ψ+−⟩−∣Ψ−+⟩\lvert\Psi_{+-}\rangle-\lvert\Psi_{-+}\rangle does not couple into the basis. Particularly, the symmetric product state can be written as, ∣Ψ+⟩=1+s2(1+s2)∣Ψ++⟩−1−s2(1+s2)∣Ψ−−⟩\lvert\Psi_{+}\rangle=\frac{1+s}{\sqrt{2(1+s^{2})}}\lvert\Psi_{++}\rangle-\frac{1-s}{\sqrt{2(1+s^{2})}}\lvert\Psi_{--}\rangle.

The Schrödinger equation projected onto this basis, Eq. (20), is H∣ψ⟩=ES∣ψ⟩H\lvert\psi\rangle=E S\lvert\psi\rangle, with (HΠ)μν=⟨Ψμ∣H∣Ψν⟩(H_{\Pi})_{\mu\nu}=\langle\Psi_{\mu}|H|\Psi_{\nu}\rangle and Sμν=⟨Ψμ∣Ψν⟩S_{\mu\nu}=\langle\Psi_{\mu}|\Psi_{\nu}\rangle the Gram matrix. The indices μ,ν\mu,\nu run over the three basis states, and the ground state ψ=(ψ++,ψ+−,ψ−−)T\psi=(\psi_{++},\psi_{+-},\psi_{--})^{T} is normalized as ψ†Sψ=1\psi^{\dagger}S\psi=1. The system thus hosts deformed eigenstate,

∣Ψ⟩=12(1−s2)Π∣Ψ′⟩(21)\lvert\Psi\rangle=\frac{1}{2(1-s^{2})}\Pi\lvert\Psi'\rangle \tag*{(21)}
∣Ψ′⟩=(β+γ)∣A⟩1,2⊗∣A⟩4,3+(β−γ)∣B⟩1,2⊗∣B⟩4,3−δ(∣A⟩1,2⊗∣B⟩4,3+∣B⟩1,2⊗∣A⟩4,3)(22)\lvert\Psi'\rangle=(\beta+\gamma)\lvert A\rangle_{1,2}\otimes\lvert A\rangle_{4,3}+(\beta-\gamma)\lvert B\rangle_{1,2}\otimes\lvert B\rangle_{4,3} -\delta\bigl(\lvert A\rangle_{1,2}\otimes\lvert B\rangle_{4,3}+\lvert B\rangle_{1,2}\otimes\lvert A\rangle_{4,3}\bigr) \tag*{(22)}

where β=(ψ+++ψ−−)−s(ψ++−ψ−−)\beta=(\psi_{++}+\psi_{--})-s(\psi_{++}-\psi_{--}), γ=ψ+−2(1−s2)\gamma=\psi_{+-}\sqrt{2(1-s^{2})}, δ=s(ψ+++ψ−−)−(ψ++−ψ−−)\delta=s(\psi_{++}+\psi_{--})-(\psi_{++}-\psi_{--}).

In the absence of the projection operator Π\Pi, the three basis states in Eq. (20) remain orthonormal and decoupled by construction. The geometric constraint imposed by the projector Π\Pi thus introduces overlap of the basis states through S≠1S \ne1, as well as a coupling between them through HΠ≠0H_{\Pi} \ne0. This leads to non-perturbative hybridization of the quantum state, and thus deviation from the product state ansatz.

We quantify this geometric deformation by considering d=3d = 3 and LL varying from 10 to 80, see Figure 8(a). We evaluate the fidelity of the exactly solved quantum state against the symmetric composition of the product state ∣Ψ+⟩\lvert\Psi_{+}\rangle, and the state solved within the three-state basis. Both fidelities deteriorate as LL increases, signaling an enhanced hybridization. This indicates that the hybridization is non-perturbative in indent limit. However, the energy of the exact quantum state converges to the product state ansatz in indent limit, see Figure 8(b). The decreasing gap indicates that, even though hybridization brings the energy of the state to below the propagating threshold, it does not lead to a bound state, since the nominal decaying length extends with the system length. More importantly, unlike binding, hybridization has no energetic contribution in indent limit. As a control comparison, the fidelity and energy for the G4−3G_{4-3} quantum state are also shown. Indeed, due to the lack of degeneracy, the deviation of the exact quantum state from the product state ansatz is perturbative.

Figure 8. Hybridization of quantum state in P4\mathcal{P}_{4} graph. (a) The fidelity of the product state ansatz, Eq. (23), and the hybridized ansatz, Eq. (18) with respect to the exact quantum state for P4\mathcal{P}_{4} graph at homogeneous boundary. (b) The energy of the exact P4\mathcal{P}_{4} state compared to the energy of the product state ansatz. The gap between them vanishes in indent limit. For comparison, the control case of paw graph G4−3\mathcal{G}_{4-3} is also shown, where the product state ansatz is precise up to negligible perturbation.

Apart from complete graphs, genuine bound states are also found in the 5-cyclic graph G5−8=C5G_{5-8}=C_{5}, and the house graph G5−12G_{5-12} among all graphs with N=5N=5 vertices, cf. Table I in Appendix A. These graphs are later referred to binding motifs, and are all collected in the set Gbound={P2,K3,K4,C5,G5−12,K6,…}\mathcal{G}_{\mathrm{bound}}=\{P_{2},K_{3},K_{4},C_{5},G_{5-12},K_{6},\ldots\}. Cliques constitute a major family of motifs.

Product-state ansatz based on cliques and motifs

Bound states are generically associated to graphs with high symmetry, particularly complete graphs. They urge a modification to the tentative product-state ansatz for a comprehensive description of quantum dynamics along annealing in indent limit. Particularly, since hybridization induces weak energetic effects in indent limit, it is not explicitly taken into account in the ansatz. The quantum many-body state can be represented by a generic IS, S={n∣σnIS=1}⊂VS=\{n\mid\sigma^{\mathrm{IS}}_{n}=1\}\subset\mathcal{V}, which is not necessarily maximal. Along the dimensions n∈Sn\in S corresponding to occupied vertices, the state hosts the logical-one mode ∣ψ1⟩\lvert\psi^{1}\rangle generated by a chain of LL sites with boundary term ϵf\epsilon_f. Particularly, we denote the ground state and first excited state for logical-one mode for the instantaneous boundary condition as ∣ψ10⟩\lvert\psi^{0}_{1}\rangle and ∣ψ11⟩\lvert\psi^{1}_{1}\rangle, respectively. These notations are convenient for discussion on gap behaviors.

The rest of the vertices V∖S\mathcal{V}\setminus S is further grouped into motifs Mr∈GboundM_r\in\mathcal{G}_{\mathrm{bound}}, r=1,…,Rr=1,\ldots,R, such that the union M∪S\mathcal{M}\cup S is an independent motif set with M={Mr}⊂V∖S\mathcal{M}=\{M_r\}\subset\mathcal{V}\setminus S. The quantum state ansatz then associates each motif to its corresponding basis state ∣Mr⟩\lvert M_r\rangle, subject to the boundary term ϵi\epsilon_i. A motif-based bound state represents a classical configuration where the corresponding vertices are logical-zeros.

The final remaining vertices in U=V∖(S∪M)\mathcal{U}=\mathcal{V}\setminus(S\cup\mathcal{M}) are then assigned with the logical-zero mode ∣ψ0⟩\lvert\psi^{0}\rangle. This is the ground state of a chain of dd sites subject to boundary term ϵi\epsilon_i. The factor states ∣ψ0⟩\lvert\psi^{0}\rangle and ∣ψ1⟩\lvert\psi^{1}\rangle are identical to the ones entering the tentative ansatz, Eq. (13).

The comprehensive product state ansatz associated to SS and M\mathcal{M} is thus

∣Ψ⟩=⨂n∈S∣ψ1⟩n⊗⨂n∈U∣ψ0⟩n⊗⨂r=1R∣Mr⟩n∈Mr.(23)\lvert\Psi\rangle=\bigotimes_{n\in S}\lvert\psi^{1}\rangle_n\otimes\bigotimes_{n\in\mathcal{U}}\lvert\psi^{0}\rangle_n\otimes\bigotimes_{r=1}^{R}\lvert M_r\rangle_{n\in M_r}. \tag*{(23)}

In the following, unless explicitly specified, we focus on the effects of cliques, ∣Kq≥2⟩\lvert K^{q\geq2}\rangle, among all binding motifs. This improves the clarity of our discussion without losing the essential features of our system. The factor states are summarized as follows,

FactorBulkBoundaryLogic
∣ψ0⟩\lvert\psi^{0}\rangle1D chain of length ddϵi\epsilon_i0
∣ψ0/11⟩\lvert\psi^{1}_{0/1}\rangle1D chain of length LLϵi,ϵf\epsilon_i,\epsilon_f1
∣M⟩\lvert M\rangle∣M∣\lvert M\rvert-D lattice from motif MMϵi\epsilon_i0⊗∣M∣0^{\otimes\lvert M\rvert}
∣Kq≥2⟩\lvert K^{q\geq2}\rangleqq-D lattice from Kq\mathcal{K}_qϵi\epsilon_i0⊗q0^{\otimes q}

Table 20.

Energetics for solving MIS

With homogeneous boundary, the quantum blockaded-chain model thus selects the independent set energetically. To identify the ground state, we associate the cliques with weights determined by the energies of the bound states. The energy of a product state is E=∑r=1REr+N0E0E=\sum_{r=1}^{R}E_r+N_0E_0, where ErE_r is the energy of the bound state ∣Kqr⟩\lvert K^{q_r}\rangle, and N0=N−∑r=1RqrN_0=N-\sum_{r=1}^{R}q_r is the number of vertices not belonging to any clique. We can thus assign an effective weight to these cliques to account for this energy,

Wq=∣EM−qE0E1−E0∣.(24)W_q=\left\lvert\frac{E_M-qE_0}{E_1-E_0}\right\rvert. \tag*{(24)}

The weight WqW_q increase strictly monotonically with qq, cf. Inequality (13), and decreases as the shape ratio d/Ld/L approaches 0, i.e., the indent limit. They converge to Wq∞≈1+αq2W_q^\infty\approx1+\alpha_q^2, q≥2q\geq2 in indent limit, c.f., Eq. (19), with particularly W2∞∼1.071W_2^\infty\sim1.071 [59]. These weights measure the boundedness of the quantum states, and provide an effective count of vertices inside the clique. At homogeneous boundary fields, maximizing the clique weight minimizes the energy within the clique-product ansatz. The ground state thus search for the ICS with the maximum effective number of vertices, i.e., the MWICS of the graph. A weight can be assigned to a general binding motif by replacing qq by ∣M∣|M|.

We further investigate the performance of quantum annealing for a specific set of graphs. For clarity of discussion, we consider the family of triangle-free graphs. Per definition, these graphs do not host cliques with M≥3M \ge3 vertices. The dominant contributions from GboundG_{\mathrm{bound}} are thus a pair of connected vertices, P2P_2. Besides, the graphs can also possibly host a binding motif of C5∈GboundC_5 \in G_{\mathrm{bound}}, or any other unexplored binding motifs with M≥6M \ge6 vertices. For simplicity of the discussion, we explicitly omit the contributions from these binding motifs momentarily. Effectively, the blockaded-chain model thus searches for the dissociation set D\mathcal{D} which maximizes N1+W2∞N2N_1 + W_2^\infty N_2. In graph theory, a dissociation set contains N1N_1 single vertices and N2N_2 vertex pairs, which are independent from each other.

We clarify whether and when the effective optimization problem facilitates the search for MIS in triangle-free, cubic graphs. These graphs have lower bound for its independence number, α(G)≥310N\alpha(G) \ge\frac{3}{10}N [60]; and elementary edge counting yields an upper bound for its dissociation set, 6N1+10N2≤3N6N_1 + 10N_2 \le3N [61]. A failure for the effective optimization problem to reproduce the MIS solution can happen when N2≥⌈1/(W2∞−1)⌉=15N_2 \ge\lceil1/(W_2^\infty- 1)\rceil= 15. In other words, the MIS solution is produced for a triangle-free, cubic graph with N≤64N \le64 vertices; and a suboptimal solution with ⌊N/64⌋\lfloor N/64\rfloor vertices fewer than MIS can potentially be produced for a larger graph. Moreover, if the graph is further planar, α(G)≥514N\alpha(G) \ge\frac{5}{14}N [62], this threshold is increased to N≤72N \le72. Indeed, the important index is the density of the independent set, α(G)/N\alpha(G)/N, since a tradeoff between single vertex and vertex pair becomes hindered by constraint with a dense MIS. If the MIS occupies more than half of the vertices of the graph, α(G)/N≥1/2\alpha(G)/N \ge1/2, the effective optimization produces the correct MIS solution. Our statements particularly apply for cubic graphs with girth at least 6, since cyclic graphs with N≥6N \ge6 vertices are not associated to bound states, CN≥6∉GboundC_{N\ge6} \notin G_{\mathrm{bound}}.

Dominant product-state channel and clique-controlled gaps

When a single MWICS is energetically dominant, the low-energy spectrum is described by the approximately factorizable product states, cf. Eq. (23). Consequently, the energies of the many-body modes are approximately additive, and in particular, the gap behaviors are inherited from the spectra and gaps of the factor states.

The paw graph G4−3\mathcal{G}_{4-3} provides a representative example of this factorized structure, as evidenced by its spectrum

in indent limit L=20,d=3L=20,d=3 shown in Figure 9(a). Its MICS consists of a single vertex {1}\{1\} and an edged pair {3,4}\{3,4\}. The few relevant lowest-lying modes can be factorized as,

Representative low-energy spectra in indent limit

Figure 9. Representative low-energy spectra in indent limit. (a) The spectrum of the blockaded-chain Hamiltonian based on the paw graph G4−3\mathcal{G}_{4-3} with L=20L=20, d=3d=3, compared against the energies of product states estimated by the ansatz Eq. (23). Specifically, the orange curve represents the (10,0,0,0)(1_0,0,0,0) state, red (11,0,0,0)(1_1,0,0,0), green (10,10,0)±(10,0,10)(1_0,1_0,0) \pm(1_0,0,1_0), purple (0,10,0,0)(0,1_0,0,0), and brown (11,0,10)(1_1,0,1_0) ±(11,0,0,10)\pm(1_1,0,0,1_0). The color scheme encodes PTP_T, cf. Eq. (11), and reflects whether the quantum state lies in the Hilbert subspace of correct MIS. (b,c) The spectra based on the K5∖e\mathcal{K}_5 \setminus e graph, G5−20\mathcal{G}_{5-20}, (b) in indent limit L=20,d=3L=20,d=3 and (c) away from indent limit L=20,d=10L=20,d=10. In (b), the orange curve represents the (10,10,0,0)(1_0,1_0,0,0) state, green (11,10,0,0)±(10,11,0,0)(1_1,1_0,0,0) \pm(1_0,1_1,0,0), red (11,11,0,0)(1_1,1_1,0,0), and purple (0,0,10,0,0)+eiθ(0,0,0,10,0)+e2iθ(0,0,0,0,10)(0,0,1_0,0,0)+e^{i\theta}(0,0,0,1_0,0)+e^{2i\theta}(0,0,0,0,1_0), with θ=0,2π/3,4π/3\theta=0,2\pi/3,4\pi/3. The color scheme encodes PTP_T, and partially anti-symmetric states decoupled from the annealing, ∑ℓ1,ℓ2,…,ℓN⟨n,ℓ∣Ψ⟩=0\sum_{\ell_1,\ell_2,\ldots,\ell_N}\langle n,\ell|\Psi\rangle=0, are shown in gray.

Vertex config.Quantum state
(10/11,0,0,0)(1_0/1_1,0,0,0)∣ψ01⟩1⊗∣ψ20⟩⊗∣K2⟩(3,4)|\psi^1_0\rangle_1 \otimes|\psi^0_2\rangle\otimes|K^2\rangle_{(3,4)}
(0,10,0,0)(0,1_0,0,0)∣ψ01⟩2⊗⨂n=1,3,4∣ψ0⟩n|\psi^1_0\rangle_2 \otimes\bigotimes_{n=1,3,4}|\psi^0\rangle_n
(10/11,0,10,0)(1_0/1_1,0,1_0,0)∣ψ01/11⟩1⊗∣ψ0⟩2⊗|\psi^1_0/1_1\rangle_1 \otimes|\psi^0\rangle_2 \otimes
(10/11,0,0,10)(1_0/1_1,0,0,1_0)(∣ψ01⟩3⊗∣ψ0⟩4±∣ψ01⟩4⊗∣ψ0⟩3)(|\psi^1_0\rangle_3 \otimes|\psi^0\rangle_4 \pm|\psi^1_0\rangle_4 \otimes|\psi^0\rangle_3)

Table 22.

up to normalization.

In the early stage of the annealing, ϵi>t\epsilon_i > t, the ground state is given by ∣ψ01⟩1⊗∣ψ0⟩2⊗∣K2⟩(3,4)|\psi^1_0\rangle_1 \otimes|\psi^0\rangle_2 \otimes|K^2\rangle_{(3,4)}. The instantaneous states are localized around ⨂n=14∣n,1⟩\bigotimes_{n=1}^{4}|n,1\rangle, and can be interpreted as logical zero, (0,0,0,0)(0,0,0,0). The uniqueness of the quantum many-body ground state and the classical logical-zero configuration are consistent with each other. The first excited state is approximately four-fold degenerate, representing the four classical configurations (1,0,0,0)(1,0,0,0), (0,1,0,0)(0,1,0,0), (0,0,1,0)(0,0,1,0), and (0,0,0,1)(0,0,0,1). The energy difference between the ground state and these four states is roughly ϵi+t2/ϵi−2t\epsilon_i + t^2/\epsilon_i - 2t. As ϵi\epsilon_i approaches tt, the degeneracy is slowly lifted. The (0,10,0,0)(0,10,0,0) state obtains a relatively higher energy than the (10,0,0,0)(10,0,0,0) state, because the latter hosts a ∣K2⟩3,4\lvert K^2\rangle_{3,4} bound state factor. Meanwhile, the symmetric and antisymmetric superposition states of (10,0,10,0)(10,0,10,0) and (10,0,0,10)(10,0,0,10) remain almost degenerate. The first gap minimum occurs near ϵi≈t\epsilon_i \approx t. The quantum state undergoes a localization-to-delocalization crossover in the 1st1^{\mathrm{st}} dimension, while keeping the common factors in the other dimensions unchanged. Consequently, their energy separation approximately follows the gap between the two lowest eigenstates, ∣ψ01⟩\lvert\psi_0^1\rangle and ∣ψ11⟩\lvert\psi_1^1\rangle, of a one-dimensional chain. This product-state description reproduces the low-energy spectrum and eigenstates accurately, with comparatively more pronounced deviations near the gap minimum.

In the second half of the annealing, a second gap closure takes place around ϵf≈t\epsilon_f \approx t. This corresponds to a transition within the union of MICS hypercuboid subspace, where the (1,0,1,0)(1,0,1,0) and (1,0,0,1)(1,0,0,1) states become energetically more favorable than the (1,0,0,0)(1,0,0,0) state. This transition concerns essentially the ∣K2⟩(3,4)\lvert K^2\rangle_{(3,4)} bound state and the (∣ψ01⟩3⊗∣ψ01⟩4+∣ψ01⟩4⊗∣ψ01⟩3)(\lvert\psi_0^1\rangle_3 \otimes\lvert\psi_0^1\rangle_4 + \lvert\psi_0^1\rangle_4 \otimes\lvert\psi_0^1\rangle_3) superposition state in the two-dimensional L-shaped domain along the 3rd3^{\mathrm{rd}} and 4th4^{\mathrm{th}} dimensions. Particularly, these are the ground state and the second excited state, while the first excited state is decoupled from the annealing since its anti-symmetric structure between the 3rd3^{\mathrm{rd}} and 4th4^{\mathrm{th}} dimensions.

Generically for factorizable quantum states, the behaviors of their gaps in the second half of the protocol are controlled by their cliques,

Δmin⁡(G;L,d)≈Δmin⁡(M;L,d).(25)\Delta_{\min}(\mathcal{G};L,d) \approx\Delta_{\min}(M;L,d). \tag*{(25)}

where Δmin⁡\Delta_{\min} refers to local minima. For factorizable quantum states, the quantum state already lies within the MICS hypercuboid subspace at the midpoint of the annealing. In the second half of the annealing, the factor clique-based bound state associated to each individual clique in M∈MM \in\mathcal{M} transitions into superposition state independently. This dependence of gap behaviors on cliques is examined and confirmed for all small graphs with N≤5N \leq5 vertices in Figure 10(a,b). The minimum gap due to the cliques follows the behaviors of the corresponding complete graphs. For a few graphs with high symmetry, a deviation from the clique-based behaviors can be seen due to hybridization and binding.

Figure 10. Scaling behaviors of gaps. The gap in the second half of the annealing around ϵf≈t\epsilon_f \approx t shows spectral collapse associated to the largest clique in the MICS. These are shown (a) in the entire protocol in linear scale, and (b) in the vicinity of the minimum gap in logarithmic scale. This collapse is shown for all graphs with N=2,3,4,5N = 2, 3, 4, 5 vertices, and for the implementation of L=20L = 20, d=5d = 5. Dashed curves indicate graphs, including G4−4G_{4-4}, G4−5G_{4-5}, G5−8G_{5-8}, G5−11G_{5-11}, G5−12G_{5-12}, G5−19G_{5-19}, G5−20G_{5-20}. These graphs have high symmetry and subject to strong hybridization and/or binding effects, and their behaviors deviate from the generic scenarios. (c,d) Scaling behaviors of the minimum gap for complete graphs KqK_q, computed using the recursive generation method. The minimum gap scales (c) exponentially with LL, and (d) polynomially with qq. These trends also apply to clique factors.

We analyse the behaviors of the minimum gap for different cliques. The low-energy spectrum associated to the complete graphs KqK_q can be solved using the recursive generation method, as detailed in Appendix E. This method applies to a sequence of graphs which can be generated with a clear pattern, and assists us to probe the low-energy spectra for large qq and LL otherwise formidable with exact diagonalization. The minimum gap scales exponentially with LL and polynomially with qq as Δmin⁡∼q−αqL\Delta_{\min} \sim q^{-\alpha_q L}, see Figure 10(c,d). Particularly, the exponent coefficient goes from αq≈0.20\alpha_q \approx0.20 for q=2q = 2 to α≈0.25\alpha\approx0.25 for q=5q = 5. This is consistent with the results presented in Ref. [35]. See Appendix D for details. Our analysis is further supported by PTP_T, Eq. (11), as illustrated by the color code in Figure 9.

The paw graph G4−3G_{4-3} example illustrates the spectrum associated with a unique dominant MWICS. Consistent with our analysis for homogeneous boundary, hybridization effects between distinct MICS sectors are negligible. As a result, the low-energy problem admits an approximate reduction to the dynamics of its constituent factors. The gap behaviors is therefore controlled by the clique, leading to the clique-controlled behavior. As we clarify soon, this factorized description ceases to apply when several macroscopically distinct MWICS constructions become energetically competitive.

Competing channels and hybridization induced gap closing

We further investigate the case of competing ICSs, using graph G5−20=K5∖e\mathcal{G}_{5-20}=K_5\setminus e as an example. This graph has one edge removed from the K5K_5 complete graph, and it has three competing ICSs: (i) a set of two vertices {1,2}\{1,2\} which is also the MIS, and (ii) two sets each consisting of a single 4-clique, which are second largest ICSs and referred to as suboptimal ICSs (subICSs). These relevant product states can be written as

Vertex config.Quantum state
(10,10,0,0,0)(1_0,1_0,0,0,0)∣ψ01⟩1⊗∣ψ01⟩2⊗⨂n=3,4,5∣ψ00⟩n\lvert\psi^{1}_{0}\rangle_1\otimes\lvert\psi^{1}_{0}\rangle_2\otimes\bigotimes_{n=3,4,5}\lvert\psi^{0}_{0}\rangle_n
(11,10,0,0,0)(1_1,1_0,0,0,0)(∣ψ01⟩1⊗∣ψ11⟩2±∣ψ11⟩1⊗∣ψ01⟩2)⊗⨂n=3,4,5∣ψ00⟩n\left(\lvert\psi^{1}_{0}\rangle_1\otimes\lvert\psi^{1}_{1}\rangle_2\pm\lvert\psi^{1}_{1}\rangle_1\otimes\lvert\psi^{1}_{0}\rangle_2\right)\otimes\bigotimes_{n=3,4,5}\lvert\psi^{0}_{0}\rangle_n
(10,11,0,0,0)(1_0,1_1,0,0,0)
(11,11,0,0,0)(1_1,1_1,0,0,0)∣ψ11⟩1⊗∣ψ11⟩2⊗⨂n=3,4,5∣ψ00⟩n\lvert\psi^{1}_{1}\rangle_1\otimes\lvert\psi^{1}_{1}\rangle_2\otimes\bigotimes_{n=3,4,5}\lvert\psi^{0}_{0}\rangle_n
(0,0,0,0,0)(0,0,0,0,0)∣K4⟩(1,3,4,5)⊗∣ψ00⟩2+∣K4⟩(2,3,4,5)⊗∣ψ00⟩1\lvert K^4\rangle_{(1,3,4,5)}\otimes\lvert\psi^{0}_{0}\rangle_2+\lvert K^4\rangle_{(2,3,4,5)}\otimes\lvert\psi^{0}_{0}\rangle_1
(0,0,10,0,0)(0,0,1_0,0,0)∣ψ00⟩1⊗∣ψ00⟩2⊗[∣ψ01⟩3⊗∣ψ00⟩4⊗∣ψ00⟩5\lvert\psi^{0}_{0}\rangle_1\otimes\lvert\psi^{0}_{0}\rangle_2\otimes[\lvert\psi^{1}_{0}\rangle_3\otimes\lvert\psi^{0}_{0}\rangle_4\otimes\lvert\psi^{0}_{0}\rangle_5
(0,0,0,10,0)(0,0,0,1_0,0)+eiθ∣ψ00⟩3⊗∣ψ01⟩4⊗∣ψ00⟩5+e^{i\theta}\lvert\psi^{0}_{0}\rangle_3\otimes\lvert\psi^{1}_{0}\rangle_4\otimes\lvert\psi^{0}_{0}\rangle_5
(0,0,0,0,10)(0,0,0,0,1_0)+e2iθ∣ψ00⟩3⊗∣ψ00⟩4⊗∣ψ01⟩5]/3+e^{2i\theta}\lvert\psi^{0}_{0}\rangle_3\otimes\lvert\psi^{0}_{0}\rangle_4\otimes\lvert\psi^{1}_{0}\rangle_5]/\sqrt{3}

Table 1.

The first three groups describe modes in the MIS subspace. The fourth row is the fully symmetric combination of the two K4K^4-based channels. The final group consists of three modes lying in the suboptimal ICS subspace, with θ=0\theta=0, 2π/32\pi/3, 4π/34\pi/3.

The automorphism of the graph G5−20\mathcal{G}_{5-20} is isomorphic to the direct product of permutation groups S2S_2 and S3S_3, Aut⁡(G5−20)≃S2×S3\operatorname{Aut}(\mathcal{G}_{5-20})\simeq S_2\times S_3. Here, S2S_2 permutes between vertices 1 and 2, and S3S_3 permutes among the vertices 3, 4, and 5. These permutation symmetries are inherited by the quantum system. For each permutation symmetry SmS_m, there exist mm corresponding symmetry-related modes. Among them, a single fully symmetric mode is bright and coupled to the fully symmetric initial state, while the rest m−1m-1 modes are dark and strictly inaccessible during the protocol. These include the antisymmetric superposition of (11,10,0,0,0)(1_1,1_0,0,0,0) and (10,11,0,0,0)(1_0,1_1,0,0,0) states, and the θ=2π/3\theta=2\pi/3 and θ=4π/3\theta=4\pi/3 superposition of (0,0,10,0,0)(0,0,1_0,0,0), (0,0,0,10,0)(0,0,0,1_0,0), and (0,0,0,0,10)(0,0,0,0,1_0) states. Consequently, only crossings between states in the accessible fully symmetric sector are dynamically relevant.

Within each orbit of mm symmetry-related channels, one trivial-irrep combination is bright and the remaining m−1m-1 orthogonal combinations are dark.

In indent limit, the MICS has a larger weight. Correspondingly, the (10,10,0,0,0)(1_0,1_0,0,0,0) state is the ground state, and the low-energy quantum dynamics lies predominantly in the MIS hypercuboid. The spectrum for L=20L=20, d=3d=3 as shown in Figure 9(b) supports this energetic picture, where the low-lying MICS-compatible quantum states are all characterized by PT≈1P_T\approx1 as defined in Eq. (11).

Although the spectrum largely matches a fully factor-izable system, apparent deviation in the fully symmetric states can be observed at around ϵi≈t\epsilon_i\approx t. In this regime, the (10,10,0,0,0)(1_0,1_0,0,0,0) state and the (0,0,0,0,0)(0,0,0,0,0) states are almost degenerate, leading to hybridization between them. The hybridized spectrum preserves the overall branch structure inferred from the ansatz, but the anti-crossing in the vicinity of ϵi=t\epsilon_i=t is substantially modified. Unlike the factor-controlled gap in § 3.1 E, this gap is not inherited from a single-chain spectrum, but rather controlled by the effective coupling between the two channels after taking their nonorthogonality into account. This gap scales according to the effective coupling ⟨MICS∣H∣subICS⟩\langle\mathrm{MICS}|H|\mathrm{subICS}\rangle, which is suppressed by spatially small mode overlap.

Away from the indent limit, competition between the two ICSs affects the spectrum in a more pronounced manner. This is illustrated by the spectrum for L=20L=20, d=10d=10 in Figure 9(c). The low energy dynamics takes place predominantly in the subICS subspace, until the later stage of the annealing, ϵf≈t\epsilon_f\approx t, where it transitions into the MIS subspace. This is consistent with the fact that the subICS is energetically more favorable than the MICS at homogeneous boundary.

The two geometries in Figure 9(b,Figure 9c) encode the same MIS problem, but favor different clique arrangements. At d=3d=3, the two-vertex MICS is energetically favored, and its product state closely describes the midpoint ground state. At d=10d=10, the single-clique subICS has a slightly larger weight, but the ground state has substantial overlap with both arrangements. Thus the clique weights rank the product configurations, and changing the chain geometry tunes the competition without changing the encoded problem.

Dynamics towards target subspace

The spectral structure of the blockaded-chain model motivates a diabatic annealing scheme that preserves the MIS target even though the dynamics leaves the ground state due to small energy gaps. The family of diamond-chain graphs provide a concrete playground for investigating the effectiveness of the scheme.

Diamond chain graphs as a recursive family of competing sectors

The diamond chain graphs, Dν\mathcal{D}_{\nu}, provide a paradigmatic example for investigating competition between different ISs in quantum annealing. As shown in Figure 11(a), Dν\mathcal{D}_{\nu} is constructed by an initial vertex attached by a chain of ν\nu 3-cyclic graphs K3K_3, which adds up to N=3ν+1N=3\nu+1 vertices in total. The diamond-chain family provides a controlled setting for studying competition between independent set sectors. Each graph Dν\mathcal{D}_{\nu} has a unique MIS with ν+1\nu+1 vertices, together with O(2ν)O(2^\nu) subISs with ν\nu vertices. This exponential proliferation of almostoptimal configurations creates a competing landscape that can hinder annealing dynamics.

Figure 11. Diamond-chain graphs. (a-c) The first three diamond-chain graphs, DνD_{\nu}, ν=1,2,3\nu= 1, 2, 3. (d,e) The maximum and suboptimal independent clique sets for D3D_{3}, each possessing total weight WMICS=4W1W_{\mathrm{MICS}} = 4W_{1} and WsubICS=W2+2W3W_{\mathrm{subICS}} = W_{2} + 2W_{3}, respectively. The suboptimal solution is energetically more favorable when WsubICS>WMICSW_{\mathrm{subICS}} > W_{\mathrm{MICS}}.

Meanwhile, the performance of quantum annealing depends on the weights of the cliques. For ν≥2\nu\ge2, the MICS of the graph is exactly the MIS, with (ν+1)(\nu+ 1) K1\mathcal{K}^{1}; while the subICS consists of two K3\mathcal{K}^{3} and (ν−2)(\nu- 2) K2\mathcal{K}^{2}, compatible to the subIS.

The two competing ICSs for D3D_{3} are shown in Figure 11(d) and (e). When 2W3+(ν−2)W2−(ν+1)W1<02W_{3} + (\nu- 2)W_{2} - (\nu+ 1)W_{1} < 0, the MICS has the largest weight. The diamond chain graphs follow a clear pattern. Therefore, their associated low-energy spectra and dynamics can be computed with the recursive generation method, allowing us to probe a larger range of NN and LL, see Appendix E for details.

The spectra shown in Figure 12 substantiate the relation between the quantum dynamics and the weights of the ICSs. Given fixed LL and dd, the spectrum associated to DνD_{\nu} is characterized by a single gap closure, where the system transitions from the subICS state to the MICS state.

Diamond chain spectra

Figure 12. Diamond chain spectra. The spectra of the lowest 100 modes for the D1D_{1} to D4D_{4} diamond chain graphs for different L=9,15,21L = 9, 15, 21 with fixed d=3d = 3. The color encodes whether the branch lies within the correct MICS subspace. The position of the minimum gap shifts towards an earlier stage as the indent limit is approached.

The position of this gap is shifted by the shape ratio. Away from the indent limit, W2>32W1W_{2} > \frac{3}{2}W_{1}, the subICS has a larger weight. As the indent limit is approached, the weights of different cliques become more uniform, and the MICS thus becomes eventually more favorable. Correspondingly, the quantum state at the midpoint of the protocol achieves the subICS configuration away from indent limit, and achieves the MICS configuration in indent limit. The gap minimum shifts towards earlier stage of the annealing with decreasing ratio of d/Ld/L, for a given diamond-chain graphs DνD_{\nu}, see Figure 12. Concomitantly, increasing number of low-energy modes lies in the MICS subspace, and all the relevant low-energy branches becomes MICS compatible for large L=24L = 24. The spectrum structure crosses over between the scenarios illustrated in Figure 9(b) and (c). Particularly, the minimum possesses a roughly exponential scaling behaviors, similar to the spinor implementation [63, 64], while a more precise estimate of the scaling is not yet achievable.

Target-preserving diabatic annealing scheme

The spectra shown in Figure 12 motivate us to use the logical annealing protocol diabatically, c.f. Sec. II.D, for recovering quantum states representing the MIS solution. Away from the indent limit, the suboptimal ICS state is favored at the homogeneous midpoint, and the lowest branch acquires MIS character only after a narrow gap in the second half of the anneal. This spectral feature constrains the feasible annealing rate. Near the indent limit, the MICS state is favored energetically at the midpoint, together with several low-energy branches that carry substantial weight in the MIS sector. This structure suggests that diabatic transitions can deplete the instantaneous ground-state population while allowing substantial target weight to be recovered by the end of the anneal.

The target-preserving feature of the diabatic annealing can be verified with dynamical evolution using the recursive generation method, see Appendix E. We initialize the system at the instantaneous ground state at ϵi=2t\epsilon_{i} = 2t, and evolve it under a normalized ramping rate of f=ϵ˙i/f(L/π)2/t2f = \dot{\epsilon}_i/f (L/\pi)^2/t^2 (ℏ=1\hbar= 1) with the logical protocol, and compute the occupation of the MICS subspace, PTP_T defined in Eq. (11), by the end of the annealing at ϵf=2t\epsilon_f = 2t.

The D3D_3 model implemented in indent limit L=21L = 21, d=3d = 3 hosts characteristic dynamics compatible to its spectrum, see Figure 13(a). Along with the several small gaps in the spectrum, the weight of the evolving quantum state in the ground state, ρ0\rho_0, and first excited state, ρ1\rho_1, drops substantially in the first half of the protocol, close to ϵi≈0.5t\epsilon_i \approx0.5t. However, the quantum state does not leave the target subspace indefinitely. In fact, the instantaneous weight in the target subspace drops initially. This detour inherits from the dressing of the ground state by ∣subICS⟩|\mathrm{subICS}\rangle states. As the annealing approaches the homogeneous midpoint, the dressing effects become weak, and the state returns to the target subspace. As the annealing further proceeds, the weight of the state in excited states retains, but it remains substantially in the target subspace. We remark that the system does not need to be restrained in the ground state throughout the annealing to preserve its target by the end of the annealing.

Figure 13. Target-preserving dynamics in diamond-chain graphs. The system is prepared in the ground state at ϵi=2t\epsilon_i = 2t, and evolved along the logical protocol, cf. Figure 2, until ϵf=2t\epsilon_f = 2t. (a,b) The dynamics of the quantum state on D3D_3 implemented with L=21L = 21, d=3d = 3 and ramp rate f=0.5f = 0.5. (a) The quantum state leaves the ground state (orange curve, ρ0\rho_0) and first excited state (green curve, ρ0+ρ1\rho_0 + \rho_1), but eventually reaches the target subspace (blue curve, PTP_T). (b) The instantaneous experimentally relevant density readout ρn(1)\rho_n^{(1)} along different vertices. Pairs like n=1n = 1 and n=10n = 10 are symmetric in the physical system, but asymmetry arises due to numerical truncation. They are shown by solid and dashed lines, respectively, of the same color. The shaded regime indicates that the mode truncation is numerically not fully converged. (c,d) The final dephased weight in the target subspace, PTP_T, cf. Eq. (11), with various ramp rates ff, is shown for (c) varying LL for D3D_3, and (d) for D1D_1 through D4D_4 at fixed L=21L = 21. A mode truncation at M=100M = 100 is used, and the hollow points indicate that the corresponding numerical convergence is not fully converged.

The preservation of the target can be experimentally measured by the partial density distribution along different dimensions,

ρn(1)=∑ℓn=d+1Lρn(ℓn),(26)\rho_n^{(1)} = \sum_{\ell_n=d+1}^{L} \rho_n(\ell_n), \tag*{(26)}

c.f. Eq. (15) and see Appendix. Appendix B for details. As shown in Figure 13(b), the targeted vertices, n=1,4,7,10n = 1,4,7,10, has increasing readouts along the annealing, while the irrelevant vertices has eventual vanishing readouts. This confirms that target weight PTP_T is compatible with experimentally measured solution readouts.

We further investigate the scaling of the ramp rate while changing the graph order ν\nu and the system size LL. Given the graph D3D_3, we increase LL from L=6L = 6 to L=24L = 24 at fixed d=3d = 3, see Figure 13(c). Far from the indent limit, i.e., for L=6,9,12L = 6,9,12, it takes exponentially slower ramp rates to reach the target subspace PT≈1P_T \approx1. This is consistent with the spectral structure of the system. In this case, the subICS is energetically more favorable at mid-protocol, and the system needs to go through the exponentially closing gap in the second half of the annealing, for entering the MICS subspace. At larger L=18,21,24L = 18,21,24, the system achieves PT≈1P_T \approx1 at roughly f≈1f \approx1, and the required ramp rate is much less sensitive to the change in LL. This is consistent with the fact that the MICS subspace is always energetically more favorable in indent limit.

The annealing performance among different graphs D1,2,3,4D_{1,2,3,4} at fixed L=21L = 21, d=3d = 3 is shown in Figure 13(d). The majority of the system weight enters the target subspace PT≳0.9P_T \gtrsim0.9 for all probed ramp rates. There is further a drop of PTP_T from PT=1P_T = 1 to PT≈0.9P_T \approx0.9 at around f≈1f \approx1, and this drop takes place at slightly faster ff for larger graph order ν\nu. This indicates the system achieves a fixed, substantial target weight through diabatic evolution within a ramp time scaling as O(L2)O(L^2), even in the presence of narrow intra-subspace gaps.

These results distinguish adiabatic ground-state preparation from target-compatible diabatic evolution. Although the ramp substantially depletes the lowest instantaneous modes, it recovers the target weight, while suppressing unwanted logical occupations. The resulting dynamics therefore involves a broader target manifold, rather than the single ground state.

The diabatic annealing implemented on diamond-chain graphs thus provides an example, where engineering the shape ratio of the system yields a spectral structure. This structure facilitates reaching the target MICS subspace associated to the correct classical solution. This scheme satisfies the unbiasedness criteria specified in Sec. II D. For sufficiently high-order diamond chains, the competing subICS becomes energetically favorable even in the indent limit, so the energetic rationale supporting the present protocol no longer applies. Since lim⁡d/L→0W2≈1.071>1\lim_{d/L\to0} W_2 \approx1.071 > 1, the subICS has a larger weight than the MICS for DνD_\nu with ν≥15\nu\ge15 (N≥46N \ge46) for any choice of d/Ld/L. By further comparison, the diabatic scheme of Ref. [64] employs an optimized detuning quench adapted to optimized quench parameters, to populate an excited branch that eventually connects to the final ground state.

Discussion and conclusions

We discuss the atomic overhead required by an experimentally relevant implementation. The standard Rydberg network construction for an NN-vertex graph requires around 4N24N^2 atoms [32], arranged into NN wires of length O(N)O(N). To approach the indent regime, we extend the logical-one end of each wire, increasing the ratio ξ=L/d\xi= L/d in accordance to Figure 7. This requires O((ξ−1)N)O((\xi- 1)N) additional atoms per wire, giving a total atom count of O(ξN2)O(\xi N^2). Thus, for a fixed elongation ratio, the atomic overhead remains quadratic in NN.

When the target-compatible sector is energetically favorable, diabatic evolution populates excited states without necessarily compromising the final target weight. For a fixed normalized ramp factor ff, the protocol requires an annealing time scaling as O(L2)O(L^2), where we attain high final target weight. In Rydberg network implementation L=ξNL = \xi N, the run-time overhead is therefore O(N2)O(N^2).

Additional avoided crossings arise from transitions involving bound states. For the clique examples studied at fixed dd, the corresponding minimum gaps decrease approximately exponentially with LL. Strategies for mitigating these spectral bottlenecks require further study. Nevertheless, failure to traverse such crossings adiabatically does not immediately invalidate the computation results in the final state. Within the factorized MICS description, retaining a bound state suppresses logical-one readouts within the corresponding vertices, without altering the readouts of the other factors. Consequently, the reported logical-one vertices form a partial independent set that can be reliably extended into an MIS. The partial solution from the quantum readout can significantly reduce the remaining classical optimization problem.

We propose further improvement to the encoding scheme that potentially alleviates the annealing bottleneck in a fundamental manner. The underlying mechanism of annealing performance lies in energetic competition, where suboptimal solutions potentially become more favorable due to quantum binding effects in the logical-zero sector [0,d]⊗N[0,d]^{\otimes N}. This observation motivates us to elevate the energy in that particular region by implementing an extra potential Hcore=ϵ0∑n=1N∑ℓ=1d∣n,ℓ⟩⟨n,ℓ∣H_{\mathrm{core}} = \epsilon_0 \sum_{n=1}^{N}\sum_{\ell=1}^{d} |n,\ell\rangle\langle n,\ell|, with ϵ0>0\epsilon_0 > 0. The effectiveness of this extra potential for alleviating the bottleneck warrants future study.

To summarize, we have investigated the low-energy spectrum and annealing dynamics of blockaded-chain models, which encodes the maximum independent set problems. These systems host competing many-body configurations whose approximate energetics can be characterized by physically derived clique and binding motif weights. Engineering the Hilbert-space geometry controls the relative energies of target-compatible and competing configurations. From the graph theoretical perspective, it engineers a cost function which relies on the global configuration. In contrast, standard classical annealing can feasibly impose cost functions based on local graph structures, which is less sensitive to the global features of the graph. Diabatic protocols exploits the resulting spectral structure, during which the state leaves the instantaneous ground state yet recovers high final target-subspace weight. Our work indicates that solving a class of combinatorial optimization problems using quantum annealing in neutral atom networks can potentially improve annealing performance. The effectiveness and robustness of this approach in larger and more complex networks remain to be further explored.

Beyond optimization problems, neutral atom networks offer a flexible setting for investigating how engineered Hilbert-space geometry shapes localization and transport. This setup has thus demonstrated its flexibility in investigating many-body localization, and can facilitate future studies on geometric effects in Hilbert-space fragmentation [65, 66, 67], and quantum thermalization [68, 69].

Acknowledgments

I would like to thank Hannes Pichler for initial conceptualization, Zhongda Zeng and Roberto Tricarico for in-depth discussions, and Yuanyuan Zhao for inspirational discussion on the recursive generation algorithm.

List of graphs

For reference, we list all the small graphs with N≤5N \leq5 vertices [58] in Table I, together with the maximum independent sets and maximum independent clique sets.

Blockaded-chain model as effective low-energy model for Rydberg networks

We review the scheme using Rydberg network to encode the maximum independent set (MIS) problem [32], and then derive the blockaded chain model that we substantially investigate throughout this work.

In this encoding scheme, an array of neutral atoms subject to nearest-neighbor Rydberg interaction, also referred to as a Rydberg wire, encodes the occupation of a graph vertex, see Figure 14(a). In each wire, an even number of atoms are subject to uniform Rabi frequency

Rydberg wire, crossing gadget, and edged gadget

Figure 14. (a) A Rydberg wire of 6 atoms encoding the quantum degree of freedom associated to a vertex. (b) A crossing gadget not imposing constraint between the two vertices. (c) An edged gadget forbidding simultaneous occupation of the logical-one state of the two vertices. The arrow points to right, indicate that the logical-zero configuration is ∣↑↓↑↓↑↓⟩\lvert\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\rangle, while the logical-one configuration is ∣↓↑↓↑↓↑⟩\lvert\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\rangle.

GraphMaximum Independent Vertex SetsMaximum Independent Clique Sets
2-1
3-1
3-2
4-1
4-2
4-3
4-4
4-5
4-6
5-1
5-2
5-3
5-4
5-5
5-6
5-7
5-8
5-9
5-10
5-11
5-12
5-13
5-14
5-15
5-16
5-17
5-18
5-19
5-20
5-21

Table 1 (PDF p. 17). Atlas list of small graphs, and their maximum independent vertex and clique sets.

Ω\Omega and detunings Δ\Delta, such that each of the two Z2\mathbb{Z}_2 configurations represents the logical-zero (unoccupied vertex) and logical-one (occupied vertex), respectively. Multiple wires are then arranged into a two-dimensional network,

such that any pair of wires crosses with each other. The crossings are always placed at (2dm⟨m,n⟩−1)(2d_m^{\langle m,n\rangle}-1)-th and (2dn⟨m,n⟩−1)(2d_n^{\langle m,n\rangle}-1)-th atoms of the wires. At the crossings, the atoms are arranged into patterns called gadgets. The crossing gadget does not implement additional constraint to the configurations of the two corresponding wires, and thus encode a pair of vertices not connected by an edge, see Figure 14(b). In contrast, the edge gadget imposes an additional constraint that the two wires cannot occupy the logical-one mode simultaneously, and thus encodes a pair of vertices connected by an edge, see Figure 14(c).

The Rydberg network can thus be formally described by a PXP Hamiltonian,

H=∑iΠnetwork(Ωσix−Δσiz)Πnetwork(27)H = \sum_i \Pi^{\mathrm{network}}(\Omega\sigma_i^x - \Delta\sigma_i^z)\Pi^{\mathrm{network}} \tag*{(27)}
Πnetwork=∏n=1NΠnwire×∏m<nΠm,ngadget(28)\Pi^{\mathrm{network}} = \prod_{n=1}^{N}\Pi_n^{\mathrm{wire}} \times\prod_{m<n}\Pi_{m,n}^{\mathrm{gadget}} \tag*{(28)}

where ii sums over all neutral atoms in the network, σix/z\sigma_i^{x/z} are Pauli matrices acting on the atomic Rydberg level ∣↑⟩\lvert\uparrow\rangle and ground level ∣↓⟩\lvert\downarrow\rangle. The product in Πwire\Pi^{\mathrm{wire}} run over all wires, with Πwire=∏i=12L−1Πi,j\Pi^{\mathrm{wire}}=\prod_{i=1}^{2L-1}\Pi_{i,j} run through all neighboring atoms; while the product in Πgadget\Pi^{\mathrm{gadget}} run over all pairs of wires, with Πm,ngadget\Pi_{m,n}^{\mathrm{gadget}} following the blockade rule established by Figure 14(b,c). Here, Πi,j=1i⊗1j−∣↑i↑j⟩⟨↑i↑j∣\Pi_{i,j}=\mathbb{1}_i\otimes\mathbb{1}_j-\lvert\uparrow_i\uparrow_j\rangle\langle\uparrow_i\uparrow_j\rvert projects out the simultaneous occupation of Rydberg levels of two blockaded atoms.

When Δ≫Ω\Delta\gg\Omega, we can work in the domain wall limit [35]. The domain wall basis states are the highly degenerate ground states of the system when taking Ω=0\Omega=0. For a single wire of 2(L−1)=82(L-1)=8 atoms, these basis states are

∣↑↓↑↓↑↓↑↓⟩, ∣↑↓↑↓↑↓↓↑⟩, ∣↑↓↑↓↓↑↓↑⟩,∣↑↓↓↑↓↑↓↑⟩, ∣↓↑↓↑↓↑↓↑⟩.(29)\left| \uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\right\rangle,\ \left| \uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\right\rangle,\ \left| \uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\right\rangle, \left| \uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\right\rangle,\ \left| \downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\right\rangle. \tag*{(29)}

We label these states by ℓn=1,2,…,L\ell_n=1,2,\ldots,L, and identify ℓ1\ell_1 and ℓL\ell_L to logical-zero and logical-one edges, respectively. When all gadgets are crossing gadgets and thus impose no constraint, they constitute LNL^N domain-wall states, which can be labeled by coordinates (ℓ1,ℓ2,…,ℓN)(\ell_1,\ell_2,\ldots,\ell_N), ℓn=1,2,…,L\ell_n=1,2,\ldots,L. In the presence of edged gadgets, the additional constraint thus forbids selected domain-wall states. Specifically, any states with coordinates ℓm>dm⟨m,n⟩, ℓn>dn⟨m,n⟩\ell_m>d_m^{\langle m,n\rangle},\ \ell_n>d_n^{\langle m,n\rangle} become illegitimate.

Once Ω\Omega is turned on, it provides a second-order perturbative channel, where one atom transitions from its Rydberg state to its ground state, while another atom transitions from its ground state to its Rydberg state. This perturbative process takes place for two neighboring atoms which are subject to the Rydberg blockade Π\Pi. In the domain-wall basis states, this effectively induces a hopping of domain wall with strength t=Ω2/2Δt=\Omega^2/2\Delta. Along the wires, this hopping involves neighboring states, leading to hnh_n as defined in Eq. (4). In the vicinity of the gadgets, it induces local terms hmngadget=∣dm⟨m,n⟩,dn⟨m,n⟩+1⟩⟨dm⟨m,n⟩+1,dn⟨m,n⟩∣+∣dm⟨m,n⟩,dn⟨m,n⟩⟩⟨dm⟨m,n⟩+1,dn⟨m,n⟩+1∣+h.c.h_{mn}^{\mathrm{gadget}}=\lvert d_m^{\langle m,n\rangle},d_n^{\langle m,n\rangle}+1\rangle\langle d_m^{\langle m,n\rangle}+1,d_n^{\langle m,n\rangle}\rvert+\lvert d_m^{\langle m,n\rangle},d_n^{\langle m,n\rangle}\rangle\langle d_m^{\langle m,n\rangle}+1,d_n^{\langle m,n\rangle}+1\rvert+\mathrm{h.c.}. As an example, for the realistic implementation shown in Figure 1(e), its effective domain-wall Hamiltonian Hdw=Πdw(h1+h2+h3+h12gadget+h23gadget)ΠdwH_{\mathrm{dw}}=\Pi_{\mathrm{dw}}(h_1+h_2+h_3+h_{12}^{\mathrm{gadget}}+h_{23}^{\mathrm{gadget}})\Pi_{\mathrm{dw}} is illustrated in Figure 1(f).

To achieve the final symmetric form of the blockaded-chain model as presented in Eq. (3) and investigated throughout this work, we further simplify the domain-wall model by omitting the gadget hoppings as detailed in Ref. [35], and the gadget structure by taking the idealized uniform gadget positioning limit, dm⟨m,n⟩=dd_m^{\langle m,n\rangle}=d. This simplification is illustrated by Figure 1(g).

A complementary and experimentally relevant measurement for PTP_T, Eq. (11), is provided by the coordinate-resolved density ρn(ℓn)\rho_n(\ell_n), Eq. (15). We can quantify whether the quantum state lies within the logical-one region by its single-body probability, ρn(1)=∑ℓn=d+1Lρn(ℓn)\rho_n^{(1)}=\sum_{\ell_n=d+1}^{L}\rho_n(\ell_n). This quantity is experimentally accessible with Rydberg arrays. In the Rydberg array, this probability translates into the occupation of the Rydberg level of the (2d)(2d)th atoms, (⟨σn,2dz⟩+1)/2(\langle\sigma_{n,2d}^{z}\rangle+1)/2, which is easily accessible in experimental measurements.

Dynamics and mapping in hypercube limit

In the hypercube limit, d=L−1d=L-1, a graph edge excludes only the simultaneous occupation of the final sites of the two corresponding chains. Although the excluded fraction of the configuration space is small, the constraint can affect low-energy modes localized

Low-energy eigenstates and reconstructed basis in a two-dimensional model without blockade

Figure 15. Low-energy eigenstates and reconstructed basis in a two-dimensional model without blockade. Parameters are taken as L=50L=50, ϵi=0\epsilon_i=0, ϵf=t\epsilon_f=t.

Low-energy eigenstates and reconstructed basis in a two-dimensional model with blockade

Figure 16. Low-energy eigenstates and reconstructed basis in a two-dimensional model with blockade. Parameters are taken in hypercube limit, L=50L=50, d=49d=49, ϵi=0\epsilon_i=0, ϵf=t\epsilon_f=t.

near that boundary. To achieve an effective low energy description, we first solve the finite one-dimensional problem and identify its crossover energy scale. This effective energetic truncation of the blockaded-chain model leads to a two-mode variational description with the connectivity of the PXP implementation.

Finite-chain eigenstates

We solve the low-energy modes of a single chain. The one-dimensional Hamiltonian in Eq. (4b) leads to the bulk equation Eψℓ=−t(ψℓ−1+ψℓ+1)\mathcal{E}\psi_\ell=-t(\psi_{\ell-1}+\psi_{\ell+1}) and boundary conditions ψ2=(E/t−ϵi/t)ψ1, ψL−1=(E/t−ϵf/t)ψL\psi_2=(\mathcal{E}/t-\epsilon_i/t)\psi_1,\ \psi_{L-1}=(\mathcal{E}/t-\epsilon_f/t)\psi_L. Along the logical protocol, see Figure 2, the local potential on one edge vanishes. We take ϵi≥0\epsilon_i\geq0 and ϵf=0\epsilon_f=0 without loss of generality.

We are most interested in the regime ϵi≳t\epsilon_i\gtrsim t, where the ground mode crosses over from a standing-wave mode to a exponentially decaying mode.

For ϵi\epsilon_i much larger than tt, the ground mode is localized on the edge and decays exponentially along the chain,

ψℓ0∝sinh⁡[κ(L+1−ℓ)](30)\psi_\ell^0 \propto\sinh[\kappa(L+1-\ell)] \tag*{(30)}

and possesses an energy below the continuum band, E<−2tE<-2t,

E=−2tcosh⁡κ(31)E=-2t\cosh\kappa \tag*{(31)}

where the decay rate κ\kappa is fixed by boundary condition on ℓ=0\ell=0 edge as sinh⁡(κ(L+1))/sinh⁡(κL)=ϵi/t\sinh(\kappa(L+1))/\sinh(\kappa L)=\epsilon_i/t. When the length of the chain is much longer than the decay length, κL≫1\kappa L\gg1, the wavefunction and the energy obtain explicit forms

ψℓ=1−t2/ϵi2 (ϵi/t)−ℓ+1(32)\psi_\ell=\sqrt{1-t^2/\epsilon_i^2}\,(\epsilon_i/t)^{-\ell+1} \tag*{(32)}

and

E/t=−ϵi/t−t/ϵi,(33)E/t=-\epsilon_i/t-t/\epsilon_i, \tag*{(33)}

respectively. In the regime 1/L≪r≪11/L\ll r\ll1, r=ϵi/t−1r=\epsilon_i/t-1, the energy can be further reduced to

E/t≈−2−(ϵi/t−1)2.(34)E/t\approx-2-(\epsilon_i/t-1)^2. \tag*{(34)}

When ϵi\epsilon_i approaches tt, the ground mode becomes a standing-wave mode. Its wavefunction and energy are

ψℓ0∝sin⁡[k(L+1−ℓ)](35)\psi_\ell^0\propto\sin[k(L+1-\ell)] \tag*{(35)}

and

E=−2tcos⁡k,(36)E=-2t\cos k, \tag*{(36)}

where the wave vector is given by sin⁡(k(L+1))/sin⁡(kL)=ϵi/t\sin(k(L+1))/\sin(kL)=\epsilon_i/t. In the regime r≪1/Lr\ll1/L, the wave vector can be approximated by

km≈(2m+1)π2L+1−r2L+1cot⁡((2m+1)π4L+2)(37)k_m\approx\frac{(2m+1)\pi}{2L+1}-\frac{r}{2L+1}\cot\left(\frac{(2m+1)\pi}{4L+2}\right) \tag*{(37)}

for ground mode m=0m=0 and first excited mode m=1m=1. The energy becomes correspondingly

Emt=−2+1L2[(2m+1)2π24−2r](38)\frac{E_m}{t}=-2+\frac{1}{L^2}\left[\frac{(2m+1)^2\pi^2}{4}-2r\right] \tag*{(38)}

This indicates a crossover at r=1/Lr=1/L, i.e., ϵi/t=1+1/L\epsilon_i/t=1+1/L, as confirmed exactly by the boundary conditions. Indeed, at this point, the ground mode becomes linear,

ψℓ0∝L+1−ℓ(39)\psi_\ell^0\propto L+1-\ell \tag*{(39)}

with energy exactly at E=−2tE=-2t. Meanwhile, the first excited mode is a standing-wave mode with wave vector k1k_1.

Two mode projection

In the hypercube limit, the blockaded-chain model can be projected onto two modes along each direction, and achieve generic scaling behaviors. We retain the two lowest exact eigenstates of each finite chain, ∣ϕ0⟩|\phi_0\rangle and ∣ϕ1⟩|\phi_1\rangle. Near the crossover, their separation is of order ∼t/L2\sim t/L^2, giving rise to effective dynamics scaling in this order. Without blockade, these two states are exactly the two modes spanning the low energy dynamics.

A graph edge excludes simultaneous occupation of site ℓ=L\ell=L on the two adjacent chains. This constraint leads to an effective overlap between the two modes. To look for an orthonormal basis ∣φ0⟩|\varphi_0\rangle and ∣φ1⟩|\varphi_1\rangle, we need a rotation

∣φ0⟩=γ∣ϕ0⟩−∣ϕ1⟩γ2+1,(40)|\varphi_0\rangle=\frac{\gamma|\phi_0\rangle-|\phi_1\rangle}{\sqrt{\gamma^2+1}}, \tag*{(40)}
∣φ1⟩=∣ϕ0⟩+γ∣ϕ1⟩γ2+1(41)|\varphi_1\rangle=\frac{|\phi_0\rangle+\gamma|\phi_1\rangle}{\sqrt{\gamma^2+1}} \tag*{(41)}

where γ=ϕℓ1ℓ=0/ϕℓ0ℓ=0≈sin⁡(3π/(2L+1))/sin⁡(π/(2L+1))\gamma=\phi_\ell^1{}_{\ell=0}/\phi_\ell^0{}_{\ell=0}\approx\sin(3\pi/(2L+1))/\sin(\pi/(2L+1)) relates the wavefunction at the edges of the original modes. Notably, this imposes an effective hopping between the two new basis modes,

t~=−⟨φ0∣h∣φ1⟩=γ1+γ2(E1−E0),(42)\tilde{t}=-\langle\varphi_0|h|\varphi_1\rangle=\frac{\gamma}{1+\gamma^2}(E_1-E_0), \tag*{(42)}

where EmE_m are the energies of original basis modes ∣ϕm⟩|\phi_m\rangle. In other words, we have spanned the system onto an effective two-mode basis,

Heff=−γ1+γ2(E1−E0)σx+γ2−12(1+γ2)(E1−E0)σz(43)H_{\mathrm{eff}}=-\frac{\gamma}{1+\gamma^2}(E_1-E_0)\sigma_x+\frac{\gamma^2-1}{2(1+\gamma^2)}(E_1-E_0)\sigma_z \tag*{(43)}

The Pauli matrices are spanned within the basis of ∣ϕm⟩|\phi_m\rangle. The projection thus yields the PXP Hamiltonian on the same graph with renormalized hopping strengths. This reveals a minimum gap of the hypercube limit model given by the energy scale of ΔL,d=L−1=t~/tΔPXP\Delta_{L,d=L-1}=\tilde{t}/t\Delta_{\mathrm{PXP}}, as confirmed numerically by Figure 17.

Figure 17. The classical hardness index, Eq. (44), compared to the minimum gap along protocol for the PXP implementation, L=2L=2, d=1d=1, for graphs with N≤7N\leq7 vertices.

Annealing difficulty for PXP implementation

The small-graph spectra also motivate an empirical indicator based on the degeneracies of competing independent-set families. We extract an empirical index,

H={Nmax⁡+qmax⁡−1Nsub+qsub−1,Nmax⁡=Nsub+1≠12Nmax⁡+qmax⁡−1Nmax⁡1.2,else(44)\mathcal{H} = \begin{cases} \dfrac{N_{\max}+\sqrt{q_{\max}}-1}{N_{\mathrm{sub}}+\sqrt{q_{\mathrm{sub}}-1}}, & N_{\max}=N_{\mathrm{sub}}+1\ne1 \\ 2\dfrac{N_{\max}+\sqrt{q_{\max}}-1}{N_{\max}^{1.2}}, & \text{else} \end{cases} \tag*{(44)}

Here, Nmax⁡/subN_{\max/\mathrm{sub}} refers to the cardinality of the maximum or suboptimal independent set, and qmax⁡/subq_{\max/\mathrm{sub}} refers to the degeneracy. When the cardinality of the maximum and suboptimal independent sets differ by 1, the quantum annealing performance is mainly determined by the competition between these two independent sets. N+g−1N+\sqrt{g}-1 thus provides a rough estimate to the weight of the independent set, and motivated by the weight Wq=qW_q=\sqrt{q} of a qq-clique when L=2,d=1L=2,d=1. The classical hardness index H\mathcal{H} estimates the ratio between the weights of the maximum and suboptimal independent clique sets. When Nmax⁡−Nsub>1N_{\max}-N_{\mathrm{sub}}>1, the maximum set does not compete with the suboptimal one, and determines the gap on its own. This index indeed shows a clear correlation with the minimum gap along the annealing in Figure 17.

Binding in Kq graphs

This Appendix complements the discussion of bound states in complete graphs, KqK_q, § 3.1 A, and we derive the bound state self-consistency equation, Eq. (19) in details.

To investigate the effects of coordination enhancement of scattering processes on the bare logical-zero state ∣ψ0⟩⊗q\lvert\psi^0\rangle^{\otimes q}, we split the full Hilbert space into the low-energy subspace spanned solely by ∣ψ0⟩⊗q\lvert\psi^0\rangle^{\otimes q} and its complement, Qq=1−∣ψ0⟩⊗q⟨ψ0∣Q_q=1-\lvert\psi^0\rangle^{\otimes q}\langle\psi^0\rvert. This allows us to write down the Feshbach equation,

E−qE0=qt~2Σq(E).(45)E-qE_0=q\tilde{t}^{2}\Sigma_q(E). \tag*{(45)}

Here qE0qE_0 is the energy of ∣ψ0⟩⊗q\lvert\psi^0\rangle^{\otimes q}, t~=tψ0(d)\tilde{t}=t\psi^0(d) is the effective coupling strength, and the self energy is

Σq(E)=⟨B|1E−QqHQq|B⟩.(46)\Sigma_q(E)=\left\langle B\middle|\frac{1}{E-Q_qHQ_q}\middle|B\right\rangle. \tag*{(46)}

with ∣B⟩=QqH(1−Qq)∣ψ0⟩⊗q\lvert B\rangle=Q_qH(1-Q_q)\lvert\psi^0\rangle^{\otimes q}, or explicitly

∣B⟩=1q∑n=1q∣n,d+1⟩⊗m≠n∣ψ0⟩m(47)\lvert B\rangle=\frac{1}{\sqrt{q}}\sum_{n=1}^{q}\lvert n,d+1\rangle\otimes_{m\ne n}\lvert\psi^0\rangle_m \tag*{(47)}

To reduce the dimensionality of the problem, we introduce a mapping onto one dimension. Specifically, we consider the variational ansatz generated by a one-dimensional wavefunction ∣φ⟩\lvert\varphi\rangle through the isometric map WW,

W∣φ⟩=1q∑j=1q∣φ⟩j⊗i≠j∣ψ0⟩i.(48)W\lvert\varphi\rangle=\frac{1}{\sqrt{q}}\sum_{j=1}^{q}\lvert\varphi\rangle_j\otimes_{i\ne j}\lvert\psi^0\rangle_i. \tag*{(48)}

where we impose ⟨φ∣ψ0⟩=0\langle\varphi\lvert\psi^0\rangle=0. Particularly, the state ∣B⟩\lvert B\rangle can be generated using WW as W∣d+1⟩=∣B⟩W\lvert d+1\rangle=\lvert B\rangle. This mapping, WW, induces a relation between QqQ_q, and its one-dimensional counterpart, Q1=W†W=1−∣ψ0⟩⟨ψ0∣Q_1=W^\dagger W=1-\lvert\psi^0\rangle\langle\psi^0\rvert, as

W†QqHQqW=Q1hQ1+(q−1)E0Q1.(49)W^\dagger Q_qHQ_qW=Q_1hQ_1+(q-1)E_0Q_1. \tag*{(49)}

The variational ansatz is split into contributions from one ∣φ⟩\lvert\varphi\rangle and q−1q-1 logical-zero modes. Defining ϵ=E−(q−1)E0\epsilon=E-(q-1)E_0, the Feshbach equation becomes

ϵ−E0=qt~2Σ~1(ϵ),(50)\epsilon-E_0=q\tilde{t}^{2}\widetilde{\Sigma}_1(\epsilon), \tag*{(50)}

where the factor of qq comes from the summation in ∣B⟩\lvert B\rangle and represents the qq different scattering processes, and

Σ~1(ϵ)=⟨d+1|1ϵ−Q1hQ1|d+1⟩.(51)\widetilde{\Sigma}_1(\epsilon)=\left\langle d+1\middle|\frac{1}{\epsilon-Q_1hQ_1}\middle|d+1\right\rangle. \tag*{(51)}

Here, we approximate the complementary-space resolvent by restricting it to the subspace generated by WW,

W†(E−QqHQq)−1W≈[ϵ−Q1hQ1]−1.(52)W^\dagger(E-Q_qHQ_q)^{-1}W\approx[\epsilon-Q_1hQ_1]^{-1}. \tag*{(52)}

This neglects virtual excursions outside the retained subspace. To proceed to evaluate the self energy, we need to transform it into the bare one-dimensional self energy without projector,

Σ1(ϵ)=⟨d+1|1ϵ−h|d+1⟩.(53)\Sigma_1(\epsilon)=\left\langle d+1\middle|\frac{1}{\epsilon-h}\middle|d+1\right\rangle. \tag*{(53)}

Splitting the one-dimensional Hamiltonian into h=E0∣ψ0⟩⟨ψ0∣+Q1hQ1h=E_0\lvert\psi^0\rangle\langle\psi^0\rvert+Q_1hQ_1, the Dyson equation relates the bare and projected self energies, Σ~1\widetilde{\Sigma}_1 and Σ1\Sigma_1 as

Σ1−1=Σ~1−1−t~2ϵ−E0(54)\Sigma_1^{-1}=\widetilde{\Sigma}_1^{-1}-\frac{\tilde{t}^{2}}{\epsilon-E_0} \tag*{(54)}

Substitution leads to

ϵ−E0=(q−1)t~2Σ1(ϵ).(55)\epsilon-E_0=(q-1)\tilde{t}^{2}\Sigma_1(\epsilon). \tag*{(55)}

Since 1/(ϵ−h)1/(\epsilon-h) is the usual one-dimensional propagator, it can be straightforwardly evaluated.

The factor qq initially arises from the coherent coupling of the bare logical-zero state ∣ψ0⟩⊗q\lvert\psi^0\rangle^{\otimes q} to qq equivalent scattering channels. After Dyson resummation, virtual processes going through ∣ψ0⟩⊗q\lvert\psi^0\rangle^{\otimes q} are also taken into account, which reduces the factor from qq to q−1q-1.

However, this reduction is merely algebraic, and should not be interpreted as a reduction in scattering channels. The energy of the dressed state is directly associated to its density profile, particularly whether it is bound to the logical-zero sector or propagating outwards. Particularly, bound states are characterized energetically by E<(q−1)E0−2tE < (q-1)E_0 - 2t, and their wavefunctions decay with rate κq\kappa_q along the lattice. Denoting E−(q−1)E0=−2tcosh⁡κqE - (q - 1)E_0 = -2t \cosh\kappa_q, the propagator for a one-dimensional lattice can be written as

G=−1−e−2κq(d+1)2tsinh⁡κq(56)G = -\frac{1-e^{-2\kappa_q(d+1)}}{2t\sinh\kappa_q} \tag*{(56)}

where κq\kappa_q is related to αq\alpha_q defined in § 3.1 A through αq=κq(d+1)/π\alpha_q = \kappa_q(d+1)/\pi. In other words, the wavefunction decays as Ψ∼e−παqL/(d+1)\Psi\sim e^{-\pi\alpha_q L/(d+1)}. This further applies to the minimum gap for Kq\mathcal{K}_q.

The recursive generation algorithm

The blockaded-chain models are solved typically using exact diagonalization with sparse matrices. This makes the required computational resources formidable as it scales with LNL^N, where LL is the length of the lattice, and NN is the number of vertices in the graph. In our work, there are two families of graphs with clear patterns, the complete graphs KNK_N and the diamond-chain graphs DνD_\nu. These graphs themselves can be generated recursively. Utilizing the patterns, we can also generate their Hamiltonian and solve their spectra recursively. This method can easily be further generalized for other families of graphs. The algorithm comes in two major steps, mode truncation and iterative generation.

Mode truncation

The lattice of the blockaded-chain model has a shape given by Eq. (10). It can be split into multiple hypercuboids, and each hypercuboid admits a straightforward solution.

Formally, this can be treated by the following Hamiltonian,

H=(HA−t1−t10⋯−t1HB−t10⋯−t1−t1HC−t1⋯00−t1HD⋯⋯⋯⋯⋯⋱)(57)H = \begin{pmatrix} H_A & -t1 & -t1 & 0 & \cdots\\ -t1 & H_B & -t1 & 0 & \cdots\\ -t1 & -t1 & H_C & -t1 & \cdots\\ 0 & 0 & -t1 & H_D & \cdots\\ \cdots& \cdots& \cdots& \cdots& \ddots \end{pmatrix} \tag*{(57)}

where HA,B,C,DH_{A,B,C,D} are Hamiltonians easily diagonalizable describing the sectors A, B, C, D,

Hi=Ui†ΛiUi,(58)H_i = U_i^\dagger\Lambda_i U_i, \tag*{(58)}

where Λi=diag⁡(λ0,λ1,…)\Lambda_i = \operatorname{diag}(\lambda_0,\lambda_1,\ldots) is a diagonal matrix containing the eigenvalues of HiH_i. Furthermore, −t1-t1 indicates a coupling between the two corresponding sectors. Generically for blockaded-chain models, this coupling is takes a uniform value of tt when it exists. In this particular example, it couples the sector pairs (A,B)(A,B), (A,C)(A,C), (B,C)(B,C), and (C,D)(C,D). It is thus possible to construct the overall transform matrix,

U=(UA000⋯0UB00⋯00UC0⋯000UD⋯⋯⋯⋯⋯⋱)(59)U = \begin{pmatrix} U_A & 0 & 0 & 0 & \cdots\\ 0 & U_B & 0 & 0 & \cdots\\ 0 & 0 & U_C & 0 & \cdots\\ 0 & 0 & 0 & U_D & \cdots\\ \cdots& \cdots& \cdots& \cdots& \ddots \end{pmatrix} \tag*{(59)}

such that

U†HU=(ΛA−tUA†UB−tUA†UC0⋯−tUB†UAΛB−tUB†UC0⋯−tUC†UA−tUC†UBΛC−tUC†UD⋯00−tUD†UCΛD⋯⋯⋯⋯⋯⋱)(60)U^\dagger H U = \begin{pmatrix} \Lambda_A & -tU_A^\dagger U_B & -tU_A^\dagger U_C & 0 & \cdots\\ -tU_B^\dagger U_A & \Lambda_B & -tU_B^\dagger U_C & 0 & \cdots\\ -tU_C^\dagger U_A & -tU_C^\dagger U_B & \Lambda_C & -tU_C^\dagger U_D & \cdots\\ 0 & 0 & -tU_D^\dagger U_C & \Lambda_D & \cdots\\ \cdots& \cdots& \cdots& \cdots& \ddots \end{pmatrix} \tag*{(60)}

The matrices (Ui†Ui+1)mn=∑nψi,m∗ψi+1,n(U_i^\dagger U_{i+1})_{mn} = \sum_n \psi_{i,m}^* \psi_{i+1,n} encode the overlap between wavefunctions from the two neighbouring sub-systems. When the neighboring sectors share the same Hamiltonian Hi=Hi+1H_i = H_{i+1}, these matrices are trivially unities Ui†Ui+1=1U_i^\dagger U_{i+1} = 1.

Upon this diagonalization, it is thus possible to truncate the full Hamiltonian U†HUU^\dagger H U, and drop the high-energy modes with large Λ\Lambda. This can significantly reduce the computational complexity.

Motivation from classical algorithm

We motivate the quantum algorithm from a classical algorithm for solving the MIS problem on the diamond chain graphs. The branching algorithm [40] generates the MIS iteratively, as illustrated in Figure 18. Starting with a single vertex as ν=0\nu= 0, in each iteration we attach a K3K_3 to Dν−1D_{\nu-1} for generating DνD_\nu. The MIS for DνD_\nu comes from either of the two branches:

Figure 18. The branching algorithm for classically solving the MIS problem on diamond chain graphs. The MIS solution to the ν\nu-graph is given by the better solution between the two branches, and can thus be generated using the MIS solution to the ν−1\nu-1-graph.

  • Either of the vertices AνA_\nu or BνB_\nu belongs to MIS of DνD_\nu. In this case, Cν−1C_{\nu-1} cannot belong to the MIS. If we construct an auxiliary blockaded diamond chain graph Dνblock=Dν∖{Cν}D_\nu^{\mathrm{block}} = D_\nu\setminus\{C_\nu\}, the MIS of DνD_\nu can be constructed as the union of the MIS of the blockaded graph Dν−1blockD_{\nu-1}^{\mathrm{block}} together with AνA_\nu or BνB_\nu,

MIS⁡1(Dν)=MIS⁡(Dν−1∖{Cν−1})∪{Aν or Bν}(61)\operatorname{MIS}_1(D_\nu)=\operatorname{MIS}(D_{\nu-1}\setminus\{C_{\nu-1}\})\cup\{A_\nu\text{ or }B_\nu\} \tag*{(61)}
  • Neither of the vertices AνA_\nu or BνB_\nu belongs to MIS of DνD_\nu. In this case, the MIS DνD_\nu can be constructed as the union of the MIS of Dν−1D_{\nu-1} together with CνC_\nu,

MIS⁡2(Dν)=MIS⁡(Dν−1)∪{Cν}(62)\operatorname{MIS}_2(D_\nu)=\operatorname{MIS}(D_{\nu-1})\cup\{C_\nu\} \tag*{(62)}

The MIS is thus the one with more vertices,

MIS⁡(Dν)=max⁡N[MIS⁡1(Dν),MIS⁡2(Dν)].(63)\operatorname{MIS}(D_\nu)=\max_N[\operatorname{MIS}_1(D_\nu),\operatorname{MIS}_2(D_\nu)]. \tag*{(63)}

The branching algorithm provides a recursive relation between the MISs of the full and blockaded graphs.

The recursive generation algorithm for the quantum problem

A similar strategy can be applied for solving the low-energy spectra of the blockaded chain models based on diamond chain graphs. After introducing an auxiliary blockaded Hamiltonian, an effective Hamiltonian for DνD_\nu, denoted as HνH_\nu, can be constructed using the spectrum of Hν−1fullH_{\nu-1}^{\mathrm{full}} and Hν−1blockH_{\nu-1}^{\mathrm{block}}. The strategy is illustrated in Figure 19. This method allows for truncation for the low-energy spectra, which significantly reduces the computational complexity.

Figure 19. Constructing the effective Hamiltonian for ν\nu-graph from the spectrum of (ν−1)(\nu-1)-graph. In each iteration, a full and a blockaded Hamiltonian are constructed and solved. For both of them, the red (blue) sites host the spectrum of the full (blockaded) Hamiltonian from the last iteration.

The “full” Hamiltonian is defined on lattice sites ℓ3=(ℓ1,ℓ2,ℓ3)∈Λ\ell^3=(\ell_1,\ell_2,\ell_3)\in\Lambda allowed by a fully connected N=3N=3-vertex graph. In other words, 1≤ℓi≤L1\leq\ell_i\leq L, and only one of them is allowed to be greater than L−dL-d, see Figure 19. The Hamiltonian thus reads

Hνfull=−∑ℓα3,mα,ℓβ3,mβtℓα3,mα,ℓβ3,mβν−1∣ℓα3,mα⟩⟨ℓβ3,mβ∣+∑ℓ3,mEℓ3,mν−1∣ℓ3,m⟩⟨ℓ3,m∣(64)H_\nu^{\mathrm{full}}=-\sum_{\ell_\alpha^3,m_\alpha,\ell_\beta^3,m_\beta}t_{\ell_\alpha^3,m_\alpha,\ell_\beta^3,m_\beta}^{\nu-1}\lvert\ell_\alpha^3,m_\alpha\rangle\langle\ell_\beta^3,m_\beta\rvert+\sum_{\ell^3,m}E_{\ell^3,m}^{\nu-1}\lvert\ell^3,m\rangle\langle\ell^3,m\rvert \tag*{(64)}

The effective local energy shift provided by the spectrum of the (ν−1)(\nu-1)-graphs is

Eℓ3,mν−1={Emν−1,full−δ,ℓ1,2≤L−d,(red),Emν−1,blockaded−δ,ℓ1>L−d or ℓ2>L−d,(blue)(65)E_{\ell^3,m}^{\nu-1}= \begin{cases} E_m^{\nu-1,\mathrm{full}}-\delta, & \ell_{1,2}\leq L-d,\quad(\mathrm{red}),\\ E_m^{\nu-1,\mathrm{blockaded}}-\delta, & \ell_1>L-d\ \mathrm{or}\ \ell_2>L-d,\quad(\mathrm{blue}) \end{cases} \tag*{(65)}

These two regions are colored in Figure 19 by red and blue, respectively. Here, Emν−1,full/blockaded∈{eigenvalue⁡(Hν−1,full/blockaded)}E_m^{\nu-1,\mathrm{full/blockaded}}\in\{\operatorname{eigenvalue}(H^{\nu-1,\mathrm{full/blockaded}})\}. δ\delta is the chemical potential on boundary condition, δ=#1ϵ1+#LϵL\delta=\#_1\epsilon_1+\#_L\epsilon_L, where #1,L\#_{1,L} denotes the number of ℓi\ell_i being 11 or LL, respectively.

Moreover, the effective hopping is provided by the overlap between the eigenmodes of the (ν−1)(\nu-1)-graphs,

tℓα3,mα,ℓβ3,mβν−1={0,∣ℓ1/2,3,α−ℓ1/2,3,β∣≠1δmα,mβ,not ℓ1/2,α=L−d, ℓ1/2,β=L−d+1⟨Ψmαfull∣Ψmβblock⟩,ℓ1/2,α=L−d, ℓ1/2,β=L−d+1(66)t_{\ell_\alpha^3,m_\alpha,\ell_\beta^3,m_\beta}^{\nu-1}= \begin{cases} 0, & \lvert\ell_{1/2,3,\alpha}-\ell_{1/2,3,\beta}\rvert\ne1\\ \delta_{m_\alpha,m_\beta}, & \text{not }\ell_{1/2,\alpha}=L-d,\ \ell_{1/2,\beta}=L-d+1\\ \langle\Psi_{m_\alpha}^{\mathrm{full}}\mid\Psi_{m_\beta}^{\mathrm{block}}\rangle, & \ell_{1/2,\alpha}=L-d,\ \ell_{1/2,\beta}=L-d+1 \end{cases} \tag*{(66)}

In other words, within the same (blue or red) region, the effective coupling is unity between the same mode of neighboring sites, and is zero in all other cases. Along the boundary between the two regions, the effective coupling is given by the overlap between modes.

The “blockaded” Hamiltonian can be straightforwardly derived from the full one by blocking the prohibited region,

Hνblockaded=Pℓ3≤dHνfullPℓ3≤d(67)H_{\nu}^{\mathrm{blockaded}} = P_{\ell_3\le d}H_{\nu}^{\mathrm{full}}P_{\ell_3\le d} \tag*{(67)}

where Pℓ3≤dP_{\ell_3\le d} is the projection operator onto ℓ3≤d\ell_3\le d, cf. Figure 19.

These two Hamiltonians together provide an iterative relation,

{Hν−1full,Hν−1blockaded}→{Hνfull,Hνblockaded}.(68)\left\{H_{\nu-1}^{\mathrm{full}},H_{\nu-1}^{\mathrm{blockaded}}\right\}\to\left\{H_{\nu}^{\mathrm{full}},H_{\nu}^{\mathrm{blockaded}}\right\}. \tag*{(68)}

By choosing a sufficiently large truncation for the number of modes considered m=1,2,…,Mm=1,2,\ldots,M, we can successively obtain the low-energy spectrum for the implementations of different diamond-chain graphs. In our simulations, we obtain converged results with M=40M=40. The same algorithm can be straightforwardly generalized to any other series of graphs of clear pattern. In the main text, it is also applied to the complete graphs KN\mathcal{K}_N.

Dynamics in the truncated instantaneous basis

We simulate the real-time dynamics in the subspace spanned by the MM lowest instantaneous modes obtained from the recursive algorithm. The quantum state is propagated following an evolution-and-projection strategy. The coefficients between step tt and t+δtt+\delta t are related through

ct+δt=St,t+δt†e−iEtδtct.(69)c_{t+\delta t}=S_{t,t+\delta t}^{\dagger}e^{-i\mathcal{E}_t\delta t}c_t. \tag*{(69)}

Here Et\mathcal{E}_t is a diagonal matrix containing the instantaneous spectrum at time tt, associated to the instantaneous modes ∣μ(t)⟩\lvert\mu(t)\rangle. St,t+δtS_{t,t+\delta t} stores the overlaps between the instantaneous modes at time tt and t+δtt+\delta t, (St,t+δt)μ,ν=⟨μ(t)∣ν(t+δt)⟩(S_{t,t+\delta t})_{\mu,\nu}=\langle\mu(t)\vert\nu(t+\delta t)\rangle. For each step, this overlap matrix can be computed iteratively from ν=1\nu=1 to the required ν\nu. Particularly, this numerical dynamical evolution is not exactly unitary due to mode truncation, and norms of the quantum states can decrease during a mode-unconverged evolution.

References

References

  1. [1]M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, et al., Nature 473, 194 (2011), URL https://doi.org/10.1038/nature10012.
  2. [2]S. Kim, S-W. Ahn, I.-S. Suh, A. W. Dowling, E. Lee, and T. Luo, npj Quantum Information 11, 77 (2025), URL https://doi.org/10.1038/s41534-025-01020-1.
  3. [3]M. Saffman, T. G. Walker, and K. Mølmer, Rev. Mod. Phys. 82, 2313 (2010), URL https://link.aps.org/doi/10.1103/RevModPhys.82.2313.DOI
  4. [4]H. Labuhn, D. Barredo, S. Ravets, S. de Léséleuc, T. Macrì, T. Lahaye, and A. Browaeys, Nature 534, 667 (2016), URL https://doi.org/10.1038/nature18274.
  5. [5]S. Ebadi, T. T. Wang, H. Levine, A. Keesling, G. Se-meghini, A. Omran, D. Blüvstein, R. Samajdar, H. Pich-ler, W. W. Ho, et al., Nature 595, 227 (2021), URL https://doi.org/10.1038/s41586-021-03582-4.
  6. [6]F. Cesa and H. Pichler, Phys. Rev. Lett. 131, 170601 (2023), URL https://link.aps.org/doi/10.1103/PhysRevLett.131.170601.DOI
  7. [7]S. J. Evered, D. Blüvstein, M. Kalinowski, S. Ebadi, T. Manovitz, H. Zhou, S. H. Li, A. A. Geim, T. T. Wang, N. Maskara, et al., Nature 622, 268 (2023), URL https://doi.org/10.1038/s41586-023-06481-y.
  8. [8]D. S. Grün, S. J. M. White, A. Ortu, A. Di Carli, H. Edri, M. Lepers, M. J. Mark, and F. Ferlaino, Phys. Rev. Lett. 133, 233402 (2024), URL https://link.aps.org/doi/10.1103/PhysRevLett.133.223402.DOI
  9. [9]M. A. Norcia, H. Kim, W. B. Cairncross, M. Stone, A. Ryou, M. Jaffe, M. O. Brown, K. Barnes, P. Battaglino, T. C. Bohdanowicz, et al., PRX Quantum 5, 030316 (2024), URL https://link.aps.org/doi/10.1103/PRXQuantum.5.030316.DOI
  10. [10]G. Pichard, D. Lim, E. Bloch, J. Vaneecloo, L. Bourachot, G.-J. Both, G. Mériaux, S. Dutartre, R. Hostein, J. Paris, et al., Phys. Rev. Appl. 22, 024073 (2024), URL https://link.aps.org/doi/10.1103/PhysRevApplied.22.024073.DOI
  11. [11]Y. Cheng and H. Zhai, Nature Reviews Physics 6, 566 (2024), URL https://doi.org/10.1038/s42254-024-00749-6.
  12. [12]T. Zhang, Z. Chi, and J. Hu, PRX Quantum 5, 030345 (2024), URL https://link.aps.org/doi/10.1103/PRXQuantum.5.030345.DOI
  13. [13]H. J. Manetsch, G. Nomura, E. Bataille, X. Lv, K. H. Leung, and M. Endres, Nature 647, 60 (2025), URL https://doi.org/10.1038/s41586-025-09641-4.
  14. [14]R. Lin, H.-S. Zhong, Y. Li, Z.-R. Zhao, L.-T. Zheng, T.-R. Hu, H.-M. Wu, Z. Wu, W.-J. Ma, Y. Gao, et al., Phys. Rev. Lett. 135, 060602 (2025), URL https://link.aps.org/doi/10.1103/2ym8-vs82.DOI
  15. [15]N.-C. Chiu, E. C. Trapp, J. Guo, M. H. Abobeih, L. M. Stewart, S. Hollerith, P. L. Stroganov, M. Kalinowski, A. A. Geim, S. J. Evered, et al., Nature 646, 1075 (2025), URL https://doi.org/10.1038/s41586-025-09596-6.
  16. [16]M. Mohan, J. de Hond, and S. Kokkelmans, Phys. Rev. Appl. 23, 054074 (2025), URL https://link.aps.org/doi/10.1103/PhysRevApplied.23.054074.DOI
  17. [17]M. Qiao, G. Emperauger, C. Chen, L. Homeier, S. Hollerith, G. Bornet, R. Martin, B. Gély, L. Klein, D. Barredo, et al., Nature 644, 889 (2025), URL https://doi.org/10.1038/s41586-025-09377-1.
  18. [18]M. Qiao, R. Martin, L. Homeier, I. Morera, B. Gély, L. Klein, Y. T. Chew, D. Barredo, T. Lahaye, E. Demler, et al., Kinetically-induced bound states in a frustrated rydberg tweezer array (2025), 2510.17183, URL https://arxiv.org/abs/2510.17183.
  19. [19]T. Zhang, W. Wang, W. Zhang, Y. Wang, A. Du, Z. Li, Y. Wu, C. Li, J. Hu, H. Zhai, et al., Phys. Rev. Lett. 135, 093403 (2025), URL https://link.aps.org/doi/10.1103/2gwz-65w1.DOI
  20. [20]Y. Wang, Y. Liao, T. Zhang, Y. Tian, Y. Wu, A. Senoo, A. Baumgärtner, J. W. Lis, G. M. Vaidya, Z. Zeng, G. Giudici, H. Pichler, and A. M. Kaufman, Nature Physics 22, 903 (2026), URL https://doi.org/10.1038/s41567-026-03258-8.
  21. [22]Z. Zeng, G. Giudici, A. Senoo, A. Baumgärtner, A. M. Kaufman, and H. Pichler, Phys. Rev. Lett. 136, 120404 (2026), URL https://link.aps.org/doi/10.1103/z2tj-cwzb.DOI
  22. [23]F. Cesa, A. D. Fini, D. A. Korbany, R. Tricarico, H. Bernien, H. Pichler, and L. Piroli, Engineering discrete local dynamics in globally driven dual-species atom arrays (2026), 2601.16961, URL https://arxiv.org/abs/2601.16961.
  23. [24]R. White, V. Ramesh, A. Imperto, S. Anand, F. Cesa, G. Giudici, T. Iadecola, H. Pichler, and H. Bernien, Quantum cellular automata on a dual-species rydberg processor (2026), 2601.16257, URL https://arxiv.org/abs/2601.16257.
  24. [25]D. Bluvstein, A. Geim, S. H. Li, S. J. Evered, J. P. Bonilla Ataides, G. Baranes, A. Gu, T. Manovitz, M. Xu, M. Kalinowski, et al., Nature 649, 39 (2026), URL https://doi.org/10.1038/s41586-025-09848-5.
  25. [26]E. Urban, T. A. Johnson, T. Henage, L. Isenhower, D. D. Yavuz, T. G. Walker, and M. Saffman, Nature Physics 5, 110 (2009), URL https://doi.org/10.1038/nphys1178.
  26. [27]A. Browaeys and T. Lahaye, Nature Physics 16, 132 (2020), URL https://doi.org/10.1038/s41567-019-0733-z.
  27. [28]H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin, Quantum optimization for maximum independent set using rydberg atom arrays (2018), 1808.10816, URL https://arxiv.org/abs/1808.10816.
  28. [29]M. Kim, K. Kim, J. Hwang, E.-G. Moon, and J. Ahn, Nature Physics 18, 755 (2022), URL https://doi.org/10.1038/s41567-022-01629-5.
  29. [30]A. Byun, M. Kim, and J. Ahn, PRX Quantum 3, 030305 (2022), URL https://link.aps.org/doi/10.1103/PRXQuantum.3.030305.DOI
  30. [31]S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeg hini, A. Omran, J.-G. Liu, R. Samajdar, et al., Science 376, 1209 (2022), https://www.science.org/doi/pdf/10.1126/science.abo6587, URL https://www.science.org/doi/abs/10.1126/science.abo6587.
  31. [32]M.-T. Nguyen, J.-G. Liu, J. Wurtz, M. D. Lukin, S.-T. Wang, and H. Pichler, PRX Quantum 4, 010316 (2023), URL https://link.aps.org/doi/10.1103/PRXQuantum.4.010316.DOI
  32. [33]A. G. de Oliveira, E. Diamond-Hitchcock, D. M. Walker, M. T. Wells-Pestell, G. Pelegrí, C. J. Picken, G. P. A. Malcolm, A. J. Daley, J. Bass, and J. D. Pritchard, PRX Quantum 6, 010301 (2025), URL https://link.aps.org/doi/10.1103/PRXQuantum.6.010301.DOI
  33. [34]M. J. A. Schuetz, R. S. Andrist, G. Salton, R. Yalovetzky, R. Raymond, Y. Sun, A. Acharya, S. Chakrabarti, M. Pistoia, and H. G. Katzgraber, Phys. Rev. Res. 7, 033107 (2025), URL https://link.aps.org/doi/10.1103/7dkh-crjj.DOI
  34. [35]L. Bombieri, Z. Zeng, R. Tricarico, R. Lin, S. Notarnicola, M. Cain, M. D. Lukin, and H. Pichler, PRX Quantum 6, 020306 (2025), URL https://link.aps.org/doi/10.1103/PRXQuantum.6.020306.DOI
  35. [36]P. Cazals, A. François, L. Henriet, L. Leclerc, M. Marin, Y. Naghmouchi, W. d. S. Coelho, F. Sikora, V. Vitale, R. Watignat, et al., Phys. Rev. Appl. 25, 034085 (2026), URL https://link.aps.org/doi/10.1103/8gjv-11lf.
  36. [37]A. G. de Oliveira, J. Kombe, G. Pelegrí, P. Schroff, M. T. Wells-Pestell, D. M. Walker, A. J. Daley, and J. D. Pritchard, A quantum wire approach to weighted combinatorial graph optimisation problems (2026), 2503.17115, URL https://arxiv.org/abs/2503.17115.
  37. [38]J. Kombe and J. D. Pritchard, Reducibility of native weighted graphs on rydberg arrays (2026), 2605.07952, URL https://arxiv.org/abs/2605.07952.
  38. [39]A. Byun, B. Klaver, A. De, P. Ildefonso, D. Khachatryan, A. Bylinskii, M. Schuler, and W. Lechner, Error-corrected quantum optimization via rydberg atom array embeddings (2026), 2610.39670, URL https://arxiv.org/abs/2610.39670.
  39. [40]X.-Z. Gao, Y.-J. Wang, P. Zhang, and J.-G. Liu, Automated discovery of branching rules with optimal complexity for the maximum independent set problem (2024), 2412.07685, URL https://arxiv.org/abs/2412.07685.
  40. [41]D. Jaksch, J. I. Cirac, P. Zoller, S. L. Rolston, R. Côté, and M. D. Lukin, Phys. Rev. Lett. 85, 2208 (2000), URL https://link.aps.org/doi/10.1103/PhysRevLett.85.2208.DOI
  41. [42]M. D. Lukin, M. Fleischhauer, R. Cote, L. M. Duan, D. Jaksch, J. I. Cirac, and P. Zoller, Phys. Rev. Lett. 87, 037901 (2001), URL https://link.aps.org/doi/10.1103/PhysRevLett.87.037901.DOI
  42. [43]A. Gaëtan, Y. Miroshnychenko, T. Wilk, A. Chotia, M. Viteau, D. Comparat, P. Pillet, A. Browaeys, and P. Grangier, Nature Physics 5, 115 (2009), URL https://doi.org/10.1038/nphys1183.
  43. [44]M. Serbyn, D. A. Abanin, and Z. Papić, Nature Physics 17, 675 (2021), URL https://doi.org/10.1038/s41567-021-01230-2.
  44. [45]G.-X. Su, H. Sun, A. Hudomal, J.-Y. Desaules, Z.-Y. Zhou, B. Yang, J. C. Halimeh, Z.-S. Yuan, Z. Papić, and J.-W. Pan, Phys. Rev. Res. 5, 023010 (2023), URL https://link.aps.org/doi/10.1103/PhysRevResearch.5.023010.DOI
  45. [46]M. Cain, S. Chattopadhyay, J.-G. Liu, R. Samajdar, H. Pichler, and M. D. Lukin, Quantum speedup for combinatorial optimization with flat energy landscapes (2023), 2306.13123, URL https://arxiv.org/abs/2306.13123.
  46. [47]D. Bluvstein, A. Omran, H. Levine, A. Keesling, G. Semeg hini, S. Ebadi, T. T. Wang, A. A. Michailidis, N. Maskara, W. W. Ho, et al., Science 371, 1355 (2021), URL https://www.science.org/doi/abs/10.1126/science.abg2530.
  47. [48]A. Hudomal, J.-Y. Desaules, B. Mukherjee, G.-X. Su, J. C. Halimeh, and Z. Papić, Phys. Rev. B 106, 104302 (2022), URL https://link.aps.org/doi/10.1103/PhysRevB.106.104302.DOI
  48. [49]G. Giudici, F. M. Surace, and H. Pichler, Phys. Rev. Lett. 133, 190404 (2024), URL https://link.aps.org/doi/10.1103/PhysRevLett.133.190404.DOI
  49. [50]H. K. Park and S. Lee, Phys. Rev. B 111, 085104 (2025), URL https://link.aps.org/doi/10.1103/PhysRevB.111.085104.DOI
  50. [51]B. Wu, H. Yu, and F. Wilczek, Phys. Rev. A 101, 012318 (2020), URL https://link.aps.org/doi/10. 1103/PhysRevA.101.012318
  51. [52]X. Zhao, P. Ge, H. Yu, L. You, F. Wilczek, and B. Wu, National Science Review 12, nwa f304 (2025), ISSN 2095-5138, https://academic.oup.com/nsr/article-pdf/12/9/nwaf304/63880869/nwaf304.pdf, URL https://doi.org/10.1093/nsr/nwaf304.
  52. [53]S. Klavžar and M. Mollard, Daisy cubes and distance cube polynomial (2017), 1705.08674, URL https://arxiv.org/abs/1705.08674.
  53. [54]A. Taranenko, European Journal of Combinatorics 85, 103058 (2020), ISSN 0195-6698, URL https://www.sciencedirect.com/science/article/pii/S0195669819301593.
  54. [55]G. Schaller, S. Mostame, and R. Schützhold, Phys. Rev. A 73, 062307 (2006), URL https://link.aps.org/doi/10.1103/PhysRevA.73.062307.DOI
  55. [56]S. Jansen, M.-B. Ruskai, and R. Seiler, Journal of Mathematical Physics 48, 102111 (2007), ISSN 0022-2488, URL https://doi.org/10.1063/1.2798382.
  56. [57]S. Boixo and R. D. Somma, Phys. Rev. A 81, 032308 (2010), URL https://link.aps.org/doi/10.1103/PhysRevA.81.032308.DOI
  57. [58]R. C. Read and R. J. Wilson, An Atlas of Graphs (Oxford University Press, Oxford, 2005).
  58. [59]F. Lenz, J. T. Londergan, E. J. Moniz, R. Rosenfelder, M. Stingl, and K. Yazaki, Annals of Physics 170, 65 (1986), ISSN 0003-4916, URL https://www.sciencedirect.com/science/article/pii/0003491686900886.
  59. [60]D. Dvořák, J.-S. Sereni, and J. Volec, Journal of the London Mathematical Society 89, 641 (2014), https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/jlms/jdt085, URL https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/jdt085.
  60. [61]R. Diestel, Graph Theory, vol. 173 of Graduate Texts in Mathematics (Springer-Verlag, Heidelberg, 2025), 6th ed., ISBN 978-3-662-70106-5.
  61. [62]W. Cames van Batenburg, G. Joret, and J. Goedgebeur, Advances in Combinatorics (2020), URL https://doi.org/10.19086/aic.13667.
  62. [63]B. F. Schiffer, D. S. Wild, N. Maskara, M. Cain, M. D. Lukin, and R. Samajdar, Phys. Rev. Res. 6, 013271 (2024), URL https://link.aps.org/doi/10.1103/PhysRevResearch.6.013271.DOI
  63. [64]A. Lukin, B. F. Schiffer, B. Braverman, S. H. Cantu, F. Huber, A. Bylinskii, J. Amato-Grill, N. Maskara, M. Cain, D. S. Wild, et al., Quantum quench dynamics as a shortcut to adiabaticity (2024), 2405.21019, URL https://arxiv.org/abs/2405.21019.
  64. [65]S. Moudgalya, B. A. Bernevig, and N. Regnault, Reports on Progress in Physics 85, 086501 (2022), URL https://doi.org/10.1088/1361-6633/ac73a0.
  65. [66]S. Moudgalya and O. I. Motrunich, Phys. Rev. X 12, 011050 (2022), URL https://link.aps.org/doi/10.1103/PhysRevX.12.011050.DOI
  66. [67]Y. Li, P. Sala, and F. Pollmann, Phys. Rev. Res. 5, 043239 (2023), URL https://link.aps.org/doi/10.1103/PhysRevResearch.5.043239.DOI
  67. [68]J. M. Deutsch, Reports on Progress in Physics 81, 082001 (2018), URL https://doi.org/10.1088/1361-6633/aac9f1.
  68. [69]M. Ueda, Nature Reviews Physics 2, 669 (2020), URL https://doi.org/10.1038/s42254-020-0237-x.

Paper details

vlnc:W_4rbky6z4
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