Sylvain Gravier

Jérôme Javelle

Mehdi Mhalla

Simon Perdrix

Quantum Secret Sharing with Graph States

Keywords: Quantum Information, Graph Theory, Quantum Cryptography, NP-Completeness

 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.506n. Regarding the upper bound, lexicographic product of the C5 graph (cycle of size 5) are known to provide n-player protocols which threshold is nn 0.68 . Using Paley graphs we improve this bound to nn 0.71 . Moreover, using probabilistic methods, we prove the existence of graphs which associated threshold is at most 0.811n. Albeit non-constructive, probabilistic methods permit to prove that a random graph G of order n has a threshold at most 0.811n with high probability. However, verifying that the threshold of a given graph is acually smaller than 0.811n 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.

Introduction

Quantum secret sharing

Secret sharing schemes were independently introduced by Shamir [START_REF] Shamir | How to share a secret Communications of the[END_REF] and Blakley [START_REF] Blakley | Safeguarding cryptographic keys[END_REF] and extended to the quantum case by Hillery [START_REF] Hillery | Quantum Secret Sharing[END_REF] and Gottesman [START_REF] Cleve | How to Share a Quantum Secret[END_REF][START_REF] Gottesman | Theory of quantum secret sharing[END_REF]. A quantum secret sharing protocol consists in encoding a secret into a multipartite quantum state. Each of the players of the protocol has a share which consists of a subpart of the quantum system and/or classical bits. Authorized sets of players are those that can recover the secret collectively using classical and quantum communications. A set of players is forbidden if they have no information about the secret. The encrypted secret can be a classical bit-string or a quantum state.

A threshold ((k, n)) quantum secret sharing protocol [START_REF] Hillery | Quantum Secret Sharing[END_REF][START_REF] Cleve | How to Share a Quantum Secret[END_REF][START_REF] Gottesman | Theory of quantum secret sharing[END_REF] is a protocol by which a dealer distributes shares of a quantum secret to n players such that any subset of at least k players is authorized, while any set of less than k players is forbidden. It is assumed that the dealer has only one copy of the quantum secret he wants to share. A direct consequence of the no-cloning theorem [START_REF] Wootters | A single quantum cannot be cloned[END_REF] is that no ((k, n)) quantum secret sharing protocol can exists when k ≤ n 2otherwise two distinct sets of players can reconstruct the secret implying a cloning of the quantum secret. On the other hand, for any k > n 2 a ((k, n)) protocol has been introduced in [START_REF] Cleve | How to Share a Quantum Secret[END_REF] in such a way that the dimension of each share is proportional to the number of players. The unbounded size of the share is a serious drawback of the protocol, as a consequence several schemes of quantum secret sharing using a bounded amount of resources for each player have been introduced [START_REF] Markham | Graph states for quantum secret sharing[END_REF][START_REF] Broadbent | The GHZ state in secret sharing and entanglement simulation[END_REF][START_REF] Keet | Quantum secret sharing with qudit graph states[END_REF].

Graph-state-based quantum secret sharing

In [START_REF] Markham | Graph states for quantum secret sharing[END_REF] a quantum secret sharing scheme using particular quantum states, called graph states [START_REF] Hein | Entanglement in graph states and its applications[END_REF], and such that every player receives a single qubit, has been introduced. The graph-state-based protocols are also of interest because graph states are at the forefront in terms of implementation and have emerged as a powerful and elegant family of entangled states [START_REF] Hein | Multi-party entanglement in graph states[END_REF][START_REF] Raussendorf | A one-way quantum computer[END_REF].

As introduced in [START_REF] Markham | Graph states for quantum secret sharing[END_REF], only one non-trivial graph (the cycle of size 5) corresponds to a threshold protocol. In [START_REF] Javelle | New protocols and lower bound for quantum secret sharing with graph states[END_REF], the graph-state-based protocol has been extended to ensure that any graph correspond to a threshold protocol. Given a graph G, the threshold of the corresponding protocol is κ Q (G). This threshold is characterized graphically by the notion of weak odd domination. In [START_REF] Javelle | New protocols and lower bound for quantum secret sharing with graph states[END_REF], it has been proved that for any graph G of order n, κ Q (G) > 0.506n, refining the no-cloning theorem. This bound is not known to be tight. All known constructions of graph-state-based quantum secret sharing protocols lead to quasi-uninimity protocols (i.e. the threshold is no(n), where n is the number of players). The best known construction is based on the lexicographic product of graphs, and leads to protocols with a threshold nn 0.68 [START_REF] Javelle | New protocols and lower bound for quantum secret sharing with graph states[END_REF].

We improve this threshold to nn 0.71 using Paley graphs. Moreover, we show, using probabilistic methods, that for any (large enough) n there exists a graph G of order n such that κ Q (G) ≤ 0.811n. The proof is not constructive, but it crucially shows that graph-state based quantum secret sharing protocols are not restricted to quasi-unanimity thresholds. We actually prove that almost all the graphs have such a 'small' κ Q : if one picks a random graph G of order n (every edge occurs with probability 1/2), then κ Q (G) ≤ 0.811n with probability greater than 1 -1 n . We also prove that, given a graph G and a parameter k, deciding whether κ Q (G) ≥ k is NP-complete. As a consequence, one cannot efficiently verify that a particular randomly generated graph has actually a 'small' κ Q .

Combinatorial properties of graph states.

