## Abstract

We present a technique for de-randomizing large deviation bounds of functions on the unitary group. We replace the Haar measure with a pseudo-random distribution, a *k*-design. *k*-Designs have the first *k* moments equal to those of the Haar measure. The advantage of this is that (approximate) *k*-designs can be implemented efficiently, whereas Haar random unitaries cannot. We find large deviation bounds for unitaries chosen from a *k*-design and then illustrate this general technique with three applications. We first show that the von Neumann entropy of a pseudo-random state is almost maximal. Then we show that, if the dynamics of the universe produces a *k*-design, then suitably sized subsystems will be in the canonical state, as predicted by statistical mechanics. Finally we show that pseudo-random states are useless for measurement-based quantum computation.

## 1. Introduction

There are many results in quantum information theory that show generic properties of states or unitaries (e.g. Hayden *et al.*2004, 2006). Often, these results say that, with high probability, a random state or unitary has some property, for example high entropy. However, simple parameter counting shows that random unitaries cannot be obtained efficiently. This limits the usefulness of such results since no physical systems will behave truly randomly. To make such results more physically relevant, it would be desirable to show that these properties are generic properties of unitaries from some natural distribution that can be implemented efficiently. Only then could we conclude that we would expect to see such properties in natural systems.

In many cases, the generic properties of unitaries are desirable but randomized constructions given by the large deviation bounds are inefficient. We would like to come up with distributions which can be implemented efficiently that have similar generic properties. One example where the best known construction is an inefficient randomized one is the -norm randomizing map (Hayden *et al.* 2006; Aubrun 2008), which is a quantum map that takes any state to a state close to the identity, as measured by the -norm. Another example is locking of classical correlations (DiVincenzo *et al.* 2004; Hayden *et al.* 2006), which is a quantum phenomenon whereby a small amount of communication can greatly enhance the classical correlation between two parties. To prove the randomized constructions, the authors show that, with some non-zero probability, random unitaries have the required property. However, there are no known efficient constructions of unitaries with these properties. If, on the other hand, we could show that unitaries drawn randomly from a set that can be implemented efficiently have the property with non-zero probability, we could move an important step closer to finding efficient constructions. (It would not actually provide an efficient construction unless we could find an efficient sampling method.) In fact, for the case of -norm randomization, this was done by Aubrun (2008).

By random unitaries, we mean unitary matrices distributed according to the unitarily invariant Haar measure, which is the unique measure on the unitary group with the property of unitary invariance. In this paper, we will consider replacing the Haar measure with a *k*-design. A unitary *k*-design is an ensemble of unitaries such that the *k**t**h* moments are the same as for the Haar measure (Dankert *et al.* 2006) (*k*-designs are formally defined in §2). In particular, this means that the expectation of a polynomial in the elements of the unitary matrices of degree at most *k* is the same whether the distribution is the Haar measure or a *k*-design. We will also consider replacing Haar random states with a state *k*-design, which is an ensemble of states such that the *k*th moments are the same as for the Haar measure (Ambainis & Emerson 2007).

The reason for using *k*-designs is twofold. Firstly, because the first *k* moments are the same we would expect similar (although weaker) measure concentration results. Secondly, for *k*=poly(*n*) (when the design is on *n* qubits), we might expect to be able to implement the *k*-design efficiently (i.e. in poly(*n*) time). Indeed, for , Harrow & Low (2008*a*) provide an efficient *k*-design construction, provided we allow for approximate designs. However, in the applications we consider here we can always make the approximation good enough to make the error negligible.

Not only can *k*-designs be constructed efficiently, they may even be the product of generic dynamics. In Harrow & Low (2008*b*), it is shown that random quantum circuits quickly converge to a 2-design for a quite general model of such circuits. It is also conjectured in Harrow & Low (2008*b*) that random circuits give *k*-designs for *k*>2 and *k*=poly(*n*) in polynomial time. If a physical system can be accurately modelled by a random circuit then, assuming this conjecture, the naturally occurring states will be *k*-designs rather than fully random states.

