Passive verification protocol for thermal graph states

Quantum computation is expected to outperform classical counterparts M16 . Driven by this expectation, several models for achieving it have been proposed such as the quantum circuit model NC00 , adiabatic quantum computation FGGS00 , measurement-based quantum computation (MBQC) RB01 , and topological quantum computation K03 . MBQC is one of promising universal quantum computing models due to its wide application range, from secure cloud quantum computing BFK09 ; MF13 to quantum error correction RHG06 . In this model, the quantum computation proceeds via adaptive single-qubit measurements on an entangled resource state (e.g., graph states (see Sec. II for its definition)). Here, “adaptive” means that each measurement basis can depend on all previous measurement outcomes.

So far, several physical systems have been proposed as candidates for realizing MBQC such as trapped ions LJZHMDBBR13 and superconducting qubits ABSRLRS18 . However, at least with current technology, it is hard to generate a large-scale graph state by using them. An obstacle to its generation is the necessity of cooling. To maintain their quantum properties, such as superposition and entanglement, they must be cooled below a few tens of millikelvins. If the cooling is not sufficient, the graph state is affected by thermal noise and consequently becomes a thermal graph state (see Sec. II for the definition). Several effects of thermal noise on graph states are explored in Ref. JDBBR09 . In particular, a critical temperature at which the graph state becomes a quantum state with only classical correlations is discussed in Ref. HV10 .

As the size of MBQC increases, it becomes more important to efficiently check whether a target graph state $|G\rangle$ is precisely prepared, namely to efficiently estimate the fidelity between $|G\rangle$ and an actually prepared state $\rho\equiv\mathcal{E}(|G\rangle\langle G|)$ that suffers from any noise $\mathcal{E}$. This task is called the verification of graph states. Although the fidelity can be estimated by using quantum state tomography SBRF93 ; H97 ; BDPS99 or direct fidelity estimation FL11 , these protocols require an exponential number of copies of $\rho$. Therefore, several efficient verification protocols tailored for graph states have been proposed HM15 ; MNS16 ; FH17 ; TM18 ; TMMMF19 ; ZH19 ; ZH19A ; MK20 . In brief, these protocols can be formalized as follows: first, a quantum computer generates some copies of $\rho$ and sends each qubit one by one to a verifier. Then the verifier randomly chooses a measurement basis and measures the received state $\rho$ in the basis. He/she repeats the same procedure for all copies of $\rho$. Finally, by processing all measurement outcomes with a classical computer, he/she outputs an estimated value of (or a lower bound on) the fidelity. Note that in most cases, only (non-adaptive) single-qubit measurements and efficient classical operations are allowed for the verifier because multi-qubit operations are technologically demanding. In this paper, we also consider the same restriction on the verifier to simplify the requirement for the verifier as much as possible.

The above existing protocols are active, that is the verifier must switch between some kinds of measurement settings. In many practical scenarios, the switching of measurement settings could be slow, and in some cases, it may be impossible (e.g., see Ref. LZLZ21 ). For example, it would be somewhat demanding to change measurement bases in the IBM quantum cloud service. It is theoretically and experimentally important to clarify how many measurement settings are required for the verification of graph states.

If any $n$-qubit unitary operator $U$ is allowed for the verifier, the necessary number of measurement settings can be trivially reduced to $1$. This is because by using the unitary operator $U^{\dagger}$ such that $U|0^{n}\rangle=|G\rangle$, the verifier can perform the measurement $\{|G\rangle\langle G|,I^{\otimes n}-|G\rangle\langle G|\}$, where $I$ is the two-dimensional identity operator. However, as we have mentioned above, we would prefer not to allow the verifier to perform such multi-qubit operations. Furthermore, if the verifier can perform such $U$, then he/she can generate the ideal graph state $|G\rangle$ by his/herself, that is he/she can completely remove the thermal noise, which is unrealistic. Therefore, we should consider the necessary number of measurement settings under the assumption that the verifier can perform only non-adaptive single-qubit projective measurements. Unfortunately, under this assumption, at least two measurement settings are required for the verification of any bipartite pure entangled state that includes a subclass of graph states LZLZ21 . Even if adaptive single-qubit projective measurements are allowed for the verifier, at least two measurement settings are still necessary ZH19A .

In this paper, we circumvent the no-go result by assuming that the noise $\mathcal{E}$ is thermal noise. More precisely, we propose a passive verification protocol for thermal graph states that requires only one measurement setting. Since the thermal noise is a major obstacle hindering the generation of large-scale graph states with matter qubits, our protocol is still sufficiently practical under this assumption. Since the thermal noise can be rephrased as an independent phase-flip error, our protocol also works for MBQC with photonic graph states. Photons are another promising candidate for qubits, and several experiments have been performed to generate photonic graph states WRRSWVAZ05 ; LZGGZYGYP07 and photonic thermal graph states AKCACWR14 . Furthermore, by generalizing our protocol to thermal hypergraph states that are generalizations of thermal graph states (see Sec. II for the definition), we apply our protocol to the demonstration of quantum computational supremacy with instantaneous quantum polynomial time (IQP) circuits BMS16 . The demonstration of quantum computational supremacy is to generate a probability distribution that cannot be efficiently generated with classical computers (under plausible complexity-theoretic assumptions) HM17 . Although its proof-of-principle experiments have already been performed by using random unitary circuits with superconducting qubits google ; ZC5D2FG4H4L7Q2RS2W4XY7Z8LPZP21 and a boson sampler with squeezed states ZWDCPLQWDHHYZLLJGYYWLLLP20 , an experiment with IQP circuits has not yet been performed. Our protocol should facilitate the realization of large-scale IQP circuits.

