PaperlayerView exact revision on arXiv

Source-linked AI summary

Verifiable measurement-only blind quantum computing with stabilizer testing

Masahito Hayashi, Tomoyuki Morimae

arXiv:1505.07535v2quant-ph

TL;DR

Blind quantum computing must let a measurement-limited client delegate computation without revealing private information or losing correctness against a malicious server. This paper proposes direct stabilizer testing of graph-state copies, with prior-work analysis addressing adversarial non-i.i.d. settings.

  • Problem

    The central problem is verifying delegated blind quantum computing when prior verification results do not directly apply without i.i.d. samples.

  • Method

    The protocol uses direct graph-state testing, with Bob generating multiple copies and Alice testing selected copies through stabilizer-based checks.

  • Results

    The paper’s principal outcome is a protocol whose verification approach satisfies the stated graph-state, single-qubit-operation, and non-i.i.d. requirements.

  • Takeaways & Limitations

    Direct graph-state testing provides a verification technique distinct from the trap technique used in earlier blind-quantum-computing proposals.

Abstract

from arXiv · show

We introduce a simple protocol for verifiable measurement-only blind quantum computing. Alice, a client, can perform only single-qubit measurements, whereas Bob, a server, can generate and store entangled many-qubit states. Bob generates copies of a graph state, which is a universal resource state for measurement-based quantum computing, and sends Alice each qubit of them one by one. Alice adaptively measures each qubit according to her program. If Bob is honest, he generates the correct graph state, and therefore Alice can obtain the correct computation result. Regarding the security, whatever Bob does, Bob cannot learn any information about Alice's computation because of the no-signaling principle. Furthermore, evil Bob does not necessarily send the copies of the correct graph state, but Alice can check the correctness of Bob's state by directly verifying stabilizers of some copies.

Appendix A: Relation to previous works

The appendix positions the protocol against prior verification approaches, emphasizing its direct graph-state testing and compatibility with non-i.i.d. adversarial settings. It also contrasts trap-based verification and multiprover methods with the protocol’s assumptions.

  • Appendix A: Relation to previous works: The protocol satisfies the stated conditions that the test apply to graph states, operations be restricted to single-qubit operations, and i.i.d. samples not be assumed.These conditions distinguish the protocol from prior studies that fail to meet them jointly.
  • Appendix A: Relation to previous works: Prior graph-state verification results cannot be directly used because they assume i.i.d. samples, which are unacceptable against unrestricted malicious adversaries in quantum cryptography.The protocol is presented as satisfying the additional requirement that i.i.d. samples cannot be assumed.
  • Appendix A: Relation to previous works: The protocol introduces direct graph-state testing instead of the trap technique used by earlier blind-quantum-computing verification proposals.Earlier proposals hide isolated qubits as traps, whereas this protocol directly tests the graph state.
  • Appendix A: Relation to previous works: Device-independent multiprover verification cannot be directly applied because assuming that separate provers do not communicate is unnatural for blind quantum computing.The appendix contrasts this setting with the single-server, minimum-client-technology assumptions discussed for other protocols.

Appendix B: Analysis of local conversion for a bipartite graph state

The appendix reduces a bipartite graph state to a canonical form using linear-algebraic basis choices and local unitaries. Classical transformations of measurement outcomes then reproduce the effects of those local operations.

  • Appendix B: Analysis of local conversion for a bipartite graph state: The possible X-basis outcomes on B form a subspace V_B, whose orthogonal complement supplies additional basis vectors for the conversion.The corresponding Hilbert spaces are denoted K_B and K′_B, and the all-zero X eigenstate on K′_B is |+⟩_B′.
  • Appendix B: Analysis of local conversion for a bipartite graph state: For a bipartite graph state, the adjacency matrix A records which sites in B are connected to sites in W.An entry a_i,j is 1 for a connected pair and zero otherwise.
  • Appendix B: Analysis of local conversion for a bipartite graph state: Measuring W in the Z basis with outcome z predicts the X-basis outcome Az on B.This relation connects the adjacency matrix to the stabilizer-style measurement check.
  • Appendix B: Analysis of local conversion for a bipartite graph state: Bases of the outcome subspaces and the kernel of A define invertible matrices C and D, yielding the transformed matrix A′ = C^-1AD.The matrices are formed from basis vectors c_i and d_i selected for the relevant spaces.
  • Appendix B: Analysis of local conversion for a bipartite graph state: The transformed state has a graph consisting of isolated edges and isolated sites, represented as |G′⟩⊗|+⟩_B′⊗|+⟩_W′.The isolated-edge component is defined on K_B ⊗ K_W, while the remaining components are isolated-site graph states.
  • Appendix B: Analysis of local conversion for a bipartite graph state: Local unitaries U_C^-1,X,B U_D^-1,Z,W convert |G⟩ to the canonical state, while classical outcome conversions reproduce their effects under complementary basis measurements.The conversions are x → C^-1x and z → D^-1z for Z on W and X on B, with transposed transformations in the reverse arrangement.

Appendix C: Concrete examples

The appendix introduces concrete few-qubit graph-state examples to make the preceding conversion results easier to understand.

  • Appendix C: Concrete examples: The authors demonstrate the preceding graph-state conversion results on few-qubit graph states.The example section is presented as an aid to understanding the general construction.

1. Three-qubit graph state