We now summarize some related results in this area. Smith & Leung (2006) and Dahlsten & Plenio (2006) found large deviation bounds for stabilizer states. They showed that, in certain regimes, stabilizer states are very likely to have large entanglement. Stabilizer states are state 2-designs, so our results can be seen as a generalization of this to *k*-designs for *k*>2 and to other problems. There are also some recent classical results related to the present work. Alon & Nussboim (2008) consider replacing full randomness with *k*-wise independence, a classical analogue of *k*-designs, in random graph theory. They show that *k*-wise independent random graphs with (*N* is the number of vertices) have similar generic properties to fully random graphs.

### (a) Introductory problem: entanglement of a 2-design

We now illustrate our main idea by showing a large deviation bound for the entanglement of a 2-design, but in a different way to Smith & Leung (2006) and Dahlsten & Plenio (2006).

It has been known for a long time that random states are highly entangled across any bipartition (Page 1993; Foong & Kanno 1994; Sanchez-Ruiz 1995). Further, in Hayden *et al.* (2006), it is shown that random unitaries generate almost maximally entangled states with high probability. However, generating random states is inefficient, so it is an interesting question to ask if random efficiently obtainable states are highly entangled.

Let the system be , where we label the two systems *S* and *E*. Let the dimensions be *d*_{S} and *d*_{E} and *d*=*d*_{S}*d*_{E}. Let the overall initial state be any fixed state ρ_{0}. Then consider applying a random unitary *U* to *S**E* to get the state ψ=*U*ρ_{0}*U*^{†}. Then the von Neumann entropy *S*(ψ_{S}) of the reduced state ψ_{S}=tr_{E}ψ is close to (the maximal) with high probability:

### Theorem 1.1 (Hayden et al. (2006), theorem 3.3).

*Let d*_{E}≥*d*_{S}≥3. *Then for unitaries chosen from the Haar measure*
1.1
*where C*=1/8π^{2} *and* .

Now, consider choosing the unitary from a 2-design instead. Later on (lemma 4.1), we show that . Since purity is a polynomial of degree 2, it does not matter if we take the expectation over the Haar measure or the 2-design. We now apply Markov’s inequality:
Using the bound and some manipulations (the details are in §4), this can be written as
1.2
where β is as in theorem 1.1. This bound is much weaker than the bound in theorem 1.1 and, in particular, does not show stronger concentration as *d* increases. Later in the paper, we will show that choosing unitaries from a *k*-design with larger *k* will give a much stronger bound that does give sharp concentration results for large *d*.

### (b) Main results

We will now state our main results. In the remainder of the paper we will use the following notation to identify the measure we are using. When the unitaries are chosen from a measure ν, we will write to mean , the probability when *U* is chosen from ν. Similarly for , the expectation. Usually ν will be a *k*-design. When the measure is the Haar measure, we will write a subscript *H*. So for the Haar average we write for .

Our most general result is:

### Theorem 1.2.

*Let f be a polynomial of degree K. Let* *where M*_{i}(*U*) *are monomials and let* . *Suppose that f has probability concentration*
1.3
*and let ν be an ε-approximate unitary k-design. Then*
1.4
*for integer m with* 2*mK*≤*k*.

We therefore take a bound for Haar random unitaries of the form equation (1.3) and turn it into a bound for *k*-designs. For our definition of ε-approximate designs, see §2. Often, we will use Levy’s Lemma (lemma 3.2) to give the initial concentration bound in equation (1.3). In this case, *a*=Θ(*d*) (provided the Lipschitz constant (see later) is constant).

We then apply this to entropy, as a generalization of §1*a*. We go via the 2-norm since the entropy function is not a polynomial. We find

### Theorem 1.3.

*Let ν be a* 4^{−n2}-*approximate unitary* -*design on dimension* 2^{n} *with n*≥19. *Let**d*_{S}*d*_{E}=2^{n} *and* 2≤*d*_{S}≤2^{n/10} *and* α≥2. *Then*,
1.5
*where* *and* *is the exponential function base 2*.

We choose a *k*-design for since this is (up to constants) the largest *k* for which we have an efficient unitary *k*-design construction (see §2*a*).