The rest of this paper is organized as follows: in Sec. II, we review graph and hypergraph states and their thermal analogues. In Sec. III, as a main result, we present our passive verification protocol for thermal graph states and show that it is optimal in a sense. In Sec. IV, we compare our protocol with existing protocols. In Sec. V, we generalize our protocol to thermal hypergraph states and apply it to the demonstration of quantum computational supremacy with IQP circuits. Section VI concludes the paper with a brief discussion. In Appendices A and B, we provide a proof of Theorem 1.

In this section, we formally define thermal graph and hypergraph states. To this end, we first review graph BR01 and hypergraph states RHBM13 . A graph $G\equiv(V,E)$ is a pair of the set $V$ of $n$ vertices and the set $E$ of edges. An $n$-qubit graph state $|G\rangle$ corresponding to the graph $G$ is defined as

$\displaystyle|G\rangle\equiv\left(\prod_{(i,j)\in E}CZ_{i,j}\right)|+\rangle^{\otimes n},$

(1)

where $|+\rangle\equiv(|0\rangle+|1\rangle)/\sqrt{2}$, and $CZ_{i,j}$ is the controlled-$Z$ ($CZ$) gate applied on the $i$th and $j$th qubits. It is known that Eq. (1) is a unique common eigenstate with eigenvalue $+1$ of stabilizer operators $\{g_{i}\}_{i=1}^{n}$, where

$\displaystyle g_{i}\equiv X_{i}\left(\prod_{j:\ (i,j)\in E}Z_{j}\right)$

(2)

for all $1\leq i\leq n$. Here, $X_{i}$ and $Z_{j}$ are the Pauli-$X$ and $Z$ operators acting on the $i$th and $j$th qubits, respectively, and the product is taken over all vertices $j$ such that $(i,j)\in E$.

Hypergraph states are defined by generalizing graphs to hypergraphs. A hypergraph $\tilde{G}\equiv(V,\tilde{E})$ is a pair of the set $V$ of $n$ vertices and the set $\tilde{E}$ of hyperedges that can connect more than two vertices, while edges can connect only two vertices. Let $\tilde{E}$ be the union of $\tilde{E}_{2}$ and $\tilde{E}_{3}$, which are sets of hyperedges connecting two and three vertices, respectively FN1 . An $n$-qubit hypergraph state $|\tilde{G}\rangle$ corresponding to the hypergraph $\tilde{G}$ is defined as

$\displaystyle|\tilde{G}\rangle\equiv\left(\prod_{(i,j,k)\in\tilde{E}_{3}}CCZ_{i,j,k}\right)\left(\prod_{(i,j)\in\tilde{E}_{2}}CZ_{i,j}\right)|+\rangle^{\otimes n},$

(3)

where $CCZ_{i,j,k}$ is the controlled-controlled-$Z$ ($CCZ$) gate applied on the $i$th, $j$th, and $k$th qubits. From Eq. (3), we notice that graph states are special cases of hypergraph states. When the set $\tilde{E}_{3}$ is empty, the hypergraph state $|\tilde{G}\rangle$ becomes a graph state. For the hypergraph state $|\tilde{G}\rangle$, we can define generalized stabilizer operators $\{\tilde{g}_{i}\}_{i=1}^{n}$ as follows:

$\displaystyle\tilde{g}_{i}\equiv X_{i}\left(\prod_{j:\ (i,j)\in\tilde{E}_{2}}Z_{j}\right)\left(\prod_{(j,k):\ (i,j,k)\in\tilde{E}_{3}}CZ_{j,k}\right).$

(4)

The equality $\tilde{g}_{i}|\tilde{G}\rangle=|\tilde{G}\rangle$ holds for any $1\leq i\leq n$, and no other state can satisfy it for all $i$.

Let $\beta\equiv 1/(k_{B}T)$ with the Boltzmann constant $k_{B}$ and temperature $T$. For a Hamiltonian $\mathcal{H}$,

$\displaystyle\rho_{T}\equiv\cfrac{e^{-\beta\mathcal{H}}}{\mathcal{Z}},$

(5)

where $\mathcal{Z}\equiv{\rm Tr}[e^{-\beta\mathcal{H}}]$ is the partition function, is called the thermal state at temperature $T$. When

$\displaystyle\mathcal{H}=-\sum_{i=1}^{n}g_{i}$

(6)

and $T\neq 0$, we call $\rho_{T}$ the thermal graph state, which is a graph state at non-zero temperature. This is because when the temperature is zero, $\rho_{0}=|G\rangle\langle G|$. An experiment has been performed toward the ground-state cooling for the Hamiltonians that are sums of stabilizer operators BMSNMCHRZB11 . In a similar way, we call $\rho_{T}$ the thermal hypergraph state when

$\displaystyle\mathcal{H}=-\sum_{i=1}^{n}\tilde{g}_{i}$

(7)

and $T\neq 0$. In this case, $\rho_{T}$ becomes $|\tilde{G}\rangle\langle\tilde{G}|$ when $T=0$.