The development and the study of graph-based protocols [START_REF] Markham | Graph states for quantum secret sharing[END_REF][START_REF] Keet | Quantum secret sharing with qudit graph states[END_REF][START_REF] Javelle | New protocols and lower bound for quantum secret sharing with graph states[END_REF][START_REF] Sarvepalli | Non-Threshold Quantum Secret Sharing Schemes in the Graph State Formalism eprint[END_REF][START_REF] Javelle | Classical versus Quantum Graph-based Secret Sharing[END_REF] have already pointed out deep connections between graph theory and quantum information theory. For instance, it has been shown [START_REF] Kashefi | Information flow in secret sharing protocols[END_REF] that a particular notion of flow [START_REF] Danos | Determinism in the one-way model[END_REF][START_REF] Browne | Generalized ow and determinism in measurement-based quantum computation[END_REF][START_REF] Mhalla | Finding optimal flows effciently[END_REF][START_REF] Mhalla | Which graph states are useful for quantum information processing? In Theory of Quantum Computation, Communication and Cryptography[END_REF] in the underlying graph captures the flow, during the protocol, of the information contained in the secret from the dealer -who encodes the secret and sends the shares -to the authorized sets of players. The results presented in this paper contribute to these deep connections: we show that weak odd domination is a key concept for studying the properties of graph-based quantum secret sharing protocols.

The study of graph-state-based protocols also contributes, as a by-product, to a better understanding of the combinatorial properties of the graph states. The graph state formalism is a very powerful tool which is used in several areas of quantum information processing. Graph states provide a universal resource for quantum computing [START_REF] Raussendorf | A one-way quantum computer[END_REF][START_REF] Van Den Nest | Universal resources for measurement-based quantum computation[END_REF][START_REF] Mhalla | Graph States, Pivot Minor, and Universality of (X,Z)measurements[END_REF] and are also used in quantum correction codes [START_REF] Schlingemann | Quantum error-correcting codes associated with graphs[END_REF][START_REF] Beigi | Graph concatenation for quantum codes[END_REF] for instance. They are also used to define pseudo-telepathy games [START_REF] Anshu | Pseudo-telepathy games and genuine NS n-way nonlocality using graph states[END_REF]. Moreover, they are very promissing in terms of physical implementation [START_REF] Prevedel | High-speed linear optics quantum computing using active feed-forward[END_REF][START_REF] Walther | Experimental one-way quantum computing[END_REF]. As a consequence, progresses in the knowledge of the fundamental properties of graph states can potentially impact not only quantum secret sharing but a wide area of quantum information processing.

2 Graph state secret sharing

Graph states

For a given graph G = (V, E) with vertices v 1 , . . . , v n , the corresponding graph state |G is a n-qubit quantum state defined as

|G = 1 √ 2 n x∈{0,1} n (-1) q(x) |x
where q(x) is the number of edges in the induced subgraph

G[x] = ({v i ∈ V | x i = 1}, {(v i , v j ) ∈ E | x i = x j = 1}).
Graph states have the following fundamental fixpoint property: given a graph G, for any vertex u ∈ V ,

X u Z N (u) |G = |G where N (u) is the neighborhood of u in G, X = |x → |x , Z = |x → (-1)
x |x are one-qubit Pauli operators and Z A = u∈A Z u is a Pauli operator acting on the qubits in A.

Sharing a classical secret using a graph state

Graph-state-based classical sharing protocols have been introduced in [START_REF] Markham | Graph states for quantum secret sharing[END_REF]. In these protocols a classical secret is shared by means of a quantum state. The authorized sets of players are those which are satisfying the following graphical property, called c-accessibility:

Definition 1. Given a graph G = (V, E), a set B ⊆ V of vertices is c- accessible if ∃D ⊆ B such that |D| = 1 mod 2 and Odd(D) ⊆ B, where Odd(D) := {v ∈ V | |N (v) ∩ D| = 1 mod 2}.
Given a graph G = (V, E) of order n, the graph state-based protocol for sharing a classical secret s ∈ {0, 1} among n players is defined as:

|G D | + j∈D∪Odd(D) s j mod 2
where |G D | is the size (i.e. the number of edges) of the subgraph induced by D.

Proof of the protocol [Sketch]. The proof that the reconstructed secret is the actual secret relies on the fact that for any D ⊆ V , (-1)

|G D | X D Z Odd(D) |G = |G , as a consequence (-1) |G D | X D Z Odd(D) |G s = (-1) s |G s , so a measure- ment according to X D Z Odd(D) produces the classical outcome s + |G D | mod 2.
Finally, the non local measurement according to X D Z Odd(D) can be decomposed into local measurements such that the parity of the local measurements is the same as the outcome of the non-local measurement. ✷ Sharing a classical bit can be done using a classical scheme, like [START_REF] Shamir | How to share a secret Communications of the[END_REF], instead of using a quantum state. Moreover the above protocol can be simulated by purely classical graph-based schemes [START_REF] Javelle | Classical versus Quantum Graph-based Secret Sharing[END_REF]. However, the study of the graphstate-based classical secret sharing, and in particular the characterization of their authorized structure are essential for the next sections where the sharing of a quantum secret is considered.

The graph-state-based classical secret sharing protocol is perfect, i.e. any set of players is either c-accessible, or has no information about the secret [START_REF] Javelle | New protocols and lower bound for quantum secret sharing with graph states[END_REF].

The proof of perfectness has two steps: using graph theory arguments, one can prove that if a set B of players is not c-accessible in a graph, then B is a WOD set (WOD stands for weak odd domination), i.e. there exists C ⊆ V \ B such that B ⊆ Odd(C). The second part of the proof consists in proving that the reduced density matrix of a WOD set of players does not depend on the secret, thus the players in this set have no information about the secret [START_REF] Kashefi | Information flow in secret sharing protocols[END_REF].

Since any subset of a WOD set is a WOD set and that any superset of a caccessible is a c-accessible set, the important quanties for a graph state-based classical secret sharing protocol are the largest WOD set and the smallest c-accessible set by considering the following quantities:

Definition 2. For a given graph G, let κ(G) = max B WOD |B| κ ′ (G) = min B c-accessible

|B|

For instance, for a C 5 graph, i.e. a cycle of size 5, κ(C 5 ) = 2 and κ ′ (C 5 ) = 3. So it means that any set of at least 3 players can recover the secret whereas any set of at most 2 players have no information about the secret. In other words, the C 5 graph induces a threshold protocol. Another example is the complete graph

K n . Since κ(K n ) = n -1 and κ ′ (K n ) = n, complete graphs induce unanimity protocol.
We consider a third example: for any p, q ∈ N, let G p,q be the complete q-partite graph where each independent set is of size p: the vertices of G p,q are pairs (i, j), with 0 ≤ i < p, 0 ≤ j < q, two vertices (i, j), (i ′ , j ′ ) are connected if and only if j = j ′ . G p,q is of order n = pq. Lemma 1. For any p, q ∈ N,

κ(G p,q ) = n -p and κ ′ (G p,q ) = q if q = 1 mod 2 κ(G p,q ) = max(n -p, n -q) and κ ′ (G p,q ) = p + q + 1 if q = 0 mod 2 Proof. If q = 1 mod 2 -[κ(G p,q ) ≥ n -p]:
The subset B composed of all the vertices but a maximal independent set (MIS) -i.e. an independent set of size p -is in the odd neighborhood of each vertex in V \B. Therefore B is WOD and

|B| = n-p. Consequently κ(G p,q ) ≥ n -p.
-[κ(G p,q ) ≤ np]: Any set B such that |B| > np contains at least one vertex from each of the q MIS, i.e. a clique of size q. Let D ⊆ B be such a clique of size |D| = q = 1 mod 2. Every vertex v outside D is connected to all the elements of D but the one in the same MIS as v. Thus Odd(D) = ∅. As a consequence, B is non-WOD.

-[κ ′ (G p,q ) ≤ q]: B composed of one vertex from each MIS is a non-WOD set (see previous item).

-[κ ′ (G p,q ) ≥ q]: If |B| < q then B does not intersect all the MIS of size p, so B is in the odd neighborhood of each vertex of such a MIS. So B is WOD.

If q = 0 mod 2 -[κ(G) ≥ max(n -p, n -q)]: For κ(G) ≥ n -p, see previous lemma.
The subset B composed of all the vertices but a clique of size q (one vertex from each MIS) is in the odd neighborhood of

V \ B. Indeed each vertex of B is connected to q -1 = 1 mod 2 vertices of V \ B. So B of size n -q is WOD, as a consequence κ(G) ≥ n -q. -[κ(G) ≤ max(n -p, n -q)]: Any set B such that |B| > max(n -p, n -q)
contains at least one vertex from each MIS and moreover it contains a MIS S of size q. Let D ⊆ B \ S be a clique of size q -1 = 1 mod 2. Every vertex u in V \B is connected to all the vertices in D but one, so Odd(D) ⊆ B.

-[κ ′ (G) ≤ p + q -1]: Let S be an MIS. Let B be the union of S and of a clique of size q. Let D = B \ S. |D| = q -1 = 1 mod 2. Every vertex u in V \ B is connected to all the vertices of D but one, so Odd(D) ⊆ B.

-

[κ ′ (G) ≥ p + q -1]: Let |B| < p + q -1. If B
:= Z V |G . 2. Distribution. Player i's share is qubit i of α |G 0 + β |G 1 . 3. Reconstruction. Let B be a c-accessible set of players such that V \ B is WOD. So ∃C, D ⊆ B such that V \ B ⊆ Odd(C), |D| = 1 mod 2, and Odd(D) ⊆ B.
-Players in B choose u ∈ B who will reconstruct the secret. Every player in B \ {u} sends his qubit to u.

u applies the unitary 1

√ 2 I U -U I where U = (-1) |G D | X D Z Odd(D)
on the (|B| + 1)-qubit system composed of an ancillary qubit |0 +|1 √ 2

and the received qubits. The resulting state of the (n + 1)-qubit system is

α |0 ⊗ |G 0 + β |1 ⊗ |G 1 -u applies the unitary I 0 0 U ′ where U ′ = (-1) |G C | X C Z V \Odd(C)
. The resulting state of the (n + 1)-qubit system is

(α |0 + β |1 ) ⊗ |G
Thus the secret is reconstructed on the first qubit.

In this protocol of graph-state based quantum secret sharing, the authorized sets of players are c-accessible such that their complementary sets are WOD. Intuitively the c-accessibility allows the players to extend the superposition to an ancillary qubit (i.e. to transform the state

α |G 0 + β |G 1 to α |0 ⊗ |G 0 + β |1 ⊗ |G 1 )
. Notice that if the secret is classical (either α or β is equal to 0), then the state of the ancillary qubit is nothing but the secret. In the general case, when the secret is a superposition, the ancillary qubit is entangled with the rest of the system. The second requirement, namely that the complementary set V \B is WOD allows the players in B to make the ancillary qubit separable from the rest of system, producing the state (α |0 +β |1 )⊗|G .

Since authorized players are c-accessing such that their complementary are WOD, the important quantity for graph-state based quantum secret sharing protocols is

κ Q (G) = max(κ(G), n -κ ′ (G)) Indeed any set B of players such that |B| > κ Q (G) is c-accessing since |B| > κ(G) and its complementary set is WOD since |V \ B| < κ ′ (G).

Threshold schemes