We then move on to apply our results to ideas in statistical mechanics from Popescu *et al.* (2006). In this paper, the authors show that, for almost all pure states of the universe, any subsystem is very close to the canonical state, which is the state obtained by assuming a uniform distribution over all allowed states of the universe (defined in equation (5.2)). This could be achieved if the dynamics of the universe produced a random unitary, but this would take exponential time in the size of the universe. We show that the random unitary can be replaced by a *k*-design, showing that the canonical state can be reached in polynomial time:

### Theorem 1.4.

*Let Ω*_{S} *be the canonical state of the system* (*defined in equation* (5.2)) *and ρ*_{S} *be the state after choosing a unitary from an ε-approximate k*-*design. Let d*_{R} *be the dimension of the universe’s Hilbert space subject to the arbitrary constraint R* (*normally this will be a total energy constraint*). *Then for* ,
1.6

Finally, we use results from Gross *et al.* (2008) to show that most states in an *O*(1)-approximate state *n*^{2}-design on *n* qubits are useless for measurement-based quantum computing (MBQC), in the sense that any computation using such states could be simulated efficiently on a classical computer. We do this, following Gross *et al.* (2008), by showing that the states are so entangled that the measurement outcomes are essentially random.

### (c) Optimality of results

An important question is how close our results are to optimal, in terms of their scaling with dimension *d*. In theorem 1.2, we will normally have *a*=Θ(*d*) so for *m* constant, we obtain polynomial bounds, rather than the exponential bounds for full randomness. This is to be expected:

### Theorem 1.5.

*Let ν be an ε-approximate unitary k*-*design. Suppose also that it is discrete, i.e. contains a finite number S of unitaries. Let f*(*U*) *be any function on matrix elements of U and μ be any constant. Then either**f*(*U*)=*μ for all U in ν or for some δ* >0,
1.7

*where*

*is the probability of choosing the least probable unitary from ν. If the probability is uniform*, .

### Proof.

There exists at least one *U* such that |*f*(*U*)−μ|≥δ for some δ>0; the probability of selecting one such *U* is at least . ▪

### Corollary 1.6.

*Our results are polynomially related to the optimal*(*i.e. the optimal bounds can be obtained by raising ours to a constant power*).

### Proof.

Our results apply for any design, so must obey the bound in theorem 1.5 for all designs. The unitary design construction we use (lemma 2.7) has , hence the bounds cannot scale better than this. ▪

We can also almost recover the tail bound for full randomness in theorem 1.2. Suppose for simplicity that we have an exact design (i.e. ε=0), so that
The optimal *m* is *a*δ^{2}/e, which gives
So our result allows us to interpolate from Markov’s inequality, which gives weak bounds, all the way to full Haar randomness and is within a polynomial correction of optimal for the full range.

The remainder of the paper is organized as follows. In §2 we formally define *k*-designs and what we mean by approximate designs. Then in §3 we present our main technique for finding large deviation bounds for *k*-designs. We then apply this to entropy in §4, to ideas in statistical mechanics in §5 and to using *k*-designs for MBQC in §6. We then conclude in §7.

## 2. *k*-Designs

Here we formally define *k*-designs.

## Definition 2.1.

Let ν be a distribution on the unitary group. *ν* is a unitary *k*-design if
2.1
for all *d*^{k}×*d*^{k} complex matrices ρ (not necessarily valid states).

We can write this as an equivalent, and for our purposes more useful, definition in terms of monomials of the elements of the matrices. We will first define what we mean by degree of a monomial (or polynomial):

## Definition 2.2.

A monomial in elements of a matrix *U* is of degree (*k*_{1},*k*_{2}) if it contains *k*_{1} conjugated elements and *k*_{2} unconjugated elements. We call it balanced if *k*_{1}=*k*_{2} and will simply say a balanced monomial has degree *k* if it is degree (*k*,*k*). A balanced polynomial is of degree *k* if it is a sum of balanced monomials of degree at most *k*.

So that, in this definition, *U*_{ij}*U**_{pq} is a balanced monomial of degree (1,1) and *U*_{ij}*U*_{kl} is a monomial of degree (2,0) and is unbalanced. We now state an equivalent definition of unitary *k*-designs in terms of monomials:

## Definition 2.3.

