arXiv:2610.00441
Quantum Secret Sharing and Error Correction vs No-Cloning
Steven Chien, Ishani Mukherjee, Mark Zhandry
Abstract
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.
AI Summary
The paper studies quantum secret sharing with $k$ identical copies of an unknown pure state as input, requiring each authorized set to recover only one copy. It asks whether feasibility is characterized by generalized no-cloning, which excludes $k+1$ pairwise disjoint authorized sets and, for thresholds, excludes $t\le n/(k+1)$. A construction shares the copies independently using single-copy schemes. It works whenever the graph whose vertices are minimal authorized sets, with edges joining disjoint sets, is $k$-colorable. For threshold structures this is a Kneser graph, giving feasibility when $n\le 2t-2+k$, equivalently $t>(n-k+1)/2$. A separate “Clique Path” obstruction gives impossibility beyond no-cloning. Ordered $k$-cliques specify alternate dealers that assign independent input states to disjoint authorized sets. A substitution lemma shows these dealers remain identical when one set is replaced while preserving disjointness; a path assigning the same set two input indices yields a contradiction. This excludes thresholds with $n\ge kt+1$, or $t\le(n-1)/k$. For $k=2$, the obstruction is equivalent to an odd cycle, so bipartiteness exactly characterizes feasibility for arbitrary access structures, and threshold schemes exist exactly when $n\le2t$. The obstruction uses correctness alone and also excludes $k$-copy erasure codes correcting $d\ge n(k-1)/k+1/k$ erasures. The setting requires exact recovery of pure-state inputs, not preservation of external entanglement, and does not address efficiency. For $k\ge3$, the bounds leave a gap; the smallest undecided threshold case is $(n,t,k)=(6,2,3)$. Whether $k$-colorability characterizes feasibility remains conjectural.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.