These thermal states can also be represented as graph and hypergraph states with an independent phase-flip error (i.e., a Pauli-$Z$ error). Note that in general, the replacement of the thermal noise with a Pauli-$Z$ error is not possible. By restring ideal quantum states to graph and hypergraph states, we make the replacement possible. Let $\mathcal{E}_{i}^{(p)}(\cdot)\equiv(1-p)(\cdot)+pZ_{i}(\cdot)Z_{i}$ be the superoperator realizing the $Z$ error on the $i$th qubit with error probability $p$. From Ref. F15 , when $\mathcal{H}=-\sum_{i=1}^{n}g_{i}$,

$\displaystyle\rho_{T}=\left(\prod_{i=1}^{n}\mathcal{E}_{i}^{(p_{\beta})}\right)\left(|G\rangle\langle G|\right),$

(8)

where $p_{\beta}\equiv e^{-2\beta}/(1+e^{-2\beta})$. For the thermal hypergraph states, the same expression holds by replacing $|G\rangle\langle G|$ with $|\tilde{G}\rangle\langle\tilde{G}|$ in Eq. (8). These expressions are useful in evaluating our passive verification protocols.

In this section, we propose our passive verification protocol for thermal graph states. Note that since we assume that the thermal graph states are generated due to thermal noise, the temperature $T$ (i.e., the value of $\beta$) is unknown for the verifier. As a remarkable property, no switching between measurement bases is required for the verifier in our protocol, while previous verification protocols require it, namely they are active. For simplicity, we assume that the size $n$ of graph states is $2k$ for a natural number $k$. Let $S_{\bf\ell}\equiv\prod_{i=1}^{n}g_{i}^{\ell_{i}}$ with ${\bf\ell}\equiv\ell_{1}\ell_{2}\ldots\ell_{n}\in\{0,1\}^{n}$. Our protocol runs as follows (see also Fig. 1):

1. 1.

   A quantum computer generates $N$ thermal graph states $\rho_{T}^{\otimes N}$ and sends them to the veirifier.

2. 2.

   The verifier measures $S_{1^{k}0^{k}}$ on each received state $\rho_{T}$. Let $o_{i}\in\{+1,-1\}$ be the $i$th outcome for $1\leq i\leq N$.

3. 3.

   The verifier outputs

   $\displaystyle F_{\rm est}\equiv\cfrac{\sum_{i=1}^{N}o_{i}}{N}$

   (9)

   as an estimated value of the fidelity.

The measurement of $S_{1^{k}0^{k}}$ in step 2 can be realized by single-qubit Pauli measurements because $S_{1^{k}0^{k}}$ is a tensor product of Pauli operators. Furthermore, by sequentially sending qubits one by one in step 1, no quantum memory is required for the verifier. To clarify these properties, we give concrete examples of our protocol in Fig. 2.

For our protocol, the following theorem holds:

The proof is given in Appendix A. Theorem 1 implies that the more the number $n$ of qubits increases, the more the precision of our protocol improves. In other words, our protocol is efficient for any temperature $T$. Although Theorem 1 is shown for only even $n$, our protocol can be applied when $n$ is odd by simply replacing the ideal state $|G\rangle$ with another graph state $|G\rangle|+\rangle$. By adding $|+\rangle$, we can always make the number of vertices even.

In step 2, we choose $S_{1^{k}0^{k}}$ among $2^{n}$ kinds of $S_{\bf\ell}$. This choice is optimal in the sense that it maximally improves the dependence on $T$ of the upper bound in Eq. (10). More formally, we show the following theorem:

(Proof) In the large limit of $N$, the values $\epsilon$ and $\delta$ become zero, i.e., the estimated value $F_{\rm est}$ becomes ${\rm Tr}[\rho_{T}S_{\bf\ell}]$. Therefore, from Eqs. (26) and (27) in Appendix A, we immediately obtain Eq. (12). $\blacksquare$

Since Eq. (12) is asymptotically minimized when the term of $e^{-2\beta}$ vanishes, Theorem 2 implies that our protocol is optimized when ${\rm wt}({\bf\ell})=n/2=k$. Thus $S_{1^{k}0^{k}}$ is one of optimal choices.

There exist several verification protocols for graph states. For example, the protocol in Ref. MNS16 works for any type of error even if it is a time-correlated one. However, it requires all of $S_{\bf\ell}$, that is it needs $2^{n}$ kinds of measurement settings FN2 . Although the necessary number of measurement settings can be improved to $n$ by using the union bound as shown in Ref. TM18 , the obtained lower bound $F_{\rm ub}$ on the fidelity becomes loose. When the protocol is applied to the case of thermal noise with unknown temperature $T$, the lower bound is

	$\displaystyle F_{\rm ub}$	$\displaystyle=$	$\displaystyle 1-\sum_{i=1}^{n}\left(1-{\rm Tr}\left[\rho_{T}\left(\cfrac{I^{\otimes n}+g_{i}}{2}\right)\right]\right)$		(13)
		$\displaystyle=$	$\displaystyle 1-np_{\beta}$		(14)