ν is a unitary *k*-design if, for all balanced monomials *M* of degree *k*,
2.2

That definitions 2.1 and 2.3 are equivalent can be seen by considering matrices ρ of the form |*i*_{1},*i*_{2},…,*i*_{k}〉〈*j*_{1},*j*_{2},…,*j*_{k}| in definition 2.1. Then each element of *U*^{⊗k}ρ(*U*^{†})^{⊗k} is a balanced monomial of degree *k*. Further, each balanced monomial appears for some choice of ρ.

We will use state *k*-designs, which are related to unitary *k*-designs although less general:

## Definition 2.4.

Let ν be a distribution on states and let ν_{H} be the uniform distribution on states, which can be thought of as a random unitary being applied to any fixed state. Then ν is a state *k*-design if
2.3

By considering unitaries acting on a fixed state, it can be seen that a unitary *k*-design can provide a state *k*-design, although the reverse is not necessarily true.

### (a) Approximate *k*-designs

There are no known efficient constructions of exact unitary *k*-designs. However, for our purposes, only approximate designs are required. In Ambainis & Emerson (2007), the authors define an ε-approximate state *k*-design using the -norm:

### Definition 2.5 (Ambainis and Emerson 2007).

*ν* is an *ε*-approximate state *k*-design if
2.4

appears because it is the dimension of the symmetric subspace.

We will need a definition of an approximate unitary design and will use a slightly different form to the approximate state design definition above that is simpler for our purposes:

### Definition 2.6.

*ν* is an *ε*-approximate unitary *k*-design if, for all balanced monomials *M* of degree ≤*k*,
2.5

While this definition is different to previous approximate *k*-design definitions (e.g. Dankert *et al.* 2006; Harrow & Low 2008*b*), it is equivalent up to multiplying ε by a polynomial (or inverse polynomial) in dimension. Since any reasonable construction of such a design will use resources that scale with , this leads to only differences in resource requirements between the definitions.

Finally, we will show how to construct an approximate unitary design according to definition 2.6. We would like to be able to have an ε-approximate *k*-design from which we can sample and implement the unitaries using resources. Firstly, Ambainis & Emerson (2007) provide an efficient construction of an ε-approximate state *k*-design for all *k*≤*d*/2. For unitary designs, we can use the efficient tensor product expander construction by Harrow & Low (2008*a*). A (*d*,*D*,λ,*k*) tensor product expander (TPE) is an ensemble of *D* unitaries ν in dimension *d* with, for all ρ,
2.6
where λ<1. In Harrow & Low (2008*a*), an efficient construction is presented with *D* and λ constant for . In particular, we can obtain an efficient construction for . To obtain a design according to definition 2.6, we can iterate the expander:

### Lemma 2.7.

*Iterating a* (*d*,*D*,λ,*k*)-*TPE* *times gives an ε-approximate unitary k-design*.

The slightly technical proof is presented in appendix A*a*. Using the efficient TPE construction from Harrow & Low (2008*a*), we have an efficient construction of an ε-approximate *k*-design for .

## 3. Main technique

The main idea in this paper can be summarized in three steps. Let be a balanced polynomial of degree *K* in the matrix elements of a unitary *U*. Then to obtain a concentration bound on *f* when *U* is chosen from a *k*-design:

Find some measure concentration result for |

*f*(*U*)−μ| when the unitaries are chosen uniformly at random from the Haar measure. Normally, μ will be the expectation of*f*.Use this to bound the moments for some integer

*m*≤*k*/2*K*.Then use Markov’s inequality and the fact that for a (approximate)

*k*-design the moments are (almost) the same as for uniform randomness. We then optimize the bound for*m*, which will often involve setting*m*close to the maximum, ⌊*k*/2*K*⌋.

We will now work through each of these steps and finish with a proof of theorem (1.2).

### (a) Step 1: concentration for uniform randomness

For the first step, we will often start with Levy’s Lemma. This states, roughly speaking, that slowly varying functions in high dimensions are approximately constant. We quantify ‘slowly varying’ by the Lipschitz constant:

### Definition 3.1.

The Lipschitz constant η (with respect to the Euclidean norm) for a function *f* is
3.1

Then we have Levy’s Lemma:

### Lemma 3.2 (Levy, see Ledoux 2001).

*Let f be an η-Lipschitz function on U*(*d*) *with mean* . *Then*
3.2
*where**C*_{1} *can be taken to be* 2/(9π^{3}).

### (b) Step 2: a bound on the moments

Levy’s Lemma says that *f* is close to its mean. This means that should be small. We will bound the moments for slightly more general concentration results:

### Lemma 3.3.

*Let X be any random variable with probability concentration*
3.3
(*Normally μ will be the expectation of X*,*although the bound does not assume this*.) *Then*
3.4
*for any**m*>0.

### Proof.

This proof is based on the proof of an analogous result by Bellare & Rompel (1994), lemma A 1.

Note that, for any random variable *Y* ≥0,
3.5
Therefore
where in the last line we used the assumed large deviation bound equation (3.3). To evaluate this integral, use the change of variables *y*=*a**x*^{2/m} to get
▪

### (c) Step 3: a concentration bound for a *k*-design

Now we show how to obtain a measure concentration result for polynomials when the unitaries are selected from an approximate *k*-design. We first show that the moments of |*f*−μ| for *f*, a polynomial, are close to the Haar measure moments:

### Lemma 3.4.

*Let f be a balanced polynomial of degree K and μ be any constant. Let* *where each M*_{i} *is a monomial. Let* . *Then for m an integer with* 2*m**K*≤*k and ν an ε-approximate k*-*design*,
3.6

### Proof.

For simplicity, we assume that *f* and *μ* are real. Our proof easily generalizes to the complex case.

Firstly we calculate using the multinomial theorem: We now calculate : ▪

Now we can simply apply Markov’s inequality to prove theorem 1.2.

We finish this section with two remarks. Firstly, provided α( *f*) (the sum of the absolute value of all the coefficients) is at most polynomially large in *d*, we can choose ε to be polynomially small to cancel this at no change to the asymptotic efficiency. Secondly, when applying the theorem we will optimize the choice of *m* (and normally choose *k*=2*m**K*). Often *a*=Θ(*d*) and the optimal choice of *m* is often Θ(*d*) as well. However, we will not take *m* so large because we can only implement an efficient *k*-design for .

## 4. Application 1: entropy of a *k*-design

We now apply the above to show that most unitaries in a *k*-design generate large amounts of entropy across any bipartition, provided the dimensions are sufficiently far apart. This means that, for any initial state, for most choices of a unitary from a *k*-design applied to the state, the resulting state will be highly entangled. We go via the purity of the reduced density matrix, since the entropy function is not a polynomial.

We will call the two systems *S* (the ‘system’) and *E* (the ‘environment’) and calculate the purity of the reduced state. That the purity, tr[(tr_{E} *U*ρ*U*^{†})^{2}], is a balanced polynomial of degree 2 is easily seen by noting that the trace is linear and the reduced state is squared. However, we should check that there are not too many terms or terms with large coefficients. To do this, we should calculate α to apply theorem 1.2.

There is a general method for calculating α(*f*) which we will use. Write for monomials *M*_{i}. To evaluate , calculate *f*(*A*) where *A* is the matrix with all entries equal to 1 (so that *M*_{i}(*A*)=1) and replace α_{i} with |α_{i}|. Using this here we find
We now calculate the expected purity:

## Lemma 4.1.

*The expected purity of the reduced state is*(*d*_{S}+*d*_{E})/(*d*+1), *where d*_{S} *is the dimension of subsystem S and d*_{E}=*d*/*d*_{S} *is the dimension of subsystem* *E*.

## Proof.

We have
4.1
where is the swap acting between systems *S*_{1} and *S*_{2}. By linearity of the trace, we can commute the through and use to find
▪

Working out the higher moments in this way is difficult (although has been done in Giraud 2007), so we use Levy’s Lemma and lemma 3.3. To use Levy’s Lemma, all we have to do is find the Lipschitz constant for the purity:

## Lemma 4.2.

*The Lipschitz constant for purity is* ≤2.

## Proof.

Now we use |||*S*||_{2}−||*T*||_{2}|≤||*S*−*T*||_{2} to find
using the fact that the purity is upper bounded by 1. ▪

## Lemma 4.3

*For μ*=(*d*_{S}+*d*_{E})/(*d*+1) *and m an integer with m*≤*k*/4 *and ν an ε-approximate k*-*design*,
4.2

