© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1806.09138 · npj Quantum Information

Resource-efficient verification of quantum computing using Serfling’s bound

Yuki Takeuchi, Atul Mantri, Tomoyuki Morimae, Akihiro Mizutani, Joseph F. Fitzsimons

Published Apr 12, 2019• 63 citations

Abstract

Abstract Verifying quantum states is central to certifying the correct operation of various quantum information processing tasks. In particular, in measurement-based quantum computing, checking whether correct graph states are generated is essential for reliable quantum computing. Several verification protocols for graph states have been proposed, but none of these are particularly resource efficient: multiple copies are required to extract a single state that is guaranteed to be close to the ideal one. The best protocol currently known requires O(n15) copies of the state, where n is the size of the graph state. In this paper, we construct a significantly more resource-efficient verification protocol for graph states that only requires O(n5 log n) copies. The key idea is to employ Serfling’s bound, which is a probability inequality in classical statistics. Utilizing Serfling’s bound also enables us to generalize our protocol for qudit and continuous-variable graph states. Constructing a resource-efficient verification protocol for them is non-trivial. For example, the previous verification protocols for qubit graph states that use the quantum de Finetti theorem cannot be generalized to qudit and continuous-variable graph states without tremendously increasing the resource overhead. This is because the overhead caused by the quantum de Finetti theorem depends on the local dimension. On the other hand, in our protocol, the resource overhead is independent of the local dimension, and therefore generalizing to qudit or continuous-variable graph states does not increase the overhead. The flexibility of Serfling’s bound also makes our protocol robust: our protocol accepts slightly noisy but still useful graph states.

DOI: 10.1038/s41534-019-0142-2

Related papers

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

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

Robust and efficient verification of graph states in blind measurement-based quantum computation

Zihao Li, Huangjun Zhu, Masahito Hayashi

Abstract Blind quantum computation (BQC) is a secure quantum computation method that protects the privacy of clients. Measurement-based quantum computation (MBQC) is a promising approach for realizing BQC. To obtain reliable results in blind MBQC, it is crucial to verify whether the resource graph states are accurately prepared in the adversarial scenario. However, previous verification protocols for this task are too resource-consuming or noise-susceptible to be applied in practice. Here, we propose a robust and efficient protocol for verifying arbitrary graph states with any prime local dimension in the adversarial scenario, which leads to a robust and efficient protocol for verifying the resource state in blind MBQC. Our protocol requires only local Pauli measurements and is thus easy to realize with current technologies. Nevertheless, it can achieve optimal scaling behaviors with respect to the system size and the target precision as quantified by the infidelity and significance level, which has never been achieved before. Notably, our protocol can exponentially enhance the scaling behavior with the significance level.

arXiv:2305.10742•npj Quantum Information•Nov 14, 2023•26 citations

Robust Verification of Graph States Under Adversarial Scenario and Noisy Measurements

Qingshan Xu, Xiaoqing Tan, Zhipeng Xiao +3 more

Abstract Graph states are resource states for measurement‐based quantum computation. Verification of graph states aims to certify whether a quantum state prepared by an untrusted device is close to an ideal graph state or not. Existing verification methods have not considered verifying graph states under an adversarial scenario and noisy measurements. In this paper, a robust verification method for graph states is proposed to overcome this issue. First, a verification model for graph states is designed. Then, two types of verification protocols based on this model are proposed. In addition, the completeness and soundness of the verification protocols are calculated when the measurement devices are affected by noises. Afterward, the measurement strategy of the robust verification protocols is extended from the specific case to the general case. In order to obtain the soundness that scales as , the verification method only requires copies of the graph state, where is the size of the graph state. Finally, several numerical examples are presented to demonstrate the effect of noises on the completeness and soundness of the verification protocols.

Advanced Quantum Technologies•Jul 31, 2025•0 citations

Efficient Verification of Hypergraph States

Huangjun Zhu, Masahito Hayashi

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.

•Jan 1, 2019•59 citations

Verification of graph states in an untrusted network

Anupama Unnikrishnan, Damian Markham

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.

arXiv:2007.13126•Physical Review A•May 13, 2022•15 citations

Abstract Verifying quantum states is central to certifying the correct operation of various quantum information processing tasks. In particular, in measurement-based quantum computing, checking whether correct graph states are generated is essential for reliable quantum computing. Several verification protocols for graph states have been proposed, but none of these are particularly resource efficient: multiple copies are required to extract a single state that is guaranteed to be close to the ideal one. The best protocol currently known requires O(n15) copies of the state, where n is the size of the graph state. In this paper, we construct a significantly more resource-efficient verification protocol for graph states that only requires O(n5 log n) copies. The key idea is to employ Serfling’s bound, which is a probability inequality in classical statistics. Utilizing Serfling’s bound also enables us to generalize our protocol for qudit and continuous-variable graph states. Constructing a resource-efficient verification protocol for them is non-trivial. For example, the previous verification protocols for qubit graph states that use the quantum de Finetti theorem cannot be generalized to qudit and continuous-variable graph states without tremendously increasing the resource overhead. This is because the overhead caused by the quantum de Finetti theorem depends on the local dimension. On the other hand, in our protocol, the resource overhead is independent of the local dimension, and therefore generalizing to qudit or continuous-variable graph states does not increase the overhead. The flexibility of Serfling’s bound also makes our protocol robust: our protocol accepts slightly noisy but still useful graph states.

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.

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.

Abstract Blind quantum computation (BQC) is a secure quantum computation method that protects the privacy of clients. Measurement-based quantum computation (MBQC) is a promising approach for realizing BQC. To obtain reliable results in blind MBQC, it is crucial to verify whether the resource graph states are accurately prepared in the adversarial scenario. However, previous verification protocols for this task are too resource-consuming or noise-susceptible to be applied in practice. Here, we propose a robust and efficient protocol for verifying arbitrary graph states with any prime local dimension in the adversarial scenario, which leads to a robust and efficient protocol for verifying the resource state in blind MBQC. Our protocol requires only local Pauli measurements and is thus easy to realize with current technologies. Nevertheless, it can achieve optimal scaling behaviors with respect to the system size and the target precision as quantified by the infidelity and significance level, which has never been achieved before. Notably, our protocol can exponentially enhance the scaling behavior with the significance level.

Abstract Graph states are resource states for measurement‐based quantum computation. Verification of graph states aims to certify whether a quantum state prepared by an untrusted device is close to an ideal graph state or not. Existing verification methods have not considered verifying graph states under an adversarial scenario and noisy measurements. In this paper, a robust verification method for graph states is proposed to overcome this issue. First, a verification model for graph states is designed. Then, two types of verification protocols based on this model are proposed. In addition, the completeness and soundness of the verification protocols are calculated when the measurement devices are affected by noises. Afterward, the measurement strategy of the robust verification protocols is extended from the specific case to the general case. In order to obtain the soundness that scales as , the verification method only requires copies of the graph state, where is the size of the graph state. Finally, several numerical examples are presented to demonstrate the effect of noises on the completeness and soundness of the verification protocols.

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