Notice that the graph-state based quantum secret sharing are not perfect in general. One can prove that the authorized sets are those which are c-accessible such that their complementary set is WOD [START_REF] Javelle | New protocols and lower bound for quantum secret sharing with graph states[END_REF]. On the otherhand, if a set is WOD and its complementary is c-accessible, then such a set has no information about the secret. But all sets which are not of that kind, for instance those such that both B and V \ B are c-accessible, have some partial information about the secret.

To make the protocol perfect, and even to obtain a threshold protocol, a variant of the previous protocol has heen introduced in [START_REF] Javelle | New protocols and lower bound for quantum secret sharing with graph states[END_REF]. The idea is to add a one-time padding of the secret to ensure that the sets of players which size is below the threshold have no information about the secret. To implement this one-time padding the previous protocol is coupled with a classical protocol for sharing the classical key of the one-time padding.

Given a graph G and an integer k > κ Q (G) the threshold graph statebased protocol for sharing a quantum secret |φ = α |0 +β |1 among n players is:

1. Encryption. The dealer chooses uniformly at random two bits p, q ∈ {0, 1} and applies X p Z q to the secret. The resulting state is α |p + β(-1) q |1p . Then, the dealer prepares the quantum state α |G p + (-1) q β |G 1-p . 2. Distribution. Player i's share is qubit i of α |G p + (-1) q β |G 1-p .

Moreover p and q are shared among the n players using a classical secret sharing protocol (not described here) with threshold k.

Reconstruction. For any

B such that |B| ≥ k, since |B| > κ Q (G), ∃C, D ⊆ B such that V \B ⊆ Odd(C), |D| = 1 mod 2, and Odd(D) ⊆ B.
-Players in B choose u ∈ B who will receive the secret. Every player in B \ {u} sends his qubit to u.

u applies 1

√ 2 I U -U I where U = (-1) |G D | X D Z Odd(D)
and then

I 0 0 U ′ where U ′ = (-1) |G C | X C Z V \Odd(C)
. The resulting state is

(α |p + β(-1) q |1 -p ) ⊗ |G
-Using the classical secret sharing protocol, the players in B reconstructs the classical bits p and q. -u applies Z q X p to the ancillary qubit. The resulting state is

α |0 + β |1 .
This protocol is a ((k, n)) threshold quantum secret sharing protocol. Indeed for any set of at most k -1 players, they have no information about the classical keys p and q which garantees that they have no information about the quantum secret. For the sets of at least k players, since k > κ Q (G), they can reconstruct the state α |p + β(-1) q |1p , like in the previous protocol, moreover they have access to the keys p and q, so they can reconstruct the quantum secret.

Lower bound and quasi-unanimity protocols

Graph-state-based secret sharing protocols are very promising in terms of physical implementations [START_REF] Prevedel | High-speed linear optics quantum computing using active feed-forward[END_REF][START_REF] Walther | Experimental one-way quantum computing[END_REF], moreover, contrary to the family of quantum secret sharing introduced by Gottesman [START_REF] Gottesman | Theory of quantum secret sharing[END_REF], the size of each quantum share does not depend on the number of players. The drawback is that some threshold protocols cannot be implemented using a graph-state-based protocol:

Lemma 2 (Lower bound [START_REF] Javelle | New protocols and lower bound for quantum secret sharing with graph states[END_REF]). For any graph G of order n > 5,

κ Q (G) > 0.506n
Notice that for any quantum secret sharing scheme, if there is a threshold, this threshold must be larger than n/2. This bound [START_REF] Gottesman | Theory of quantum secret sharing[END_REF] is a direct application of the no-cloning theorem: if k < n/2 then two distinct sets of k players can recover the quantum secret, leading to a cloning of the quantum secret. The lower bound for graph-state-based protocols is not known to be tight.

Regarding the upper bound, all known constructions of graph-state-based quantum secret sharing protocols are quasi-unanimity protocols. In the next section, we will prove using non constructive methods that for any n there exists a graph G of order n such that κ Q (G) < 0.811n.

Thanks to lemma 1, for any p, q ∈ N, the complete q-partite graph G p,q of order n = pq (see section 2.2), κ Q (G p,q ) = max(np, nq). Thus, for any square number n, κ

Q (G √ n, √ n ) = n - √ n.
The corresponding secret sharing protocol is a quasi-unanimity protocol since the ratio k/n tends to 1 as n tends to infinity. The best known construction is based on the lexicographic product of graphs:

Given G = (V, E) G • G = (V ′ , E ′ ) is defined as V ′ := V × V and E ′ := {((u 1 , u 2 ), (v 1 , v 2 )) | (u 1 , v 1 ) ∈ E or (u 1 = v 1 ∧ (u 2 , v 2 ) ∈ E)}.

Lemma 3 ([17]). For any graph G, of order

n κ Q (G • G) ≤ 2n.κ Q (G) -κ Q (G) 2
Graphs-state-based quantum secret sharing protocols with threshold nn 0.68 , where n is the number of players, can be obtained using inductively the lexicographic product of C 5 graph (cycle on five vertices) [START_REF] Javelle | New protocols and lower bound for quantum secret sharing with graph states[END_REF].

In fact, the C 5 graph is a particular case of a family of graphs called Paley graphs, that have been used recently in [START_REF] Javelle | On the Minimum Degree up to Local Complementation: Bounds and Complexity[END_REF] to provide the best known upper bound for the minimum degree up to local complementation which can be defined as min D⊆V,D =∅ |D ∪ Odd(D)| -1.

For any prime p such that p = 1 mod 4, the Paley graph P al p is a graph on p vertices where each vertex is an element of F p . There is an edge between two vertices i and j if and only if ij is a square in F p .

Graphs-state-based quantum secret sharing protocols with n players and threshold n-n 0.71 is obtained using the lexicographic product of P al 29 graphs. This is, up to our knowledge, the best known constructive threshold. Theorem 1. For any i > 0,

