PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Secret Sharing and Error Correction vs No-Cloning

Steven Chien, Ishani Mukherjee, Mark Zhandry

arXiv:2610.00441v1quant-phcs.CR

TL;DR

The paper asks whether multiple input copies can relax no-cloning limits when only one copy must be recovered. It develops graph-coloring constructions and Clique Path obstructions, while leaving a gap between positive and negative threshold results for k≥3.

  • Problem

    The paper asks whether providing multiple input copies can overcome no-cloning limits when a QSS scheme must recover only one copy.

    Source: §1 · p. 2

  • Method

    The paper studies parallel single-copy schemes based on access-structure decompositions and uses graph colorings and Clique Paths to construct schemes and prove impossibility.

    Source: §1.1 · p. 3, §3 · p. 11

  • Results

    The paper gives a positive threshold existence result and proves impossibility for k≥2 when t≤(n−1)/k.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The positive and negative results leave a gap for k≥3, which the authors identify as an open direction.

    Source: §1.1 · p. 4

    For k≥3 the results leave a gap; the threshold Clique Path argument requires n≥kt+1 to allow substitutions.

    Source: §1.1 · p. 4, §4.6 · p. 17

Abstract

from arXiv · show

Secret sharing is ubiquitous throughout cryptography. All possible access structures are classically feasible, and in the case of threshold access structures, the protocols are even very efficient. However, when moving to the quantum setting, the no-cloning theorem shows that many access structures are impossible. In fact, no-cloning exactly characterizes feasibility: for thresholds, quantum secret sharing is possible if and only if the threshold $t$ is strictly more than $n/2$. In this work, we propose a variant of quantum secret sharing (QSS) where two or more identical copies of the input state are provided, but the output is only required to recover one copy. This notion circumvents the simple one-copy no-cloning obstruction, though the natural $k$-copy generalization still gives much milder obstructions. For thresholds using $k$ copies, no-cloning implies that QSS is impossible whenever $t\leq n/(k+1)$. It is tempting to hypothesize that no-cloning continues to exactly characterize the many-copy case. However, we show that this is not the case. We give positive results showing that multiple copies allow for going slightly beyond the single-copy obstruction: for thresholds, we construct QSS whenever $t>(n-k+1)/2$. On the other hand, we give a novel obstruction we call the Clique Path obstruction, which applies to arbitrary access structures. For thresholds, it shows that QSS is impossible whenever $t\leq (n-1)/k$. Our upper and lower bounds exactly match for $k=2$. Both our results leverage connections to the $k$-colorability of certain graphs derived from the access structure. We leave closing the gap for $k\geq 3$ copies as a fascinating direction for future work. Secret sharing is closely related to error correction, which can also be considered in the many-copy setting. Our results imply similar obstructions for quantum error correction for erasure channels.

1 Introduction

This section studies quantum secret sharing with multiple identical input copies, where authorized sets need recover only one copy, and examines how this setting changes no-cloning limits. It surveys threshold and graph-based feasibility and impossibility results, including Clique Paths, and connects the obstructions to quantum erasure codes while discussing an open coloring conjecture and future directions.

1 Introduction

  • This work initiates the study of quantum secret sharing and quantum error correction when multiple copies of the input are provided, with recovery required for only one copy.For threshold sharing, the generalized no-cloning obstruction rules out schemes when t ≤ n/(k+1), while for general access structures it rules out schemes containing k+1 pairwise disjoint authorized sets.Source: §1 · p. 2, §1.1 · p. 2

1.1 Results Summary

  • For thresholds, a ((n, t, k))-QTSS scheme exists when t > (n-k+1)/2, and a general access structure admits a scheme when its access-structure graph is k-colorable.For thresholds, the graph is the Kneser graph K(n, t), whose k-colorability yields the stated condition.Source: §1.1 · p. 3
  • For k ≥ 2, the Clique Path obstruction rules out threshold schemes when t ≤ (n-1)/k and general schemes when GΓ is non-k-colorable by Clique Paths.The obstruction is stronger than generalized no-cloning: a (k+1)-clique implies it, but the converse does not hold.Source: §1.1 · pp. 3–4
  • For k = 2, the positive and negative threshold bounds match, and the general graph obstruction is equivalent to failure of 2-colorability.In this case, a 2-Clique Path with inconsistent colors is an odd-length cycle; in particular, ((5, 2, 2))-QTSS does not exist.Source: §1.1 · p. 3, §1.2 · p. 6

1.2 Technical Overview

  • The Clique Path proof constructs alternate dealers that assign independent input states to disjoint authorized sets, then uses their equality along adjacent cliques to derive contradictions from inconsistent colors.The proof must avoid assigning copies directly in the original dealer, since identical-copy inputs lie in the symmetric subspace and swapping registers acts identically there.Source: §1.1 · p. 3, §1.2 · pp. 5–6

