Graph and hypergraph states are of wide interest in quantum information processing as well as fundamental physics, and efficient verification of these states is key to various applications. The authors propose a simple recipe for verifying hypergraph states that requires only two distinct Pauli measurements for each party, and is dramatically more efficient than conventional protocols based on local measurements. This approach enables verification of hypergraph states and genuine multipartite entanglement of thousands of qubits, even in an adversarial scenario.
Graph and hypergraph states are of wide interest in quantum information processing as well as fundamental physics, and efficient verification of these states is key to various applications. The authors propose a simple recipe for verifying hypergraph states that requires only two distinct Pauli measurements for each party, and is dramatically more efficient than conventional protocols based on local measurements. This approach enables verification of hypergraph states and genuine multipartite entanglement of thousands of qubits, even in an adversarial scenario.
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.
Bipartite and multipartite entangled states are of central interest in quantum information processing and foundational studies. Efficient verification of these states, especially in the adversarial scenario, is a key to various applications, including quantum computation, quantum simulation, and quantum networks. However, little is known about this topic in the adversarial scenario. Here we initiate a systematic study of pure-state verification in the adversarial scenario. In particular, we introduce a general method for determining the minimal number of tests required by a given strategy to achieve a given precision. In the case of homogeneous strategies, we can even derive an analytical formula. Furthermore, we propose a general recipe to verifying pure quantum states in the adversarial scenario by virtue of protocols for the nonadversarial scenario. Thanks to this recipe, the resource cost for verifying an arbitrary pure state in the adversarial scenario is comparable to the counterpart for the nonadversarial scenario, and the overhead is at most three times for high-precision verification. Our recipe can readily be applied to efficiently verify bipartite pure states, stabilizer states, hypergraph states, weighted graph states, and Dicke states in the adversarial scenario, even if only local projective measurements are accessible. This paper is an extended version of the companion paper Zhu and Hayashi, Phys. Rev. Lett. 123, 260504 (2019).
Hypergraph states are generalizations of graph states where controlled-Z gates on edges are replaced with generalized controlled-Z gates on hyperedges. Hypergraph states have several advantages over graph states. For example, certain hypergraph states, such as the Union Jack states, are universal resource states for measurement-based quantum computing with only Pauli measurements, while graph state measurement-based quantum computing needs non-Clifford basis measurements. Furthermore, it is impossible to classically efficiently sample measurement results on hypergraph states unless the polynomial hierarchy collapses to the third level. Although several protocols have been proposed to verify graph states with only sequential single-qubit Pauli measurements, there was no verification method for hypergraph states. In this paper, we propose a method for verifying a certain class of hypergraph states with only sequential single-qubit Pauli measurements. Importantly, no i.i.d. property of samples is assumed in our protocol: any artificial entanglement among samples cannot fool the verifier. As applications of our protocol, we consider verified blind quantum computing with hypergraph states, and quantum computational supremacy demonstrations with hypergraph states.
Quantum hypergraph states extend the well-studied class of graph states by taking into account multi-qubit interactions through hyperedges. They provide a powerful framework to represent a family of quantum states with genuine multipartite entanglement. In this review, we provide a compact overview of the formal structure, entanglement characteristics, and operational relevance of hypergraph states in quantum information theory. We begin by introducing their mathematical foundations and generalizations of the stabilizer formalism. A central focus is placed on their entanglement properties, including the classification under local unitary (LU) and stochastic local operations with classical communication (SLOCC), the quantification of multipartite entanglement, and detection techniques via entanglement witnesses. We also explore other nonclassical features of hypergraph states, such as contextuality and genuine multipartite nonlocality, derived from stabilizer-based Bell-type inequalities. Additional attention is given to the role of hypergraph states in error correction, and as a computational resource in measurement-based quantum computation (MBQC), and to their non-stabilizer character - quantified via resource-theoretic measures of quantum magic. Finally we review their generalization to higher dimensions, i.e. to qudits and continuous variables.
Complex entangled states are the key resources for measurement-based quantum computations, which is realised by performing a sequence of measurements on initially entangled qubits. Executable quantum algorithms in the graph-state quantum computing model are determined by the entanglement structure and the connectivity of entangled qubits. By generalisation from graph-type entanglement in which only the nearest qubits interact to a new type of hypergraph entanglement in which any subset of qubits can be arbitrarily entangled via hyperedges, hypergraph states represent more general resource states that allow arbitrary quantum computation with Pauli universality. Here we report experimental preparation, certification and processing of complete categories of four-qubit hypergraph states under the principle of local unitary equivalence, on a fully reprogrammable silicon-photonic quantum chip. Genuine multipartite entanglement for hypergraph states is certificated by the characterisation of entanglement witness, and the observation of violations of Mermin inequalities without any closure of distance or detection loopholes. A basic measurement-based protocol and an efficient resource state verification by color-encoding stabilizers are implemented with local Pauli measurement to benchmark the building blocks for hypergraph-state quantum computation. Our work prototypes hypergraph entanglement as a general resource for quantum information processing.
Efficient verification of pure quantum states in the adversarial scenario is crucial to many applications in quantum information processing, such as blind measurement-based quantum computation and quantum networks. However, little is known about this topic so far. Here, we establish a general framework for verifying pure quantum states in the adversarial scenario and clarify the resource cost. Moreover, we propose a simple and general recipe to constructing efficient verification protocols for the adversarial scenario from protocols for the nonadversarial scenario. With this recipe, arbitrary pure states can be verified in the adversarial scenario with almost the same efficiency as in the nonadversarial scenario. Many important quantum states can be verified in the adversarial scenario using local projective measurements with unprecedented high efficiencies.