Quantum Secret Sharing with Graph States

We study the graph-state-based quantum secret sharing protocols [24,17] which are not only very promising in terms of physical implementation, but also resource efficient since every player’s share is composed of a single qubit. The threshold of a graph-state-based protocol admits a lower bound: for any graph of order

n

, the threshold of the corresponding

n

-player protocol is at least 0.506

n

. Regarding the upper bound, lexicographic product of the

C

5

graph (cycle of size 5) are known to provide

n

-player protocols which threshold is

n

 − 

n

0.68

. Using Paley graphs we improve this bound to

n

 − 

n

0.71

. Moreover, using probabilistic methods, we prove the existence of graphs which associated threshold is at most 0.811

n

.Albeit non-constructive, probabilistic methods permit to prove that a random graph

G

of order

n

has a threshold at most 0.811

n

with high probability. However, verifying that the threshold of a given graph is acually smaller than 0.811

n

is hard since we prove that the corresponding decision problem is NP-Complete.These results are mainly based on the graphical characterization of the graph-state-based secret sharing properties, in particular we point out strong connections with domination with parity constraints.