Verification of graph states in an untrusted network

Graph states are a large class of multipartite entangled quantum states that form the basis of schemes for quantum computation, communication, error correction, metrology, and more. In this work, we consider verification of graph states generated by an untrusted source and shared between a network of possibly dishonest parties. This has implications in certifying the application of graph states for various distributed tasks. We present a protocol which is globally efficient for a large family of useful graph states, including cluster states, GHZ states, cycle graph states, and more. For general graph states, efficiency with respect to the security parameter is maintained, though there is a cost increase with the size of the graph state. The protocols are practical, requiring only multiple copies of the graph state, local measurements, and classical communication.

Figure 1

Examples of a (a) complete graph, (b) pentagon graph, (c) cycle graph, (d) $1\mathrm{D}$ cluster state, and (e) $2\mathrm{D}$ cluster state. For quantum states that correspond to these types of graphs, one can perform efficient verification using Protocol 1, possibly with some information regarding the dishonest parties, as shown in Theorem t2.

Figure 2

Five- and six-qubit complete graph states.

Figure 3

Sets of honest ($H$) and dishonest ($D$) parties for the pentagon graph state considered in Theorem t12.

Figure 4

Three-, four-, and six-qubit cycle (ring) graph states.

Figure 5

Five-qubit path graph state, or $1\mathrm{D}$ cluster state.

Figure 6

Sets of honest (H) and dishonest (D) parties for the $4\times 4$ cluster state considered in Theorem t15.