1.1 Results Summary

  • For k ≥ 2, the Clique Path argument also gives a rate-independent impossibility result for quantum erasure codes.A ((d, n, k))-QErC is a ((n, n-d, k))-QTSS scheme satisfying correctness, and the obstruction uses reconstruction procedures without requiring security.Source: §1.1 · p. 4

1.2 Technical Overview

  • The positive construction partitions the access structure by a graph coloring and applies separate single-copy schemes to the input copies, letting each authorized set reconstruct from its color’s shares.For thresholds, assigning the first k−1 colors by membership in successive users leaves the last color to a single-copy scheme on n−k+1 users, yielding t > (n−k+1)/2; Kneser’s Conjecture shows this approach cannot do better.Source: §1.2 · pp. 4–5
  • For settings with k = 3 or more copies, the authors state that their approach also generalizes, but that it is not tight.Source: §1.2 · p. 7

1.3 Further Discussion

  • The work considers pure-state inputs only; monogamy of entanglement makes producing two identical copies that retain the same entanglement infeasible.The authors nevertheless consider pure-state QSS and error correction useful because many cases concern pure states.Source: §1.3 · p. 8
  • The authors conjecture QSS exists exactly when the access-structure graph is k-colorable; they prove this for k ≤ 2 and leave k ≥ 3 open.The k = 1 case was resolved by.Source: §1.3 · p. 8
  • For k ≥ 3, proving the conjecture via explicit counterexamples faces witness-verification barriers, while extracting an unambiguous coloring from a dealer seems difficult.Unless NP = coNP, non-k-colorability has no polynomial-time-verifiable classical witness; even quantum witnesses require NP ⊆ coQMA.Source: §1.3 · p. 8
  • The authors ask whether multiple copies can raise the correctable Pauli error rate beyond the no-cloning limit of 1/4.Correcting d arbitrary Pauli errors allows correcting 2d erasures; classical codes can approach a bit-flip error rate of 1/2.Source: §1.3 · p. 8
  • In the ((4, 2, 2))-QTSS example, any two users recover one copy, but {2, 3, 4} recovers only one; higher thresholds might enable recovery of more copies.The authors suggest such schemes may need to operate on the joint input system rather than use a union of access structures, or may be impossible.Source: §1.3 · p. 8

1.4 Publication History

  • The paper subsumes and, strengthening their negative results; [C¸GLZR23] gives efficient QSS for efficiently represented access structures but does not study the minimum copies needed.The [C¸GLZR23] scheme assumes post-quantum secure one-way functions and is secure only against computationally bounded adversaries.Source: §1.4 · p. 9

2 Preliminaries

This section defines multi-copy quantum secret sharing and recalls how no-cloning constrains authorized sets. It also introduces the graph-coloring concepts used to analyze access structures.

2.1 Quantum Secret Sharing

  • A multi-copy QSS scheme takes k identical copies of a pure state as input; authorized sets recover the secret correctly, while unauthorized sets learn nothing.The paper assumes pure-state secrets because that assumption is necessary for its multi-copy definition.Source: §2.1 · p. 9
  • For one copy, a QSS scheme exists exactly when the access structure has no two disjoint authorized sets; for thresholds, this is equivalent to n < 2t.Two disjoint authorized sets could reconstruct two copies from one input, violating no-cloning.Source: §2.1 · p. 10
  • With k copies, QSS is impossible if the access structure contains k + 1 pairwise disjoint authorized sets; for thresholds, impossibility follows when n ≥ (k + 1)t.Each disjoint set could reconstruct a copy, producing k + 1 copies from the k inputs.Source: §2.1 · p. 10

2.2 Graph Theory

  • The access structure graph has minimal authorized sets as vertices, with edges between disjoint sets; vertex coloring assigns different colors to adjacent vertices.The chromatic number is the minimum number of colors needed for a valid coloring.Source: §2.2 · p. 10
  • For threshold access structures, the access structure graph is the Kneser graph K(n, t), whose vertices are t-element subsets and whose edges connect disjoint subsets.For m ≥ 2ℓ, its chromatic number is χ(K(m, ℓ)) = m − 2ℓ + 2; when m < 2ℓ, it has no edges and χ = 1.Source: §2.2 · p. 11

3 Positive Results

The positive results decompose multi-copy sharing into single-copy schemes whose access structures are assigned according to graph colorings. This gives a bipartite criterion for two copies and a k-colorability criterion for arbitrary k.

3 Positive Results

  • The union-of-access-structures approach shares k independent input copies through k parallel single-copy schemes, allocating shares so the construction avoids no-cloning conflicts.Any authorized set is assigned to a sub-access structure whose single-copy scheme can reconstruct the secret.Source: §3 · p. 11

