T M Michelitsch

B A Collet

A P Riascos

A F Nowakowski

F C G A Nicolleau

A fractional generalization of the classical lattice dynamics approach

We develop physically admissible lattice models in the harmonic approximation which define by Hamilton's variational principle fractional Laplacian matrices of the forms of power law matrix functions on the n-dimensional periodic and infinite lattice in n = 1, 2, 3, .. dimensions. The present model which is based on Hamilton's variational principle is confined to conservative non-dissipative isolated systems. The present approach yields the discrete analogue of the continuous space fractional Laplacian kernel. As continuous fractional calculus generalizes differential operators such as the Laplacian to non-integer powers of Laplacian operators, the fractional lattice approach developed in this paper generalized difference operators such as second difference operators to their fractional (non-integer) powers. Whereas differential operators and difference operators constitute local operations, their fractional generalizations introduce nonlocal long-range features. This is true for discrete and continuous fractional operators. The nonlocality property of the lattice fractional Laplacian matrix allows to describe numerous anomalous transport phenomena such as anomalous fractional diffusion and random walks on lattices. We deduce explicit results for the fractional Laplacian matrix in 1D for finite periodic and infinite linear chains and their Riesz fractional derivative continuum limit kernels.

The fractional lattice Laplacian matrix contains for α = 2 the classical local lattice approach with well known continuum limit of classic local standard elasticity, and for other integer powers to gradient elasticity. We also present a generalization of the fractional Laplacian matrix to n-dimensional cubic periodic (nD tori) and infinite lattices. We show that in the continuum limit the fractional Laplacian matrix yields the well-known kernel of the Riesz fractional Laplacian derivative being the kernel of the fractional power of Laplacian operator. In this way we demonstrate the interlink of the fractional lattice approach with existing continuous fractional calculus. The developed approach appears to be useful to analyze fractional random walks on lattices as well as fractional wave propagation phenomena in lattices.

Introduction

There are various phenomena in nature including complex, chaotic, turbulent, critical, fractal and anomalous transport phenomena having erratic trajectories with often non-differentiable characteristics. Such 'anomalous' phenomena as a rule cannot be described by standard approaches involving integer order partial differential equations. However, it has been shown that they often can be described by non-integer order, i.e. fractional differential equations [START_REF] Metzler | The random walk's guide to anomalous diffusion: A fractional dynamics approach[END_REF][START_REF] Metzler | The restaurant at the end of the random walk: recent developments in the description of anomalous transport by fractional dynamics[END_REF].

There are many definitions for fractional derivatives and integrals (Riemann, Liouville, Caputo, Grünwald-Letnikow, Marchaud, Weyl, Riesz, Feller, and others), see e.g. [START_REF] Hilfer | Threefold Introduction to Fractional Derivatives[END_REF][START_REF] Metzler | The random walk's guide to anomalous diffusion: A fractional dynamics approach[END_REF][START_REF] Samko | Fractional Integrals and Derivatives: Theory and Applications[END_REF][START_REF] Samko | Fractional Weyl-Riesz Integrodifferentiation of Periodic Functions of Two Variables via the Periodization of the Riesz Kernel[END_REF][START_REF] Podlubny | Fractional Differential Equations[END_REF] and the references therein. This diversity of definitions is due to the fact that fractional operators take different kernel representations in different function spaces which is a consequence of the nonlocal character of fractional kernels.

Whereas fractional operators are well known in the continuous space and obtained as power law convolutional kernels, the fractional calculus on discrete networks and lattices is more involved and much less developed.

An approach to define fractional differential operators on lattices was suggested in the papers [START_REF] Tarasov | Map of discrete system into continuous[END_REF][START_REF] Tarasov | Continuous limit of discrete systems with long-range interaction[END_REF][START_REF] Tarasov | Exact discretization by Fourier transforms[END_REF]. In [START_REF] Tarasov | Lattice fractional calculus[END_REF] was suggested the fractional calculus which includes fractional difference operators and fractional integro-differential operators on lattices where exact results have been presented in these works (see also [START_REF] Tarasov | United lattice fractional integro-differentiation[END_REF]). In contrast to that approach, the goal of the present work is to introduce fractional centered difference operators on the lattice appearing as a natural fractional generalization of Born von Karman's centered symmetric second order difference operator. In the same time all good properties of the classical Born von Karman lattice approach such as translational symmetry and elastic stability is conserved by the fractional lattice model to be developed in the present paper. In this way the present approach opens the door towards a generalization of the classical lattice approaches [START_REF] Maradudin | Theory of lattice dynamics in the harmonic approximation[END_REF].