## Proof.

We use the fact that von Neumann entropy is lower bounded by the Renyi 2-entropy, i.e. 4.3 Then using theorem 1.2 in the last line. ▪

We have written this in a more convenient form in theorem 1.3, which is proved in the appendix A*b*. This is to be compared with the Haar random version theorem 1.1. As expected, we have appearing in the exponent rather than *d*. Note also that our bound does not work well for *d*_{S}≈*d*_{E}. In fact, in this case, we do not get a bound that improves with dimension. To get this, *d*_{S} must be polynomially smaller than *d*_{E}.

## 5. Application 2: *k*-designs and statistical mechanics

We can also apply these ideas to partially de-randomize some of the arguments on the foundations of statistical mechanics in Popescu *et al.* (2006). In this paper, the authors develop the idea that the uncertainty in statistical mechanics comes from entanglement rather than the traditional assumption of the principle of equal *a priori* probabilities. They consider the universe being in a pure quantum state and that the uncertainty in the state of a subsystem comes from the entanglement between this system and the rest of the universe.

The setting is that there is an arbitrary global linear constraint *R*. Often this will be a total energy constraint although this is not assumed. Let the Hilbert space of states satisfying *R* be . Then let the system and environment Hilbert spaces be and , respectively. Then
5.1
Let the dimensions be *d*_{R}, *d*_{S} and *d*_{E} and let . Note that *d*_{R}≤*d*_{S}*d*_{E}, unlike in the above where we took *d*=*d*_{S}*d*_{E}. Normally, we will have *d*_{S}≪*d*_{R}. The principle of equal *a priori* probabilities says that the state of the universe is , which implies that the subsystem state is the canonical state, given by
5.2
The main result of Popescu *et al.* (2006) (the ‘principle of *apparently* equal *a priori* probabilities’) is that, for almost all pure states of the universe, the subsystem state is almost exactly the canonical state.

## Theorem 5.1 (Popescu et al. (2006), theorem 1).

*For a randomly chosen state* *and arbitrary ε*>0, *the distance between the reduced density matrix of the system ρ*_{S}=tr_{E}(|ϕ〉〈ϕ|) *and the canonical state Ω*_{S} (*equation* (5.2))*is given probabilistically by*
5.3
*where C*_{2}=1/(18π^{3}) *and* .

This result gives compelling evidence to replace the principle of equal *a priori* probabilities with the principle of apparently equal *a priori* probabilities, but it does not address the problem of how the system reaches this state. It will take an extremely (exponentially) long time for the universe to reach a randomly pure state, in contrast to the observed fact that thermalization occurs quickly. Here, we show that for almost all unitaries in a *k*-design applied to the universe, the subsystem state is close to the canonical state. Since these unitaries can be implemented and sampled efficiently, this means that equilibrium could be reached quickly to match observations.

We are now ready to show that a *k*-design gives a small ‖ρ_{S}−Ω_{S}‖_{1}. Firstly, we have to modify lemma 3.3 slightly.

## Lemma 5.2.

*Let X be any non-negative random variable with probability concentration*
5.4
*where η*≥0. *Then*
5.5
*for any m*>0.

The proof is very similar to the proof of lemma 3.3.

Now we state and prove the main result in this section:

## Theorem 5.3.

*Let ν be an ε*-*approximate unitary k*-*design. Then*
5.6
*In particular, with* , ,
5.7

Again, we need *d*_{S} to be polynomially smaller than *d*_{R} to obtain non-trivial bounds.

## Proof.

We go via the 2-norm and use lemmas 5.2 and 3.4.

We have from theorem 5.1 that
5.8
where . Since ‖ρ_{S}−Ω_{S}||_{2}≤||ρ_{S}−Ω_{S}||_{1},
5.9
We now apply lemma 5.2 to get
5.10
So for *m*≤*k*/4, using Markov’s inequality and lemma 3.4 (with μ=0) on the polynomial
5.11
Here, we used an estimate of α, the sum of the moduli of the coefficients
5.12
which we obtain via a calculation similar to that in §4.