κ Q (P al 29 • i ) ≤ n -n log(11)
log (29) ≈ nn 0.71

where P al Proof. κ Q (P al 29 ) is computed taking benefits of the symmetries of the Paley graphs (strong regularity, vertex transitivity, edge transitivity, self complementarity). The evolution with the lexicographic product is given by lemma 3.

✷

It is significant and interesting to notice that the conjecture of the existence of an infinite family of Paley graphs leading to non quasi-unanimity protocols is related to the Bazzi-Mitter conjecture [START_REF] Bazzi | Some randomized code constructions from group actions[END_REF].

3 Graphs with small κ Q In this section, we prove the existence of graph-state-based secret sharing protocols which are not quasi-unanimity. More precisely, using the asymmetric Lovász Local Lemma [START_REF] Lovász | Problems and results on 3-chromatic hypergraphs and some related questions[END_REF] we show that there exists an infinite family of graphs {G i } such that κ Q (G i ) ≤ 0.811n i where n i is the order of G i . Moreover, we prove that a random graph G(n, 1/2) (graph on n vertices where each pair of vertices have probability 1/2 to have an edge connecting them) satisfies κ Q (G(n, 1/2)) ≤ 0.811n with high probability.

First we prove the following lemma:

Lemma 4. Given k and G = (V, E), if for any non empty set D ⊆ V , |D ∪ Odd(D)| > n -k and |D ∪ (V \ Odd(D))| > n -k then κ Q (G) < k. Proof. Since ∀D ⊆ V |D ∪ Odd(D)| > n -k, κ ′ (G) > n -k. Let B ⊆ V , |B| ≥ k, if B is not WOD then ∃C ⊆ V \ B such that B ⊆ Odd(C), so (V \ Odd(C)) ⊆ V \ B which implies |C ∪ (V \ Odd(C))| ≤ n -k. ✷
We use the asymmetric form of the Lovász Local Lemma that can be stated as follows:

Theorem 2 (Asymmetric Lovász Local Lemma, no independency case). Let A = {A 1 , • • • , A n }

be a set of bad events in an arbitrary probability space. If for every

A i there exists w(A i ) ∈ [0, 1) such that P r(A i ) ≤ w(A i ).p, where p = A j ∈A (1 -w(A j )) then P r(A 1 , • • • , A n ) ≥ p Theorem 3.
There exists an infinite family of graphs {G i } such that κ Q (G i ) ≤ 0.811n i where n i is the order of G i .

Proof. Let G(n, 1/2) = (V, E) be a random graph. We use the asymmetric Lovász local lemma to show that the probability that for all non empty set c)n is positive for some constant c. This ensures by Lemma 4 that κ Q (G) < cn.

D ⊆ V |D ∪ Odd(D)| > (1 -c)n and |D ∪ (V \ Odd(D))| > (1
We consider the "bad" events

A D : |Odd(D) ∪ D| ≤ (1 -c)n and A ′ D : |Odd(D)∪(V \Odd(D))| ≤ (1-c)n. When |D| > (1-c)n, P r(A D ) = P r(A ′ D ) = 0,
therefore the previous events are defined for all D such that |D| ≤ (1c)n.

For all D such that |D| ≤ (1c)n, we want to get an upper bound on P r(A D ). Let |D| = dn for some d ∈ (0, 1c]. For all u ∈ V \ D, P r("u ∈ Odd(D)") = 1 2 . If D is fixed, the events "u ∈ Odd(D)" when u is outside D are independent. Therefore, if the event A D is true, any but at most (1-c-d)n vertices outside D are contained in Odd(D). There are (1-d)n vertices outside D,

then P r(A D ) = 1 2 (1-d)n (1-c-d)n k=0 (1-d)n k ≤ 1 2 (1-d)n 2 (1-d)nH( 1-c-d 1-d ) = 2 (1-d)n[H( c 1-d )-1] where H : t → -t log 2 (t) -(1 -t) log 2 (1 -t) is the binary entropy function. Similarily, P r(A ′ D ) ≤ 2 (1-d)n[H( c 1-d )-1] .
We consider that all the events can be dependent. For any

D ⊆ V such that 0 < |D| ≤ (1 -c)n, we define w(A D ) = w(A ′ D ) = 1 r( n |D| )
. First, we

verify that P r(A D ) ≤ w(A D ) D ′ ⊆V,|D|≤(1-c)n (1 -w(A D ′ ))(1 -w(A ′ D ′ ))
. The product of the right-hand side of the previous equation can be written p =

(1-c)n |D ′ |=1 1 -1 r( n |D ′ | ) 2( n |D ′ | ) = (1-c)n |D ′ |=1 1 -1 r( n |D ′ | ) r( n |D ′ | ) 2 r
. The function

f : x → 1 -1 x x verifies f (x) ≥ 1 4 when x ≥ 2, therefore p ≥ 1 4 2 r (1-c)n = 2 -4(1-c)n r for any r ≥ 2. Thus, it is sufficient to have 2 (1-d)n[H( c 1-d )-1] ≤ 1 r( n dn ) 2 -4(1-c)n r . Rewriting this inequality gives r n dn 2 (1-d)n[H( c 1-d )-1]+ 4(1-c)n r ≤ 1.
Thanks to the bound n dn ≤ 2 nH( dn n ) and after applying the logarithm function and dividing by n, it is sufficient that (1

-d) H c 1-d -1 + H(d) + 4(1-c) r + log 2 r n ≤ 0.
If we take r = n, the condition becomes asymptotically

(1 -d) H c 1-d -1 + H(d) ≤ 0.
Numerical analysis shows that this condition is true for any c > 0.811 and for all d ∈ (0, 1c]. Thus, thanks to the Lovász Local Lemma, for any -c)n > 0, therefore there exists an infinite family of graphs {G i } such that κ Q (G i ) ≤ 0.811n i where n i is the order of G i for n i ≥ N 0 for some N 0 ∈ N.