In the context of Markovian processes on networks, the concept of 'fractional diffusion on undirected networks' generalizing the 'normal random walk' was recently introduced by Riascos and Mateos [START_REF] Riascos | Long-range navigation on complex networks using Lévy random walks[END_REF][START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and L evy flights[END_REF][START_REF] Riascos | Fractional diffusion on circulant networks: emergence of a dynamical small world[END_REF][START_REF] Riascos | Fractional quantum mechanics on networks: Long-range dynamics and quantum transport[END_REF]. Such random motions on lattices are defined by diffusion equations where instead of discrete Laplacian matrices defined by second order difference operators their fractional generalizations come into play. In these works it has been demonstrated that fractional generalizations of lattice models have a huge interdisciplinary potential as they are able to describe phenomena which account for nonlocal interactions including the emergence of Lévy flights on lattices [START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and L evy flights[END_REF][START_REF] Riascos | Fractional diffusion on circulant networks: emergence of a dynamical small world[END_REF].

Fractional generalizations second order difference operators introduce nonlocal long-range features. In contrast to fractional orders, the standard finite differences of integer orders describe local nearest neighbor interactions. The nonlocality increases with the integer order of the power. The difference operators of integer orders at the lattice level correspond to spatial forms of non-local lattice sums and the relations of differences and differential operators defined by infinite series are analyzed in recent articles [START_REF] Tarasov | Exact discrete analogs of derivatives of integer orders: Differences as infinite series[END_REF][START_REF] Tarasov | Exact discretization by Fourier transforms[END_REF], and further a fractional generalization of lattice derivative approach was introduced in [START_REF] Tarasov | United lattice fractional integro-differentiation[END_REF].

Beside the applications on diffusion problems on the lattice, the importance of fractional lattice models appears also for a description of fractional lattice vibrational phenomena, a generalization of crystal lattice dynamics. Some initial steps towards such a fractional generalization generalization of nonlinear classical lattice dynamics has been introduced by Laskin and Zaslavsky [START_REF] Laskin | Nonlinear fractional dynamics on a lattice with long-range interactions[END_REF] and Tarasov and Zaslavsky [START_REF] Tarasov | Fractional dynamics of coupled oscillators with long-range interaction[END_REF]. In a lattice dynamics model which defines by Hamilton's variational principle the 'Laplacian matrix' which contains all constitutive information of the harmonic interparticle interactions, it is therefore desirable to develop a 'fractional generalization' of the existing lattice dynamics approach. To this end in the present paper we utilize the methodology of characteristic matrix function which was introduced recently [START_REF] Michelitsch | Nonlocal constitutive laws generated by matrix functions: Lattice dynamics models and their continuum limits[END_REF].

The interdisciplinary fractional lattice approach developed in the present paper allows to describe all types of physical fields in the harmonic approximation defined on lattices having a continuum limit governed by a non-classical, 'anomalous' power-law nonlocality in the form of Riesz fractional derivative kernels. Physical applications include especially problems of fractionally generalized lattice dynamics: lattice vibrations, elastic wave propagation, nonlocal elasticity, nonlocal electrodynamics, fractional quantum mechanics on lattices and networks, and last but not least above mentioned anomalous transport and diffusion phenomena with 'fractional random walk models' and emergence of Lévy flights. The entire set of problems of classical lattice dynamics in the harmonic approximation [START_REF] Born | Dynamical Theory of Crystal Lattices[END_REF] can be fractionally generalized by the present approach. This generalization contains only one characteristic parameter, namely the power-law index α. Newly emerging phenomena of this 'fractionalization' are to be expected. The classical (Born von Karman) theories are contained in the approach at the value α = 2. Since the present fractional lattice approach is well defined by Hamilton's variational principle, it provides a physically admissible nonlocal generalization of any classical harmonic lattice model.

The present paper is organized as follows. In the first part of the paper we deduce from "fractional harmonic lattice potentials" on the cyclically closed linear chain a discrete fractional Laplacian matrix. We do so by applying our recent approach to generate nonlocal lattice models by matrix functions where the generator operator is the discrete centered Born von Karman Laplacian [START_REF] Michelitsch | Nonlocal constitutive laws generated by matrix functions: Lattice dynamics models and their continuum limits[END_REF]. First we obtain the discrete fractional Laplacian in explicit form for the infinite chain for particle numbers N → ∞, being in accordance with the fractional centered difference models of Ortiguiera [START_REF] Ortiguera | Riesz Potential Operators and Inverses via Fractional Centered Derivatives[END_REF] and Zoia et al. [START_REF] Zoia | Fractional Laplacian in bounded domains[END_REF]. Utilizing the discrete infinite chain fractional Laplacian matrix we construct an explicit representation for the fractional Laplacian matrix on the N -periodic finite 1D lattice where the particle number N can be arbitrary not necessarily large. Then we analyse continuum limits of the discrete fractional model: The infinite space continuum limit of the fractional Laplacian matrix yields the well known infinite space kernel of the standard fractional Laplacian. The periodic string continuum limit yields an explicit representation for the kernel of the fractional Laplacian (Riesz fractional derivative) which fulfills periodic boundary conditions and is defined on the finite L-periodic string.

In the second part of the paper we suggest an extension of the fractional approach on nD periodic and infinite lattices. We deduce an integral representation for fractional Laplacian on the infinite nD lattice and proof that as asymptotic representation the well known Riesz fractional derivative of the nD infinite space is emerging. More detailed derivations of some of the results of the present paper can be found in recent articles [START_REF] Michelitsch | Fractional Laplacian matrix on the finite periodic linear chain and its periodic Riesz fractional derivative continuum limit[END_REF][START_REF] Michelitsch | Lattice fractional Laplacian and its continuum limit kernel on the finite cyclic chain[END_REF]. All these results are fully equivalent and can also be deduced by employing the more general approach of Riascos and Mateos for fractional diffusion problems on networks [START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and L evy flights[END_REF][START_REF] Riascos | Fractional diffusion on circulant networks: emergence of a dynamical small world[END_REF], and see also the references therein.

Fractional Laplacian matrix on cyclically closed chains

We consider first a periodic, cyclically closed linear chain (1D periodic lattice or ring) with equidistant lattice points p = 0, .., N -1 consisting of N identical particles with particle mass µ. Each mass point p has equilibrium position at 0 ≤ x p = ph < L = N h where L denotes the length of the chain and h the interparticle distance (lattice constant). Further we impose periodicity (cyclic closure of the chain). For convenience of our demonstration we introduce the unitary shift operator D defined by Du p = u p+1 and its adjoint D † = D -1 with D † u p = u p-1 . We employ periodic boundary conditions (cyclic closure of the chain) u p = u p+sN (s ∈ Z) and equivalently, cyclic index convention p → p mod (N ) ∈ {0, 1, .., N -1}. Any elastic potential in the harmonic approximation defined on the 1D periodic lattice can be written in the representation [START_REF] Michelitsch | Nonlocal constitutive laws generated by matrix functions: Lattice dynamics models and their continuum limits[END_REF]

V f = µ 2 N -1 p=0 u * p f (2 1 -D -D † )u p = - 1 2 N -1 p=0 N -1 q=0 u * q ∆ f (|p -q|)u p , (1)
where ∆ f (|p -q|) = -µf |p-q| indicates the (negative-semidefinite) Laplacian N × N -matrix, 1 the identity matrix, and f we refer to as the characteristic function: Physically admissible, elastically stable and translational invariant positive elastic potentials require for the 1D periodic lattice (cyclic ring) that the characteristic function f which is defined as a scalar function to have the following properties 0 < f (λ) < ∞ for 0 < λ ≤ 4 (elastic stability) and f (λ = 0) = 0 (translational invariance, zero elastic energy for uniform translations of the lattice). For the approach to be developed we propose the characteristic function to assume power law form

f (α) (λ) = Ω 2 α λ α 2 , α > 0, (2)
which fulfills for α > 0 and Ω 2 α > 0 the above required good properties for the characteristic function. Ω α denotes a dimensional constant of physical dimension sec -1 . Note that 2 1 -D -D † is the central symmetric second difference operator which is defined by ( 2

1 -D -D † )u p = 2u p -u p+1 -u p-1 . The matrix function f (2 1 -D -D † ) is in general a self-adjoint (symmetric) positive semidefinite N × N -matrix function of the simple N ×N generator matrix [2 1-D-D † ] pq = 2δ pq -δ p+1,q -δ p-1,q . It can be easily seen that f (2 1-D-D † )
has Töplitz structure, i.e. its additional symmetry consists in the form f pq = f qp = f |p-q| , p, q = 0, ..N -1 giving the fractional generalization of the Born von Karman centered difference operator. The fractional elastic potential has then with (1) the representation

V α = µΩ 2 α 2 N -1 p=0 u * p (2 1 -D -D † ) α 2 u p = µ 2 N -1 p=0 N -1 q=0 u * q f (α) |p-q| u p , (3)
with the matrix elements f

(α) |p-q| = Ω 2 α [(2 1 -D -D † ) α 2
] |p-q| of the fractional characteristic matrix function. In full analogy to the negative semidefinite continuous Laplacian (second derivative operator) we define here the fractional Laplacian matrix as the negative semidefinite matrix defined through Hamilton's variational principle 1

∆ α u p = - ∂ ∂u p V α , (∆ α ) |q-p| = -µΩ 2 α [(2 1 -D -D † ) α 2 ] |p-q| = -µf (α) |p-q| . (4)
We emphasize again that the fractional Laplacian matrix ∆ α = ∆ † α is self-adjoint having a symmetric Töplitz structure matrix representation (∆ α ) pq = (∆ α ) qp = (∆ α ) |q-p| = (∆ † α ) pq . This property appears naturally as the shift operators D and their adjoint D † are symmetrically contained. This is true for all admissible α > 0 and includes α = 2 for the conventional central symmetric second difference operator. In this relation we have introduced the positive-semidefinite fractional characteristic matrix f

(α)
|p-q| which is in our convention up to the prefactor -µ identical with the fractional Laplacian matrix (which we define as negative-semidefinite being the fractional analogue of d 2 dx 2 . To determine the fractional Laplacian matrix it is useful to consider the spectral representation

f (α) |p-q| = Ω 2 α N N -1 =0 e iκ (p-q) 4 sin 2 κ 2 α 2 , κ = 2π N (5)
where we take advantage of the N -periodicity of the chain, i.e. the eigenvectors of the fractional Laplacian matrix are ortho-normal Bloch-vectors having the components e iκ p √ N . For the infinite chain in the limit N → ∞ 1 The sign convention differs in many references, so e.g. in [START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and L evy flights[END_REF][START_REF] Riascos | Fractional diffusion on circulant networks: emergence of a dynamical small world[END_REF] the fractional Laplacian matrix is defined positive semidefinite corresponding to the definition of the characteristic fractional operator ( 2

1 -D -D † ) α 2 .
the matrix elements of the fractional Laplacian matrix (4) can be evaluated explicitly.

f (α) |p-q| = Ω 2 α (2 -D -D † ) α 2 |p-q| , p, q ∈ Z 0 , f (α) |p| , = Ω 2 α 2π π -π e iκp 4 sin 2 κ 2 α 2 dκ, p ∈ Z 0 . (6)
This expression can be obtained in explicit form [START_REF] Michelitsch | Fractional Laplacian matrix on the finite periodic linear chain and its periodic Riesz fractional derivative continuum limit[END_REF][START_REF] Michelitsch | Lattice fractional Laplacian and its continuum limit kernel on the finite cyclic chain[END_REF][START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and L evy flights[END_REF][START_REF] Zoia | Fractional Laplacian in bounded domains[END_REF]]

f (α) (|p|) = Ω 2 α α! α 2 !( α 2 + |p|)! (-1) p |p|-1 s=0 ( α 2 -s) = Ω 2 α (-1) p α! ( α 2 -p)!( α 2 + p)! , (7)
where we introduced the generalized factorial function β! = Γ(β + 1). In view of [START_REF] Metzler | The random walk's guide to anomalous diffusion: A fractional dynamics approach[END_REF] we observe that for noninteger α 2 any matrix element f (α) (|p -q|) = 0 is non-vanishing indicating the nonlocality of the harmonic fractional interparticle interaction (4). For α 2 = m ∈ N the matrix elements ( 7) take the values of the standard binomial coefficients. ( 6) 2 can be read as the Fourier coefficients of the infinite Fourier series

ω 2 α (κ) = Ω 2 α 4 sin 2 κ 2 α 2 = Ω 2 α 2 -e iκ -e -iκ α 2 = ∞ p=-∞ f (α) |p| e ipκ = f (α) 0 + 2 ∞ p=1 f (α) |p| cos (pκ) (8)
representing the fractional dispersion relation. Putting κ = 0 in the dispersion relation, we can verify directly that the fractional Laplacian matrix conserves translational symmetry which is expressed by

∞ p=-∞ f (α) |p| = 0 (9)
This equation can also be read as (2 -D -D † ) α 2 1 = 0, i.e. the fractional centered difference operator applied to a constant is vanishing. This property appears as the fractional generalization of the same property of second order centered differences when α = 2. We further observe in view of (8) the positive semi-definiteness of the fractional characteristic matrix f (α) |p-q| where positiveness of (8) for 0 < κ < 2π indicates elastic stability of the chain.

The fractional dispersion relation (8) leads to the remarkable relation which holds only for complex numbers on the unit circle z = e iκ , namely

2 -z - 1 z α 2 = ∞ p=-∞ (-1) p α! ( α 2 -p)!( α 2 + p)! z p , |z| = 1. ( 10
)
This Laurent series converges nowhere except on the unit circle |z| = 1. For instance the zero eigenvalue ω 2 α (κ = 0) = 0 which corresponds to translational invariance (zero elastic energy for uniform translations) is obtained by putting z = 1 in [START_REF] Michelitsch | Lattice fractional Laplacian and its continuum limit kernel on the finite cyclic chain[END_REF]. For integer α 2 = m ∈ N (7) takes the form of the standard binomial coefficients and the series ( 8), [START_REF] Michelitsch | Lattice fractional Laplacian and its continuum limit kernel on the finite cyclic chain[END_REF] then take the representations of standard binomial series of 2 -z -

1 z α 2 = (-1) m ( √ z-1 √ z ) 2m
breaking at |p| = m corresponding to zero values for the matrix elements for [START_REF] Metzler | The random walk's guide to anomalous diffusion: A fractional dynamics approach[END_REF] for |p| > m. We further observe for noninteger α 2 / ∈ N the power law asymptotics for |p| >> 1 which can be obtained by utilizing Stirling's asymptotic formula for the Γ-function [START_REF] Michelitsch | Fractional Laplacian matrix on the finite periodic linear chain and its periodic Riesz fractional derivative continuum limit[END_REF][START_REF] Michelitsch | Lattice fractional Laplacian and its continuum limit kernel on the finite cyclic chain[END_REF]

f (α) |p|>>1 → -Ω 2 α α! π sin ( απ 2 ) p -α-1 . (11)
The asymptotic power law (scale free) characteristics of the fractional Laplacian matrix ∆ pq ∼ |p -q| -α-1 is the essential property which gives rise to many 'anomalous phenomena' such as in 'fractional diffusion' problems on networks such as the emergence of Lévy flights [START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and L evy flights[END_REF][START_REF] Riascos | Fractional diffusion on circulant networks: emergence of a dynamical small world[END_REF] (and references therein). The fractional continuum limit kernels are discussed in the subsequent section. The expressions ( 6)-( 11) hold for the infinite 1D lattice corresponding to N → ∞. As everything in nature is limited we shall consider now the fractional Laplacian matrix for a finite periodic lattice where the particle number N is arbitrary and not necessarily large.

1D finite periodic lattice -ring

It is only a small step to construct the finite lattice Laplacian matrix in terms of infinite lattice Laplacian matrix. We can perform this step by the following consideration: Let -µf

(∞)
|p-q| the Laplacian matrix of the infinite lattice, and ω2 (κ) the continuous dispersion relation of the infinite lattice matrix f |p-q| obeying the eigenvalue relation

∞ q=-∞ f (∞) |p-q| e iqκ = ω 2 (κ)e ipκ , 0 ≤ κ < 2π. ( 12
)
This relation holds identically in the entire principal interval 0 ≤ κ < 2π and is 2π-periodic in the κ-space.

Let us now choose κ = κ = 2π N with = 0, .., N -1 being the Bloch wave number of the finite periodic lattice of N lattice points where N is not necessarily large. Since the Bloch wave numbers of the chain are discrete points within the interval 0 ≤ κ < 2π, then relation [START_REF] Michelitsch | The Fractional Laplacian as a limiting case of a self-similar spring model and applications to n-dimensional anomalous diffusion[END_REF] holds as well for these N κ-points, namely

[9, 10] 2 ∞ p=-∞ f (∞) |q| e iqκ = ω 2 (κ ), 0 ≤ κ = 2π N < 2π, N -1 p=0 ∞ s=-∞ f (∞) |p+sN | e i(p+sN )κ = N -1 p=0 e ipκ ∞ s=-∞ f (∞) |p+sN | = N -1 p=0 e ipκ f f inite |p| = ω 2 (κ ). (13)
In the second relation the N -periodicity of the finite lattice Bloch eigenvector e i(p+sN )κ = e ipκ has been used. The last relation can be read as the eigenvalue relation for the N -periodic lattice matrix of Töplitz structure

f f inite |p-q| = ∞ s=-∞ f (∞) |p-q+sN | = f (∞) |p-q| + ∞ s=1 (f (∞) |p-q+sN | + f (∞) |p-q-sN | ). ( 14
)
It follows that in the limiting case N → ∞ the finite lattice matrix [START_REF] Michelitsch | Fractional random walk lattice dynamics[END_REF] recovers the infinite lattice matrix f f inite → f (∞) . From ( 14) we read of for the fractional lattice Laplacian of the finite periodic 1D lattice

∆ α,N (|p|) = -µf (α,f inite) |p| , 0 ≤ p ≤ N -1 (15)
with

f (α,f inite) |p| = Ω 2 α (-1) p α! ( α 2 -p)!( α 2 + p)! + Ω 2 α ∞ s=1 (-1) p+N s α! 1 ( α 2 -p -sN )!( α 2 + p + sN )! + 1 ( α 2 -p + sN )!( α 2 + p -sN )! . ( 16
)
We observe N -periodicity of ( 16) and furthermore the necessary property that in the limit of infinite chain N → ∞, (16) recovers the infinite lattice expression of eq. (7).

Fractional continuum limit kernels

In this section we investigate the interlink between the lattice fractional approach introduced above and continuum fractional derivatives. To this end we introduce the following hypotheses which are to be observed when performing continuum limits. Following [START_REF] Michelitsch | Nonlocal constitutive laws generated by matrix functions: Lattice dynamics models and their continuum limits[END_REF] we require in the continuum limit that extensive physical quantities, i.e. quantities which scale with the length of the 1D system, such as the total mass N µ = M and the total elastic energy of the chain remain finite when its length L is kept finite3 , i.e. neither vanish nor diverge. Let L = N h be the length of the chain and h the lattice constant (distance between two neighbor atoms or lattice points). We can define two kinds of continuum limits: (i) The periodic string continuum limit where the length of the chain L = N h is kept finite and h → 0 (i.e.

N (h) = Lh -1 → ∞).
(ii) The infinite space continuum limit where h → 0, however, the length of the chain tends to infinity N (h)h = L(h) → ∞4 . The kernels of the infinite space limit can be recovered from those of the periodic string limit by letting L → ∞. From the finiteness of the total mass of the chain, it follows that the particle mass µ = M N = M L h = ρ 0 h scales as ∼ h. Then by employing expression (3) for the fractional elastic potential, the total continuum limit elastic energy Ṽα can be defined by

Ṽα = lim h→0+ V α = µΩ 2 α 2 N -1 p=0 u * (x p ) -4 sinh 2 h 2 d dx α 2 u(x p ). ( 17
)
Putting D = e h d dx (ph = x p → x) and accounting for 2

-D(h) -D(-h) = -4 sinh 2 h 2 d dx ≈ -h 2 d 2 dx 2 + O(h 4 ) we get lim h→0 -4 sinh 2 h 2 d dx α 2 = h α (- d 2 dx 2 ) α 2 . ( 18
)
The formal relation [START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and L evy flights[END_REF] shows that the continuum limit kernels to be deduced in explicit forms have the interpretation of the Fractional Laplacian or also in the literature referred to as Riesz Fractional Derivative. To maintain finiteness of the elastic energy in the continuum limit h → 0 the following scaling relations for the characteristic model constants, the mass µ and the frequency Ω α are required [START_REF] Michelitsch | Fractional Laplacian matrix on the finite periodic linear chain and its periodic Riesz fractional derivative continuum limit[END_REF][START_REF] Michelitsch | Lattice fractional Laplacian and its continuum limit kernel on the finite cyclic chain[END_REF]]

Ω 2 α (h) = A α h -α , µ(h) = ρ 0 h, A α , ρ 0 > 0 ( 19
)
where ρ 0 denotes the mass density with dimension g × cm -1 and A α denotes a positive dimensional constant of dimension sec -2 × cm α , where the new constants ρ 0 , A α are independent of h. Note that the dimensional constant A α is only defined up to a non-dimensional positive scaling factor as its absolute value does not matter due to the scale-freeness of the power law. We obtain then as continuum limit of the elastic energy by taking into account N -1 p=0 hG(x p ) → L 0 G(x)dx and h → dx, x p → x,

Ṽα = lim h→0 µ(h) 2 N -1 q=0 N -1 p=0 u * q f (α) N (|p -q|)u p Ṽα = ρ 0 A α 2 L 0 u * (x) - d 2 dx 2 α 2 u(x) dx =: - 1 2 L 0 L 0 u * (x ) ∆α (|x -x |)u(x)dxdx . (20)
The continuum limit Laplacian kernel ∆α (|x -x |) can then formally be represented by the distributional kernel representation in the spirit of generalized functions [START_REF] Gelfand | I: Properties and Operations[END_REF] ∆α,L (|x

-x |) = -ρ 0 A α - d 2 dx 2 α 2 δ L (x -x ). ( 21
)
The last relation contains the distributional representation of the fractional Laplacian and is obtained for the infinite space limit (ii) in explicit form as (where (..) indicates the real part of (..)) [START_REF] Michelitsch | Fractional Laplacian matrix on the finite periodic linear chain and its periodic Riesz fractional derivative continuum limit[END_REF][START_REF] Michelitsch | Lattice fractional Laplacian and its continuum limit kernel on the finite cyclic chain[END_REF]

K (α) ∞ (x) = -- d 2 dx 2 α 2 δ L (x -x ) = - α! π lim →0+ i α+1 (x + i ) α+1 , (22)
being defined 'under the integral' in the distributional sense and yields for noninteger α 2 / ∈ N for x = 0 the well known Riesz fractional derivative kernel of the infinite space K (α)

∞ (x) = α! sin ( απ 2 ) π 1
|x| α+1 with a characteristic |x| -α-1 power law nonlocality reflecting the asymptotic power law behavior ( 11) of ( 7) for sufficiently large |p| >> 1.

(i) Periodic string continuum limit

The continuum procedure of L-periodic string where L is kept finite is then obtained as [9, 10]5 --

d 2 dx 2 α 2 δ L (x) = K (α) L (|x|) = α! sin ( απ 2 ) π ∞ n=-∞ 1 |x -nL| α+1 , ξ = x L , K (α) L (|x|) = α! sin ( απ 2 ) πL α+1 - 1 |ξ| α+1 + ζ(α + 1, ξ) + ζ(α + 1, -ξ) K (α) L (|x|) = - α! π lim →0+ ∞ n=-∞ i α+1 (x -nL + i ) α+1 = α! πL α+1 lim →0+ i α+1 1 (ξ + i ) α+1 -ζ(α + 1, ξ + i ) -ζ(α + 1, -ξ + i ) . ( 23
)
This kernel can be conceived as the explicit representation of the fractional Laplacian (Riesz fractional derivative) on the L-periodic string. The last relation is the distributional representation and is expressed by standard Hurwitz ζ-functions denoted by ζ(..). The two variants of ζ-functions which occur in above relation are defined by

ζ(β, x) = ∞ n=0 1 |x + n| β , ζ(β, x) = ∞ n=0 1 (x + n) β , (β) > 1, (x) > 0. ( 24
)
We see for α > 0 and x = 0 that the series in [START_REF] Samko | Fractional Weyl-Riesz Integrodifferentiation of Periodic Functions of Two Variables via the Periodization of the Riesz Kernel[END_REF] are absolutely convergent as good as the power function integral ∞ 1 ξ -α-1 dξ. For integer powers α 2 ∈ N the distributional representations (23) 3,4 take the (distributional) forms of the (negative semi-definite) 1D integer power Laplacian operators, namely

K (α=2m) L (|x|) = (-1) m+1 d 2m dx 2m ∞ n=-∞ lim →0+ 1 π ((x -nL) 2 + 2 ) , α 2 = m ∈ N 0 , = (-1) m+1 d 2m dx 2m ∞ n=-∞ δ ∞ (x -nL) = -- d 2 dx 2 α 2 =m δ L (x), (25)
where δ ∞ (..) and δ L indicate the Dirac's δ-functions of the infinite and the L-periodic string, respectively. We further observe in full correspondence to the discrete fractional Laplacian matrix, the necessary property that in the limit of an infinite string lim [START_REF] Samko | Fractional Weyl-Riesz Integrodifferentiation of Periodic Functions of Two Variables via the Periodization of the Riesz Kernel[END_REF] recovers the expression of the standard 1D infinite space fractional Laplacian kernel [START_REF] Samko | Fractional Integrals and Derivatives: Theory and Applications[END_REF] known from the literature (see for a further discussion [START_REF] Michelitsch | Fractional Laplacian matrix on the finite periodic linear chain and its periodic Riesz fractional derivative continuum limit[END_REF][START_REF] Michelitsch | Lattice fractional Laplacian and its continuum limit kernel on the finite cyclic chain[END_REF] and references therein).

L→∞ K (α) L (|x|) = K (α) ∞ (x)

Fractional Laplacian matrix on n-dimensional cubic lattices

In this section we deduce the nD counterpart of the fractional Laplacian matrix introduced above. With that approach the fundamentals of 'fractional lattice dynamics' can be deduced as a generalization of conventional lattice dynamics.

In this section our goal is to generalize the above 1D lattice approach to cubic periodic lattices in n = 1, 2, 3, .. dimensions of the physical space where the 1D lattice case is contained. We assume the lattice contains N = N 1 .. × N n lattice points, each covered by identical atoms with mass µ. Each mass point is characterized by p = (p 1 , p 2 , .., p n ) (p j = 0, ..N j -1) and n = 1, 2, 3, .. denotes the dimension of the physical space embedding the lattice. In order to define the lattice fractional Laplacian matrix, it is sufficient to consider a scalar generalized displacement field u p (one field degree of freedom) associated to each mass point p only. The physical nature of this scalar field can be any scalar field, such as for instance a one degree of freedom displacement field, an electric potential or, in a stochastic context a probability density function (pdf) or in a fractional quantum mechanics context a Schrödinger wave function. This demonstrates the interdisciplinary character of the present fractional lattice approach.

The fractional Laplacian matrix for general networks was only recently and to our knowledge for the first time introduced by Riascos and Mateos [START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and L evy flights[END_REF][START_REF] Riascos | Fractional diffusion on circulant networks: emergence of a dynamical small world[END_REF] in the framework of fractional diffusion analysis on networks which include nD periodic lattices (nD tori) as special cases being subject of the present analysis. For cubic nD lattices the fractional Laplacian matrix can be written as [START_REF] Michelitsch | Fractional Laplacian matrix on the finite periodic linear chain and its periodic Riesz fractional derivative continuum limit[END_REF][START_REF] Michelitsch | Lattice fractional Laplacian and its continuum limit kernel on the finite cyclic chain[END_REF][START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and L evy flights[END_REF][START_REF] Riascos | Fractional diffusion on circulant networks: emergence of a dynamical small world[END_REF]

∆ α,n = -µΩ 2 α,n L α 2 n , L α 2 n = 2n 1 -A n α 2 , α > 0, (26)
where 1 denotes the identity matrix, n indicates the dimension of the physical space and 2n indicates the connectivity, i.e. the number of next neighbors of a lattice point in the nD cubic lattice. In [START_REF] Tarasov | Lattice fractional calculus[END_REF] we introduced the adjacency matrix A n which has for the cubic lattice with next neighbor connections the form

A n = n j=1 (D j + D † j ), (27)
where then D j and D † j = D -1 j denote the next neighbor shift operators in the j = 1, .., n-directions defined by D j u p 1 ,..p j ,..,pn = u p 1 ,..p j +1,..,pn and D † j u p 1 ,..p j ,..,pn = u p 1 ,..p j -1,..,pn , i.e. D j shifts the field associated to lattice point p = (.., p j , .. to the field associated with the adjacent lattice point in the positive j-direction (.., p j+1 , ..), and the inverse (adjoint) shift operator D † j = D -1 j to the adjacent lattice point in the negative j-direction (.., p j-1 , ..). All matrices introduced in ( 26) and ( 27) are defined on the nD lattice being N × N matrices (N = N 1 × .. × N n ). As in the case of 1D lattice the so defined fractional Laplacian matrix [START_REF] Tarasov | Lattice fractional calculus[END_REF] describes for non-integer powers α 2 , / ∈ N nonlocal elastic interactions, whereas they are generated by the 'local' next neighbor Born von Karman Laplacian which is in our definition up to a negative dimension factor -µΩ 2 equal to L n . We therefore refer to L n as 'generator matrix'. We emphasize that the sign convention of what we call '(fractional) Laplacian matrix' varies in the literature (e.g. by denoting the positive semidefinite matrix L α 2 n as 'fractional Laplacian matrix', this convention is chosen, e.g. in [START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and L evy flights[END_REF][START_REF] Riascos | Fractional diffusion on circulant networks: emergence of a dynamical small world[END_REF]). We have chosen to refer to as 'fractional Laplacian matrix' the negative-semidefinite matrix -µΩ 2 α L α 2

n to be in accordance with the negative definiteness of continuum limit fractional Laplacian (25) containing as a special case α 2 = 1 the negative semidefinite conventional Laplacian d 2 dx 2 δ L (x -x )). For a discussion of some general properties of the fractional Laplacian [START_REF] Tarasov | Lattice fractional calculus[END_REF] well defined on general networks including nD lattices, we refer to [START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and L evy flights[END_REF][START_REF] Riascos | Fractional diffusion on circulant networks: emergence of a dynamical small world[END_REF]. In the periodic and infinite lattice the shift operators are unitary. Assuming N j -periodicity in each direction j, the fractional Laplacian matrix is defined by the spectral properties of the L n -matrix, namely by

[L α 2 n ] ( p-q) = 1 N e i κ •( p-q) λ α 2 , λ =   2n -2 n j=1 cos (κ j )   , α > 0, (28)
where we denoted (..) = N 1 -1 1 =0 (..).. Nn-1 n=0 (..) and κ = (κ 1 , ..κ n ) denotes the Bloch wave vectors of the Brillouin zone where their components can the values κ j = 2π N j j ( j = 0, .., N j -1). It can be seen that ( 28) has Töplitz structure depending only on |p 1 -q 1 |, .., |p j -q j |, ..|p n -q n |). For the infinite lattice when all N j → ∞ in [START_REF] Tarasov | Exact discretization by Fourier transforms[END_REF], the summation over the reciprocal lattice points assumes asymptotically the form of an integral

1 N g( κ ) ∼ 1 (2π) n π -π .. π -π dκ 1 ..dκ n g( κ)
, where the integration intervals [-π, π] can be chosen instead of [0, 2π] for 2π-periodic functions g(κ j ) = g(κ j + 2π).

where τ is a scalar parameter and 1 the identity matrix and δ(τ -λ ) the conventional scalar Dirac δ-function.

Then with the matrix δ-function defined in [START_REF] Tarasov | Fractional dynamics of coupled oscillators with long-range interaction[END_REF] we can write

L α 2 = ∞ -∞ δ(L -τ 1)|τ | α 2 dτ (31)
and by utilizing δ(τ -λ ) = 1 (2π)

∞

-∞ e ik(τ -λ ) dk together with the kernel -D α 2 of the 1D fractional Laplacian (Riesz fractional derivative) of order α 2 in its distributional form [13]

D α 2 (k -ξ) = - d 2 dk 2 α 4 δ(k -ξ) =: 1 (2π) ∞ -∞ e i(k-ξ)τ |τ | α 2 dτ = lim →0+ 1 π ∞ 0 e -τ ( -i(k-ξ)) |τ | α 2 dτ = lim →0+ Γ( α 2 + 1) π( -i(k -ξ)) α 2 . ( 32
)
Then we can write for the matrix power function [START_REF] Zoia | Fractional Laplacian in bounded domains[END_REF] the representation

L α 2 = ∞ -∞ e ikL D α 2 (k)dk, (33)
where the exponential e ikL of the matrix L = L n can be determined more easily for the generator . The matrix elements of the spectral representation of the exponential of L n can hence be written as

L n = n j=1 L (j) (L (j) = 2 -D j -D † j )
[e iξLn ] p-q = e i κ •( p-q) N e iξλ = n j=1 N j -1 j =1 e i(p j -q j )κ j N j e i2k(1-cos κ j ) . (34)

Infinite nD lattice

In the limiting case of an infinite nD lattice when all N j → ∞ we can write by using

1 N g( κ ) ∼ 1 (2π) n π -π .. π -π dκ 1 ..dκ n g( κ) to arrive at [e iξLn ] p-q = [e iξLn ] |p 1 -q 1 |,..,|pn-qn| = n j=1 1 (2π) π -π e i(p j -q j )κ e i2ξ(1-cos κ) dκ. ( 35
)
Taking into account the definition of the modified Bessel functions of the first kind I p (z) = 1 π π 0 e z cos ϕ cos pϕdϕ where p = N 0 denotes non-negative integers [START_REF] Abramowitz | Handbook of Mathematical Function[END_REF], we can write the exponential matrix (35) in the form

[e iξLn ] |p 1 -q 1 |,..,|pn-qn| = e i2nξ n j=1 I |p j -q j | (-2iξ). ( 36
)
Applying now the matrix relation [START_REF] Zoia | Fractional Laplacian in bounded domains[END_REF] and plugging in the exponential (36) yields an integral representation of the (negative semidefinite) fractional Laplacian matrix [START_REF] Tarasov | Lattice fractional calculus[END_REF] in terms of a product of modified Bessel functions of the first kind, namely

[∆ α,n ] |p 1 -q 1 |,..,|pn-qn| = -µΩ 2 α,n [L α 2 n ] |p 1 -q 1 |,..,|pn-qn| = -µΩ 2 α,n ∞ -∞ dξ e i2nξ D α 2 (ξ) n j=1 I |p j -q j | (-2iξ), (37)
with -D α 2 (ξ) indicating the Riesz fractional derivative kernel of (32). Asymptotic behavior Introducing the new vector valued integration variable ξ = κp (ξ j = pκ j , ∀j = 1, .., n) we can write for the infinite lattice integral of (28) by utilizing spherical polar coordinates p = p e p ( e p • e p = 1, p

2 = n j p 2 j ) L α 2 n (p) = 1 (2π) n πp -πp .. πp -πp dξ 1 ..dξ n p n   4 n j=1 sin 2 ξ j 2p   α 2 cos ( ξ • e p ). (38)
The dominating term for p >> 1 becomes , e.g. [START_REF] Michelitsch | The Fractional Laplacian as a limiting case of a self-similar spring model and applications to n-dimensional anomalous diffusion[END_REF][START_REF] Michelitsch | A regularized representation of the fractional Laplacian in n dimensions and its relation to Weierstrass-Mandelbrot-type fractal functions[END_REF], and holds only for 0 < α < 2. Relation (40) does not hold for α = 2 where the fractional Laplacian takes asymptotically for α → 2 -0 the localized singular distributional representation (-∆)δ n (p) of the standard Laplacian. The details of this limiting case calculation can be found in [START_REF] Michelitsch | A regularized representation of the fractional Laplacian in n dimensions and its relation to Weierstrass-Mandelbrot-type fractal functions[END_REF]. We can identify the asymptotic representation (39), (40) with the kernel of Riesz fractional derivative (fractional Laplacian) of the nD infinite space. For a more detailed discussion of properties we refer to [START_REF] Michelitsch | The Fractional Laplacian as a limiting case of a self-similar spring model and applications to n-dimensional anomalous diffusion[END_REF][START_REF] Michelitsch | A regularized representation of the fractional Laplacian in n dimensions and its relation to Weierstrass-Mandelbrot-type fractal functions[END_REF].

Conclusions

In the present paper we have developed a fractional lattice approach on nD periodic and infinite lattices. The fractional Laplacian matrices conserve the 'good' properties of the Laplacian matrices (translational symmetry and in our sign convention negative semi-definiteness). The fractional lattice approach generalizes the concept of second order centered difference operator appearing in the context of classical lattice models [START_REF] Maradudin | Theory of lattice dynamics in the harmonic approximation[END_REF] to the concept of centered fractional order difference operator. For α = 2 the fractional lattice approach contains the classical lattice approach, and for integer orders α 2 ∈ N finite centered differences of integer orders of the second difference operator are generated. For a discussion of properties of fractional Laplacian matrix on the cyclic chain, we refer to [START_REF] Michelitsch | Fractional Laplacian matrix on the finite periodic linear chain and its periodic Riesz fractional derivative continuum limit[END_REF]. In the infinite space and periodic lattice continuum limits these fractional Laplacian matrices take the representations of the well known respective Riesz fractional derivative kernels, i.e. the convolutional kernels of the (continuous) fractional Laplacians. The approach allows to model 'anomalous diffusion' phenomena on lattices with fractional transport phenomena including asymptotic emergence of Lévy flights. In such a fractional lattice diffusion model, the conventional Laplacian matrix is generalized by its fractional power law matrix function counterpart. The formulation of our approach is consistent with recent works on the fractional approach developed on undirected networks by Riascos and Mateos [START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and L evy flights[END_REF][START_REF] Riascos | Fractional diffusion on circulant networks: emergence of a dynamical small world[END_REF]. The present fractional lattice approach represents a point of departure to investigate anomalous diffusion and fractional random walk phenomena on lattices. Such problems are defined by master equations involving fractional Laplacian matrices such as deduced in the present work as generator matrices for the random dynamics. Fractional random walks on lattices and undirected networks open currently a huge interdisciplinary research field [START_REF] Michelitsch | Fractional random walk lattice dynamics[END_REF][START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and L evy flights[END_REF][START_REF] Riascos | Fractional diffusion on circulant networks: emergence of a dynamical small world[END_REF].

  being the sum of the 1D generator matrices of the N j -periodic 1D lattices and having therefore the eigenvalues λ( j ) = 2 -2 cos κ j and as a consequence having a Cartesian product space spanned by the periodic Bloch eigenvectors e i κ • p √

  normalization constant is obtained explicitly as C n,α = 2 α-1 αΓ( α+n 2 ) π n 2 Γ(1-α 2 )

where p = 0 in[START_REF] Michelitsch | The Fractional Laplacian as a limiting case of a self-similar spring model and applications to n-dimensional anomalous diffusion[END_REF] has been put to zero.

In the case of infinite string L → ∞ we require the mass per unit length and elastic energy per unit length to remain finite.

which can be realized for instance by choosing by N (h) ∼ h -δ where δ > 1.

where (..) denotes the real part of a quantity (..)

i.e. all eigenvalues λ of this matrix are non-negative.

Acknowledgements

This work has been performed in the framework of the ERCOFTAC SIG/42 cooperation during the sabbatical stay of F.C.G.A Nicolleau at Institut Jean le Rond dAlembert. We thank the two anonymous reviewers for their useful remarks.

for the 2D cubic lattice (n = 2) of ( 28) for four values of α, while (c-d) illustrate cross-sections of these dispersion sheets with the planes (0 1 0) and (1 1 0), respectively.

For α fixed, the circular frequency is given by ω α (κ 1 , κ 2 ) = λ 2 obtained for a wave vector located in (001) plane. It will be noted that the sheets cut at dimensionless frequency ω α (κ 1 , κ 2 )/ω α=2 (π, π) ≈ 0.351 and the dispersion relations of the classical next neighbor Born von Karman lattice are recovered (indicated by ω α (κ 1 , κ 2 )/ω α=2 (π, π) → 1 for α = 2 and κ 1,2 → π, ω α (κ 1 , 0)/ω α=2 (π, 0) → 1 for α = 2 and κ 1 → π). When the value of α decreases, one observes in agreement with another work [START_REF] Michelitsch | Fractional Laplacian matrix on the finite periodic linear chain and its periodic Riesz fractional derivative continuum limit[END_REF], namely a decrease of the maximum dimensionless frequency in end of the first Brillouin zone.

The goal is now to deduce a more convenient integral representation of [START_REF] Tarasov | Exact discretization by Fourier transforms[END_REF]. To this end we utilize the following observation: Let in the following L be a positive semidefinite 6 matrix and α > 0 like [START_REF] Tarasov | Lattice fractional calculus[END_REF] with the spectral representation

where we have to put for the periodic nD lattice of (28) the Bloch-eigenvectors < p| >= N -1 2 e i κ • p . Then it will be useful to define the matrix Dirac δ-function by


Peter Høyer
email: hoyer@cpsc.ucalgary.ca

Mehdi Mhalla
email: mehdi.mhalla@imag.fr

Simon Perdrix
email: simon.perdrix@imag.fr

Resources required for preparing graph states

Keywords: Quantum Computing, Algorithms, Foundations of computing

Graph states have become a key class of states within quantum computation. They form a basis for universal quantum computation, capture key properties of entanglement, are related to quantum error correction, establish links to graph theory, violate Bell inequalities, and have elegant and short graph-theoretical descriptions. We give here a rigorous analysis of the resources required for producing graphs states. Using a novel graph-contraction procedure, we show that any graph state can be prepared by a linear-size constant-depth quantum circuits, and we establish trade-offs between depth and width. We show that any minimal-width quantum circuit requires gates that acts on several qubits, regardless of the depth. We relate the complexity of preparing graph states to a new graph-theoretical concept, the local minimum degree, and show that it captures basic properties of graph states.

Introduction

What are the minimal resources required for universal quantum computation? This single question is one of the most fundamental questions related to building quantum computers, and it is one of the most studied questions within quantum computing. In 2000, in seminal work, Raussendorf and Briegel [START_REF] Raussendorf | A one-way quantum computer[END_REF] proposed a new model for quantum computations. They show that if certain initial quantum states, called graph states, are provided, then the mere ability to perform one-qubit measurements suffices for quantum computations.

Graph states have been studied extensively within the last five years. The recent survey [START_REF] Hein | Entanglement in graph states and its applications[END_REF] by Hein et al. provides an excellent introduction to the area. These efforts have established several fundamental results on the universality of quantum computations based on graph states, physical implementations of graph states, the entanglement embodied by graph states, and have proved links to basic concepts within graph theory. In this paper, we study computational aspects of graph states. We study in particular the question of characterizing the resources required for producing graph states and we establish stronger links to graph theory.

We first and foremost prove that any graph state can be prepared in constant time. That is, given a classical description of a graph G = (V, E), we can produce the corresponding graph state |G by a constant-depth quantum circuit that has size linear in the input size |V | + |E| and that consists only of one-qubit operations and control-not operations. This implies that all two-qubit operations ever required by any quantum algorithm can be conducted at the outset of the algorithm in parallel, after which all operations act only on one qubit. We also show that our circuit is robust against various alterations. If we for instance do not wish to conduct all two-qubit operations at the outset, they can be postponed, and if for instance we want to limit the number of qubits used, i.e., the size of the Hilbert space acted upon, we can trade width for depth without compromising the overall linear upper bound on the size of the circuit.

The ability to efficiently procedure arbitrary graph states has several advantages: it reduces the number of qubits involved in the computation, sometimes even quadratically, and hence decreases the possibilities of errors, it replaces two-qubit quantum operations by simple and reliable classical computations, and it allows tailoring the preparation to specific quantum algorithms such as Shor's factoring algorithm [START_REF] Aliferis | Computation by measurements: A unifying picture[END_REF].

We then introduce a new graph-theoretical measure, the local minimum degree, denoted ⇥ loc , and show that it is intimately linked to the complexity of preparing graph states. For instance, we use it to prove that any measurement-based quantum circuit for preparing graph states requires either ancilla qubits or multi-qubit measurements that act on at least ⇥ loc + 1 qubits (or both). We also establish that the local minimum degree is related to the entanglement in graph states, and we give a family of graphs for which the local minimum degree is large. Such families may be suitable for cryptographic purposes, though likely difficult to create in practice [START_REF] Goyal | Purification of large bi-colorable graph states[END_REF]. Other graph-theoretical measures related to graph states have recently and independently been considered in [START_REF] Markov | Simulating quantum computation by contracting tensor networks[END_REF][START_REF] Shi | Classical simulation of quantum many-body systems with a tree tensor network[END_REF][START_REF] Van Den Nest | Universal resources for measurement-based quantum computation[END_REF].

Graph states and signed graph states

A graph state on n qubits is a state that is a superposition over all basis states,

|G = 1 # 2 n x⌅{0,1} n ( 1) q (x) |x , (1)
where is the adjacency matrix of a graph G = (V, E) on n = |V | vertices and q (x) = i<j:(i,j)⌅E x i x j . The quadractic form q satisfies that q (x) = x T upper x where upper is the upper-triangle of obtained by setting entries i,j with i ⌦ j to zero, and where T denotes taking transpose.

For technical reasons, it is sometimes convenient to associate signs to graph states. Given any graph state |G and any subset S V the signed graph state |G; S is the state

|G; S = Z S |G , (2)
where Z S = ⌥ v⌅S Z v where Z v denotes that the local operator Z = |0 0| |1 1| acts on qubit v. We sometimes omit the signs when they are not essential for the discussion. We use similar abbreviated notation,

X S = ⌥ v⌅S X v and Y S = ⌥ v⌅S Y v , for the two other pauli-operators X = |1 0| + |0 1| and Y = # 1|1 0| # 1|0 1|.
Proposition 1 For all graphs G = (V, E) and all non-empty subsets S V , G; S|G = 0, and hence G; S|G; S ⇤ = 0 for all distinct subsets S, S ⇤ V , and the 2 |V | states {|G; S } S⇥V form an orthonormal basis.

Preparation of graph states

There is a simple algorithm for preparing the graph state |G corresponding to any graph G = (V, E) on n = |V | vertices with m = |E| edges. We first prepare n qubits in a superposition of all 2 n basis states,

|⌅ 0 = 1 # 2 n x⌅{0,1} n |x ,
by applying for instance the Hadamard operator

H = 1 2 |0 0| + |0 1| + |1 0| |1 1|
⇥ on each of the n qubits in the initial state |0 . Each of the qubits corresponds to a vertex of G. We then modify the phases of the basis states by applying a sequence of m two-qubit operations, producing the graph state |G ,

|G = ⌦ (u,v)⌅E ⇥ u (Z v )|⌅ 0 . (3)
For each edge (u, v) E, we apply the controlled phase change operator defined by

⇥ u (Z v ) = |00 00| + |01 01| + |10 10| |11 11|
on the two qubits labelled by the endpoints u, v of the edge. These m two-qubit operations are diagonal and thus commute, allowing us to apply them in any order of our choosing. Summarizing, we can prepare any graph state |G using n single-qubit operations and m two-qubit ⇥(Z) operations. Considering this simple algorithm a quantum circuit, we can prepare a graph state by a circuit on n qubits of size n+m and depth m+1 using only single-qubit and two-qubit operations.

The depth of the circuit may be improved by parallelizing the two-qubit operations by choosing an edge coloring of G [START_REF] Aliferis | Computation by measurements: A unifying picture[END_REF]. An edge coloring using ⌃ ⇤ colors is a mapping c : E {1, 2, . . . , ⌃ ⇤ } satisfying that if two distinct edges e and e ⇤ share one endpoint, then they are assigned different colors. Any graph has an edge coloring using at most ⇥(G) + 1 colors, where ⇥(G) is the maximum degree of the vertices in G, and we can find such an edge coloring in time polynomial in n and m, for instance by Vizing's (classical) algorithm [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF]. This implies that we can arrange the m two-qubit operations in our circuit such that it has depth at most ⇥(G) + 2.

Proposition 2 ([1]

) Any graph state |G can be prepared by a quantum circuit consisting of single-qubit and two-qubit operations of size O(n + m) and depth O(⇥(G)) acting on n qubits, where ⇥(G) is the maximum degree of any vertex in G.

The above proposition implies that graphs of bounded degree can be prepared by constant depth quantum circuits. In particular, two-dimensional cluster states, which is the common name for graph states arising from two-dimensional grid graphs, can be prepared by constant depth quantum circuits. We now extend this result and prove that arbitrary graphs can prepared in constant depth.

Theorem 3 (Constant depth graph state preparation) For any graph G, we can prepare some signed graph state |G; S by a constant depth quantum circuit consisting of single-qubit and two-qubit operations of size O(n + m) acting on n + O(m) qubits.

A key idea in our proof is to embed G as an induced minor of a larger graph of bounded degree, and then utilize that taking induced minors can be obtained by Pauli measurements.

We consider four types of substructures of a graph G = (V, E). A deletion of a vertex v V in G is the graph G \ v obtained from G by deleting v and all edges incident to v. A deletion of an edge e E in G is the graph G \ e obtained from G by simply deleting the edge e. A contraction of an edge (u, v) E in G is the graph G/(u, v) obtained from G by introducing edges between v and each vertex in N G (u) \ N G (v), and then deleting u and all its incident edges.

A graph G is an induced subgraph of G ⇤ if G is isomorphic to a graph that can be obtained from G ⇤ by vertex deletions. It is a subgraph of G ⇤ if we can obtain a graph isomorphic to G by edge deletions. It is a minor of G ⇤ if it
is isomorphic to a graph that can be obtained from G ⇤ by edge deletions and edge contractions, and it is an induced minor of G ⇤ if it is isomorphic to a graph that can be obtained from G ⇤ by vertex deletions and edge contractions. Any induced subgraph is also a subgraph, and any induced minor is also a minor.

The next two lemmas provide our main technical tools for generating the graph state |G .

Lemma 4 (Vertex deletion) Let v V be any vertex. Conducting a Z measurement of the qubit v maps |G to |G \ v and thus corresponds to deleting the vertex v.

Proof We first note that for any S V ,

|G; S = 1 # 2 |G \ v; S |0 v + |G \ v; S⇥N G (v) |1 v ⇥ L ⌥ ⇧ ⌃ v ⇤⇥ ⌅ R ⌥ ⇧ ⌃ Expansion Contraction ⇧ ⌅ L ⌥ ⇧ ⌃ v v ⇤ v ⇤⇤ ⇤⇥ ⌅ ⇤⇥ ⌅ ⇤⇥ ⌅ R ⌥ ⇧ ⌃ ⌃ ⌃ ⌃ ⌃ ⌃ ⌃ ⌃ ⌃
Figure 1: Embedding G as an induced minor of a bounded degree graph G by repeated applications of graph expansions. Conducting X measurements of qubits v ⇤ and v ⇤⇤ contracts the two edges (v, v ⇤ ) and (v ⇤ , v ⇤⇤ ).

which follows from Eqs. 2 and 3. If qubit v is Z-measured (that is, measured in the basis of the eigenvectors of the Pauli operator Z), the resulting state is thus either |G \ v; S or |G \ v; S⇥N G (v) (where ⇥ denotes the symmetric difference), and hence is equal to |G \ v up to (known) signs.

% $ Lemma 5 (Edge contraction) Let v, v ⇤ , v ⇤⇤ V so that N G (v ⇤ ) = {v, v ⇤⇤ } and N G (v) ⌫ N G (v ⇤⇤ ) = {v ⇤ }. Conducting an X measurement of each of the two qubits v ⇤ and v ⇤⇤ maps |G to |G/(v, v ⇤ )/(v ⇤ , v ⇤⇤ ) and thus corresponds to contracting the two edges (v, v ⇤ ) and (v ⇤ , v ⇤⇤ ).
Proof Let v, v ⇤ , v ⇤⇤ V be as in the lemma. For any subset S V ,

|G; S = Z S 2 k,l⌅{0,1} ⇧ Z k v ⇥⇥ Z l N G (v)\{v ⇥ } |G/vv ⇤ /v ⇤ v ⇤⇤ ⌃ |0 + Z l v ⇥ |1 ⇥ v ⇥ |0 + Z k v ⇥⇥ |1 ⇥ v ⇥⇥ and hence, if qubits v ⇤ and v ⇤⇤ are X-measured, the resulting state is |G/(v, v ⇤ )/(v ⇤ , v ⇤⇤ ) up to (known) signs. % $

Proof of Theorem 3

We first embed G as an induced minor of a larger graph G of bounded degree by repeatedly expanding any vertex v of degree d ⌦ 4 into three vertices v, v ⇤ , v ⇤⇤ of strictly smaller degrees, as illustrated in Figure 1. Formally, we partition the neighborhood N G (v) of v in two sets L and R of sizes d 2 ⌧ and ⇡ d 2 ⇢, respectively. We then set V = V {v ⇤ , v ⇤⇤ } and Ê = E \({v}⇤R) {(v, v ⇤ ), (v ⇤ , v ⇤⇤ )} ({v ⇤⇤ }⇤R). We set Ĝ = ( V , Ê), and recursively expand any vertex v of Ĝ till all vertices have degree at most three. The thus obtained graph G will have O(m) vertices and maximum degree three.

We first prepare the graph state | G by a constant-depth circuit on O(m) qubits by applying Proposition 2, and then apply Lemma 5 to contract | G to |G by applying X measurements on all vertices introduced during the expansion of G to G. The X measurements commute and can thus all be conducted in parallel by a circuit of depth one.

% $ Proposition 2 and Theorem 3 give two linear-size circuits for preparing any graph state, up to signs. The former has small width and large depth, the latter large width and small depth. We can trade width for depth in the above construction, without compromising the overall size of the circuit, by stopping the expansion once all vertices have degree at most T .

Theorem 6 (Small depth graph state preparation) For any graph G, we can prepare some signed graph state |G; S by a quantum circuit consisting of single-qubit and two-qubit operations of size O(n + m) and depth O(T ) acting on n + O(m/T ) qubits, for any integer T .

In the above theorems, we can replace the unitary operations by projective measurements. Any singlequbit unitary operation can be simulated using two single-qubit projective measurements, one two-qubit projective measurement, and one ancilla qubit [START_REF] Perdrix | State transfer instead of teleportation in measurement-based quantum computation[END_REF]. Similarly, a two-qubit control-not operation can be simulated using two single-qubit projective measurements, two two-qubit projective measurements, and one ancilla qubit [START_REF] Perdrix | State transfer instead of teleportation in measurement-based quantum computation[END_REF]. In Theorem 6, we may thus replace the unitary operations by projective measurements. We re-use the ancilla qubits in each of the ⇤(T ) layers of the circuit so that the the total number of additional ancilla qubits required by the simulation is only O(m/T ). In the standard circuit for graph preparation, in which each of the O(m) layers of the circuit consists of exactly one gate, we may similarly replace the unitary operations by projective measurements, yielding that any graph state can be prepared using n + 1 qubits by single-qubit and two-qubit projective measurements. We require only one ancilla qubit for iteratively simulating each of the O(m) two-qubit operations.

Proposition 8 (Measurement-based preparation using one ancilla qubit) For any graph G, we can prepare some signed graph state |G; S by a quantum circuit consisting of single-qubit and two-qubit projective measurements of size O(n + m) and depth O(m) acting on n + 1 qubits.

It would be interesting to extend Theorem 3 and its corollaries to incorporate noise and errors, for instance as discussed for cluster states in [START_REF] Duan | Efficient quantum computation with probabilistic quantum gates[END_REF].

Circuits and local complementation

The circuit constructions for preparation of graph states given above are based on the concept of graph minors. To improve the constructions further, we require the additional concept of local complementation in graphs. A local complementation is a graph operation that maps one graph into another. Kotzig first showed that the class of circle graphs are closed under local complementation (see [START_REF] De Fraysseix | Local complementation and interlacement graphs[END_REF][START_REF] Bouchet | ⇤-transformations, local complementations and switching. In Cycles and rays: Basic structures in finite and infinite graphs[END_REF]) and it was then used by Bouchet [START_REF] Bouchet | Circle graph obstructions[END_REF] to give a characterization of circle graphs.

A local complementation of a graph G at a vertex v V is the operation which replaces the subgraph of G induced by the neighborhood N G (v) of v by its complement. We denote the thus obtained graph by G v.

Local complementation defines an equivalence relation. We say two graphs G 1 and G 2 are locally equivalent if one can be obtained from the other by a sequence of local complementations, and write

G 1 ↵ loc G 2 .
A pivoting on a edge (u, v) E is the operation that maps G to G u v u. This operation is well-defined as G u v u = G v u v, and we denote it by G ⇠ (u, v). Following Oum [START_REF] Oum | Approximating rank-width and clique-width quickly[END_REF], we say a graph H is a vertex minor of G if H can be obtained from G by vertex deletions and local complementations. A graph H is a pivot minor of G if H can be obtained from G by vertex deletions and pivotings.

The most important property of local complementation for this paper, is that it can be implemented by local quantum operations. Let G and G ⇤ be two locally equivalent graphs, G ↵ loc G ⇤ . Then there exists a tensor product U = ⌥ v⌅V U (v) of n single-qubit unitary operations U (v) such that |G ⇤ = U|G . This implies that if C is a circuit that maps |⌅ 0 to |G ⇤ , then UC is a circuit that maps |⌅ 0 to |G . Thus, any two locally equivalent graphs can be implemented by circuits of the same depths, up to an additive constant of 1.

Let ⇥(G) = min{deg G (v) : v V } denote the minimum degree of any vertex in G, where deg G (v) denotes the degree of v in G. Let ⇥ loc (G) = min{⇥(G ⇤ ) : G ⇤ ↵ loc G} denote the minimum degree achievable by local complementations. We refer to ⇥ loc as the local minimum degree of G. Similarly, let m loc (G) = min{|E ⇤ | : (V, E ⇤ ) ↵ loc G} denote the minimum total number of edges achievable by local complementations. Unfortunately, there is no known polynomial-time algorithm for computing either of the two quantities ⇥ loc (G) and m loc (G), given a graph G as input. The thus far best result in this direction is a result of Bouchet [START_REF] Bouchet | Diagraph decompositions and eulerian systems[END_REF] stating that the problem of deciding if two graphs are locally equivalent is polynomial-time computable. Van den Nest [START_REF] Van Den Nest | Local equivalence of stabilizer states and codes[END_REF] gives in his Ph.D. thesis a short description of Bouchet's algorithm.

The quantity m loc is related to the size of any quantum circuit preparing a graph state. Suppose we could find a polynomial-time algorithm that given any graph, outputs a locally equivalent graph of minimum total degree. Then in Theorems 3, 6 and 7, we could replace m by m loc , and still have polynomial-time constructable quantum circuits. However, currently no such result is in sight.

We now show that ⇥ loc is related to the usage of ancilla qubits in the circuits for preparing graph states. To prove this, we first give three equivalent definitions of ⇥ loc , the first graph theoretical, the second combinatorial, and the third algebraic. We require the following notation and concepts.

For any subset X V of vertices, let Odd G (X) = {u V \ X : N G (u) ⌫ X = 1 mod 2} denote the set of vertices that is adjacent to an odd number of vertices in X in G. Similarly, let Even G (X) = {u V \ X : N G (u) ⌫ X = 0 mod 2}. We say that the vertices in Odd G (X) are odd neighbors of X in G, and that the vertices in Even G (X) are even neighbors of X in G.

The cut-matrix of a subset X V of vertices is the submatrix G (X, V \ X) indexed by X ⇤ (V \ X) of the adjacency matrix G of G. The cut-rank Cutrk(X) of X is the rank of its cut-matrix, where we define the rank over GF [START_REF] Bouchet | Diagraph decompositions and eulerian systems[END_REF]. The cut-rank of X is invariant under local complementation [START_REF] Bouchet | Connectivity of isotropic systems[END_REF], though the null-space of G (X, V \ X) may change under local complementation. It was used by Bouchet [START_REF] Bouchet | Diagraph decompositions and eulerian systems[END_REF] and others under the name "connectivity function", and coined the cut-rank by Oum [START_REF] Oum | Approximating rank-width and clique-width quickly[END_REF]. We say that a set of vertices L V is local if L = X Odd G (X) for some subset X L. Note that a local set L does not have full cut-rank, and that {v} N G (v) is local for any vertex v V .

Lemma 9

Any local set L is invariant under local complementation. Moreover, for all y L, there exists a graph G ⇤ locally equivalent to G such that {y} Odd G ⇥ ({y}) L.

Proof Suppose that L = X Odd G (X). We consider how the three-way partition V = X Odd G (X) Even G (X) changes under local complementation at a vertex v V . Let G ⇤ = G v. Then the three-way partition changes as follows.

X ⇤ Odd G ⇥ (X ⇤ ) Even G ⇥ (X ⇤ ) v Even G (X) X Odd G (X) Even G (X) v Odd G (X) X {v} Odd G (X) \ {v} Even G (X) v X and |N X (v)| is odd X \ {v} Odd G (X) {v} Even G (X) v X and |N X (v)| is even X Odd G (X) Even G (X)
The forth and last column implies that any local set L is invariant under local complementation, and thus only the internal structure of L changes. By the second row, we can move vertex y into X, if y Odd G (X). By the third row, we can move vertices out of X as long as there exists a vertex in X having an odd number of neighbors in X. If all vertices in X have an even number of neighbors in X, and if any vertex in X has a neighbor z in Even G (X), then a local complementation at z creates at least two vertices in X having an odd number of neighbors in X. One of these must be a vertex different from y. Thus, by a sequence of local complementations, we can map G to some graph G ⇤ in which there are no edges between X and Even G ⇥ (X), and in which y X. Hence N G ⇥ (y) L and thus {y} Odd G ⇥ ({y}) L. % $ Corollary 10 Let x V be any vertex of degree d = deg G (x). Then for all neighbors y N G (x), there exists a graph G ⇤ locally equivalent to G for which N G ⇥ (y) = (N G (x) {x})\{y}. In particular, all neighbors of x can be locally reduced to having degree d.

Theorem 11 (Characterization of local minimum degree)

For any graph G, the local minimum degree ⇥ loc (G) is equal to

1. min ⇤ ⇥(G ⇤ ) : G ⇤ ↵ loc G ⌅ .
2. min ⇤ |L| : L is nonempty and local} 1.

min

⇤ |X| : Cutrk(X) < |X| ⌅ 1.
Proof We first show that the quantity in (1) is an upper bound on the quantity in [START_REF] Bouchet | Diagraph decompositions and eulerian systems[END_REF]. Let y V be a vertex of degree

⇥ loc (G) in G ⇤ ↵ loc G. Then {y} N G ⇥ (y) is local.
Similarly, we show that the quantity in (2) is an upper bound on the quantity in [START_REF] Bouchet | Connectivity of isotropic systems[END_REF].

Let L = X Odd G (X) be local. Then ⌃ X G [L, V \ L] = 0
, where ⌃ X is the indicator function of X in L, and thus L does not have full cutrank. Finally, we show that the quantity in (3) is an upper bound on the quantity in (1). Let X V be a set that does not have full cutrank. Let

Y V \ X be such that ⌃ Y [X, V \ X] = 0. Then Odd G (Y ) X. By Lemma 9, for all y Y , there is a graph G ⇤ locally equivalent to G such that deg G ⇥ (y) |X| 1.
% $ By Theorem 11, for any fixed integer d, there exists a polynomial-time algorithm for deciding if ⇥ loc > d. If d is part of the input, no polynomial-time algorithm is known. Though plausible, it is not known whether the concept of cut-rank is helpful in computing ⇥ loc in polynomial time. One result in this direction is by Oum [START_REF] Oum | Approximating rank-width and clique-width quickly[END_REF], who gives a polynomial-time algorithm that given any two disjoint non-empty sets of vertices A, B V as input, computes the value min{Cutrk(Z) : X Z V \ B} by greedily searching for blocking sequences as introduced by Geelen [START_REF] Geelen | Matchings, Matroids and Unimodular Matrices[END_REF].

We now use the above characterization to show that if no ancilla qubits are available for preparing a graph state, then joint projective measurements on at least ⇥ loc (G) + 1 qubits are required. As a consequence, for all graphs for which ⇥ loc > 1, there does not exist a measurement-based preparation using only single-qubit and two-qubit projective measurements without the use of ancilla qubits. It follows that W acts trivially on |G; S⇥U for all subsets U X. Since these 2 |X| states are pairwise orthogonal, W is the identity, which is a contradiction.

% $

It is natural to consider recursive methods for preparing a graph state G, for instance by partitioning the vertex set V into parts which then are considered individually. The next lemma states that deleting any one vertex or edge may decrease the local degree by at most one.

Lemma 13

For any graph G = (V, E), any vertex u V , and any edge e

= (v, w) E, ⇥ loc (G \ v) ⌦ ⇥ loc (G) 1 and ⇥ loc (G \ e) ⌦ ⇥ loc (G) 1.
Proof Let X V \ {u} be any set of vertices satisfying that Cutrk G\u (X) < |X|. Then Cutrk G (X {u}) Cutrk G\u (X) + 1 < |X {u}|. Now, let X V be any set of vertices satisfying that Cutrk G\e (X) < |X|, and consider an edge e = (v, w) E. Suppose we are given an oracle O that given any graph G returns ⇥ loc (G). Then there exists a deterministic algorithm that given any graph G outputs a graph G ⇤ locally equivalent to G with ⇥(G ⇤ ) = ⇥ loc (G). The algorithm runs in time polynomial in n and uses at most a linear number of oracle queries. The proof is given in Appendix A.

Firstly, if v, w X or v, w ✏ X, then Cutrk G (X) = Cutrk G\e (X). Secondly, if v X and w ✏ X, then Cutrk G (X {w}) = Cutrk G\e (X {w}) Cutrk G\e (X) + 1 < |X| + 1 = |X {w}|. % $ a b c d e f ⇤ ⇤ ⇥ ⇥ ⇥ ⌥ ⌥ ⌥ ⇥ ⇥ ⇥ ⇥ ⇥ ⇥ ⇥ ⌥ ⌥ ⌥ ⌥ ⌥ ⌥ ⌥

Theorem 14

The following two computational problems are polynomially equivalent: (1) computing ⇥ loc (G) and ( 2) finding a graph G ⇤ with G ⇤ ⌥ G and ⇥(G ⇤ ) = ⇥ loc (G).

Bi-separability and loc

An n-qubit state ⌅ is bi-separable if there exists a partition A, B of V such that ⌅ can be written on the form Proof Let G ⇤ be a graph that is locally equivalent to G and contains a vertex v of degree d = ⇥ loc (G). We show that the state ⌅ obtained from |G ⇤ G ⇤ | by tracing out the d qubits corresponding to the neighbors N G ⇥ (v) of v is separable. We do this by giving a procedure for preparing ⌅ that preserves separability.

⌅ = k i=1 i ⌅ A i ⌃ ⌅ B i for
Let H = G ⇤ \ N G ⇥ (v) be the subgraph of G ⇤ obtained by removing the neighbors N G ⇥ (v) of v. The subgraph H consists of (at least) two components, {v} and the rest. The graph state |H is thus separable and can be written on the form |v |H \ {v} .

Consider we first prepare the separable pure state |H . Now for each neighbor w N G ⇥ (v) in turn, we randomly flip an unbiased coin. If the outcome of the coinflip is head, we apply a (single-qubit) ⇧ z operation on each of the qubits of |H corresponding to the neighbors N G ⇥ (w) ⌫ H of w. If the outcome of the coinflip is tail, we do not alter the state. This maps the state |v |H \ {v} to some other pure state |v |H ⇤ that is also separable with respect to the same partitioning of vertices. We take sum of the density operators |v |H ⇤ H ⇤ | v| over all 2 d possible outcomes, yielding a density operator ⌅ ⇤ that is separable with respect to the same partitioning. The density operator ⌅ ⇤ is the same as the density operator ⌅ obtained by tracing out the neighbors N G ⇥ (v) of v in G ⇤ , and thus ⌅ is separable.

% $

The upper bound of ⇥ loc (G) on separability in Theorem 15 is tight for some graphs, but not all. An example for which the bound is not tight is the prism graph P on six vertices, illustrated in Figure 2. On the one hand, any local set in P has size at least 4, and hence its local minimum degree is (at least) 3 by Theorem 11. On the other hand, if we trace out qubits b and e in |P , the remaining state is separable across the cut ({a, d}, {c, f }). One way of seeing this, is to first delete the edge (b, e), do a local complementation on b and then e, deleting b and e, and noticing that the remaining graph consists of two components, {a, d} and {c, f }. It would be interesting to explore the relationship between ⇥ loc and separability further, and also to consider k-separability and full separability [START_REF] Eisert | Lectures on Quantum Information, chapter Multi-particle entanglement[END_REF].

We show in Appendix B that there exists a natural family of graphs for which ⇥ loc is polynomial in the input graph. It seems plausible that this family of graphs contains entanglement that is very robust against quantum operations acting on a sublinear number of qubits, and thus could be useful in for instance quantum cryptography and quantum communication complexity.

Corollary 16

There exists a constant c > 0 and a family of graphs G for which ⇥ loc (G) ⇧(|G| c ).

Theorem 7 (

 7 Measurement-based preparation) For any graph G, we can prepare some signed graph state |G; S by a quantum circuit consisting of single-qubit and two-qubit projective measurements of size O(n+m) and depth O(T ) acting on n + O(m/T ) qubits, for any integer T .

Theorem 12 (

 12 Lower bound on measurement-based preparation)Let G be any graph. Any preparation of |G by a quantum circuit acting on n qubits and consisting of projective measurements requires measurements acting on ⇥ loc (G) + 1 qubits.Proof By contradiction. Assume the last measurement of the preparation acts on at most ⇥ loc (G) qubits X and that it produces the signed graph state |G; S . Let W be the observable describing this measurement. Then W|G; S = |G; S , and thus G; S|W|G; S = 1.Let U X be any subset of the measured vertices X. Since |X| ⇥ loc (G), subset X has full cutrank by Theorem 11, and thus there exists a subset YV \ X such that ⌃ U = [X, V \ X]⌃ Y .The operator X Y acts only on qubits not in X, and thus commutes with W. In addition, Z Odd(Y ) X Y |G; S = ±|G; S , and hence 1 = G; S|W|G; S = G; S|X Y WX Y |G; S = G; S|Z Odd(Y ) WZ Odd(Y ) |G; S = G; S|Z U WZ U |G; S = G; S⇥U |W|G; S⇥U .

Figure 2 :

 2 Figure 2: The prism graph P on six vertices. Tracing out vertices b and e from |G creates a separable mixed state.