Now we go back to the 1-norm, using to get
5.13
To obtain the result in equation (5.6), we just use and set *m*=*k*/8.

To prove the simplified version, first use, as in §4, that for . This is implied by . We then set *m*=*k*/8 to find
5.14
Then, using , with , we obtain the simplified result equation (5.7). ▪

## 6. Application 3: using *k*-designs for measurement-based quantum computing

Here we apply our ideas to partially de-randomize some results of Gross *et al.* (2008) and Bremner *et al.* (2008). The main result in these two papers is that most states do not offer any advantage over classical computation when used in the MBQC model. In MBQC, a classical computer is given access to a large quantum state on which it can do single qubit measurements. Some states allow for universal quantum computation, whereas others do not add any extra power to the classical computer. These results are concerned with the question of characterizing which states do and do not work. Showing that random states do not give any speed up shows that useful states for MBQC are not generic and so must be carefully constructed.

While the results in these two papers are similar, we will concentrate on the methods from Gross *et al.* (2008) since their methods are simpler to apply here. They prove their result by showing that most states are very entangled in the geometric measure (see definition 6.1). They then use this to show that the measurement outcomes of even the best possible measurement scheme are almost completely random. In fact, the state could be thrown away and the measurement outcomes replaced with random numbers to solve the computational problem just as efficiently. This shows that you can classically simulate any quantum computation that uses these highly entangled states. The measure of entanglement they use is the geometric measure:

## Definition 6.1

The geometric measure of entanglement of a state |Ψ〉 is (Shimony 1995; Barnum & Linden 2001) 6.1 where is the set of all product states.

They show that any MBQC using a state |Ψ〉 with can be efficiently simulated classically. They then show that (we abuse notation slightly by writing for , etc.)

## Theorem 6.2 (Gross et al. (2008), theorem 2).

For *n*≥11,
6.2

This shows that most states are useless. We partially de-randomize this result to show that most states in an ε-approximate (ε can be taken as a constant) state *n*^{2}-design have high geometric measure of entanglement and thus are useless in the same way.

We could apply our technique and use theorem 1.2, but in this case it is simpler to directly bound the probability using Markov’s inequality.

## Lemma 6.3.

6.3
*where* |*Ψ*〉*is chosen from an ε*-*approximate state k*-*design ν*, *m*≤*k and a positive integer and* |*Φ*〉*is any fixed state*.

## Proof.

We prove this bound directly using Markov’s inequality ▪

We now prove the main result in this section:

## Theorem 6.4.

*For* |*Ψ*〉*randomly drawn from an ε*-*approximate state k*-*design with d*=2^{n}
6.4
*In particular, for**k*=*n*^{2}, *and* ε=1,
6.5

We note that this bound is almost the same as in theorem 6.2. It only works for slightly larger deviations from *n*, which is why we obtain a slightly better probability bound. Note also that we can obtain an exponential bound in *n* (not *d*=2^{n}) because the design is exponentially large in *n*.

## Proof.

This proof closely mirrors the proof of theorem 2 in Gross *et al.* (2008). We use the idea of a γ-net. is a γ-net on product states if
6.6
In Gross *et al.* (2008), it is shown that such a net exists with . We then proceed by showing that most states in the state design have small overlap with every state in the net using the union bound and lemma 6.3. Finally, since every state is close to one in the net, we can show that most states in the design have small overlap with every product state.

We now formalize the above. Using lemma 6.3 and the union bound,
6.7
Now, we need to bound
We now claim that
6.8
To prove this claim, let |α〉 be the state that achieves the supremum on the left hand side, and let be the state closest to it in the δ′/2-net. It is shown in Gross *et al.* (2008) that this implies for any |Ψ〉
6.9
Therefore
6.10
This implies that the supremum over all states in the net must be at least δ′/2 to prove the claim.

We can now finish the proof. Set δ′=2^{−(n−δ)} in equation (6.8) and use equation (6.7) with γ=δ′/2 to find
▪

