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

Physical Review A

Efficient verification of two-colorable graph states

Qingshan Xu, Xiaoqing Tan, Yangwei Ou, Daipengwei Bao, Rui Huang

Published Jul 8, 2024• 4 citations
Publisher

Abstract

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.

DOI
10.1103/physreva.110.012606

Related papers

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•28 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

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

Yuki Takeuchi, Atul Mantri, Tomoyuki Morimae +2 more

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.

arXiv:1806.09138•npj Quantum Information•Apr 12, 2019•67 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

Improved Resource State for Verifiable Blind Quantum Computation

Qingshan Xu, Xiaoqing Tan, Rui Huang

Recent advances in theoretical and experimental quantum computing raise the problem of verifying the outcome of these quantum computations. The recent verification protocols using blind quantum computing are fruitful for addressing this problem. Unfortunately, all known schemes have relatively high overhead. Here we present a novel construction for the resource state of verifiable blind quantum computation. This approach achieves a better verifiability of 0.866 in the case of classical output. In addition, the number of required qubits is 2N+4cN, where N and c are the number of vertices and the maximal degree in the original computation graph, respectively. In other words, our overhead is less linear in the size of the computational scale. Finally, we utilize the method of repetition and fault-tolerant code to optimise the verifiability.

Entropy•Sep 7, 2020•15 citations

A simplified verifiable blind quantum computing protocol with quantum input verification

Junyu Quan, Qin Li, Chengdong Liu +2 more

Blind quantum computing (BQC) enables a client with limited quantum capability to delegate her quantum computation to a remote quantum server and still keeps the client's input, output, and the algorithm private. One important property of BQC is verifiability, which means the client can verify the correctness of the computation or unknown quantum inputs. Recently, Morimae proposed a verifiable blind quantum computing protocol where the client can verify both the correctness of computing and the quantum input. However, the client needs much quantum memory and takes a lot of qubits to get the true result. We reduce the size of quantum memory and the number of qubits used in Morimae's protocol. Besides, we extend the resource state in Morimae's protocol from graph state to hypergraph state. For certain hypergraph states as resources states, such as Union Jack State, the client only needs Pauli measurements in the computation stage but he needs non-Clifford basis measurements if graph states are considered as resources states.

Quantum Engineering•Jan 3, 2021•19 citations
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.
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.
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.
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.
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.
Recent advances in theoretical and experimental quantum computing raise the problem of verifying the outcome of these quantum computations. The recent verification protocols using blind quantum computing are fruitful for addressing this problem. Unfortunately, all known schemes have relatively high overhead. Here we present a novel construction for the resource state of verifiable blind quantum computation. This approach achieves a better verifiability of 0.866 in the case of classical output. In addition, the number of required qubits is 2N+4cN, where N and c are the number of vertices and the maximal degree in the original computation graph, respectively. In other words, our overhead is less linear in the size of the computational scale. Finally, we utilize the method of repetition and fault-tolerant code to optimise the verifiability.
Blind quantum computing (BQC) enables a client with limited quantum capability to delegate her quantum computation to a remote quantum server and still keeps the client's input, output, and the algorithm private. One important property of BQC is verifiability, which means the client can verify the correctness of the computation or unknown quantum inputs. Recently, Morimae proposed a verifiable blind quantum computing protocol where the client can verify both the correctness of computing and the quantum input. However, the client needs much quantum memory and takes a lot of qubits to get the true result. We reduce the size of quantum memory and the number of qubits used in Morimae's protocol. Besides, we extend the resource state in Morimae's protocol from graph state to hypergraph state. For certain hypergraph states as resources states, such as Union Jack State, the client only needs Pauli measurements in the computation stage but he needs non-Clifford basis measurements if graph states are considered as resources states.