in the limit of large $N$, where we have used Eq. (27) to derive the second equality. Therefore, by increasing $n$, the lower bound $F_{\rm ub}$ becomes loose. In contrast, in the limit of large $N$, our lower bound $F_{\rm est}$ becomes tight by increasing $n$ [see Eq. (11)]. Fig. 3 gives a comparison between $F_{\rm est}$ and $F_{\rm ub}$ in the limit of large $N$. It shows that our estimated value $F_{\rm est}$ is close to the actual value $F\equiv\langle G|\rho_{T}|G\rangle$ even when the number $n$ of qubits and $k_{B}T$ (i.e., $p_{\beta}$) are large. On the other hand, $F_{\rm ub}$ becomes distinct from $F$ when $k_{B}T$ is large (i.e., $p_{\beta}$ is large).

The number of required measurement settings was further improved by restricting the target states. In particular, only two measurement settings are sufficient when the target state is any bipartite graph state HM15 . Recently, Li et al. generalized this result to any bipartite pure entangled state and showed that two settings cannot be improved to one LZLZ21 . They also showed that any bipartite pure product state can be verified with a single measurement setting if local projective measurements are allowed for the verifier LZLZ21 . Our result implies that a single measurement setting is sufficient even for graph states if the type of noise is restricted. By assuming thermal noise (i.e., the independent $Z$ error), we circumvent the no-go result in Ref. LZLZ21 .

In this section, we generalize our protocol to a restricted class of $n$-qubit thermal hypergraph states that become, at the temperature $T=0$, the hypergraph states in Eq. (3) such that $\tilde{E}_{3}$ is the union of $\{(4j-3,4j-2,4j-1)\}_{j=1}^{\lceil(n+1)/4\rceil}$, $\{(4j-3,4j-1,4j)\}_{j=1}^{\lceil n/4\rceil}$, $\{(4j-1,4j,4j+1)\}_{j=1}^{\lceil(n-1)/4\rceil}$, and $\{(4j-1,4j+1,4j+2)\}_{j=1}^{\lceil(n-2)/4\rceil}$. Note that $\tilde{E}_{2}$ is arbitrary, and we assume that $n$ is even. For clarity, we depict such a hypergraph state with $n=10$ and $\tilde{E}_{2}=\emptyset$ in Fig. 4.

Let $\tilde{S}_{\bf\ell}\equiv\prod_{i=1}^{n}\tilde{g}_{i}^{\ell_{i}}$ with ${\bf\ell}=\ell_{1}\ell_{2}\ldots\ell_{n}\in\{0,1\}^{n}$. In the case of hypergraph states mentioned above, by setting ${\bf\ell}=0101\ldots 01=(01)^{n/2}$, we can obtain

$\displaystyle\tilde{S}_{(01)^{n/2}}=\prod_{(i,j)\in\tilde{E}_{2}}CZ_{i,j}\left(\prod_{k=1}^{n/2}X_{2k}\right)CZ_{i,j}.$

(15)

When $i=2k$ $(j=2k)$, the equality $CZ_{i,j}X_{2k}CZ_{i,j}=X_{i}Z_{j}$ $(Z_{i}X_{j})$ holds. Otherwise, $CZ_{i,j}X_{2k}CZ_{i,j}=X_{2k}$. Therefore, $\tilde{S}_{(01)^{n/2}}$ is a tensor product of $n$ Pauli operators (up to $\pm 1$), and just half of them are the Pauli-$X$ or $Y$. As a result, from the argument in Appendix A, by replacing $S_{1^{k}0^{k}}$ with $\tilde{S}_{(01)^{n/2}}$ in step 2 of our protocol, we can also show that Theorem 1 holds for the thermal hypergraph states.

Hypergraph states in the above class have only two qubits in the column direction while they can have any number of qubits in the row direction (see Fig. 4). The above argument can also be applied even if we increase the number of qubits in the column direction to more than two. As an example, let us consider the $20$-qubit hypergraph state in Fig. 5. Since $\tilde{S}_{(01)^{10}}=\prod_{i=1}^{10}X_{2i}$, we can show that Theorem 1 holds for this hypergraph state. Therefore, our verification protocol is applicable to hypergraph states from which we can obtain the Union Jack states MM16 , which are universal resource states for MBQC, under postselection.

Our verification protocol can be applied to the demonstration of quantum computational supremacy with IQP circuits BMS16 under conjectures. An $n$-qubit IQP circuit is a quantum circuit such that the initial state and measurements are $|+\rangle^{\otimes n}$ and $X$-basis measurements, respectively, and the applied quantum gate $D$ is any diagonal unitary in the $Z$ basis SB09 . For IQP circuits with $D$ consisting of $Z$, $CZ$, and $CCZ$ gates, Bremner, Montanaro, and Shepherd showed that it is hard to efficiently simulate classically any probability distribution $\{q_{z}\}_{z\in\{0,1\}^{n}}$ obtained from IQP circuits BMS16 . More precisely, it is hard to generate $\{p_{z}\}_{z\in\{0,1\}^{n}}$ in classical polynomial time such that $\sum_{z\in\{0,1\}^{n}}|q_{z}-p_{z}|\leq 1/192$. Therefore, the generation of a probability distribution $\{q^{\prime}_{z}\}_{z\in\{0,1\}^{n}}$ such that $\sum_{z\in\{0,1\}^{n}}|q_{z}-q^{\prime}_{z}|\leq 1/192$ is called the demonstration of quantum computational supremacy. Since IQP circuits just measure hypergraph states in the $X$ basis when $D$ consists of $Z$, $CZ$, and $CCZ$ gates, their result shows that if appropriate hypergraph states can be prepared with sufficiently high fidelity, then quantum computational supremacy is successfully demonstrated.