For a three-qubit linear graph state, different measurement-basis choices produce explicit classical data conversions and corresponding consistency checks.

  • 1. Three-qubit graph state: The example uses a three-qubit graph state arranged as a linear chain and considers alternative choices for the basis vector c2.The displayed construction begins by numbering the left black-circle site 1.
  • 1. Three-qubit graph state: For X measurements on sites 1 and 2 and a Z measurement on site 1, the converted data are X2, X1 + X2, and Z1.The resulting check is X2 = Z1.
  • 1. Three-qubit graph state: For Z measurements on sites 1 and 2 and an X measurement on site 1, the converted data are Z1 + Z2, Z1, and X1.The resulting check is X1 = Z1 + Z2.

2. Four-qubit graph state

The four-qubit graph state is labeled by numbering its black vertices, and measurement outcomes are converted into classical relations for verification.

  • The two black circles of the four-qubit graph state are numbered 1 and 2.
  • When B is measured in X and W in Z, the verification data are transformed to check X1 + X2 = Z1 and X2 = Z2.
  • When B is measured in Z and W in X, the data are transformed using Z1, Z1 + Z2, X1, and X2 for the corresponding checks.

Appendix D: Analysis of the classical hypothesis testing problem

The appendix analyzes permutation-invariant distributions over 2k + 1 two-bit trials by decomposing them into typical distributions and cases, deriving the hypothesis-testing bound and its tightness.

  • The derived lemma is sufficient because it is the contraposition of Theorem 2 in the main text, and its bound is shown to be tight.Tightness is established using the distribution with one (1, 1) event and the remaining 2k events equal to (0, 0).
  • A permutation-invariant distribution on 2k + 1 trials is decomposed into typical distributions indexed by the counts a, b, and c of event types.The counts of (0, 0), (1, 0), (0, 1), and (1, 1) are fixed by 2k + 1 − (a + b + c), a, b, and c.
  • For c = 1, the conditioned event requiring all specified outcomes to be zero has probability zero.The appendix explicitly derives this for the event involving S2k+1 = T2k+1 = 0 together with the first k paired conditions.
  • The analysis restricts the relevant support to c = 0 and c = 1, representing the distribution as a mixture βQ0 + (1 − β)Q1.Q0 and Q1 have the supports specified for the c = 0 and c = 1 cases, respectively.

Appendix E: Proof of Lemma 3

Appendix E proves non-negativity of ξ(a, b, k) by exploiting its symmetry and dividing the analysis into small-k cases and the remaining k ≥ 4 cases.

  • The proof targets ξ(a, b, k) ≥ 0 and assumes a ≥ b without loss of generality because ξ is symmetric in a and b.The constraints k + 1 ≥ a, b ≥ 0 and 2k + 1 ≥ a + b are also assumed.
  • The cases k = 1, 2, and 3 are handled through the listed combinations of (a, b) across Subsections E 2, E 3, and E 4.For k = 3, the cases (3, 3, 3) and (4, 0, 3) through (4, 3, 3) are assigned to Subsections E 4 and E 3.
  • For k ≥ 4, cases with a + b ≥ 6 and a ≥ 3 are classified in Table I after separately covering the remaining low-a and low-sum cases.The remaining cases include (4, 0), (4, 1), and (5, 0), which are assigned to Subsections E 5 and E 6.

d. Cases: a + b ≥6, a ≥3 and k ≥4

The subsection completes the classification for cases with a + b ≥ 6, a ≥ 3, and k ≥ 4, thereby covering all cases.

  • Table I classifies the cases satisfying a + b ≥ 6, a ≥ 3, and k ≥ 4.
  • The classification completes the proof coverage, so all cases have been covered.

2. Case: (a, b) = (0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2), (3, 0), (3, 1), (3, 2)

For the listed small parameter pairs, ξ(a, b, k) is evaluated explicitly, and the resulting values are non-negative when k ≥ a, b.

  • ξ(a, b, k) is symmetric in a and b, so only cases with a ≥ b need consideration.
  • ξ(1, 0, k), ξ(1, 1, k), and ξ(2, 0, k) are all 0, while ξ(2, 1, k) = k − 1.
  • The listed values are non-negative whenever k ≥ a, b.
  • The calculation proceeds by rewriting factorial-like products into successive factors involving k and k + 1 − b.

4. Case: (a, b) = (3, 3)

The (a, b) = (3, 3) case has a dedicated expression for ξ(3, 3, k) and is possible only for k ≥ 3, where it is positive.

  • ξ(3, 3, k) is evaluated separately from the smaller cases.
  • The case (a, b) = (3, 3) is possible only when k ≥ 3 and is positive in that range.

6. Case: b = 1 and a ≥3

The section derives product bounds for the remaining parameter regime by separating parity cases and combining earlier inequalities under constraints on a, b, and k.

  • The derivation treats even k = 2s and odd k = 2s + 1 separately before combining the resulting cases.
  • Combining (E5), (E6), and (E7) yields the next relation in the proof.
  • For the remaining discussion, the analysis assumes a + b ≥ 6, k ≥ 4, b ≥ 2, and a ≥ b + 1 after covering cases with a + b ≤ 5.
  • Under the stated assumptions, inequality (E9) lower-bounds the product by 2^(a+b−3)k.
  • The expression for ξ(a, b, k) is represented using products over factors indexed by a, b, and their combined value.
Loading 1505.07535v2…