Combining this with the arguments of Gross *et al.* (2008) shows that most states in a state *n*^{2}-design on *n* qubits are useless for MBQC. This shows that even many efficiently preparable states are useless.

## 7. Conclusions

We have seen how to turn large deviation bounds for Haar-random unitaries into bounds for *k*-designs. The main technique was applied to show that unitaries from *k*-designs generate large amounts of entanglement. Then we showed that, if the dynamics of the universe produced a *k*-design, the entanglement generated would be sufficient to reproduce the principle of equal *a priori* probabilities. Finally, we showed that most states in sufficiently large state designs are useless for MBQC, in the sense that computation using them can be efficiently simulated classically.

However, there are other bounds for which our technique does not work. Since we cannot obtain exponential bounds for polynomially sized designs, our technique cannot directly de-randomize some bounds. Some results, for example showing that the -norm of the reduced state of a random pure state is close to 1/*d*_{S} (Harrow *et al.* 2004), are proven by using an ε-net of states and the union bound. Since the ε-net is exponentially large, exponentially small bounds are required. We do not know how to apply our idea to results of this kind and still have . (Note that we could cope with the ε-net in §6 since it was just a net on product states which is considerably smaller.)

It is also possible that our ideas could be used to completely de-randomize some constructions, for example locking (DiVincenzo *et al.* 2004; Hayden *et al.* 2004). If we could show that unitaries drawn from a *k*-design work with non-zero probability, and come up with an efficient sampling method, then we could obtain efficient randomized constructions.

## Appendix A

Here we present some miscellaneous proofs.

### (a) Proof of lemma 2.7

### Proof of lemma 2.7.

We claim that, if for all *d*^{k}×*d*^{k} matrices ρ,
A1
then σ is an ε-approximate *k*-design. To prove this claim, let *m*≤*k* and take *M* to be any balanced monomial of degree *m*. Write . Then let ρ_{m}=|*q*_{1},…,*q*_{m}〉〈*s*_{1},…,*s*_{m}|. Let , and ρ_{k}=ρ_{m}⊗*I*^{⊗k−m}/*d*^{k−m}. Then
We then use the fact that the largest matrix element is upper bounded by the 2-norm. For any matrix *A*,
For us, this implies
A2
which gives
A3
to prove the claim.

Then we just have to show how to obtain equation (A1) from equation (2.6). Iterating the TPE *t* times gives
A4
where ν^{t} is the ensemble obtained by applying *t* unitaries from ν. Now choose *t* such that λ^{t}≤ε/*d*^{3k/2}. □

### (b) Proof of theorem 1.3

Here we prove the more convenient form of lemma 4.3 stated as theorem 1.3.

### Proof of theorem 1.3.

Firstly, we will write the left hand side of equation (4.2) in a more useful way. Using , we find
where , following the notation in Hayden *et al.* (2006). This means
We now simplify the right hand side. Let δ=2^{α}−1. For *d*_{S}≥2, we have μ≥1/*d*_{S}. We shall also assume that *m*=*k*/8. This gives us (using μ≤1)
A5
Now, one can easily show (e.g. by induction on *n*) that
A6
for 2*n*δ≤1. We use this for *n*=*k*/4 and δ=1/*d*^{4}. The condition is then *k*≤2*d*^{4}, which we shall assume (we will set later). We now obtain
A7
We will now take ε=2(*k*/(2*C*_{1}*d*))^{k/8}, so that the two terms are the same. is , so this remains efficient. Now
A8
Assuming that , we should take *k* as large as possible up to , when the right hand side is maximized. We then find the result after further simplification. ▪

## Acknowledgements

I am grateful for funding from the UK Engineering and Physical Science Research Council through ‘QIP IRC.’ I thank Aram Harrow for many useful discussions on this topic, comments on earlier drafts of this manuscript and for suggesting the use of existing large deviation bounds to bound the high moments. I also thank Toby Cubitt for suggesting applying this method to the results of Popescu *et al.* (2006), Ashley Montanaro for useful discussions and comments on drafts of this manuscript as well as Andreas Winter and Michael Bremner for useful discussions and comments.

## Footnotes

- Received April 29, 2009.
- Accepted July 8, 2009.

- © 2009 The Royal Society