Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Efficient Verification of Hypergraph States

Huangjun Zhu, Masahito Hayashi

Published Jan 1, 2019• 59 citations
OpenAlex

Abstract

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.

Related papers

Efficient Verification of Hypergraph States

Huangjun Zhu, Masahito Hayashi

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.

arXiv:1806.05565•Physical Review Applied•Nov 20, 2019•71 citations

Verification of hypergraph states

Tomoyuki Morimae, Yuki Takeuchi, Masahito Hayashi

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.

arXiv:1701.05688•Physical Review A•Dec 20, 2017•63 citations

General framework for verifying pure quantum states in the adversarial scenario

Huangjun Zhu, Masahito Hayashi

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).

arXiv:1909.01943•Physical Review A•Dec 27, 2019•66 citations

Efficient verification of two-colorable graph states

Qingshan Xu, Xiaoqing Tan, Yangwei Ou +2 more

Graph states known as the resource states for measurement-based quantum computation play an important role in quantum information processing. Verifying the correctness of graph states in an efficient way is crucial to scalable quantum computing. In this paper, we propose an efficient method for verifying two-colorable graph states with Pauli measurements, where the number of required measurement settings is a constant that is independent of the size of graph states. In addition, the number of required tests is less than the existing protocols. We also present several examples, such as the brickwork state and the two-dimensional square lattice state, to show how to get the specific verification strategy. Furthermore, we propose a robust verification of graph states for resisting the noise acting on the measurement device. Finally, based on the verification of two-colorable graph states in the adversarial scenario, we propose a verifiable blind quantum computing protocol, which can realize the less resource overhead.

Physical Review A•Jul 8, 2024•4 citations

Demonstration of hypergraph-state quantum information processing

Jieshan Huang, Xudong Li, Xiaojiong Chen +7 more

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.

Nature Communications•Mar 23, 2024•27 citations

Verification of blind quantum computation with entanglement witnesses

Qingshan Xu, Xiaoqing Tan, Rui Huang +1 more

Verifiable blind quantum computation provides a cloud scenario for scalable quantum information processing. However, constructing one resource-efficient verification protocol is still an open problem. In this paper, the context of verification we consider is the measurement-based model, in which the client receives the graph state prepared by the server and performs single-qubit measurements on it to drive the computation. We first utilize three entanglement witnesses to estimate the fidelity of the prepared graph state. Applying entanglement witnesses to design the test phase, we propose verification protocols. Our protocol requires overhead in terms of copies of the graph state that scales as $O({n}^{2}logn)$, where $n$ is the number of qubits of the graph state. Furthermore, the soundness of our protocol is improved. The advantages of our protocol are derived from the fact that each entanglement witness can be implemented by the client with a fixed number of measurement settings.

Physical Review A•Oct 12, 2021•20 citations
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.
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.
Hypergraph states are generalizations of graph states where controlled-ZZZ gates on edges are replaced with generalized controlled-ZZZ 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.
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).
Graph states known as the resource states for measurement-based quantum computation play an important role in quantum information processing. Verifying the correctness of graph states in an efficient way is crucial to scalable quantum computing. In this paper, we propose an efficient method for verifying two-colorable graph states with Pauli measurements, where the number of required measurement settings is a constant that is independent of the size of graph states. In addition, the number of required tests is less than the existing protocols. We also present several examples, such as the brickwork state and the two-dimensional square lattice state, to show how to get the specific verification strategy. Furthermore, we propose a robust verification of graph states for resisting the noise acting on the measurement device. Finally, based on the verification of two-colorable graph states in the adversarial scenario, we propose a verifiable blind quantum computing protocol, which can realize the less resource overhead.
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.
Verifiable blind quantum computation provides a cloud scenario for scalable quantum information processing. However, constructing one resource-efficient verification protocol is still an open problem. In this paper, the context of verification we consider is the measurement-based model, in which the client receives the graph state prepared by the server and performs single-qubit measurements on it to drive the computation. We first utilize three entanglement witnesses to estimate the fidelity of the prepared graph state. Applying entanglement witnesses to design the test phase, we propose verification protocols. Our protocol requires overhead in terms of copies of the graph state that scales as O(n2logn)O({n}^{2}logn)O(n2logn), where nnn is the number of qubits of the graph state. Furthermore, the soundness of our protocol is improved. The advantages of our protocol are derived from the fact that each entanglement witness can be implemented by the client with a fixed number of measurement settings.