c > 0.811, P r(κ Q (G) < cn) ≥ p ≥ 1 4 2 r (1
✷

Recently [START_REF] Sarvepalli | Non-Threshold Quantum Secret Sharing Schemes in the Graph State Formalism eprint[END_REF], Sarvepalli proved that quantum secret sharing protocols based on graph states are equivalent to quantum codes. Combining this result with the Gilbert Varshamov bounds on quantum stabilizer codes [START_REF] Feng | A finite Gilbert-Varshamov bound for pure stabilizer quantum codes[END_REF], we can provide an alternative proof of theorem 3. However, we believe the use of the Lovász Local Lemma offers several advantages: the proof is a purely graphical proof with a potential extension to the construction of good quantum secret sharing schemes using the recent development in the algorithmic version [START_REF] Moser | A constructive proof of the general Lovász Local Lemma[END_REF] of the Lovász Local Lemma. Moreover, the use of the probabilistic methods already offers a way of generating good quantum secret sharing protocols with high probability by adjusting the parameters of the Lovász Local Lemma: Theorem 4. There exists n 0 such that for any n > n 0 , a random graph G(n, 1 2 ) has a κ Q smaller than 0.811n with high probability:

P r κ Q (G(n, 1 2
)

) < 0.811n ≥ 1 - 1 n
Proof. The proof of the theorem is done as in the proof of theorem 3, by taking c = 0.811 and r = 4 ln(2

)(1 -c)n 2 . It guarantees that for n ≥ 26681, (1 -d) H c 1-d -1 + H(d) + 4(1-c) r + log 2 r n ≤ 0. Thus, for any D ⊆ V such that 0 < |D| ≤ (1 -c)n, P r(A D ) ≤ w(A D ) D ′ ⊆V,|D|≤(1-c)n (1 - w(A D ′ ))(1 -w(A ′ D ′ ))
. Moreover the probability that none of the bad events occur is

P r κ Q (G(n, 1 2 )) < 0.811n ≥ 1 4 2 r (1-c)n = 1 4 1 2n ln(2) = e -1 n ≥ 1 -1 n . ✷

Complexity of computing the threshold of graph-state-based protocols

According to Theorem 4, a random graph G(n, 1/2) induces a secret sharing protocol with a threshold smaller than 0.811n with high probability:

P r κ Q (G(n, 1 2
)) < 0.811n ≥ 1 -1 n . So even if the Lovász local Lemma is not constructive, one can pick uniformly at random a graph G of order n, if κ Q (G) ≥ 0.811n, he picks another one and so on. Since the probability that κ Q (G) ≥ 0.811n this procedure seems to be efficient, however the crucial point here is the complexity of deciding whether κ Q (G) ≥ 0.811n or not. In this section we consider the complexity of this problem and show that the problem is NP-complete (Theorem 10). To prove this result we introduce several bounds and complexity results on weak odd domination, and in particular on the quantities κ(G), κ ′ (G) and κ Q (G) of a graph G.

First, we show that the sum of κ(G) and κ ′ (G) is always greater than the order of the graph G. The proof is based on the duality property that the complement of a non-WOD set in G is a WOD set in G, the complement graph of G.

Lemma 5. Given a graph G = (V, E), if B ⊆ V is not a WOD set in G then V \ B is a WOD set in G. Proof. Let B be a non-WOD set in G. ∃D ⊆ B such that |D| = 1 mod 2 and Odd G (D) ⊆ B. As a consequence, ∀v ∈ V \ B, |N G (v) ∩ D| = 0 mod 2. Since |D| = 1 mod 2, ∀v ∈ V \ B, |N G (v) ∩ D| = 1 mod 2. Thus, V \ B is a WOD set in G. ✷ Theorem 5. For any graph G of order n, κ ′ (G) + κ(G) ≥ n.
Proof. There exists a non-WOD set

B ⊆ V such that |B| = κ ′ (G). According to Lemma 5, V \ B is WOD in G, so n -|B| ≤ κ(G), so n -κ ′ (G) ≤ κ(G). ✷
For any vertex v of a graph G, its (open) neighborhood N (v) is a WOD set, whereas its closed neighborhood (i.e. N [v] = {v} ∪ N (v)) is a non-WOD set, as a consequence:

κ(G) ≥ ∆ κ ′ (G) ≤ δ + 1
where ∆ (resp. δ) denotes the maximal (resp. minimal) degree of the graph G.

In the following, we prove an upper bound on κ(G) and a lower bound on κ ′ (G). Lemma 6. For any graph G of order n and degree ∆, κ(G) ≤ n.∆ ∆+1 .

Proof.

Let B ⊆ V be a WOD set. ∃C ⊆ V \ B such that B ⊆ Odd(C). |C| ≤ n -|B| and |B| ≤ |Odd(C)| ≤ ∆.|C|, so |B| ≤ ∆.(n -|B|). It comes that |B| ≤ n.∆ ∆+1 , so κ(G) ≤ n.∆ ∆+1 . ✷
In the following we prove that this bound is reached only for graphs having a perfect code. A graph G = (V, E) has a perfect code if there exists C ⊆ V such that C is an independent set and every vertex in V \ C has exactly one neighbor in C. Proof. MaxWOD is in the class NP since a WOD set B of size k is a YES certificate. Indeed, deciding whether the certificate B is WOD or not can be done in polynomial time by solving for X the linear equation Γ V \B .X = 1 B in F 2 , where 1 B is a column vector of dimension |B| where all entries are 1, and Γ V \B is the cut matrix, i.e. a submatrix of the adjacency matrix of the graph which columns correspond to the vertices in V \ B and rows to those in B. In fact, X ⊆ V \ B satisfies Γ V \B .X = 1 B if and only if (X ⊆ V \ B and B ⊆ Odd(X)) if and only if B is WOD. For the completeness, given a 3-regular graph, if κ(G) ≥ 3 4 n then κ(G) = 3 4 n (since κ(G) ≤ n∆ ∆+1 for any graph). Moreover, according to Corollary 1, κ(G) = 3 4 n if and only if G has a perfect code. Since the problem of deciding whether a 3-regular graph has a perfect code is known to be NP complete (see [START_REF] Kratochvil | Perfect codes in general graphs. 7th Hungarian colloqium on combinatorics[END_REF] and [START_REF] Klavzar | 1-perfect codes in sierpinski graphs[END_REF]), so is MaxWOD. ✷ Now we introduce a lower bound on κ ′ . Lemma 7. For any graph G, κ ′ (G) ≥ n n-δ where δ is the minimal degree of G.

Proof. According to

Theorem 5, κ ′ (G) ≥ n -κ(G). Moreover, thanks to Lemma 6, n -κ(G) ≥ n -n∆(G) ∆(G)+1 = n -n(n-1-δ(G)) n-δ(G) = n n-δ . ✷
This bound is reached for the regular graphs for which their complement graph has a perfect code, more precisely:

Theorem 8. Given G a δ-regular graph such that n n-δ is odd, κ ′ (G) = n n-δ if and only if G has a perfect code. Proof. (⇐) Let C be a perfect code of G. Since |C| = n ∆(G)+1 = n n-δ = 1 mod 2, Odd G (C) ⊆ C, thus C is a non-WOD set in G, so κ ′ (G) ≤ n n-δ . Since κ ′ (G) ≥ n n-δ for any graph, κ ′ (G) = n n-δ (⇒) Let B be a non-WOD set of size n n-δ in G. ∃D ⊆ B such that |D| = 1 mod 2 and Odd G (D) ⊆ B. According to Lemma 5, V \ B ⊆ Odd G (D), so |Odd G (D)| ≥ ∆(G) n n-δ , which implies that |D|.∆(G) ≥ ∆(G) n n-δ . As a consequence, |D| = n n-δ and since every vertex of V \ B (of size ∆(G) n n-δ ) in G is connected to D,
(G ∪ K 4 ) = n 4 + 1.
Since deciding whether a 3-regular graph has a perfect code is known to be NP complete, so is Min¬WOD ✷

In the following, we prove that deciding, given a graph G and k ≥ 0, whether κ Q (G) ≥ k is NP complete (Theorem 10). The proof consists in a reduction from the problem Min¬WOD, which is based on the evaluation of κ and κ ′ for particular graphs consisting of multiple copies of a same graph: Lemma 8. For any graph G and any r > 0, κ(G r ) = r.κ(G) and κ

′ (G r ) = κ ′ (G) where G 1 = G and G r+1 = G ∪ G r . Proof. -[κ(G r ) = r.κ(G)]: Let B be a WOD set in G of size κ(G). B is in the odd neighborhood of some C ⊆ V . Then the set B r ⊆ V (G r )
which is the union of sets B in each copy of the graph G is in the odd neighborhood of C r ⊆ V (G r ), the union of sets C of each copy of G. Therefore B r is WOD and κ(G r ) ≥ r.κ(G). Now if we pick any set B 0 ⊆ V (G r ) verifying |B 0 | > r.κ(G), there exists a copy of G such that |B 0 ∩ G| > κ(G). Therefore B 0 is a non-WOD set and κ(G r ) ≤ r.κ(G).

-[κ ′ (G r ) = κ ′ (G)]: Let B be a non-WOD set in G of size κ ′ (G). If we consider B as a subset of V (G r ) contained in one copy of the graph G, B is a non-WOD set in G r . Therefore κ ′ (G r ) ≤ κ ′ (G). If we pick any set B ⊆ V (G r ) verifying |B| < κ ′ (G), its intersection with each copy of G verifies |B ∩ G| < κ ′ (G). Thus, each such intersection is in the odd neighborhood of some C i . So B is in the odd neighborhood of i=1..r C i . Consequently, B 0 is a WOD set in G r and κ ′ (G r ) ≥ κ ′ (G). ✷

We consider the problem QuantumThreshold which consists in deciding, for a given graph G and k ≥ 0, whether κ Q (G) ≥ k, i.e. κ(G) ≥ k or κ ′ (G) ≤ nk? Theorem 10. QuantumThreshold is NP-Complete.

Proof. QuantumThreshold is in NP since a WOD set of size k or a non-WOD set of size nk is a YES certificate. For the completeness, we use a reduction to the problem Min¬WOD. Given a graph G and any k ≥ 0,

κ Q (G k+1 ) ≥ (k + 1)n -k ⇔ κ(G k+1 ) ≥ (k + 1)n -k or κ ′ (G k+1 ) ≤ k ⇔ κ(G) ≥ n-1+ 1 k+1 or κ ′ (G) ≥ k ⇔ κ(G) > n-1 or κ ′ (G) ≥ k .
In the last disjunction, the first inequality κ(G) > n-1 is always false since for any graph G of order n we have κ(G) ≤ n -1. Thus, the answer of the oracle call gives the truth of the second inequality κ ′ (G) ≥ k which corresponds to the problem Min¬WOD. As a consequence, QuantumThreshold is NP-complete. ✷

Conclusion

In this paper, we have studied secret sharing with graph states which lead to the analysis of the combinatorial quantity κ Q that can be computed on graphs.

We have studied and computed these quantities on some specific families of graphs, providing the best known constructive threshold protocols for graphstate based secret sharing. Then, we have proven using probabilistic methods that there exist graphs that allow non-quasi-unanimity protocols and that a random graph G of order n satisfies κ Q (G) ≤ 0.811n with high probability. Finally, we have shown that given a graph G and an integer k, deciding whether κ Q (G) ≥ k is NP-Complete. Recently, in [START_REF] Cattanéo | Parametrized Complexity of Weak Odd Domination Problems[END_REF], the analysis of this problem has been refined by considering its parameterized complexity: the problem belongs to W [START_REF] Bazzi | Some randomized code constructions from group actions[END_REF] and is hard for W [START_REF] Anshu | Pseudo-telepathy games and genuine NS n-way nonlocality using graph states[END_REF].

It is very interesting to see that the best known protocols use Paley graph states and that they seem promising candidates to have even better bounds. Paley graph states have also been used in [START_REF] Javelle | On the Minimum Degree up to Local Complementation: Bounds and Complexity[END_REF] to provide the best known family in terms of minimum degree up to local complementation, which is related to the complexity of graph state preparation [START_REF] Høyer | Resources required for preparing graph states[END_REF]. Paley graph states also form an optimal family in terms of multipartie nonlocality [START_REF] Anshu | Pseudo-telepathy games and genuine NS n-way nonlocality using graph states[END_REF]. Thus, these states seem very interesting in terms of entanglement and might be useful for other applications in quantum information theory.

Theorem 6 .Corollary 1 .

 61 For any graph G of order n and degree ∆, κ(G) = n.∆ ∆+1 if and only if G has a perfect codeC such that ∀v ∈ C, d(v) = ∆. Proof. (⇐) Let C be a perfect code of G such that ∀v ∈ C, δ(v) = ∆. V \ C is a WOD set since Odd(C) = V \ C. Moreover |V \ C| = n∆ ∆+1 , so κ(G) ≥ n.∆ ∆+1 . According to Lemma 6, κ(G) ≤ n∆ ∆+1 , so κ(G) = n∆ ∆+1 . (⇒) Let B be a WOD set of size n.∆ ∆+1 . There exists C ⊆ V \ B such that B ⊆ Odd(C). Notice that |C| ≤ n-n.∆ ∆+1 = n ∆+1 . Moreover |C|.∆ ≥ |Odd(C)| ≥ |B|, so |C| = n ∆+1 . It comes that |B| = |B ∩Odd(C)| ≤ v∈C d(v) ≤ ∆. n ∆+1 = |B|.Notice that if C is not a perfect code the first inequality is strict, and if ∃v ∈ C, d(v) < ∆, the second inequality is strict. Consequently, C is a perfect code and ∀v ∈ C, d(v) = ∆.✷ Given a ∆-regular graph G, κ(G) = n∆ ∆+1 if and only if G has a perfect code.We consider the problem MaxWOD which consists in deciding, given a graph G and an integer k ≥ 0, whether κ(G) ≥ k.Theorem 7. MaxWOD is NP-Complete.

1 .

 1 Encryption. The dealer prepares the graph state |G . If s = 1 the dealer applies Z V on the qubits of the graph state. The resulting state is |G s := Z s V |G 2. Distribution. Player j's share is qubit j of |G s . 3. Reconstruction. Let B be a c-accessible set of player, with D ⊆ B such that |D| = 1 mod 2 and Odd(D) ⊆ B. -The players in Odd(D) apply S = |x → i x |x on their qubit. -The players in D apply H = |x → 1

	√ -Each player j ∈ D∪Odd(D) measures his qubit in the {|0 , |1 }-basis 2 (|0 +(-1) x |1 ) on their qubit. and broadcasts his result s i ∈ {0, 1} to the players in B. -The reconstructed secret is

  The dealer prepares the quantum state α |G 0 + β |G 1 where |G 0 := |G and |G 1

does not intersect all the MIS of size p, then B is in the odd neighborhood of each vertex of such a non intersecting MIS. If B intersects all the MIS then it does not contain any MIS, thus there exists a clique C ⊆ V \ B of size q. Every vertex in B is in the odd neighborhood of C.

✷

2.3 Sharing a quantum secret

Graph state based classical secret sharing can be extended to the quantum case as follows (the encryption method has been introduced in

[START_REF] Markham | Graph states for quantum secret sharing[END_REF]

, and for the reconstruction method in

[START_REF] Javelle | New protocols and lower bound for quantum secret sharing with graph states[END_REF]

):

Given a graph G of order n, the graph state-based protocol for sharing a quantum secret |φ = α |0 + β |1 among n players is:

1. Encryption.

  D must be a perfect code. ✷We consider the problem Min¬WOD which consists in deciding, given a graph G and an integer k ≥ 0, whether κ ′ (G) ≤ k?Theorem 9. Min¬WOD is NP-Complete. Proof. Min¬WODis in the class NP since a non-WOD set of size k is a YES certificate. For the completeness, given a 3-regular graph G, if n 4 is odd then according to Theorem 8, G has a perfect code if and only if κ ′ (G) = n 4 . If n 4 is even, we add a K 4 gadget to the graph G. Indeed, G ∪ K 4 is a 3-regular graph and n+4 4 = n 4 + 1 is odd. Moreover, G has a perfect code if and only if G ∪ K 4 has a perfect code if and only if κ ′

Acknowledgements

This work has been funded by the ANR-10-JCJC-0208 CausaQ grant.