3.1 The Dual-Copy Case (k = 2)

  • For two copies, the union-of-access-structures approach realizes a QSS scheme exactly when the access structure graph is bipartite, or 2-colorable.The two color classes define sub-access structures, each without disjoint authorized sets, and one copy is shared according to each class.Source: §3.1 · p. 11

3.2 Generalizing to Arbitrary k

  • For arbitrary k, the union-of-access-structures approach realizes a QSS scheme exactly when the access structure graph is k-colorable.Each color class supplies a single-copy sub-access structure, and the k independent sub-sharings preserve correctness and security.Source: §3.2 · p. 12
  • For threshold QTSS, the access-structure graph is exactly K(n,t); the union-of-access-structures approach realizes a scheme iff K(n,t) is k-colorable, requiring χ(K(n,t)) ≤ k.Source: §3.2 · p. 12
  • The combinatorial bound is n < 2t for k = 1, while adding k copies allows the network size to scale linearly with k without violating no-cloning constraints.The paper presents this as the k-copy extension of the single-copy bound.Source: §3.2 · p. 12

4 Negative Results

This section develops and applies a color-propagation obstruction to many-copy quantum secret sharing, including threshold impossibility in a specified regime and a feasibility characterization for two copies. It also identifies the smallest undecided case and explains why neither the Clique Path obstruction nor the union-of-access-structures approach settles it.

4.4 The Clique Path Obstruction

  • Color propagation starts from a labeled k-clique and forces color i on a set disjoint from the clique’s other k − 1 sets; a set assigned two colors yields an inconsistent path.The k − 1 required neighbors must belong to the same already-reached clique.Source: §4 · p. 12, §4.4 · pp. 15–16

4.1 Canonical Form

  • The proof puts dealing and reconstruction in canonical isometric form, with disjoint authorized sets’ reconstruction unitaries acting on disjoint registers and commuting.This yields a unitary reconstruction with a d-dimensional output register and a residue factor.Source: §4.1 · p. 13

4.2 Labeled Cliques and the Residual State

  • For each labeled k-clique, reconstructing all k copies leaves a fixed residual state independent of the secret, while each set’s index identifies the input it recovers.Alternate dealers for labeled cliques agree on identical inputs, and their index-specific recovery works even for nonidentical inputs.Source: §4.2 · pp. 13–14

4.3 The Substitution Lemma

  • Labeled cliques differing by one authorized-set substitution have alternate dealers that agree on all inputs.The substitution replaces one set at an index while leaving the other k − 1 sets fixed.Source: §4.3 · p. 14

4.4 The Clique Path Obstruction

  • An inconsistent Clique Path rules out every QSS scheme for a monotone access structure containing the path’s authorized sets.The obstruction uses no authorized sets beyond those named along the path and applies beyond threshold structures.Source: §4.4 · pp. 15–16
  • For any monotone access structure, a two-copy QSS scheme exists if and only if its access structure graph is bipartite.For k = 2, an inconsistent Clique Path exists exactly when the graph contains an odd cycle.Source: §4.4 · p. 16

4.5 The Clique Path Obstruction Applied to Threshold Structures

  • No ((n, t, k))-QTSS scheme exists for n ≥ kt + 1 and k ≥ 2.At n = kt + 1, any labeled k-clique can be connected to one swapping its first two sets, making the path inconsistent; larger n reduces to this case.Source: §4.5 · p. 17

4.6 What the Obstruction Does Not Decide

  • Combining Theorem 23 with Theorem 42, the supplied threshold conclusion identifies n ≥ kt + 1 as unrealizable.The provided passage states this bound without specifying what the combined results decide outside it.Source: §4.6 · p. 17
  • The bounds meet for every t when k = 2; otherwise, the middle range is nonempty exactly when (k − 2)(t − 1) ≥ 1, leaving ((6, 2, 3))-QTSS the smallest undecided case.Source: §4.6 · p. 17
  • For ((6, 2, 3))-QTSS, labeled 3-cliques are perfect matchings, so no substitutions are available, Clique Paths have length zero, and the obstruction does not apply.More generally, an inconsistent path for threshold structures requires k disjoint authorized sets and room to vary one, which means n ≥ kt + 1; Theorem 42 marks where substitution becomes possible.Source: §4.6 · p. 17
  • Although GΓ2,6 = K(6, 2) has chromatic number 4 > 3, ruling out union-of-access-structures schemes, this does not yield an inconsistent Clique Path.Closing the gap requires either a construction beyond that scheme type or an impossibility argument that does not rely on substitutions.Source: §4.6 · pp. 17–18
Loading 2610.00441v1…