--- abstract: 'Affleck-Kennedy-Lieb-Tasaki (AKLT) states are an important class of many-body quantum states that are useful in quantum information processing, including measurement-based quantum computation in particular. Here we propose a general approach for constructing efficient verification protocols for AKLT states on arbitrary graphs with local spin measurements. Our verification protocols build on bond verification protocols and matching covers (including edge coloring) of the underlying graphs, which have a simple geometric and graphic picture. We also provide rigorous performance guarantee that is required for practical applications. With our approach, most AKLT states of wide interest, including those defined on 1D and 2D lattices, can be verified with a constant sample cost, which is independent of the system size and is dramatically more efficient than all previous approaches. As an illustration, we construct concrete verification protocols for AKLT states on various lattices and on arbitrary graphs up to five vertices.' author: - Tianyi Chen - Yunting Li - Huangjun Zhu bibliography: - 'all\_references.bib' title: 'Efficient verification of Affleck-Kennedy-Lieb-Tasaki states' --- Introduction ============ Ground states of local Hamiltonians play crucial roles in many-body physics and have also found increasing applications in quantum information processing @StepWPW17 [@Wei18; @StepNBE19; @DaniAM20; @GoihWET20; @WeiRA22]. The Affleck-Kennedy-Lieb-Tasaki (AKLT) states @AfflKLT87 [@AfflKLT88] are of special interest because they are the ground states of exactly solvable models and are tied to the famous Haldane conjecture @Hald83C [@Hald83N]. These states are originally defined on spin chains and have been generalized to arbitrary graphs later @KiriK09 [@XuK08; @KoreX10]. Recently, AKLT states have attracted increasing attention because of their connection with symmetry-protected topological orders @ChenGLW12 [@Sent15; @ChiuTSA16]. Moreover, AKLT states on many 2D lattices, including the honeycomb lattice, are universal resource states for measurement-based quantum computation @RausB01 [@KaltLZB10; @WeiAR11; @Miya11; @WeiAR12]. In practice it is not easy to prepare many-body states, such as AKLT states, perfectly. Therefore, it is crucial to verify these states within a desired precision efficiently. However, traditional tomographic approaches are too resource consuming to achieve this goal for large and intermediate quantum systems. Recently, great efforts have been directed to addressing this problem @EiseHWR20 [@CarrEKK21; @KlieR21; @YuSG22; @MorrSGD22], and various alternative approaches have been proposed, including compressed sensing @GrosLFB10, direct fidelity estimation @FlamL11 [@SilvLP11], and shadow estimation @Aaro18 [@HuanKP20] etc. Here we are particularly interested in a promising approach known as quantum state verification (QSV), which can achieve high efficiency based on local measurements @HayaMT06 [@CramPFS10; @AoliGKE15; @HangKSE17; @PallLM18; @TakeM18; @ZhuH19AdS; @ZhuH19AdL; @WuBGL21; @LiuSHZ21; @GocaSD22] . So far efficient verification protocols have been constructed for bipartite pure states @HayaMT06 [@Haya09G; @PallLM18; @ZhuH19O; @LiHZ19; @WangH19; @YuSG19], stabilizer states (including graph states and Greenberger-Horne-Zeilinger states in particular) @HayaM15 [@FujiH17; @HayaH18; @PallLM18; @MarkK18; @ZhuH19E; @ZhuH19AdL; @LiHZ20], hypergraph states @ZhuH19E, weighted graph states @HayaT19, Dicke states @LiuYSZ19, and phased Dicke states (including Slater determinant states) @LiuYSZ19 [@LiHSS21]. In addition, several verification protocols have been demonstrated successfully in experiments @ZhanZCP20 [@ZhanLYP20; @LuXCC20; @JianWQC20]. Moreover, this approach can be generalized to the verification of quantum gates and processes @WuB19 [@LiuSYZ20; @ZhuZ20; @ZengZL20], which have also been demonstrated in experiments @ZhanHTS22 [@LuooZZ22]. Unfortunately, efficient verification protocols known so far are usually tailored to quantum states with special structures and rely on explicit expressions of the states under consideration. For the ground states of local Hamiltonians, although several verification protocols have been proposed @CramPFS10 [@HangKSE17; @GluzKEA18; @TakeM18; @CruzBTS22], it is still too resource consuming to verify large and intermediate quantum systems. In this paper, following the simple recipe proposed in the companion paper @ZhuLC22, we propose a general approach for constructing efficient verification protocols for AKLT states defined on arbitrary graphs. Notably, explicit expressions for the AKLT states are not necessary. Our verification protocols are based on local spin measurements and are thus easy to implement in experiments. In addition, these verification protocols have very simple description in terms of elementary geometric and graph theoretic concepts. Moreover, we provide rigorous upper bounds on the number of tests (sample cost) required to achieve a given precision. With our approach, most AKLT states of practical interest, including those defined on 1D and 2D lattices, can be verified with a number of tests that is independent of the system size, which is dramatically more efficient than previous approaches @CramPFS10 [@HangKSE17; @TakeM18; @CruzBTS22]. In addition, we construct concrete verification protocols for all AKLT states defined on arbitrary graphs up to five vertices. The rest of this paper is organized as follows. In <span>Sec. \[sec:QSV\]</span> we first review the basic framework of QSV and then introduce the idea of subspace verification as a generalization. In <span>Sec. \[sec:AKLT\]</span> we review the definition and basic properties of AKLT states that are relevant in later studies. In <span>Sec. \[sec:BondVerify\]</span> we clarify potential bond test operators based on spin measurements and construct various optimal and efficient bond verification protocols. In <span>Sec. \[sec:ApproachGen\]</span> we propose a general approach for constructing efficient verification protocols for AKLT states together with rigorous performance guarantee. In <span>Sec. \[sec:1DAKLT\]</span> we discuss in detail the verification of 1D AKLT states. In <span>Sec. \[sec:VAKLTgenGraph\]</span> we construct concrete verification protocols for AKLT states defined on general graphs up to five vertices. In <span>Sec. \[sec:summary\]</span> we summarize this paper. Several technical proofs and a table are relegated to the Appendix. \[sec:QSV\]Quantum state verification ===================================== In this section we first review the general framework of QSV following <span>Refs. @PallLM18 [@ZhuH19AdS; @ZhuH19AdL]</span>. Then we generalize the idea to subspace verification, which is closely tied to the verification of ground states of local Hamiltonians. Basic framework --------------- A primitive in quantum information processing is to produce a given quantum state $|\Psi\rangle$ with prescribed properties. In practice, the device we employ is never perfect, and the states produced in individual runs may be different from the target state and also different from each other. So it is crucial to verify whether the deviation from the target state, usually quantified by the infidelity, is tolerable. To address this problem, in each run we can perform a random two-outcome measurement $\{T_l,1-T_l\}$ determined by the test operator $T_l$, where the two outcomes correspond to passing and failing the test, respectively. To guarantee that the target state $|\Psi\rangle$ can pass the test with certainty, the test operator $T_l$ needs to satisfy the following requirement $$\begin{aligned} \label{eq:TestTargetCon} T_l|\Psi\>=|\Psi\>. \end{aligned}$$ Let $p_l$ be the probability of performing the test $T_l$ and define the *verification operator* $$\label{eq:VO} \Omega=\sum_l p_l T_l.$$ Suppose $\sigma$ is a quantum state whose fidelity with the target state is at most $1-\epsilon$, that is, ${\< \Psi|}\sigma {| \Psi\>} \leq 1-\epsilon$; then the probability that $\sigma$ can pass each test on average is bounded from above as follows @PallLM18 [@ZhuH19AdS; @ZhuH19AdL], $$\label{eq:PassProb} \max_{\<\Psi|\sigma|\Psi\>\leq 1-\epsilon }{\operatorname{tr}}(\Omega \sigma)=1- [1-\beta(\Omega)]\epsilon=1- \nu(\Omega)\epsilon,$$ where $\beta(\Omega)$ denotes the second largest eigenvalue of the verification operator $\Omega$, and $\nu(\Omega)=1-\beta(\Omega)$ is referred to as the *spectral gap*. As a corollary of <span>Eq. </span> the probability that the states $\sigma_1, \sigma_2, \ldots, \sigma_N$ can pass all $N$ tests satisfies @PallLM18 [@ZhuH19AdS; @ZhuH19AdL] $$\begin{aligned} \label{eq:PassProb1} \prod_{j=1}^N{\operatorname{tr}}(\Omega \sigma_j)\leq \prod_{j=1}^N [1- \nu(\Omega)\epsilon_j]\leq [1- \nu(\Omega)\bar{\epsilon}]^N,\end{aligned}$$ where $\epsilon_j=1-\<\Psi|\sigma_j|\Psi\>$ is the infidelity of the state $\sigma_j$ and $\bar{\epsilon}=\sum_j\epsilon_j/N$ is the average infidelity. To verify the target state $|\Psi\rangle$ within infidelity $\epsilon$ and significance level $\delta$, which means $\delta\geq [1- \nu(\Omega)\epsilon]^N$, the minimum number of tests required is given by @PallLM18 [@ZhuH19AdS; @ZhuH19AdL] $$\label{eq:nu} N=\biggl\lceil\frac{ \ln \delta}{\ln[1-\nu(\Omega)\epsilon]}\biggr\rceil\approx \frac{ \ln (\delta^{-1})}{\nu(\Omega)\epsilon},$$ which decreases monotonically with the spectral gap $\nu(\Omega)$. To achieve a high efficiency, we need to construct a verification operator with a large spectral gap. Here we shall focus on verification protocols that can be realized by local projective measurements, which are most amenable to practical applications. The verification operator $\Omega$ is *homogeneous* @ZhuH19O [@ZhuH19AdS; @ZhuH19AdL] if it has the form $$\Omega=|\Psi\>\<\Psi|+\lambda(1-|\Psi\>\<\Psi|).$$ In this case, the probability that $\sigma$ can pass each test on average is completely determined by its fidelity with the target state $|\Psi\>$, $${\operatorname{tr}}(\Omega\sigma)=\lambda+\nu F=1-\nu \epsilon,$$ where $F=\<\Psi|\sigma|\Psi\>$ and $\epsilon=1-F$. Such verification protocols are of special interest because they can also be used for fidelity estimation. Subspace verification --------------------- The basic idea of QSV can also be applied to subspace verification, which emerges naturally in the verification of multipartite pure states, such as the ground states local Hamiltonians. To see this point, suppose we want to verify the multipartite pure state $|\Psi\>$ whose reduced states are mixed and are supported in certain subspaces. To this end, we can verify that each reduced state is supported in a particular subspace. Quite often it turns out that the target state $|\Psi\>$ can be verified in this way without additional steps. Notably, this strategy is particularly useful to verifying the ground states of frustrate-free Hamiltonians, including AKLT states in particular. Let ${\mathcal{V}}$ be a given subspace of the Hilbert space ${\mathcal{H}}$ under consideration and $Q$ the corresponding projector. Our task is to verify whether the state produced is supported in this subspace. To address this problem, we can construct a set of tests and perform a random test from this set in each run. Every test corresponds to a two-outcome measurement $\{T_l,1-T_l\}$, which is determined by the test operator $T_l$, as in the verification of a pure state. Now the condition in <span>Eq. </span> is replaced by $$\begin{aligned} \label{eq:TestTargetProj} T_l Q=Q, \end{aligned}$$ so that all states supported in ${\mathcal{V}}$ can pass each test with certainty. Let $p_l$ be the probability of performing the test $T_l$ and define the verification operator $$\begin{aligned} \Omega=\sum_l p_l T_l\end{aligned}$$ as in QSV \[cf. <span>Eq. </span>\]. Then $\Omega$ satisfies the condition $\Omega Q=Q$ thanks to <span>Eq. </span>. Suppose the quantum state $\sigma$ under consideration satisfies the condition ${\operatorname{tr}}(Q\sigma)\leq 1-\epsilon$; then the probability that $\sigma$ can pass each test on average is bounded from above as follows, $$\label{eq:PassProbSS} \max_{{\operatorname{tr}}(Q\sigma)\leq 1-\epsilon }{\operatorname{tr}}(\Omega \sigma)=1- [1-\beta(\Omega)]\epsilon=1- \nu(\Omega)\epsilon,$$ where $$\begin{aligned} \beta(\Omega)&=\|\bar{\Omega}\|, \quad \nu(\Omega)=1-\beta(\Omega),\\ \bar{\Omega}&=(1-Q)\Omega(1-Q).\end{aligned}$$ As a corollary of <span>Eq. </span>, the probability that the states $\sigma_1, \sigma_2, \ldots, \sigma_N$ produced in $N$ runs can pass all $N$ tests satisfies $$\begin{aligned} \prod_{j=1}^N{\operatorname{tr}}(\Omega \sigma_j)\leq \prod_{j=1}^N [1- \nu(\Omega)\epsilon_j]\leq [1- \nu(\Omega)\bar{\epsilon}]^N,\end{aligned}$$ where $\epsilon_j=1-{\operatorname{tr}}(Q\sigma_j)$ and $\bar{\epsilon}=(\sum_j \epsilon_j)/N$. This result has the same form as the counterpart in QSV. To verify the subspace ${\mathcal{V}}$ within infidelity $\epsilon$ and significance level $\delta$, the number of tests required reads $$N=\biggl\lceil\frac{ \ln \delta}{\ln[1-\nu(\Omega)\epsilon]}\biggr\rceil\approx \frac{ \ln (\delta^{-1})}{\nu(\Omega)\epsilon},$$ which also has the same form as the counterpart in QSV as presented in <span>Eq. </span>. The concept of homogeneous verification operators has a natural generalization in the context of subspace verification. Now the verification operator $\Omega$ is *homogeneous* if it has the form $$\Omega=Q+\lambda(1-Q).$$ In this case, the probability that $\sigma$ can pass each test on average is completely determined by the overlap ${\operatorname{tr}}(Q\sigma)$, $${\operatorname{tr}}(\Omega\sigma)=\lambda+\nu {\operatorname{tr}}(Q\sigma)=1-\nu [1-{\operatorname{tr}}(Q\sigma)].$$ In other words, the overlap ${\operatorname{tr}}(Q\sigma)$ can be estimated from the passing probability ${\operatorname{tr}}(\Omega\sigma)$. Such verification protocols will play an important role in the verification of AKLT states, as we shall see shortly. \[sec:AKLT\]AKLT States ======================= In this section we briefly review AKLT states defined on general graphs @AfflKLT87 [@AfflKLT88; @KiriK09; @XuK08; @KoreX10]. For the convenience of the readers, basic facts about spin operators and graphs are introduced in advance. Spin operators -------------- The spin operator associated with a spin-$S$ particle is denoted by $\bm{S}=(S_x,S_y,S_z)$, where $S_x$, $S_y$, $S_z$ are the spin operators along directions $\hat{x}$, $\hat{y}$, $\hat{z}$, respectively, which act on a Hilbert space of dimension $2S+1$. Note that $S_x$, $S_y$, $S_z$ are nondegenerate and have eigenvalues $S, S-1, \ldots, -S$. Given an eigenvalue $m$ of $S_z$, the corresponding eigenstate is denoted by $|S, m\>$ or $|m\>$ when $S$ is clear from the context. Then the operators $S_x, S_y, S_z$ can be expressed as $$\begin{aligned} S_x=\frac{S_++S_-}{2},\;\; S_y=\frac{S_+-S_-}{2{\mathrm{i}}},\;\; S_z=\sum_{m=-S}^S m|m\>\<m|, \label{eq:Spin}\end{aligned}$$ where $$\begin{aligned} S_{+}&=\sum_{m=-S}^{S-1} \sqrt{S(S+1)-m(m+ 1)}|m+1\>\<m|, \\ S_{-}&=\sum_{m=-S+1}^S \sqrt{S(S+1)-m(m- 1)}|m-1\>\<m|. \end{aligned}$$ When $S=1$ for example, $S_x$, $S_y$, $S_z$ have the following matrix representations, $$\begin{aligned} S_x&=\frac{1}{\sqrt{2}} \begin{pmatrix} 0 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 0\\ \end{pmatrix},\quad S_y=\frac{{\mathrm{i}}}{\sqrt{2}} \begin{pmatrix} 0 & -1 & 0\\ 1 & 0 & -1\\ 0 & 1 & 0\\ \end{pmatrix},\\ S_z&= \begin{pmatrix} 1 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & -1\\ \end{pmatrix}. \end{aligned}$$ Let $\bm{r}$ be a (real) unit vector in dimension 3, then the spin operator along direction $\bm{r}$ reads $$\begin{aligned} \label{eq:sr} S_{\vec{r}}:=\bm{r}\cdot\bm{S}=r_x S_x +r_y S_y + r_z S_z.\end{aligned}$$ Note that $S_{\vec{r}}$ has the same eigenvalues as $S_z$ for any unit vector $\vec{r}$ in dimension 3. The eigenstate of $S_{\vec{r}}$ associated with the eigenvalue $m$ is denoted by $|S,m\>_\vec{r}$ or $|m\>_\vec{r}$ when $S$ is clear from the context. When $m=S$ ($m=-S$), the eigenstate is also denoted by $|+\>_{\vec{r}}$ ($|-\>_\vec{r}$). The projector onto $|m\>_\vec{r}$ can be expressed as $$\begin{aligned} |m\>_\vec{r}\<m|=\prod_{k=-S, k\neq m}^S \frac{S_{\vec{r}}-k}{m-k}, \label{eq:SpinProj}\end{aligned}$$ which implies that $$\begin{aligned} |+\>_\vec{r}\<+|&=|S\>_\vec{r}\<S|=\prod_{k=-S}^{S-1} \frac{S_{\vec{r}}-k}{S-k},\\ |-\>_\vec{r}\<-|&=|-S\>_\vec{r}\<-S|=\prod_{k=-S+1}^{S} \frac{S_{\vec{r}}-k}{-S-k}. \label{eq:eigSpm} \end{aligned}$$ In the special case $S=1/2$, <span>Eq. </span> yields $$|\pm\>_\vec{r}\<\pm|=\Bigl|\pm\frac{1}{2}\Bigr\>_\vec{r}\Bigl\<\pm \frac{1}{2}\Bigr|=\frac{1}{2}\pm S_\vec{r}= \frac{1\pm\vec{r}\cdot\vec{\sigma}}{2},\\$$ where $\vec{\sigma}=(\sigma_x,\sigma_y,\sigma_z)$ is the vector composed of the three Pauli operators. When $S=1$ by contrast, <span>Eq. </span> yields $$\label{eq:proj} |\pm\>_{\vec{r}}\<\pm|=\frac{S_{\vec{r}}(S_{\vec{r}}\pm 1)}{2},\quad |0\>_{\vec{r}}\<0|= 1-S_\vec{r}^2.$$ In addition, given two unit vectors $\bm{r},\bm{s}$ in dimension 3, the fidelities between $|\pm\>_\vec{r}$ and $|\pm\>_\vec{s}$ read (cf. Sec. III D in <span>Ref. @ZhanFG90</span>) $$\label{eq:rsOverlap} \begin{split} |\sideset{_{\bm{r}}}{_{\bm{s}}}{\mathop{\<+|+\>}}|^2=|\sideset{_{\bm{r}}}{_{\bm{s}}}{\mathop{\<-|-\>}}|^2=\Bigl(\frac{1+\bm{r}\cdot\bm{s}}{2}\Bigr)^{2S},\\ |\sideset{_{\bm{r}}}{_{\bm{s}}}{\mathop{\<+|-\>}}|^2=|\sideset{_{\bm{r}}}{_{\bm{s}}}{\mathop{\<-|+\>}}|^2=\Bigl(\frac{1-\bm{r}\cdot\bm{s}}{2}\Bigr)^{2S}. \end{split}$$ When $S=1/2$, <span>Eq. </span> yields the familiar fidelity formula for a qubit, $$\label{eq:rsOverlapS1} \begin{split} |\sideset{_{\bm{r}}}{_{\bm{s}}}{\mathop{\<+|+\>}}|^2=|\sideset{_{\bm{r}}}{_{\bm{s}}}{\mathop{\<-|-\>}}|^2=\frac{1+\bm{r}\cdot\bm{s}}{2},\\ |\sideset{_{\bm{r}}}{_{\bm{s}}}{\mathop{\<+|-\>}}|^2=|\sideset{_{\bm{r}}}{_{\bm{s}}}{\mathop{\<-|+\>}}|^2=\frac{1-\bm{r}\cdot\bm{s}}{2}. \end{split}$$ Graph basics ------------ A graph $G(V,E)$ is specified by a vertex set $V$ and edge set $E$, where each edge is a two-vertex subset of $V$ (here we only consider graphs without loops) @Volo09book. Two distinct vertices $j,k\in V$ are adjacent if $\{j,k\}\in E$, in which case $j,k$ are also called neighbors. The degree of a vertex $j$ is the number of its neighbors and is denoted by $\deg(j)$. The degree of $G$ is the maximum vertex degree and is denoted by $\Delta(G)$. The graph $G$ is $k$-regular if all the vertices have degree $k$. The graph $G$ is connected if for any pair of distinct vertices $i,j$, there exists a sequence of vertices $i_1, i_2, \ldots,i_h$ with $i_1=i$ and $i_h=j$ such that each pair of consecutive vertices are adjacent, that is, $\{i_k, i_{k+1}\}\in E$ for $k=1, 2, \ldots, h-1$. Two distinct edges of $G$ are adjacent if they share a same vertex and nonadjacent otherwise. A *matching* $M$ is a subset of $E$ in which no two edges are adjacent. The matching is a *maximal matching* if it is not contained in any other matching; it is a *maximum matching* if it contains the largest number of edges. The *matching number* is the cardinality of a maximum matching and is denoted by $\upsilon(G)$. A *matching cover* ${\mathscr{M}}$ is a set of matchings that covers the edge set $E$, which means $\cup_{M\in {\mathscr{M}}}=E$. An *edge coloring* of $G$ is an assignment of colors to its edge such that only nonadjacent edges can have the same color. An edge coloring is trivial if all edges have different colors. By definition, each edge coloring determines a matching cover composed of disjoint matchings, and vice versa. The *chromatic index* (or edge chromatic number) of $G$ is the minimum number of colors required to color the edges of $G$ and is denoted by $\chi'(G)$. Meanwhile, $\chi'(G)$ is also the minimum number of matchings required to cover the edge set $E$. According to Vizing's theorem @Vizi64 [@Volo09book], the chromatic index of $G$ satisfies $$\begin{aligned} \Delta(G)\leq \chi'(G)\leq \Delta(G)+1. \label{eq:VizingBound}\end{aligned}$$ AKLT Hamiltonians and AKLT States --------------------------------- Let $G(V,E)$ be a connected graph with $n$ vertices, to define the AKLT Hamiltonian associated with this graph, we first assign a Hilbert space ${\mathcal{H}}_j$ of dimension $\deg(j)+1$ to each vertex $j$. The whole Hilbert space is a tensor product of ${\mathcal{H}}_j$, that is, ${\mathcal{H}}=\bigotimes_{j\in V}{\mathcal{H}}_j$. Then we can assign a spin operator $\vec{S}_j=(S_{j,x}, S_{j,y}, S_{j,z})$ of spin value $S_j=\deg(j)/2$ on ${\mathcal{H}}_j$. Next, for each edge $e=\{j,k\}\in E$ of the graph, define $S_e=S_j+S_k$, then $S_e$ is the maximum possible value of the total spin of the two nodes. Define $$\begin{aligned} S_E:=\max_{e\in E}S_e=\max_{\{j,k\}\in E}(S_j+S_k); \label{eq:S_E}\end{aligned}$$ then we have $$\begin{aligned} \label{eq:SEDeltaG} S_E\leq \Delta(G),\end{aligned}$$ where the inequality is saturated if $G$ is regular. Given an edge $e=\{j,k\}$, denote by $P_e=P_{S_e}(\vec{S}_j+\vec{S}_k)$ the projector onto the spin-$S_e$ subspace of spins $j$ and $k$. To be concrete, the projector can be expressed as follows, $$\begin{aligned} P_e=P_{S_e}(\vec{S}_j+\vec{S}_k)=\prod_{l=|S_j-S_k|}^{ S_j+S_k-1}\frac{(\vec{S}_j+\vec{S}_k)^2 -l(l+1)}{S_e(S_e+1)-l(l+1)},\label{eq:Pe} \end{aligned}$$ where $$\begin{aligned} (\vec{S}_j+\vec{S}_k)^2&=(S_{j,x}+S_{k,x})^2+(S_{j,y}+S_{k,y})^2\nonumber\\ &\quad +(S_{j,z}+S_{k,z})^2.\end{aligned}$$ When $S_j=S_k=1$, <span>Eq. </span> can be simplified as $$\label{eq:spin2} P_2(\vec{S}_j+\vec{S}_k)=\frac{\bm{S}_{j}\cdot \bm{S}_{k}}{2}+\frac{\left(\bm{S}_{j}\cdot \bm{S}_{k}\right)^2}{6}+\frac{1}{3}.$$ When $S_j=S_k=3/2$, <span>Eq. </span> can be simplified as $$\begin{aligned} \label{eq:P3} P_3(\bm{S}_i+\bm{S}_j)&=\frac{27}{160}\bm{S}_i \cdot \bm{S}_j+\frac{29}{360}(\bm{S}_i \cdot \bm{S}_j)^2\nonumber\\ &\quad+\frac{1}{90}(\bm{S}_i \cdot \bm{S}_j)^3+\frac{11}{128}.\end{aligned}$$ Now the AKLT Hamiltonian associated with the graph $G(V,E)$ can be expressed as $$\begin{aligned} H_G=\sum_{e\in E} P_e=\sum_{\{j,k\}\in E}P_{S_j+S_k}(\vec{S}_j+\vec{S}_k). \label{eq:H_G}\end{aligned}$$ It is known that this Hamiltonian is frustration free and has a unique ground state @KiriK09 [@XuK08; @KoreX10], which is denoted by $|\Psi_G\>$ henceforth. By definition we have $$\begin{aligned} P_e |\Psi_G\>=0 \quad \forall e\in E. \label{eq:Psi_G}\end{aligned}$$ Moreover, $|\Psi_G\>$ is the only state (up to an irrelevant overall phase factor) that satisfies this condition. Suppose $e,e'\in E$ are two edges of $G$; then $P_e$ and $P_{e'}$ commute unless the intersection $e\cap e'$ is nonempty. Suppose $e=\{j,k\}$, then at most $\deg(j)+\deg(k)-2$ projectors $P_{e'}$ do not commute with $P_e$. Let $$\begin{aligned} \label{eq:g} g&=g(H_G)=\max_{j<k} [\deg(j)+\deg(k)-2]=2\max_{e\in E} S_e-2\nonumber\\ &=2S_E-2;\end{aligned}$$ then each projector $P_e$ does not commute with at most $g$ projectors that compose the Hamiltonian $H_G$ in <span>Eq. </span>. By <span>Eq. </span> we have $$\begin{aligned} g\leq 2\Delta(G)-2. \end{aligned}$$ When $G$ is the cycle graph with $n\geq 3$ vertices, we get the prototypical 1D AKLT Hamiltonian, $$\begin{aligned} H^{\circ}(n):=H_G=\sum_{j=1}^n P_2(\vec{S}_j+\vec{S}_{j+1}), \end{aligned}$$ where the vertex label $n+1$ is identified with 1 by convention. Explicit expression for the AKLT state $|\Psi_G\>$ is known @AfflKLT87 [@AfflKLT88], but it is not necessary to the current study. By contrast, the AKLT Hamiltonian for the open chain with $n$ nodes is denoted by $$\begin{aligned} H_{\frac{1}{2},\frac{1}{2}}(n):=&P_{\frac{3}{2}}(\vec{S}_1+\vec{S}_2)+P_{\frac{3}{2}}(\vec{S}_{n-1}+\vec{S}_n)\nonumber\\ &+\sum_{j=2}^{n-2} P_2(\vec{S}_j+\vec{S}_{j+1});\end{aligned}$$ here the spin values for the two boundary spins are both equal to $1/2$ as indicated in the subscripts. For the convenience of later discussions, we also define two auxiliary Hamiltonians, $$\begin{aligned} H_{\frac{1}{2},1}(n):=&P_{\frac{3}{2}}(\vec{S}_1+\vec{S}_2)+\sum_{j=2}^{n-1} P_2(\vec{S}_j+\vec{S}_{j+1}), \label{eq:Hh1} \\ H_{1,1}(n):=&\sum_{j=1}^{n-1} P_2(\vec{S}_j+\vec{S}_{j+1}),\label{eq:H11}\end{aligned}$$ where the subscripts indicate the spin values of the two boundary spins. Note that the ground state spaces of $H_{\frac{1}{2},1}(n)$ and $H_{1,1}(n)$ are two-fold degenerate and four-fold degenerate, respectively, in contrast with $H^{\circ}(n)$ and $H_{\frac{1}{2},\frac{1}{2}}(n)$, which are nondegenerate. Spectral gaps of AKLT Hamiltonians ---------------------------------- The spectral gaps of AKLT Hamiltonians are of key interest in many-body physics. They also play a crucial role in the verification of AKLT states as we shall see later. In the original papers @AfflKLT87 [@AfflKLT88], Affleck, Kennedy, Lieb, and Tasaki proved that the AKLT Hamiltonian on the closed chain is gapped. Recently, researchers further showed that the AKLT Hamiltonians on several 2D lattices are also gaped. Notably, spectral gaps can be established rigorously for the honeycomb lattice, decorated honeycomb lattice, and decorated square lattice @AbduLLN20 [@PomaW19; @PomaW20; @LemmSW20; @GuoPW21]. The estimated spectral gaps for the 1D chain, honeycomb lattice, and square lattice are 0.350, 0.100, and 0.015, respectively @GarcMW13 [@WeiRA22]. Here we discuss briefly about the spectral gaps in the 1D case and for arbitrary connected graphs up to five vertices. The spectral gap of the Hamiltonian $H_G$ is denoted by $\gamma(H_G)$ or $\gamma$ for simplicity when there is no danger of confusion. ### 1D chains The spectral gaps of the AKLT Hamiltonians for four types of 1D chains up to 10 nodes are presented in <span>Table \[tab:AKLTgap\]</span> and illustrated <span>Fig. \[fig:AKLTGap\]</span>. Numerical calculation shows that the spectral gaps for open chains, corresponding to $H_{\frac{1}{2},\frac{1}{2}}(n)$, $H_{\frac{1}{2},1}(n)$, and $H_{1,1}(n)$, decrease monotonically with the number of nodes. In the case of the closed chain corresponding to $H^{\circ}(n)$, by contrast, the spectral gap decreases monotonically if the chain has odd length, but increases monotonically if the chain has even length. In addition, numerical calculation suggests the following relations, $$\begin{gathered} \gamma\bigl(H_{\frac{1}{2},\frac{1}{2}}(n)\bigr)\geq \gamma\bigl(H_{\frac{1}{2},1}(n)\bigr)\geq \gamma(H_{1,1}(n)),\quad n\geq 3,\\ \gamma\bigl(H_{\frac{1}{2},\frac{1}{2}}(n)\bigr)\geq \gamma(H^{\circ}(n)), \quad n\geq 4,n\neq5.\end{gathered}$$ $n$ 3 4 5 6 7 8 9 10 ------------------------------- ------- ------- ------- ------- ------- ------- ------- ------- $H_{\frac{1}{2},\frac{1}{2}}$ 0.667 0.517 0.454 0.421 0.402 0.390 0.381 0.376 $H_{\frac{1}{2},1}$ 0.592 0.473 0.431 0.408 0.393 0.384 0.377 0.372 $H_{1,1}$ 0.500 0.449 0.413 0.398 0.387 0.379 0.374 0.367 $H^{\circ}$ 0.833 0.333 0.454 0.348 0.402 0.350 0.381 0.350 $\tilde{c}_n$ 0 0.173 0.218 0.248 0.264 0.276 0.284 0.291 $c_n$ 0 0.207 0.254 0.280 0.290 0.296 0.299 0.301 : \[tab:AKLTgap\] Spectral gaps of the AKLT Hamiltonians $H_{\frac{1}{2},\frac{1}{2}}(n)$, $H_{\frac{1}{2},1}(n)$, $H_{1,1}(n)$, and $H^{\circ}(n)$ for $n=3,4,\ldots,10$ together with the lower bounds $\tilde{c}_n$ and $c_n$ defined in <span>Theorems \[thm:gapKnabe\]</span> and \[thm:gapGM\]. Note that $\tilde{c}_k$ is a lower bound for $\gamma(H^{\circ}(n))$ when $n>k$, while $c_k$ is a lower bound for $\gamma(H^{\circ}(n))$ when $n>2k$. ![\[fig:AKLTGap\]Spectral gaps of the AKLT Hamiltonians $H_{\frac{1}{2},\frac{1}{2}}(n)$, $H_{\frac{1}{2},1}(n)$, $H_{1,1}(n)$, and $H^{\circ}(n)$ for $n=3,4,\ldots,10$. Here lines are guides for the eyes (similarly for other figures). ](fig1.pdf){width="42.00000%"} In the thermodynamic limit, the AKLT Hamiltonian on the closed chain was shown to be gaped already in the original work of AKLT @AfflKLT87 [@AfflKLT88]. Later, Knabe derived a lower bound for $\gamma(H^{\circ}(n))$ based on the spectral gap $\gamma(H_{1,1}(k))$ @Knab88, where $H_{1,1}(k)$ is the Hamiltonian associated with the open chain of $k$ nodes as defined in <span>Eq. </span>. \[Knabe\]\[thm:gapKnabe\] Suppose $n>k>2$. Then $\gamma(H^{\circ}(n))\geq \tilde{c}_k$ with $$\tilde{c}_k:= \left(\frac{k-1}{k-2}\right)\left[\gamma(H_{1,1}(k))-\frac{1}{k-1}\right].$$ The Knabe's bound above is nontrivial whenever $\gamma(H_{1,1}(k))>1/(k-1)$. Recently, Gosset and Mozgunov proved a stronger result as stated in the following theorem @GossM16. \[Gosset-Mozgunov\]\[thm:gapGM\] Suppose $k>2$ and $n>2k$. Then $\gamma(H^{\circ}(n))\geq c_k$ with $$\label{eq:ck} c_k:= \frac{5}{6}\left(\frac{k^2+k}{k^2-4}\right)\left[\gamma(H_{1,1}(k))-\frac{6}{k(k+1)}\right].$$ Numerical calculation suggests that <span>Theorems \[thm:gapKnabe\]</span> and \[thm:gapGM\] still hold if $H^{\circ}(n)$ is replaced by $H_{\frac{1}{2},\frac{1}{2}}(n)$, $H_{\frac{1}{2},1}(n)$, or $H_{1,1}(n)$ (cf. <span>Table \[tab:AKLTgap\]</span>). ### general graphs ![\[fig:gammaMaxMin\]Connected graphs of three, four, and five vertices whose AKLT Hamiltonians have the largest spectral gaps (up) and smallest spectral gaps (down).](fig2.pdf){width="46.00000%"} Next, we consider the spectral gaps of AKLT Hamiltonians associated with general connected graphs $G(V,E)$ up to five vertices, that is, $n=|V|\leq 5$. Up to isomorphism there are 1 connected graph of two vertices, 2 connected graphs of three vertices, 6 connected graphs of four vertices, and 21 connected graphs of five vertices. The corresponding spectral gaps are presented in <span>Table \[tab:VAKLTgen\]</span> in <span>Appendix \[app:VAKLTgen\]</span>. Calculation shows that the Hamiltonian associated with the complete graph has the largest spectral gap among all graphs with the same number of vertices, as illustrated in <span>Fig. \[fig:gammaMaxMin\]</span>. To be specific, the spectral gaps are $5/6$, $7/10$, and $3/5$ for complete graphs of three, four, and five vertices, respectively. We guess the same conclusion holds even for graphs with more than five vertices. We have not found a general pattern for the graph that leads to the smallest spectral gap: the minimum is attained at the linear graph when $n=3$, the cycle graph when $n=4$, and the lower-right graph shown in <span>Fig. \[fig:gammaMaxMin\]</span> (corresponding to graph No. 18 in <span>Table \[tab:VAKLTgen\]</span>) when $n=5$. \[sec:BondVerify\]Bond verification protocols ============================================= To verify the AKLT state associated with a given graph, we first need to construct bond verification protocols for verifying each pair of adjacent nodes, which is tied to the problem of subspace verification. Here we shall focus on verification protocols that build on spin measurements. \[sec:TestOperator\]Test operators based on spin measurements ------------------------------------------------------------- Let $\vec{S}_1$ and $\vec{S}_2$ be two spin operators of spin values $S_1$ and $S_2$, respectively. Let $S=S_1+S_2$ and let $P_S=P_S(\vec{S}_1+\vec{S}_2)$ be the projector onto the subspace associated with the maximum total spin $S$ as defined in <span>Eq. </span>; let $Q=1-P_S$. Here our goal is to verify the null space of $P_S$, that is, the support of $Q$. To this end, we shall construct test operators based on spin measurements. Suppose the two parties perform spin measurements along directions $\vec{r}, \vec{s}$, respectively, where $\vec{r}, \vec{s}$ are real unit vectors in dimension 3. The measurement outcomes can be labeled by eigenvalues $m_1$ and $m_2$ of $\vec{r}\cdot \vec{S}_1$ and $\vec{s}\cdot \vec{S}_2$, respectively. Let $$\begin{aligned} |S_1,m_1; S_2,m_2\>_{\vec{r},\vec{s}}:=&|S_1,m_1\>_\vec{r}\otimes |S_2,m_2\>_\vec{s},\\ p_{\vec{r},\vec{s}}(S_1,m_1;S_2,m_2):=&\|P_S |S_1,m_1; S_2,m_2\>_{\vec{r},\vec{s}}\|^2\nonumber\\ =&{\operatorname{tr}}[P_S P_{\vec{r},\vec{s}}(S_1,m_1; S_2,m_2)],\end{aligned}$$ where $P_{\vec{r},\vec{s}}(S_1,m_1; S_2,m_2)$ is the rank-1 projector onto the state $|S_1,m_1; S_2,m_2\>_{\vec{r},\vec{s}}$. Then a general test operator $R$ is a linear combination of the projectors $P_{\vec{r},\vec{s}}(S_1,m_1; S_2,m_2)$ associated with all possible outcomes. To guarantee that all states supported in the support of $Q$ can pass the test with certainty, $R$ should satisfy the condition $$\begin{aligned} R\geq P_{\vec{r},\vec{s}}(S_1,m_1; S_2,m_2) \label{eq:TestCondition}\end{aligned}$$ whenever $p_{\vec{r},\vec{s}}(S_1, m_1; S_2,m_2)<1$. If $\vec{r}$ is neither parallel nor antiparallel to $\vec{s}$, then the inequality in <span>Eq. </span> should hold for all possible outcomes $m_1, m_2$ according to <span>Lemma \[lem:SpinProjProb\]</span> below. So the test operator $R$ is equal to the identity operator, and the test is trivial. When $\vec{s}$ is parallel to $\vec{r}$, nontrivial test operators can be constructed. Here we are particularly interested in the canonical test projector associated with $\vec{r}$ as defined as follows, $$\begin{aligned} R_\vec{r}:=&1-P_{\vec{r}}(S_1; S_2)-P_{\vec{r}}(-S_1; -S_2)\nonumber\\ =&1-|++\>_{\vec{r}}\<++|-|--\>_{\vec{r}}\<--|, \label{eq:TestCanonical}\end{aligned}$$ where $$\begin{aligned} P_{\vec{r}}(S_1; S_2):=&P_{\vec{r},\vec{r}}(S_1,S_1; S_2,S_2),\\ P_{\vec{r}}(-S_1; -S_2):=&P_{\vec{r},\vec{r}}(S_1,-S_1; S_2,-S_2),\\ |\pm\pm\>_{\vec{r}}:=&|\pm S_1\>_\vec{r}\otimes |\pm S_2\>_\vec{r}.\end{aligned}$$ According to <span>Lemma \[lem:SpinProjProb\]</span> below, any other test operator $R$ based on the same spin measurements satisfy $R\geq R_\vec{r}$ and is thus suboptimal. When $\vec{s}=-\vec{r}$, the set of accessible test operators does not change given that $$\begin{aligned} P_{\vec{r},\vec{s}}(S_1,m_1; S_2,m_2)&=P_{\vec{r},-\vec{s}}(S_1,m_1; S_2, -m_2). \end{aligned}$$ Therefore, it suffices to consider canonical test projectors based on parallel spin measurements. The following lemma employed in the above analysis is proved in <span>Appendix \[sec:SpinProjProbProof\]</span>. \[lem:SpinProjProb\] Suppose $S_1$ and $S_2$ are positive integers or half integers. Then $$\begin{aligned} p_{\vec{r},\vec{s}}(S_1,m_1; S_2,m_2)\leq 1,\end{aligned}$$ and the inequality is saturated iff one of the following four conditions holds $$\begin{aligned} \vec{r}&=\vec{s}, & m_1&=S_1, & m_2&=S_2; \label{eq:SpinCa}\\ \vec{r}&=\vec{s}, & m_1&=-S_1, & m_2&=-S_2; \label{eq:SpinCb} \\ \vec{r}&=-\vec{s},& m_1&=S_1,& m_2&=-S_2; \label{eq:SpinCc}\\ \vec{r}&=-\vec{s},& m_1&=-S_1,& m_2&=S_2. \label{eq:SpinCd}\end{aligned}$$ Spectral gaps of bond verification protocols -------------------------------------------- According to the discussion in <span>Sec. \[sec:TestOperator\]</span>, each canonical test projector is specified by a unit vector $\vec{r}$ in dimension 3. Given any probability distribution $\mu$ on the unit sphere, then a bond verification protocol can be constructed by performing each test $R_{\vec{r}}$ with a suitable probability. The corresponding verification operator reads $$\begin{aligned} \Omega_{S_1, S_2}(\mu)=\int R_{\vec{r}} d \mu(\bm{r}). \label{eq:BondVO}\end{aligned}$$ When $S_1$ and $S_2$ are clear from the context, $\Omega_{S_1, S_2}(\mu)$ can be abbreviated as $\Omega(\mu)$ for simplicity. The spectral gap of $\Omega_{S_1, S_2}(\mu)$ reads $$\begin{aligned} \nu(\Omega_{S_1, S_2}(\mu))=1-\|P_S\Omega_{S_1, S_2}(\mu))P_S\|, \label{eq:SpectralGapBond}\end{aligned}$$ where $P_S$ is the projector defined according to <span>Eq. </span>. Note that the spectral gap $\nu(\Omega_{S_1, S_2}(\mu))$ is invariant when $\mu$ is subjected to any orthogonal transformation; in addition, $\nu(\Omega(\mu))$ is concave in $\mu$. \[lem:SpectralGapBond\] The spectral gap $\nu(\Omega_{S_1, S_2}(\mu))$ is independent of $S_1$ and $S_2$ once the sum $S=S_1+S_2$ is fixed. <span>Lemma \[lem:SpectralGapBond\]</span> follows from the definition of the test operator $R_\vec{r}$ in <span>Eq. </span> and the fact that the representation of the angular momentum operators carried by the states $|S_1, S_2\>_{\vec{r}}$ is independent of $S_1$ and $S_2$ once the sum $S=S_1+S_2$ is fixed. This result holds even if $S_1=0$ or $S_2=0$, which is very helpful to simplify the computation of the spectral gap. In view of these facts, we shall denote the spectral gap of $\Omega_{S_1, S_2}(\mu)$ by $\nu_S(\mu)$ for simplicity. Denote by $\mu_{\mathrm{sym}}$ the average distribution of $\mu$ and its center inversion. Define $$\begin{aligned} \Omega_S(\mu):=&\int(\,1-|S\>_{\vec{r}}\<S|-|-S\>_{\vec{r}}\<-S|\,) d\mu(\vec{r})\nonumber\\ =& 1-2\int |S\>_{\vec{r}}\<S| d\mu_{\mathrm{sym}}(\vec{r}). \label{eq:OmegaS}\end{aligned}$$ Then $$\begin{aligned} \nu_S(\mu)=1-\|\Omega_S(\mu)\|=\lambda_{\min}(O_S(\mu)), \label{eq:nuSmu}\end{aligned}$$ where $$\begin{aligned} O_S(\mu):=2\int |S\>_{\vec{r}}\<S| d\mu_{\mathrm{sym}}(\vec{r}), \label{eq:MSmu}\end{aligned}$$ and $\lambda_{\min}$ denotes the smallest eigenvalue. In particular, $\nu_S(\mu)$ is nonzero iff the operator $O_S(\mu)$ has full rank. When $\mu$ is a discrete distribution, to achieve a nonzero spectral gap $\nu_S(\mu)>0$, the support of $\mu_{\mathrm{sym}}$ should contain at least $2S+1$ points, so the support of $\mu$ should contain at least $\lceil S+\frac{1}{2}\rceil$ points. To construct a nontrivial bond verification protocol, therefore, at least $\lceil S+\frac{1}{2}\rceil$ distinct canonical tests are required. The following lemma proved in <span>Appendix \[asec:nuSmuProof\]</span> is very instructive to understanding the properties of $\nu_S(\mu)$. \[lem:nuSmu\] Suppose $\mu$ is a probability distribution on the unit sphere. Then $\nu_S(\mu)$ is nonincreasing in $S$. If $S_1\leq S_2$, then $$\begin{aligned} \nu_{S_1}(\mu)\geq \frac{2S_2+1}{2S_1+1} \nu_{S_2}(\mu). \label{eq:nuSmuIneq} \end{aligned}$$ In the special case $S=1/2$, we have $\nu_S(\mu)=1$ irrespective of the distribution $\mu$. So <span>Lemma \[lem:nuSmu\]</span> implies that $$\begin{aligned} \nu_S(\mu)\leq \frac{2}{2S+1}, \label{eq:nuMax}\end{aligned}$$ which sets an upper bound for the spectral gap achievable by spin measurements. Alternatively, <span>Eq. </span> follows from <span>Eq. </span>, which implies that $$\begin{aligned} {\operatorname{tr}}[\Omega_S(\mu)]=2S-1, \quad \|\Omega_S(\mu)\|\geq \frac{2S-1}{2S+1}. \end{aligned}$$ Bond verification protocols that saturate the upper bound in <span>Eq. </span> are called optimal. Notably, this bound is saturated when $\mu$ is the isotropic (uniform) distribution on the unit sphere, which leads to the *isotropic protocol*. To clarify the condition required for constructing an optimal bond verification protocol, we need to introduce additional concepts. Let $t$ be a nonnegative integer. A probability distribution $\mu$ on the unit sphere is a (spherical) $t$-design if the average of any polynomial of degree less than or equal to $t$ over the distribution is equal to the average over the isotropic distribution @DelsGS77 [@Seid01; @BannB09]. By definition a $t$-design is automatically a $(t-1)$-design for any positive integer $t$. The design strength of the distribution $\mu$ is the largest integer $t$ such that $\mu$ is a $t$-design. The isotropic distribution forms a spherical $\infty$-design and has strength $\infty$. If $\mu$ is center symmetric, then $\mu$ is a $2j$-design iff $\mu$ is a $(2j+1)$-design for any positive integer $j$, so the strength of $\mu$ is always an odd integer. The next theorem follows from a similar reasoning used to establish Theorem 3 in the companion paper @ZhuLC22. A self-contained proof is presented in <span>Appendix \[asec:OmegaSdesign\]</span>. \[thm:OmegaSdesign\] Let $\mu$ be a probability distribution on the unit sphere and $S$ a positive integer or half integer. Then the following four statements are equivalent. 1. $\nu_S(\mu)=\frac{2}{2S+1}$. 2. $\Omega_S(\mu)=\frac{2S-1}{2S+1}$. 3. $\Omega_S(\mu)$ is proportional to the identity operator. 4. $\mu_{\mathrm{sym}}$ forms a spherical $t$-design with $t=2S$. According to the discussion before <span>Theorem \[thm:OmegaSdesign\]</span>, when $S$ is a positive integer, $\mu_{\mathrm{sym}}$ forms a $2S$-design iff it forms a $(2S+1)$-design; when $S$ is a positive half integer, $\mu_{\mathrm{sym}}$ forms a $2S$-design iff it forms a $2\lfloor S\rfloor$-design. \[sec:BondVC\]Concrete verification protocols --------------------------------------------- <span>c|ccccccccccc</span> && & & &\_1 &\_<span>3/2</span> &\_<span>2</span> & \_<span>5/2</span> &\_3 &\_<span>7/2</span>&\_4\ &\_&4&4& 2 & & & & && &0\ &\_&6&3& 3 & &&&& 0&0&0\ &\_&8&4&3 & &&&&&&0\ &\_&12&6&5 & &&&&&&\ &\_&20&10&5 & &&&&&&\ \_<span>24</span>&(\_<span>24</span>) &24&24&7 & &&&&&&\ \_<span>32</span> & (\_<span>32</span>) &32&16&9 & &&&&& &\ &\_ &&&& &&&&& &\ In this section we construct a number of concrete bond verification protocols based on discrete distributions on the unit sphere, which are appealing to practical applications. First, we consider bond verification protocols based on platonic solids. Each platonic solid inscribed in the unit sphere determines a probability distribution on the unit sphere (by convention all vertices have the same weight), which in turn determines a bond verification protocol for any given pair of spins. In this way we can construct five bond verification protocols by virtue of the five platonic solids. To be concrete, the vertices of the regular tetrahedron are chosen to be: $$\begin{aligned} &\frac{1}{\sqrt{3}}\left(1,1,1\right), & \frac{1}{\sqrt{3}}\left(1,-1,-1\right),\\ & \frac{1}{\sqrt{3}}\left(-1,1,-1\right), &\frac{1}{\sqrt{3}}\left(-1,-1,1\right).\\ \end{aligned}$$ The vertices of the octahedron are chosen to be: $$\begin{array}{ccc} \left(\pm 1,0,0\right), & \left(0,\pm 1,0\right), & \left(0,0,\pm 1\right).\\ \end{array}$$ The vertices of the cube are chosen to be: $$\frac{1}{\sqrt{3}}\left(\pm 1,\pm 1,\pm 1\right).$$ The vertices of the icosahedron are chosen to be: $$\label{eq:ico} \begin{aligned} &\frac{1}{\sqrt{1+b^2}}(\pm 1,\pm b,0), \quad \frac{1}{\sqrt{1+b^2}}(\pm b,0,\pm 1),\\ &\frac{1}{\sqrt{1+b^2}}(0,\pm 1,\pm b), \end{aligned}$$ where $b=(1+\sqrt{5})/2$. The vertices of the dodecahedron are chosen to be: $$\label{eq:de} \begin{aligned} &\frac{1}{\sqrt{3}}\biggl(\pm b,\pm\frac{1}{b},0\biggr), & \frac{1}{\sqrt{3}}\biggl(\pm\frac{1}{b},0,\pm b\biggr), \\ &\frac{1}{\sqrt{3}}\biggl(0,\pm b,\pm\frac{1}{b}\biggr), & \frac{1}{\sqrt{3}}(\pm 1,\pm 1,\pm 1). \end{aligned}$$ For the convenience of the following discussions, the verification operators associated with the regular tetrahedron, octahedron, cube, icosahedron, and dodecahedron, are denoted by $\Omega_{{\mathrm{t}}}$, $\Omega_{{\mathrm{o}}}$, $\Omega_{{\mathrm{c}}}$, $\Omega_{{\mathrm{i}}}$, and $\Omega_{{\mathrm{d}}}$, respectively. Although these verification operators may depend on the specific choices of vertices, their spectral gaps as shown in <span>Table \[tab:BondSpectralGap\]</span> are independent of the specific choices. Except for the regular tetrahedron, every platonic solid is center symmetric, and the two tests based on each pair of antipodal vertices are equivalent; so the total number of distinct tests is equal to one half of the vertex number. It is known that the regular tetrahedron, octahedron, cube, icosahedron, and dodecahedron form spherical $t$-designs with $t=2, 3, 3, 5, 5$, respectively. Therefore, the icosahedron and dodecahedron protocols are optimal when $S=S_1+S_2\leq 5/2$. To construct optimal bond verification protocols for $S\geq 3$, we need to go beyond platonic solids and consider spherical designs with higher strengths. For example, a spherical $7$-design can be constructed from an orbit of the rotational symmetry group of the standard cube (which has order 24): one fiducial vector has the form $(u_1, u_2, u_3)$, where $$u_j=\sqrt{\frac{1}{3}\biggl(1+2\sqrt{\frac{2}{5}}\cos\frac{\theta+2j\pi}{3}\biggr)},\quad \theta=\arctan\frac{3\sqrt{10}}{20}$$ for $j=1,2,3$. This orbit has 24 vectors, which can be expressed as $$\begin{aligned} \{(a_1 u_{\sigma(1)}, a_2 u_{\sigma(2)},a_1 a_2{\operatorname{sgn}}(\sigma)u_{\sigma(3)})| a_1, a_2=\pm 1, \sigma\in {\mathscr{S}}_3 \}. \end{aligned}$$ Here ${\mathscr{S}}_3$ denotes the symmetric group of three letters; ${\operatorname{sgn}}(\sigma)$ is equal to 1 for even permutations and equal to $-1$ for odd permutations. All points corresponding to these vectors have the same weight as before; the resulting distribution on the unit sphere is denoted by $\mu_{24}$ henceforth. Note that $\mu_{24}$ is not center symmetric. A spherical 9-design can be constructed from the union of the vertices of the icosahedron in <span>Eq. </span> and that of the dodecahedron in <span>Eq. </span>, which form pentakis dodecahedron (cf. <span>Ref. @HughW20</span>). The icosahedron has weight $5/14$ in total and each vertex has weight $5/168$, while the dodecahedron has weight $9/14$ in total and each vertex has weight $9/280$. The resulting distribution on the unit sphere is denoted by $\mu_{32}$, which is center symmetric by construction. The spectral gaps $\nu_S(\mu)$ for $1\leq S\leq 4$ of bond verification operators based on $\mu_{24}$ and $\mu_{32}$ are also shown in <span>Table \[tab:BondSpectralGap\]</span>. \[sec:ApproachGen\]Verification of AKLT states: General approach ================================================================ Construction of verification protocols -------------------------------------- ![image](fig3.pdf){width="80.00000%"} Consider the AKLT Hamiltonian $H_G$ and AKLT state $|\Psi_G\>$ associated with a given graph $G=(V,E)$ of $n$ vertices \[cf. <span>Eqs. and </span>\]. To verify $|\Psi_G\>$, we need to verify each bond associated with each edge of the graph $G$. More specifically, we need to verify the null space of the projector $P_e$ for each $e\in E$. Here we shall focus on bond verification protocols based on spin measurements, which are determined by probability distributions on the unit sphere as discussed in <span>Sec. \[sec:BondVerify\]</span>. For simplicity we also assume that the same distribution is chosen for each bond, although this is not compulsory. Let $\mu$ be a probability distribution on the unit sphere. According to <span>Sec. \[sec:BondVerify\]</span> we can construct a bond verification protocol for each edge of the graph $G$. The bond verification operator associated with the edge $e\in E$ is denoted by $\Omega_e(\mu)$ \[cf. <span>Eq. </span>\]. Given a matching $M$ of $G$, then a test for $|\Psi_G\>$ can be constructed by performing the bond verification protocols for all the bonds associated with edges in $M$ independently. The corresponding test operator is given by $$\begin{aligned} T_M(\mu)=\prod_{e\in M} \Omega_e(\mu). \label{eq:TestMatch}\end{aligned}$$ Note that all the bond verification operators $\Omega_e(\mu)$ for $e\in M$ commute with each other, so the order in the above product is irrelevant. Suppose $\nu(\Omega_e(\mu))>0$ for each $e\in M$, then a quantum state $|\Phi\>$ satisfies the condition $T_M|\Phi\>=|\Phi\>$ iff $P_e|\Phi\>=0$ for each $e\in M$. Therefore, a state can pass the test $T_M(\mu)$ with certainty iff it belongs to the null space of the projector $P_e$ for each $e\in M$. Let $M'$ be another matching of $G$, then we can deduce from <span>Eq. </span> the following relation: $$\begin{aligned} T_M(\mu)\geq T_{M'}(\mu)\quad \mbox{ if }\quad M\subseteq M' \label{eq:TestMatchOrder}.\end{aligned}$$ Let ${\mathscr{M}}=\{M_1, M_2, \ldots, M_m\}$ be a matching cover of $G$ that consists of $m$ matchings and let $p=(p_1,p_2,\ldots, p_m)$ be a probability distribution on ${\mathscr{M}}$ (we shall assume that the distribution is uniform when $p$ is not mentioned explicitly). Then a verification protocol for $|\Psi_G\>$ can be constructed by performing each test $T_{M_l}(\mu)$ with probability $p_l$. The resulting verification protocol is specified by the triple $(\mu, {\mathscr{M}},p)$ (here $p$ can be omitted for the uniform distribution), and the corresponding verification operator reads $$\begin{aligned} \Omega(\mu, {\mathscr{M}},p)=\sum_{l=1}^m p_l T_{M_l}(\mu). \end{aligned}$$ Suppose $p_l>0$ for $l=1,2,\ldots, m$ and $\nu(\Omega_e(\mu))>0$ for each $e\in \cup_l M_l =E$; then a quantum state $|\Phi\>$ can pass all the tests with certainty iff $P_e|\Phi\>=0$ for each $e\in E$. So only the target state $|\Psi_G\>$ can pass all the tests with certainty, which means this verification protocol is effective. According to <span>Eq. </span>, the spectral gap of $\Omega(\mu, {\mathscr{M}},p)$ does not decrease if $M_l$ is replaced by another matching $M_l'$ that contains $M_l$. To maximize the spectral gap, therefore, it is advisable to choose matching covers composed of maximal matchings. If the matchings in ${\mathscr{M}}=\{M_1, M_2, \ldots, M_m\}$ form one orbit under the symmetry group of the graph $G$, then the spectral gap of the verification operator $\Omega(\mu, {\mathscr{M}},p)$ is maximized when the probability distribution $p$ is uniform. In general, given the distribution $\mu$ and the matching cover ${\mathscr{M}}$, the maximum spectral gap of $\Omega(\mu, {\mathscr{M}},p)$ can be determined by semidefinite programming (SDP). Define $$\begin{aligned} \bar{T}_{M_l}(\mu)&:=T_{M_l}(\mu)-|\Psi_G\>\<\Psi_G|,\\ \bar{\Omega}(\mu, {\mathscr{M}},p)&:=\Omega(\mu, {\mathscr{M}},p)-|\Psi_G\>\<\Psi_G|= \sum_{l=1}^m p_l \bar{T}_{M_l}(\mu);\end{aligned}$$ then $$\begin{aligned} \nu(\Omega(\mu, {\mathscr{M}},p))=1-\|\bar{\Omega}(\mu, {\mathscr{M}},p)\|.\end{aligned}$$ To maximize the spectral gap of $\Omega(\mu, {\mathscr{M}},p)$, it is equivalent to minimize the operator norm of $\bar{\Omega}(\mu, {\mathscr{M}},p)$, which can be realized by the following SDP: $$\label{eq:normSDP} \begin{aligned} &\mbox{minimize}\quad \; h\\ &\mbox{subject to}\quad h\geq \sum_{l=1}^m p_l \bar{T}_{M_l}(\mu),\\ &\quad \quad \quad \quad \quad \;\; p_l\geq 0,\quad \sum_{l=1}^m p_l =1. \end{aligned}$$ To construct an optimal matching protocol, in principle we need to consider all maximal matchings before the optimization, which is feasible only for small systems. When this approach is too prohibitive, we can consider simple matching protocols and resort to analytical bounds derived in the next subsection. Sample complexity ----------------- Before presenting our main results on the sample complexity, we need to introduce some terminology. Suppose $P_e$ and $P_{e'}$ are two projectors associated with two edges of $G=(V,E)$ as defined in <span>Eq. </span>. Denote by $s(P_e P_{e'})$ the largest singular value of $P_e P_{e'}$ that is not equal to 1. By definition $s(P_e P_{e'})=0$ if $e=e'$ or if $e$ and $e'$ are disjoint. If $e=\{1,2\}$ and $e'=\{2,3\}$, then $$\begin{aligned} P_e&=P_{12}:=P_{S_1+S_2}(\vec{S}_1+\vec{S}_2),\\ P_{e'}&=P_{23}:=P_{S_2+S_3}(\vec{S}_2+\vec{S}_3). \end{aligned}$$ So the value of $s(P_e P_{e'})=s(P_{12}P_{23})$ is determined by the spin values $S_1, S_2, S_3$; in addition, this value is invariant if $S_1$ and $S_3$ are exchanged. The specific value of $s^2(P_{12}P_{23})$ for $S_1, S_2, S_3\leq 5/2$ can be found in <span>Table \[tab:s2\]</span>, which suggests the following conjecture. Suppose $S_1, S_2, S_3$ are positive integers or half integers; then $s^2(P_{12}P_{23})$ is a rational number. If in addition $S_1, S_3\leq S_2$, then $$\begin{aligned} s^2(P_{12}P_{23})\leq 1/4,\end{aligned}$$ and the inequality is saturated iff $S_1=S_2=S_3$. <span>l|cccccc</span> & $\frac{1}{2}$ & $1$ & $\frac{3}{2}$ & $2$ & $\frac{5}{2}$ & $3$\ \ $(\frac{1}{2},\:\frac{1}{2})$ & $\frac{1}{4}$ & $\frac{1}{9}$ & $\frac{1}{16}$ & $\frac{1}{25}$ & $\frac{1}{36}$ & $\frac{1}{49}$\ $(\frac{1}{2},\:1)$ & $\frac{1}{3}$ & $\frac{1}{6}$ & $\frac{1}{10}$ & $\frac{1}{15}$ & $\frac{1}{21}$ & $\frac{1}{28}$\ $(\frac{1}{2},\:\frac{3}{2})$ & $\frac{3}{8}$ & $\frac{1}{5}$ & $\frac{1}{8}$ & $\frac{3}{35}$ & $\frac{1}{16}$ & $\frac{1}{21}$\ $(\frac{1}{2},\:2)$ & $\frac{2}{5}$ & $\frac{2}{9}$ & $\frac{1}{7}$ & $\frac{1}{10}$ & $\frac{2}{27}$ & $\frac{2}{35}$\ $(\frac{1}{2},\:\frac{5}{2})$ & $\frac{5}{12}$ & $\frac{5}{21}$ & $\frac{5}{32}$ & $\frac{1}{9}$ & $\frac{1}{12}$ & $\frac{5}{77}$\ $(\frac{1}{2},\:3)$ & $\frac{3}{7}$ & $\frac{1}{4}$ & $\frac{1}{6}$ & $\frac{3}{25}$ & $\frac{1}{11}$ & $\frac{1}{14}$\ $(1,\:1)$ & $\frac{4}{9}$ & $\frac{1}{4}$ & $\frac{4}{25}$ & $\frac{1}{9}$ & $\frac{4}{49}$ & $\frac{1}{16}$\ $(1,\:\frac{3}{2})$ & $\frac{1}{2}$ & $\frac{3}{10}$ & $\frac{1}{5}$ & $\frac{1}{7}$ & $\frac{3}{28}$ & $\frac{1}{12}$\ $(1,\:2)$ & $\frac{8}{15}$ & $\frac{1}{3}$ & $\frac{8}{35}$ & $\frac{1}{6}$ & $\frac{8}{63}$ & $\frac{1}{10}$\ $(1,\:\frac{5}{2})$ & $\frac{5}{9}$ & $\frac{5}{14}$ & $\frac{1}{4}$ & $\frac{5}{27}$ & $\frac{1}{7}$ & $\frac{5}{44}$\ $(1,\:3)$ & $\frac{4}{7}$ & $\frac{3}{8}$ & $\frac{4}{15}$ & $\frac{1}{5}$ & $\frac{12}{77}$ & $\frac{1}{8}$\ $(\frac{3}{2},\:\frac{3}{2})$ & $\frac{9}{16}$ & $\frac{9}{25}$ & $\frac{1}{4}$ & $\frac{9}{49}$ & $\frac{9}{64}$ & $\frac{1}{9}$\ $(\frac{3}{2},\:2)$ & $\frac{3}{5}$ & $\frac{2}{5}$ & $\frac{2}{7}$ & $\frac{3}{14}$ & $\frac{1}{6}$ & $\frac{2}{15}$\ $(\frac{3}{2},\:\frac{5}{2})$ & $\frac{5}{8}$ & $\frac{3}{7}$ & $\frac{5}{16}$ & $\frac{5}{21}$ & $\frac{3}{16}$ & $\frac{5}{33}$\ $(\frac{3}{2},\:3)$ & $\frac{9}{14}$ & $\frac{9}{20}$ & $\frac{1}{3}$ & $\frac{9}{35}$ & $\frac{9}{44}$ & $\frac{1}{6}$\ $(2,\:2)$ & $\frac{16}{25}$ & $\frac{4}{9}$ & $\frac{16}{49}$ & $\frac{1}{4}$ & $\frac{16}{81}$ & $\frac{4}{25}$\ $(2,\:\frac{5}{2})$ & $\frac{2}{3}$ & $\frac{10}{21}$ & $\frac{5}{14}$ & $\frac{5}{18}$ & $\frac{2}{9}$ & $\frac{2}{11}$\ $(2,\:3)$ & $\frac{24}{35}$ & $\frac{1}{2}$ & $\frac{8}{21}$ & $\frac{3}{10}$ & $\frac{8}{33}$ & $\frac{1}{5}$\ $(\frac{5}{2},\:\frac{5}{2})$ & $\frac{25}{36}$ & $\frac{25}{49}$ & $\frac{25}{64}$ & $\frac{25}{81}$ & $\frac{1}{4}$ & $\frac{25}{121}$\ $(\frac{5}{2},\:3)$ & $\frac{5}{7}$ & $\frac{15}{28}$ & $\frac{5}{12}$ & $\frac{1}{3}$ & $\frac{3}{11}$ & $\frac{5}{22}$\ $(3,\:3)$ & $\frac{36}{49}$ & $\frac{9}{16}$ & $\frac{4}{9}$ & $\frac{9}{25}$ & $\frac{36}{121}$ & $\frac{1}{4}$\ Define $$\begin{aligned} \label{eq:sG} s(G):=\max_{e,e'\in E}s(P_e P_{e'})=\max_{e,e'\in E|e\neq e'}s(P_e P_{e'}).\end{aligned}$$ By definition $0\leq s(G)< 1$. Here $s(G)$ can be abbreviated as $s$ if there is no danger of confusion. According to <span>Table \[tab:s2\]</span>, we have $s(G)=1/2$ for most lattices of practical interest, including the open chain (with at least four nodes), closed chain, square lattice, honeycomb lattice, triangular lattice, kagome lattice, and square-octagon lattice (cf. <span>Fig. \[fig:LatticeColoring\]</span>). For the open chain with three nodes, we have $s(G)=1/3$. In the following theorem, $\gamma=\gamma(H_G)$ is the spectral gap of $H_G$, while $S_E$ and $\nu_{S_E}(\mu)$ are defined in <span>Eqs. and </span>, respectively. \[thm:AKLTnu1\] Let $|\Psi_G\>$ be the AKLT state defined on the graph $G=(V,E)$. Suppose $\Omega(\mu, {\mathscr{M}})$ is the verification operator specified by the probability distribution $\mu$ and the matching cover ${\mathscr{M}}$ composed of $m$ matchings. Then $$\begin{aligned} \nu(\Omega(\mu, {\mathscr{M}})) \geq \frac{\nu_{S_E}(\mu)}{m}f\Bigl(\frac{\gamma}{s^2g^2}\Bigr)\geq \frac{\nu_{S_E}(\mu)\gamma}{24m(S_E-1)^2}, \label{eq:nuLB1}\end{aligned}$$ where $s=s(G)$, $g=2S_E-2$, and $$\begin{aligned} \label{eq:fx} f(x)=\begin{cases} \frac{\sqrt{1+x}-1}{\sqrt{1+x}} &m=2,\\[1ex] \frac{\sqrt{1+x}-1}{\sqrt{1+x}+1} &m\geq 3. \end{cases}\end{aligned}$$ If $\mu_{\mathrm{sym}}$ forms a spherical $t$-design with $t=2S_E$, then $$\begin{aligned} \nu(\Omega(\mu, {\mathscr{M}}))&\geq \frac{2}{m(2S_E+1)}f\Bigl(\frac{\gamma}{s^2g^2}\Bigr)\nonumber\\ &\geq \frac{\gamma}{12m(2S_E+1)(S_E-1)^2}. \label{eq:nuLB2}\end{aligned}$$ <span>Theorem \[thm:AKLTnu1\]</span> follows from Theorem 1 in the companion paper @ZhuLC22 as well as <span>Lemma \[lem:nuSmu\]</span> and <span>Theorem \[thm:OmegaSdesign\]</span> in <span>Sec. \[sec:BondVerify\]</span>. In conjunction with <span>Eq. </span>, it is now straightforward to derive the following upper bound on the the minimum number of tests required to verify the AKLT state $|\Psi_G\>$ within infidelity $\epsilon$ and significance level $\delta$: $$\begin{aligned} N&\leq \biggl\lceil \frac{m(2S_E+1)\ln(\delta^{-1})}{2\epsilon f\bigl(\frac{\gamma}{s^2g^2}\bigr)}\biggr\rceil\nonumber\\ &\leq \biggl\lceil\frac{12m(2S_E+1)(S_E-1)^2\ln(\delta^{-1})}{\gamma\epsilon}\biggr\rceil. \label{eq:NUB}\end{aligned}$$ When $x\ll 1$, $f(x)$ can be approximated by $x/2$ for $m=2$ and $x/4$ for $m\geq 3$. If $\gamma/(s^2g^2)\ll1$, then <span>Eq. </span> implies that $$\begin{aligned} \nu(\Omega(\mu, {\mathscr{M}})) \gtrsim\begin{cases} \frac{\gamma\nu_{S_E}(\mu)}{2m s^2g^2} &m=2,\\[1ex] \frac{\gamma\nu_{S_E}(\mu)}{4m s^2g^2} &m\geq 3. \end{cases} \end{aligned}$$ This equation is instructive to understanding the efficiency of the matching protocol. <span>Equations and </span> can be simplified in a similar way. Recall that the minimum number of matchings required to cover the edge set of $G$ is equal to the chromatic index $\chi'(G)$. If $m=\chi'(G)$, then <span>Eq. </span> reduces to $$\begin{aligned} &\nu(\Omega(\mu, {\mathscr{M}}))\geq \frac{\nu_{S_E}(\mu)}{\chi'(G)}f\Bigl(\frac{\gamma}{s^2g^2}\Bigr)\geq \frac{\nu_{S_E}(\mu)\gamma}{24\chi'(G)(S_E-1)^2}\nonumber\\ &\quad \geq \frac{\nu_{S_E}(\mu)\gamma}{24[\Delta(G)+1][\Delta(G)-1]^2}\geq \frac{\nu_{S_E}(\mu)\gamma}{24\Delta(G)^3}, \label{eq:nuLB3}\end{aligned}$$ where the third inequality follows from the facts that $\chi'(G)\leq \Delta(G)+1$ and $S_E\leq \Delta(G)$. Although it is not always easy to find an optimal matching cover, a nearly optimal matching cover composed of $\chi'(G)+1$ matchings can be found efficiently. If in addition $\mu$ forms a spherical $t$-design with $t=2S_E$, then <span>Eq. </span> implies that $$\begin{aligned} &\nu(\Omega(\mu,{\mathscr{M}})) \geq \frac{2}{\chi'(G)(2S_E+1)}f\Bigl(\frac{\gamma}{s^2g^2}\Bigr)\nonumber\\ &\geq \frac{\gamma}{12\chi'(G)(2S_E+1)(S_E-1)^2}\geq\frac{\gamma}{24\Delta(G)^4}, \label{eq:nuLB4}\end{aligned}$$ Accordingly, <span>Eq. </span> reduces to $$\begin{aligned} N\leq \biggl\lceil \frac{\chi'(G)(2S_E+1)\ln(\delta^{-1})}{2\epsilon f\bigl(\frac{\gamma}{s^2g^2}\bigr)}\biggr\rceil\leq \biggl\lceil \frac{24\Delta(G)^4\ln(\delta^{-1})}{\gamma\epsilon} \biggr\rceil. \label{eq:NUB2}\end{aligned}$$ For most AKLT states of practical interest, including those defined on various lattices as illustrated in <span>Fig. \[fig:LatticeColoring\]</span> (see also Fig. 1 in the companion paper @ZhuLC22), $\Delta(G)$ does not increase with the system size. So these AKLT states can be verified with constant sample cost that is independent of the system size as long as the spectral gap $\gamma$ has a nontrivial system-independent lower bound. Our verification protocols are much more efficient than protocols known in the literature @CramPFS10 [@HangKSE17; @TakeM18; @CruzBTS22] and the sample costs have much better scaling behaviors with respect to the system size, spectral gap of the underlying Hamiltonian, and the precision as quantified by the infidelity. The next theorem follows from Theorems 2, 3 in the companion paper @ZhuLC22 and <span>Lemma \[lem:nuSmu\]</span> in <span>Sec. \[sec:BondVerify\]</span>. \[thm:AKLTnu2\] Suppose ${\mathscr{M}}$ in <span>Theorem \[thm:AKLTnu1\]</span> is an edge coloring of $G$ and let $p=(|M_1|, |M_2|, \ldots, |M_m|)/|E|$; then $$\begin{aligned} \nu(\Omega(\mu, {\mathscr{M}},p))\geq \frac{\nu_{S_E}(\mu)\gamma}{|E|} \geq \frac{2\nu_{S_E}(\mu)\gamma}{n(n-1)} . \label{eq:SpectralGapColor} \end{aligned}$$ If $\mu_{\mathrm{sym}}$ forms a spherical $t$-design with $t=2S_E$, then $$\begin{aligned} \nu(\Omega(\mu, {\mathscr{M}},p))\geq \frac{2\gamma}{(2S_E+1)|E|} \geq \frac{4\gamma}{(2S_E+1)n(n-1)}. \label{eq:SpectralGapColor2}\end{aligned}$$ The first inequality in <span>Eq. </span> is saturated if $S_e$ is independent of $e\in E$ and ${\mathscr{M}}$ is the trivial edge coloring with $|{\mathscr{M}}|=|E|$. By virtue of <span>Eqs. and </span>, we can derive another upper bound on the minimum number of tests required to verify the AKLT state $|\Psi_G\>$ within infidelity $\epsilon$ and significance level $\delta$: $$\begin{aligned} N\leq \biggl\lceil \frac{(2S_E+1)|E|\ln(\delta^{-1})}{2\gamma\epsilon}\biggr\rceil. \end{aligned}$$ When $G$ is a connected $k$-regular graph with $n\geq 2$ vertices, we have $|E|=nk/2$ and $S_e=S_E=\Delta(G)=k$ for all $e\in E$, so <span>Eq. </span> reduces to $$\begin{aligned} \nu(\Omega(\mu, {\mathscr{M}},p))\geq \frac{2\nu_k(\mu)\gamma}{nk}. \end{aligned}$$ If in addition $\mu_{\mathrm{sym}}$ forms a spherical $t$-design with $t=2S_E=2k$, then we have $\nu_k(\mu)=2/(2k+1)$, so the above equation (cf. <span>Eq. </span>) reduces to $$\begin{aligned} \nu(\Omega(\mu, {\mathscr{M}},p))\geq \frac{4\gamma}{nk(2k+1)}.\end{aligned}$$ This inequality is saturated if ${\mathscr{M}}$ corresponds to the trivial edge coloring and $p$ is uniform. In conjunction with <span>Eq. </span>, it is straightforward to derive the number of tests required to achieve a given precision. \[sec:1DAKLT\]Verification of 1D AKLT states ============================================ In this section we discuss in more detail the verification of 1D AKLT states, that is, AKLT states defined on the closed chain (cycle) and open chain. ![Trivial edge colorings of closed chains with five and six vertices.<span data-label="fig:Closed56color"></span>](fig4.pdf){width="45.00000%"} Verification of the AKLT state on the closed chain -------------------------------------------------- ### Simplest verification protocols Let $G(V,E)$ be the closed chain with $n$ vertices. Given a bond verification protocol specified by a probability distribution $\mu$ on the unit sphere, then a verification protocol of the AKLT state $|\Psi_G\>$ is specified by a weighted matching cover of $G$. The simplest matching cover, denoted by ${\mathscr{M}}_{\mathrm{T}}$, corresponds to the trivial edge coloring and consists of $n$ matchings, each of which consists of only one edge as illustrated in <span>Fig. \[fig:Closed56color\]</span>. Accordingly, each test operator is associated with one edge. Denote by $T_j$ the test operator associated with the edge $\{j,j+1\}$ (here $n+1$ is identified with 1 under the periodic boundary condition). Note that test operators $T_j$ for $j=1,2,\ldots, n$ are related to each other by cyclic permutations, so they should be performed with the same probability to maximize the spectral gap. The resulting verification operator reads $$\begin{aligned} \label{eq:VOAKLT1} \Omega(\mu,{\mathscr{M}}_{\mathrm{T}})=\frac{1}{n}\sum_{j=1}^{n} T_j(\mu).\end{aligned}$$ <span>Figure \[fig:cycleSimple\]</span> shows the spectral gap of $\Omega(\mu,{\mathscr{M}}_{\mathrm{T}})$ with $\mu$ constructed from the five platonic solids; in addition, the figure shows the number of tests required to verify the AKLT state within infidelity $\epsilon=0.01$ and significance level $\delta=0.01$. ![\[fig:cycleSimple\] Spectral gap $\nu(\Omega(\mu,{\mathscr{M}}_{\mathrm{T}}))$ and number $N$ of tests required to verify the AKLT state on the closed chain of $n$ nodes with precision $\delta=\epsilon=0.01$. Each protocol is based on the trivial edge coloring, and the underlying bond verification protocol is constructed from a platonic solid or the isotropic distribution on the unit sphere as discussed in <span>Sec. \[sec:BondVC\]</span> and indicated in the legend. The black dots represent the asymptotic approximation presented in <span>Eq. </span>. ](fig5.pdf){width="42.00000%"} According to <span>Theorem \[thm:AKLTnu2\]</span>, the spectral gap of $\Omega(\mu,{\mathscr{M}}_{\mathrm{T}})$ satisfies $$\begin{aligned} \nu(\Omega(\mu,{\mathscr{M}}_{\mathrm{T}}))&\geq \frac{\nu_2(\mu)\gamma(H^{\circ}(n))}{n}; \label{eq:nuLB}\end{aligned}$$ here $\nu_2(\mu)$ denotes the spectral gap (from the maximum eigenvalue 1) of the bond verification operator, while $\gamma(H^{\circ}(n))$ denotes the spectral gap of the Hamiltonian (from the minimum eigenvalue corresponding to the ground state). By virtue of <span>Theorem \[thm:gapGM\]</span> and <span>Eq. </span> we can further deduce that $$\label{eq:nuLBck} \nu\left(\Omega(\mu,{\mathscr{M}}_{\mathrm{T}})\right)\geq \frac{c_k \nu_2(\mu)}{n},\quad n>2k,$$ where $c_k$ is defined in <span>Eq. </span>. So the number of tests required to verify the AKLT state $|\Psi_G\>$ within infidelity $\epsilon$ and significance level $\delta$ satisfies $$\begin{aligned} N&\leq \left\lceil\frac{ \ln (\delta^{-1})}{\nu(\Omega(\mu,{\mathscr{M}}_{\mathrm{T}}))\epsilon}\right \rceil\leq \left\lceil\frac{n \ln (\delta^{-1})}{\nu_2(\mu)\gamma(H^{\circ}(n))\epsilon}\right \rceil \nonumber\\ &\leq\left\lceil\frac{ n\ln (\delta^{-1})}{c_k\,\nu_2(\mu)\,\epsilon}\right \rceil, \quad n>2k,\label{eq:NUBck}\end{aligned}$$ which is linear in the number of spins. The inequality in <span>Eq. </span> is saturated when $\mu$ forms a spherical 4-design (icosahedron and dodecahedron protocols for example), in which case we have $\nu_2(\mu)=2/5$ and $$\begin{aligned} \nu(\Omega(\mu,{\mathscr{M}}_{\mathrm{T}}))&=\frac{2\gamma(H^{\circ}(n))}{5n}, \label{eq:nutri1D4design}\\ N &\approx \left\lceil\frac{5n \ln (\delta^{-1})}{2\gamma(H^{\circ}(n))\epsilon}\right \rceil \leq\left\lceil\frac{ 5n\ln (\delta^{-1})}{2c_k\,\epsilon}\right \rceil, \end{aligned}$$ where the inequality holds whenever $n>2k$. Although <span>Eq. </span> is derived under the 4-design assumption, calculation shows that it holds with high precision (with deviation less than 5% for $n\leq 10$) for all protocols based on platonic solids, as illustrated in <span>Fig. \[fig:cycleSimple\]</span>. When $n=3$ for example, we have $\gamma(H^{\circ}(n))=5/6$ and $\nu(\Omega(\mu,{\mathscr{M}}_{\mathrm{T}}))=1/9$ for all protocols based on platonic solids. This observation indicates that the general lower bound in <span>Eq. </span> is usually not tight when $\mu$ does not form a 4-design. In other words, protocols based on tetrahedron, octahedron, and cube are more efficient than expected; the reason is still not very clear now. In the large-$n$ limit, the spectral gap $\gamma(H^{\circ}(n))$ is approximately equal to $0.350$ @GarcMW13 [@WeiRA22]. If in addition $\mu$ forms a spherical 4-design, then we have $$\begin{aligned} \label{eq:AsympApprox} \nu(\Omega(\mu,{\mathscr{M}}_{\mathrm{T}}))&\approx \frac{0.140}{n},\quad N\approx\frac{7.14\, n\ln (\delta^{-1})}{\epsilon}. \end{aligned}$$ Numerical calculation shows that all protocols based on platonic solids can achieve a similar performance as illustrated in <span>Fig. \[fig:cycleSimple\]</span>. ### Optimal matching protocols ![\[fig:ntests\]Verification of the AKLT state on the closed chain of nine nodes based on the matching covers ${\mathscr{M}}_m=\{M_j\}_{j=1}^m$. Here $M_j$ is the maximum matching defined in <span>Eq. </span>, and $m$ is the number of maximum matchings and also the number of distinct tests employed. Infidelity and significance level are chosen to be $\delta=\epsilon=0.01$ as in <span>Fig. \[fig:cycleSimple\]</span>; the choice of bond verification protocols is also the same. ](fig6.pdf){width="42.00000%"} $n$ 3 4 5 6 7 8 9 10 -------------- ----------- ----------- ----------- ----------- ----------- ------------ ------------ ------------ closed chain (1, 3, 3) (2, 2, 2) (2, 5, 5) (3, 5, 2) (3, 7, 7) (4, 10, 2) (4, 12, 9) (5, 17, 2) open chain (1, 2, 2) (2, 2, 1) (2, 3, 3) (3, 4, 1) (3, 5, 4) (4, 7, 1) (4, 9, 5) (5, 12, 1) More efficient verification protocols can be constructed from better matching covers. For the cycle graph $G$ with $n$ vertices, the chromatic index is given by $$\begin{aligned} \chi'(G)=\begin{cases} 2 & \mbox{if $n$ is even},\\ 3 & \mbox{if $n$ is odd}. \end{cases}\end{aligned}$$ When $n$ is even, there exist two maximum matchings, namely, $$\begin{aligned} M_1&=\{\{1,2\}, \{3,4\},\ldots, \{n-1,n\}\}, \\ M_2&=\{\{2,3\},\{4,5\},\ldots, \{n,1\}\}, \end{aligned}$$ which form the matching cover ${\mathscr{M}}=\{M_1, M_2\}$ and also defines an edge coloring of $G$. Given a probability distribution $\mu$ on the unit sphere, then we can construct
{'source': 'arXiv_out/2206'}