Efficient Verification of Hypergraph States

Graph states and hypergraph states are of wide interest in quantum information processing and foundational studies. Efficient verification of these states is a key to various applications. Here we propose a simple method for verifying hypergraph states, which requires only two distinct Pauli measurements for each party, yet its efficiency is comparable to the best strategy based on entangling measurements. For a given state, the overhead is bounded by the chromatic number and degree of the underlying hypergraph. Our protocol is dramatically more efficient than all previous protocols based on local measurements, including tomography and direct-fidelity estimation. It enables the verification of hypergraph states and genuine multipartite entanglement of thousands of qubits. The protocol can also be generalized to the adversarial scenario, while achieving almost the same efficiency. This merit is particularly appealing to demonstrating blind measurement-based quantum computation and quantum supremacy.

Figure 1

Examples of hypergraphs and associated hypergraph states. Left plot: one-dimensional (1D) and two-dimensional (2D) order-3 cluster states; every three neighboring vertices on a row or column are connected by an order-3 hyperedge. Right plot: Union Jack states on a chain and a 2D lattice, respectively; the three vertices of each elementary triangle are connected by an order-3 hyperedge [23]. All four hypergraphs are three-colorable as illustrated.

Figure 2

Resource costs for verifying hypergraph states in the nonadversarial scenario. Left plot: 1D order-3 cluster states; right plot: Union Jack states on a chain. Here $n$ is the number of qubits, and $N$ is the (expected) number of tests required to verify the state within infidelity $ϵ=0.01$ and significance level $\delta =0.05$. In the case of the Morimae, Takeuchi, and Hayashi (MTH) protocol proposed in Ref. [25], only a lower bound for $N$ is given. The lines are guides for the eye. Our cover protocol dramatically outperforms DFE [34] and the MTH protocol (cf. Appendix pp4).

Figure 3

Resource costs for verifying three-colorable hypergraph states in the adversarial scenario. Here $n$ is the number of qubits, and $N$ is the number of tests required to verify the state within infidelity $ϵ=1/(4n)$ and significance level $\delta =1/(4n)$. The lines are guides for the eye. Our cover protocol (Cover) and hedged cover protocol (HCover) outperform the Takeuchi and Morimae (TM) protocol proposed in Ref. [35] by at least 18 orders of magnitude.