Their hardness proof is based on the anticoncentration lemma and two plausible complexity-theoretic conjectures (i.e., the average-case ${\sf\#P}$-hardness of the approximation of output probabilities $q_{0^{n}}$ for random $D$’s and infiniteness of the polynomial hierarchy). The lemma implies that for any $z$, when $D$ is randomly chosen, the probability of $q_{z}$ being larger than a certain value is at least a constant. It holds even if qubits on which $CCZ$ gates are applied are fixed as long as qubits on which $Z$ and $CZ$ gates are applied are randomly chosen. In other words, hypergraph states with a fixed $\tilde{E}_{3}$ are sufficient to show the anticoncetration lemma. This is why our hypergraph states mentioned above can be used to demonstrate quantum computational supremacy under the assumption that the two conjectures hold for our class of hypergraph states with the fixed $\tilde{E}_{3}$. A similar assumption was used in Ref. MTH17 .

Although several certification protocols to check whether the demonstration of quantum computational supremacy is correctly achieved have been proposed for IQP circuits HKSE17 ; MTH17 ; TM18 ; KD19 , they are active; that is, some switching between quantum operations is required for a certifier. In contrast, we propose a passive certification protocol under the assumption that the noise is thermal noise or an independent phase-flip error. For simplicity, we set $n\geq 4\times 10^{5}$, $\epsilon=10^{-6}$, and $\delta=10^{-2}$ in Theorem 1. Our certified quantum computational supremacy protocol proceeds as follows:

1. 1.

   An experimentalist runs a quantum computer to generate an $n$-qubit thermal hypergraph state $\rho_{T}$ and measures $\tilde{S}_{(01)^{n/2}}$. He/she repeats the same procedure $N(\leq 1.06\times 10^{13})$ times. Let $o_{i}\in\{+1,-1\}$ be the $i$th outcome for $1\leq i\leq N$.

2. 2.

   The experimentalist calculates

   $\displaystyle F_{\rm est}=\cfrac{\sum_{i=1}^{N}o_{i}}{N}.$

   (16)

3. 3.

   If $F_{\rm est}-2/n\geq 0.999995$, the experimentalist generates $\{q^{\prime}_{z}\}_{z\in\{0,1\}^{n}}$ by generating $\rho_{T}$’s again and then measuring them in the $X$ basis. Otherwise, he/she declares that the precision of the quantum computer is not enough to demonstrate quantum computational supremacy.

We show that when $F_{\rm est}-2/n\geq 0.999995$, the generated probability distribution $\{q^{\prime}_{z}\}_{z\in\{0,1\}^{n}}$ satisfies $\sum_{z\in\{0,1\}^{n}}|q_{z}-q^{\prime}_{z}|\leq 1/192$ with probability of $0.99$, that is the experimentalist succeeds in demonstrating quantum computation supremacy. Note that if the temperature is $0$, the inequality $F_{\rm est}-2/n\geq 0.999995$ can be satisfied with unit probability because $F_{\rm est}=1$ and $n\geq 4\times 10^{5}$. From Ref. NC00 and the Fuchs-van de Graaf inequality FG99 ,

	$\displaystyle\sum_{z\in\{0,1\}^{n}}|q_{z}-q^{\prime}_{z}|$	$\displaystyle\leq$	$\displaystyle\left|\left||\tilde{G}\rangle\langle\tilde{G}|-\rho_{T}\right|\right|$		(17)
		$\displaystyle\leq$	$\displaystyle 2\sqrt{1-\langle\tilde{G}|\rho_{T}|\tilde{G}\rangle},$		(18)

where $||\cdot||$ is the trace norm. Therefore, from Theorem 1 with $\epsilon=10^{-6}$ and $\delta=10^{-2}$, the required number $N$ of samples is at most $1.06\times 10^{13}$, and

$\displaystyle\sum_{z\in\{0,1\}^{n}}|q_{z}-q^{\prime}_{z}|\leq 2\sqrt{1+10^{-6}-\left(F_{\rm est}-\cfrac{2}{n}\right)}$

(19)

with probability at least $0.99$. To satisfy that the right-hand side of Eq. (19) is at most $1/192$, it is sufficient to satisfy

	$\displaystyle F_{\rm est}-\cfrac{2}{n}$	$\displaystyle\geq$	$\displaystyle 1+10^{-6}-\cfrac{1}{384^{2}}$		(20)
		$\displaystyle=$	$\displaystyle 0.999994\ldots$		(21)

We have proposed a passive verification protocol for thermal graph and hypergraph states. As a remarkable property, our verification protocol requires only one measurement setting. This passiveness cannot be obtained when the noise is general, even if any single-qubit projective measurements are allowed for the verifier ZH19A ; LZLZ21 . We circumvent their no-go result by assuming thermal noise (or independent phase-flip error), which is a major obstacle to the generation of large-scale entangled states. Note that for Fock-basis photonic quantum states, a passive verification protocol has already been proposed CGKM21 . Particularly, under the two conjectures, our verification protocol for thermal hypergraph states can be used to demonstrate quantum computational supremacy in a certifiable manner. As another application, our verification protocol can also be used as a quantum sensing protocol to estimate unknown temperature $T$. This is because the fidelity $\langle G|\rho_{T}|G\rangle$ is uniquely determined by $n$ and $\beta$ [see Eq. (26) and Figs. 3 (a) and (b)]. Note that in this application, the product state $|G\rangle=|+\rangle^{\otimes n}$ is sufficient as an input.

It would be interesting to consider whether our protocol can be generalized to other classes of quantum states such as weighted graph states HDERNB05 ; HCDB07 and/or other types of errors such as depolarizing noises and noises induced by the finite lifetime of matter qubits. Recently, Ref. YS22 proposed a one-shot protocol to decide whether an error rate is lower than a constant value $a$ or larger than another constant value $b$ for any bounded-degree periodic graph states with depolarizing noise. Their idea may be useful in generalizing our passive verification protocol, but we leave that as a future work.

For simplicity, we have assumed that the verifier’s measurements are perfect. However, independent phase-flip errors on the measurement apparatuses can be allowed if the error probabilities are the same for all apparatuses. Since measurement errors affect the performance of our verification protocol, it should be important to also take other measurement errors into account. Although an active error-tolerant verification protocol has already been proposed FH17 , it is still open whether it can be combined with our protocol to construct a passive error-tolerant one.

We thank Shion Yamashika for fruitful discussions about Appendix A. ST is supported by the Japan Society for the Promotion of Science Grant-in-Aid for Scientific Research (KAKENHI Grant No. 19K03691). RY is supported by JSPS Grant-in-Aid for Scientific Research (KAKENHI Grant No. 19K14616 and 20H01838). YT is supported by MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) Grant Number JPMXS0118067394 and JPMXS0120319794 and JST [Moonshot R&D – MILLENNIA Program] Grant Number JPMJMS2061.

In this appendix, we prove Theorem 1. First, we derive a value to which the estimated value $F_{\rm est}$ in Eq. (9) converges. Let $m_{+}$ and $m_{-}(=N-m_{+})$ be the numbers of $+1$ and $-1$ outcomes, respectively. From Eq. (9),

$\displaystyle F_{\rm est}=(+1)\cdot\cfrac{m_{+}}{N}+(-1)\cdot\cfrac{m_{-}}{N}.$

(22)

Therefore, it converges to ${\rm Tr}[\rho_{T}S_{1^{k}0^{k}}]$, and thus the Hoeffding inequality H63 guarantees that when $N=\lceil 2/\epsilon^{2}\log{(2/\delta)}\rceil$, the inequality

$\displaystyle\left|{\rm Tr}[\rho_{T}S_{1^{k}0^{k}}]-F_{\rm est}\right|\leq\epsilon$

(23)

holds with probability at least $1-\delta$. By using the triangle inequality and Eq. (23),

			$\displaystyle\left|\langle G|\rho_{T}|G\rangle-F_{\rm est}\right|$		(25)
		$\displaystyle\leq$	$\displaystyle\left|\langle G|\rho_{T}|G\rangle-{\rm Tr}[\rho_{T}S_{1^{k}0^{k}}]\right|+\left|{\rm Tr}[\rho_{T}S_{1^{k}0^{k}}]-F_{\rm est}\right|$
		$\displaystyle\leq$	$\displaystyle\left|\langle G|\rho_{T}|G\rangle-{\rm Tr}[\rho_{T}S_{1^{k}0^{k}}]\right|+\epsilon$

with probability at least $1-\delta$.

The remaining task is to upper bound $\left|\langle G|\rho_{T}|G\rangle-{\rm Tr}[\rho_{T}S_{1^{k}0^{k}}]\right|$. To this end, we calculate $\langle G|\rho_{T}|G\rangle$ and ${\rm Tr}[\rho_{T}S_{1^{k}0^{k}}]$ in order. By substituting Eq. (8) for $\rho_{T}$, we obtain

$\displaystyle\langle G|\rho_{T}|G\rangle=(1-p_{\beta})^{n}=1/(1+e^{-2\beta})^{n}.$

(26)

This is because if at least one $Z$ error occurs on the graph state $|G\rangle$, it becomes orthogonal to the ideal state $|G\rangle$.

To calculate ${\rm Tr}[\rho_{T}S_{1^{k}0^{k}}]$, we derive a general expression for ${\rm Tr}[\rho_{T}S_{\bf\ell}]$ with any ${\bf\ell}\in\{0,1\}^{n}$. Recall that $S_{\bf\ell}$ is a tensor product of $n$ Pauli operators, i.e., $S_{\bf\ell}=(-1)^{s}\otimes_{i=1}^{n}\sigma_{i}$ with $\sigma_{i}\in\{X,Y,Z,I\}$ and $s\in\{0,1\}$. Here, $Y$ is the Pauli-$Y$ operator. Let us call $\sigma_{i}$ the $i$th operator in $S_{\bf\ell}$. From Eq. (2), we notice that the $i$th operator in $S_{\bf\ell}$ is $X$ or $Y$ if and only if $\ell_{i}=1$. In other words, when $\ell_{i}=0$, the $i$th operator is $Z$ or $I$. The thermal noise can be considered as an independent phase-flip error as shown in Eq. (8), and the phase-flip error is detected by $X$ and $Y$ measurements. Since the $m$ phase-flip errors occur with probability $(1-p_{\beta})^{n-m}p_{\beta}^{m}$, using Eq. (8), we obtain a general expression for ${\rm Tr}[\rho_{T}S_{\bf\ell}]$ as

	$\displaystyle{\rm Tr}[\rho_{T}S_{\bf\ell}]=\sum_{m=0}^{n}C(m)(1-p_{\beta})^{n-m}p_{\beta}^{m},$		(27)
	$\displaystyle C(m)\equiv\sum_{j=w({\bf\ell},m,n)}^{f({\bf\ell},m)}(-1)^{j}\binom{{\rm wt}(\bf\ell)}{j}\binom{n-{\rm wt}(\bf\ell)}{m-j},$		(28)

where ${\rm wt}(\ell)\equiv\sum_{i=1}^{n}\ell_{i}$ is the Hamming weight, $f({\bf\ell},m)\equiv{\rm min}\{{\rm wt}({\bf\ell}),m\}$, and $w({\bf\ell},m,n)\equiv{\rm max}\{0,{\rm wt}({\bf\ell})+m-n\}$. We assumed $\binom{0}{0}=1$. $C(m)$ is the summation of the outcomes of the measurements of $S_{\bf\ell}$ for the cases of $m$ phase-flip errors. The term $\binom{{\rm wt}(\bf\ell)}{j}\binom{n-{\rm wt}(\bf\ell)}{m-j}$ is the number of patterns where $j$ phase-flip errors among $m$ phase-flip errors occur on the ${\rm wt}({\bf\ell})$ qubits such that $\ell_{i}=1$, and the other $m-j$ phase-flip errors occur on the other $(n-{\rm wt}({\bf\ell}))$ qubits such that $\ell_{i}=0$. The factor $(-1)^{j}$ corresponds to the outcome of the measurement of $S_{\bf\ell}$ that is $+1$ $(-1)$ if the number $j$ of errors among the ${\rm wt}(\bf\ell)$ qubits is even (odd). To make our argument clearer, we give the concrete derivation of Eq. (27) for the ideal state $CZ|++\rangle$ in Appendix B.

$C(0)=1$ represents that the outcome of the measurement of $S_{\bf\ell}$ is always $+1$ when no error occurs. This is because $|G\rangle$ is stabilized by any $S_{\bf\ell}$. Note that since $m=0$ does not imply $T=0$, it does not mean the ideal case. We here just claim that when the error probability is $p_{\beta}$, no error occurs on all $n$ qubits with probability $(1-p_{\beta})^{n}$.

We find that $C(m)$ is equivalent to the coefficient of the term $x^{n-m}y^{m}$ in the expansion of the polynomial $(x-y)^{{\rm wt}({\bf\ell})}(x+y)^{n-{\rm wt}({\bf\ell})}$. Therefore, substituting $x=1-p_{\beta}$ and $y=p_{\beta}$ in $(x-y)^{{\rm wt}({\bf\ell})}(x+y)^{n-{\rm wt}({\bf\ell})}$, we finally obtain

			$\displaystyle{\rm Tr}[\rho_{T}S_{\bf\ell}]$		(29)
		$\displaystyle=$	$\displaystyle[(1-p_{\beta})-p_{\beta}]^{{\rm wt}({\bf\ell})}[(1-p_{\beta})+p_{\beta}]^{n-{\rm wt}({\bf\ell})}$
		$\displaystyle=$	$\displaystyle(1-2p_{\beta})^{{\rm wt}({\bf\ell})}.$		(30)

At zero temperature, i.e., the ideal case $\rho_{0}=|G\rangle\langle G|$, using $p_{\beta}=0$, we obtain ${\rm Tr}[\rho_{T}S_{\bf\ell}]=1$ from Eq. (30) as it should be.

We confirm that Eqs. (27), (28), and (30) include the cases of ${\rm wt}({\bf\ell})=n$ and ${\rm wt}({\bf\ell})=0$. Setting ${\rm wt}({\bf\ell})=n$ in them, we obtain

	$\displaystyle{\rm Tr}\left[\rho_{T}S_{\bf\ell}\right]$	$\displaystyle=$	$\displaystyle\sum_{m=0}^{n}(-1)^{m}\binom{n}{m}(1-p_{\beta})^{n-m}p_{\beta}^{m}$		(31)
		$\displaystyle=$	$\displaystyle[(1-p_{\beta})-p_{\beta}]^{n}=(1-2p_{\beta})^{n},$		(32)

where we have used the binomial theorem. This is the expected result. Analogously, setting ${\rm wt}({\bf\ell})=0$ in them, we obtain

	$\displaystyle{\rm Tr}\left[\rho_{T}S_{\bf\ell}\right]$	$\displaystyle=$	$\displaystyle\sum_{m=0}^{n}\binom{n}{m}(1-p_{\beta})^{n-m}p_{\beta}^{m}$		(33)
		$\displaystyle=$	$\displaystyle[(1-p_{\beta})+p_{\beta}]^{n}=1.$		(34)

This is consistent with the fact that the outcome of the measurement of $S_{0^{n}}=I^{\otimes n}$ is always unity.

From Eq. (30), when $n=2k$ and ${\bf\ell}=1^{k}0^{k}$,

$\displaystyle{\rm Tr}[\rho_{T}S_{1^{k}0^{k}}]=[(1-p_{\beta})^{2}-p_{\beta}^{2}]^{k}=\cfrac{(1-e^{-4\beta})^{k}}{(1+e^{-2\beta})^{n}}.$

(35)

If one expands the middle expression in Eq. (35), one finds that $C(m)=0$ when $m$ is odd. By using Eqs. (26) and (35),

	$\displaystyle\left|\langle G|\rho_{T}|G\rangle-{\rm Tr}[\rho_{T}S_{1^{k}0^{k}}]\right|$	$\displaystyle=$	$\displaystyle\cfrac{1-(1-e^{-4\beta})^{k}}{(1+e^{-2\beta})^{n}}$		(36)
		$\displaystyle\leq$	$\displaystyle\cfrac{1-(1-ke^{-4\beta})}{(1+e^{-2\beta})^{n}}$		(37)
		$\displaystyle=$	$\displaystyle\cfrac{ne^{-4\beta}}{2(1+e^{-2\beta})^{n}}$		(38)
		$\displaystyle\leq$	$\displaystyle\cfrac{2}{n}.$		(39)

Finally, we combine Eqs. (25), (38), and (39) and obtain Eqs. (10) and (11).

In the limit of large $N$, the values $\epsilon$ and $\delta$ become zero, i.e., $F_{\rm est}={\rm Tr}[\rho_{T}S_{1^{k}0^{k}}]$. Therefore, from Eqs. (26) and (35),

$\displaystyle\langle G|\rho_{T}|G\rangle\geq{\rm Tr}[\rho_{T}S_{1^{k}0^{k}}]=F_{\rm est}.$

(40)

In this appendix, we derive the value of ${\rm Tr}[\rho_{T}S_{\bf\ell}]$ when the ideal state is $|G\rangle=CZ|++\rangle$. From Eq. (8), the thermal graph state $\rho_{T}$ is

	$\displaystyle(1-p_{\beta})^{2}|G\rangle\langle G|$
	$\displaystyle+p_{\beta}(1-p_{\beta})\left(Z_{1}|G\rangle\langle G|Z_{1}+Z_{2}|G\rangle\langle G|Z_{2}\right)$
	$\displaystyle+p_{\beta}^{2}Z_{1}Z_{2}|G\rangle\langle G|Z_{1}Z_{2},$		(41)

where $Z_{i}$ is the Pauli-$Z$ operator on the $i$th qubit for $i\in\{1,2\}$. Regardless of the value of $\ell$, the ideal state $|G\rangle\langle G|$ satisfies ${\rm Tr}[|G\rangle\langle G|S_{\ell}]=1$. Therefore,

$\displaystyle{\rm Tr}\left[(1-p_{\beta})^{2}|G\rangle\langle G|S_{\bf\ell}\right]=C(0)(1-p_{\beta})^{2},$

(42)

which corresponds to the term of $m=0$ in Eq. (27).

Next, we consider the second and third terms in Eq. (41), which correspond to terms of $m=1$ and $m=2$ in Eq. (27), respectively. The values of ${\rm Tr}[Z_{1}|G\rangle\langle G|Z_{1}S_{\bf\ell}]$, ${\rm Tr}[Z_{2}|G\rangle\langle G|Z_{2}S_{\bf\ell}]$, and ${\rm Tr}[Z_{1}Z_{2}|G\rangle\langle G|Z_{1}Z_{2}S_{\bf\ell}]$ depend on ${\bf\ell}$. For example, when ${\rm wt}({\bf\ell})=1$,

	$\displaystyle{\rm Tr}\left[\left(Z_{1}|G\rangle\langle G|Z_{1}+Z_{2}|G\rangle\langle G|Z_{2}\right)S_{\bf\ell}\right]$	$\displaystyle=$	$\displaystyle 0$		(43)
	$\displaystyle{\rm Tr}\left[Z_{1}Z_{2}|G\rangle\langle G|Z_{1}Z_{2}S_{\bf\ell}\right]$	$\displaystyle=$	$\displaystyle-1.$		(44)

Therefore,

			$\displaystyle{\rm Tr}\left[p_{\beta}(1-p_{\beta})\left(Z_{1}|G\rangle\langle G|Z_{1}+Z_{2}|G\rangle\langle G|Z_{2}\right)S_{\bf\ell}\right]$
		$\displaystyle=$	$\displaystyle\left[\sum_{j=w({\bf\ell},1,2)}^{f({\bf\ell},1)}(-1)^{j}\binom{1}{j}\binom{1}{1-j}\right](1-p_{\beta})p_{\beta},$		(45)

where $w({\bf\ell},1,2)=0$ and $f({\bf\ell},1)=1$, and

			$\displaystyle{\rm Tr}\left[p_{\beta}^{2}Z_{1}Z_{2}|G\rangle\langle G|Z_{1}Z_{2}S_{\bf\ell}\right]$		(46)
		$\displaystyle=$	$\displaystyle\left[\sum_{j=w({\bf\ell},2,2)}^{f({\bf\ell},2)}(-1)^{j}\binom{1}{j}\binom{1}{2-j}\right]p_{\beta}^{2},$

where $w({\bf\ell},2,2)=f({\bf\ell},2)=1$. By combining Eqs. (42), (45), and (46), we actually obtain Eq. (27). For the cases of ${\rm wt}({\bf\ell})=0$ and ${\rm wt}({\bf\ell})=2$, a similar argument holds.