Data Loading...

Approximate Counting and Quantum Computation Flipbook PDF

Approximate Counting and Quantum Computation 741 is easily checked that this is compensated by the change in the terms i

128 Views
109 Downloads
FLIP PDF 179.47KB

c 2005 Cambridge University Press Combinatorics, Probability and Computing (2005) 14, 737–754. doi:10.1017/S0963548305007005 Printed in the United Kingdom

Approximate Counting and Quantum Computation

´ S Z2 and D. W E L S H1‡ M. B O R D E W I C H,1† M. F R E E D M A N,2 L. L O V A 1 Mathematical

Institute, University of Oxford, 24-29 St. Giles’, Oxford, OX1 (e-mail: [email protected], [email protected])

2 Microsoft

Research, One Microsoft Way, Redmond, WA 98052, USA (e-mail: [email protected], [email protected])

Received 15 October 2003; revised 7 February 2005 ´ on his 60th birthday For B´ela Bollobas Motivated by the result that an ‘approximate’ evaluation of the Jones polynomial of a braid at a 5th root of unity can be used to simulate the quantum part of any algorithm in the quantum complexity class BQP, and results relating BQP to the counting class GapP, we introduce a form of additive approximation which can be used to simulate a function in BQP. We show that all functions in the classes #P and GapP have such an approximation scheme under certain natural normalizations. However, we are unable to determine whether the particular functions we are motivated by, such as the above evaluation of the Jones polynomial, can be approximated in this way. We close with some open problems motivated by this work.

1. Introduction The quantum complexity class BQP consists of those decision problems that can be computed with bounded error, using quantum resources, in polynomial time. Relative to the polynomial hierarchy of classical computation, it is known that BPP ⊆ BQP ⊆ PP ⊆ PSPACE, and at the moment none of these inclusions is known to be proper [1]. Recent work by Freedman, Kitaev, Larson and Wang [5] has shown that the ‘quantum part’ of any quantum computation can be replaced by an approximate evaluation of the Jones polynomial of a related braid. A classical polynomial time algorithm can convert a quantum circuit for an instance of such a problem, into a braid, such that the probability that the output of the quantum computation is zero is a simple (polynomial time) function † ‡

Research funded by the EPSRC and Vodafone, and supported in part by ESPRIT Project RAND-APX. Research supported in part by ESPRIT Project RAND-APX.

738

M. Bordewich, M. Freedman, L. Lov´ asz and D. Welsh

of the Jones polynomial of the braid at a 5th root of unity. For an exact statement of this see Freedman, Kitaev, Larsen and Wang [5], or the more detailed papers by Freedman, Kitaev and Wang [6], and Freedman, Larsen and Wang [7, 8]. It therefore follows that if we take A(L, x) to be an oracle that returns the evaluation of the Jones polynomial of a braid L at a point x, any BQP computation can be replicated by a classical polynomial time algorithm with one call to A, i.e., BQP ⊆ PA . Since computing the Jones polynomial is in general a #P-hard problem, this does not help. However, it is not an exact evaluation of the Jones polynomial that is required, but an approximate evaluation at a speciﬁc point for braids of a speciﬁc class. Hence we may look for a weaker oracle A such that BQP ⊆ PA . In a diﬀerent approach Fortnow and Rogers [4] link quantum complexity to the classical complexity class GapP. In particular they show that for any quantum Turing machine M running in time t(n) there is a GapP function f such that for all inputs x f(x) . 52t(|x|) Again evaluating a general GapP function exactly is #P-hard; however, one can simulate M using a polynomial algorithm with access to an oracle A , where A is an oracle giving an approximation to the GapP function f. With this motivation we examine the type of approximation needed in order to simulate a quantum computation, and then consider the complexity of such approximations. It turns out that an additive approximation is suﬃciently powerful. We should emphasize that a polynomial time additive approximation scheme is weaker than the familiar and much studied fully polynomial randomized approximation scheme (FPRAS). However, it is well known that any function which counts objects for which the corresponding decision problem is NP-complete cannot have an FPRAS (unless NP = RP). We show below that all #P functions do have polynomial time additive approximation schemes under natural normalizations. We also show that in two senses this is the best sort of approximation we can hope to achieve in polynomial time (see Theorems 4.1, 4.3 and 4.4). Pr(M(x) accepts) =

2. Quantum computing A link L is a smooth submanifold of S 3 , consisting of c(L) disjoint simple closed curves. A braid on m strings is constructed as follows. Take m distinct points in a horizontal line (p1 , p2 , . . . , pm ) and link them to m distinct points (q1 , q2 , . . . , qm ) lying on a parallel line, by m disjoint simple arcs fi in R3 , so that fi starts at pi and ends at qπ(i) where π is a permutation. A braid can be closed in numerous ways, by identifying the points pi and qj in some way, creating a link. Similarly any link can be represented as a braid. In particular, the plat closure of a braid on 2m strings is obtained by identifying the points p2i−1 and p2i , and q2i−1 and q2i for 1 i m. 2.1. Topological computing and the Jones polynomial One of the major diﬃculties in building a quantum computer has been the sensitivity of the system to outside interference. Freedman, Kitaev, Larson and Wang [5] introduced the notion of topological quantum computing, in an attempt to make the computations less

Approximate Counting and Quantum Computation

739

sensitive to small disturbances. The basic idea is as follows. One can create pairs of special quasi-particles, called anyons, in a 2-dimensional plane sandwiched between two blocks of a superconductor. The anyons have a certain probability of annihilating each other (leaving a vacuum) when brought together. However, this probability changes, according to the laws of quantum mechanics when one anyon is moved around the other before they are brought together. Even if it is moved in a complete circle around the other, on reaching its original position the probability of annihilation is changed. Thus a system of a large number of these particles can be used as a quantum computer for decision problems; pairs of anyons are created, moved around relative to each other, and then a predeﬁned pair of the anyons is brought together. If this pair annihilate each other leaving a vacuum, this is taken to be an output of 0 (or rejection); if they do not it is taken to be an output of 1 (or acceptance). The paths in the 2-dimensional surface, combined with a time dimension, give rise to a 3-dimensional representation of the ‘computation’ as a braid. There remain major diﬃculties in constructing such a quantum computer, and controlling the movement of anyons. However, one of the important results of Freedman, Kitaev, Larsen and Wang is that small changes in the paths of the anyons do not aﬀect the outcome of the computation; indeed it is determined by the isotopy class of the braid, and therefore stable under perturbations of the paths that do not change the braiding itself. The way in which the probability changes is suﬃciently subtle that such a quantum computer is universal in the following sense. The Kitaev–Solovay theorem [12, 14] together with the density theorem of Freedman, Larsen and Wang [7, 8] yields an algorithm which given any quantum circuit on m/2 qubits and error parameter , outputs a braid on m strings using a polynomial number of crossings (polynomial in m and log −1 ). The topological quantum computation using this braid eﬃciently simulates the quantum circuit, (the probability of acceptance is within of the correct value). Since an algorithm for a BQP problem can be used to generate a quantum circuit for a given instance, the above result gives an explicit method for ﬁnding an equivalent topological quantum computation, and so the class BQP is the same under either model. Hence a quantum computation on m/2 qubits is approximately represented by a braid b. In showing that the topological quantum computation depends on the isotopy class of b alone [5], the following link L is considered. L is the plat closure of the composition of b−1 , b and a small loop γ inserted (between b−1 and b) around the leftmost two strings (see Figures 1 and 2). Both b and b−1 are needed as any quantum computation must be reversible; the loop γ eﬀects a measurement of the qubit represented by the leftmost pair of strings. The conclusions of [5] may then be summarized as the following theorem: refer to [5] for full details. Theorem 2.1. Let π be a problem in BQP, with a polynomial time quantum algorithm A, and let I be an instance of π. For any > 0, a link L may be determined in time polynomial in |I| and log such that (−1)c(L)+w(L) (−a)3w(L) VL (e2πi/5 ) 1 Pr(A(I) = 0) − (2.1) 1 + < , 1 + [2]25 [2]m(L)−2 5

740

M. Bordewich, M. Freedman, L. Lov´ asz and D. Welsh

b

Figure 1. The braid b.

b–1

γ

b

minima Figure 2. The link L.

where a = eiπ/10 and [2]5 = 2 cos π/5 and c(L), w(L) and m(L) are the number of components, writhe and number of minima of the link L respectively. The minima of [5] are the individual joins in the plat closure at the bottom of the braid, hence m(L) is half the number of strings in b plus one. By construction, the number of strings in b is twice the number of (qu)bits in the input, hence m(L) = |I| + 1. The writhe is deﬁned for an oriented link, and is the number of ‘positively oriented’ crossings minus the number of ‘negatively oriented’ crossings, with respect to the given orientation of L. It is easily computable. The Jones polynomial is also deﬁned for oriented links; however, the formula above is independent of the orientation chosen for L. Since every crossing in b appears reversed in b−1 , these do not contribute to the writhe of L, hence the writhe is determined by the four crossings involving γ, and can only be −4, 0, or 4 (depending on the orientation of the two strands passing through γ). If L∗ denotes L with the orientation of one component reversed, then VL∗ (t) = t−3λ/2 VL (t), where λ is the contribution to the writhe of L from crossings of the reversed component over (or under) the rest of L. Hence only reversing γ or one of the leftmost two strings can aﬀect the Jones evaluation, and it

Approximate Counting and Quantum Computation

741

is easily checked that this is compensated by the change in the terms involving the writhe. To be consistent, we will retain the notation [2]5 for 2 cos π/5 from [5] throughout. It is Theorem 2.1 that gives rise to our interest in approximating VL (t). Further explanation of the derivation of this equation is given in [18] where the special but suﬃcient case w(L) = 0 is considered (we could restrict attention to braids with writhe zero without aﬀecting the main results). Although this formula involves an evaluation at e2πi/5 , similar results can be obtained for the nth root of unity for any n 5, n = 6 but these involve multiple Ls. The preceding paragraphs explain how an evaluation of a Jones polynomial can yield the answer to a (general) quantum computation. There is a weak converse to this. Suppose we have a quantum computer at our disposal with which to learn something about a Jones evaluation of a link L. We may assume without loss of generality (Freedman, Larsen and Wang [7]) that our quantum computer is of the topological kind and thus nicely adapted to braids. We can (easily) write L as the plat closure of a braid b by starting with the link diagram and pulling the overcrossings up and the undercrossings down. Let m be the number of strands of this braid b. If we wish to evaluate VL (α), α = e2πi/r , we encounter an important constant d = 2 cos π/r. The norm |VL (α)| is bounded from above by dm/2 with |VL (α)| = dm/2 achieved only when L is the unlink on m/2 components, a case which occurs when b is the identity braid. Our quantum computer will be able to provide an additive approximation (see below) of |VL (α)| as a variable with range [0, dm/2 ]. Given m marked points in the horizontal plane and the number α, there is a ﬁnite dimensional Hilbert space H on which m-strand braids act through a Jones representation p. The m/2 maxima (in the plat closure) determine a vector c in this space and the m/2 minima (in the plat closure) determine a vector in the dual H ∗ , which when identiﬁed with H by the Hermitian inner product, is the same c. We have VL (α) = c|p(b)|c. dm/2 Furthermore Prob(|0) = |c|p(b)|c|2 , where Prob(|0) refers to the physical probability that below the cups, after all the ‘particles’ have been fused in pairs, the vacuum |0 is observed, that is, no nontrivial particles result from these fusions. The last formula reﬂects the quantum mechanical rule that the probability of observing an outcome, in this case |0, is proportional to the square of the component of the state vector in the |0-direction. Because the range of |VL (α)| depends exponentially on the number of strings in the braid, m(b), our quantum computer will give much better information (sooner) if we succeed in displaying L with, or nearly with, the minimal m(b), called the braid index of L. Turning to the computational question, it is a theorem of Thistlethwaite [15] that when L is an alternating link, with associated plane graph G, then VL (t) = αT (G; −t, −t−1 ) where α is an easily computable function, and T is the Tutte polynomial of the planar graph. It is known [17] that even for planar graphs, computing T (G; x, y) is #P-hard,

742

M. Bordewich, M. Freedman, L. Lov´ asz and D. Welsh

except when (x, y) is one of a few special points, or lies on a hyperbola satisfying (x − 1)(y − 1) = q ∈ {1, 2}. Since (−e2πi/n , −e−2πi/n ), n 5, is not one of these ‘easy’ points, exact computation in polynomial time is not feasible (unless #P=P). It also seems unlikely that an FPRAS exists for these points. However, the notion of an FPRAS seems to be much stronger than the kind of approximation that is needed in the current context. For any BQP language L there is a quantum Turing machine M such that for all x ∈ L, M accepts with probability at least 3/4, and for all x ∈ L, M accepts with probability at most 1/4. Therefore all that we require is to determine which quartile of its range VL (e2πi/5 ) lies in. We return to this topic in Section 5. When considering algorithms on braids or links, the size of the input is taken to be the number of crossings. A quantum gate on m/2 qubits is converted into a braid on m strings of length polylog (1/), therefore the number of crossings in the braid associated with a BQP circuit is polynomially related to the number of gates in the BQP circuit. This in turn is bounded by a polynomial in the input size, hence an algorithm will either be polynomial with respect to both the number of crossings in the braid and the number of input qubits to the circuit, or neither.

2.2. GapP functions The class of counting functions which constitute #P is the set of functions that count certiﬁcates of membership of a language belonging to NP, hence #P functions are constrained to evaluate to non-negative integers. The class of functions GapP can be regarded as the closure of #P under subtraction, that is to say a function f : I → Z is in GapP if and only if there exist functions g, h ∈ #P such that f(I) = g(I) − h(I) for all I ∈ I. The class AWPP can be deﬁned as follows [3]. A language L is in AWPP if and only if there exist a polynomial p and a GapP function g such that for all I ∈ I, g(I) 3 p(|I|) 1, 4 2 g(I) 1 I∈ L ⇒ 0 p(|I|) . 4 2 I∈L⇒

(2.2)

The increase in power of quantum computation over classical computation is that in a quantum computer there is an ability to cancel out computations paths. Fortnow and Rogers [4] show that this power is captured by the class GapP, in which a similar eﬀect is seen. In particular they show that BQP ⊆ AWPP. It therefore follows that for a BQP language L, polynomial p and GapP function g satisfying (2.2), determining which quartile of the range [0, 2p(|I|) ] contains g(I) would be enough to determine membership of L. To summarize, our foremost problems can be interpreted as ﬁnding a suitable approximation for the Jones polynomial of a link, VL (t), the Tutte polynomial of an associated planar graph, T (G; x, y), at a particular point, or for the GapP functions arising from BQP languages.

Approximate Counting and Quantum Computation

743

3. Approximation Given a function ψ : I → R for which no eﬃcient exact evaluation algorithm is known, one may be interested in an ‘approximate’ answer instead. A standard approach is to look for a fully polynomial randomized approximation scheme (FPRAS) for the problem. If ψ is such a function and I ∈ I is an input, then an FPRAS for ψ is a randomized algorithm ˆ ), such that that given any I ∈ I, > 0 will output ψ(I, ˆ ) − ψ(I)| > ψ(I)] < 1/4, Pr[|ψ(I, and the running time is polynomial in |I| and −1 . Here one might be prompted to consider the following sort of approximation. Suppose we know a range in which the answer lies. Can we say where in that range the answer lies? Is it in the top or bottom half of the range, or in which quartile? We shall see that this approach is unlikely to be feasible, and in Section 3.1 we present an alternative. Clearly this type of approximation depends on the nature of the range. For the moment let us restrict our attention to the class of functions in #P. We will make the standard assumption that for a given NDTM M there exists a ﬁxed polynomial p such that for any input x, all certiﬁcates have size p(|x|) (so the total number of possible certiﬁcates of M is 2p(|x|) ). We would like to answer the following problem, denoted by πr : Given r, for p(|x|) and kr 2p(|x|) ? which k is the number of accepting certiﬁcates for x between (k−1) r 2 The problem π2 is simply to determine which inputs have more than half of all certiﬁcates as accepting certiﬁcates. The set of languages in this class is exactly the set PP of probabilistic polynomial time languages. Furthermore, π2 is clearly Turing reducible to π2s , for any positive integer s, since if π2s (x) s then π2 (x) = 1, otherwise π2 (x) = 2. Hence it is no surprise that this approach to approximation is NP-hard for #SAT, indeed the following lemma shows that any attempt to approximate #SAT in this way, or any problem with a parsimonious reduction to SAT, is unlikely to work. The proof is straightforward and we omit it; details may be found in [2]. Lemma 3.1. For k ∈ Z, deciding whether a CNF formula in n literals has more than 2n−k solutions is NP-hard. When k = 1 the same decision for disjunctive normal form (DNF) formulae is equivalent to that for SAT, since the negation of a SAT formula is in DNF, and hence for an instance F, we have #SAT(F) = 2n −#DNF(F), where n is the number of literals. This observation leads to the following related lemma. Again, the proof is omitted and details may be found in [2]. Lemma 3.2. For k ∈ Z, deciding whether a DNF formula in n literals has at least 2n−k solutions is NP-hard. This may seem more counterintuitive since not only is DNF in P, but also #DNF has an FPRAS [11]. On the other hand, the next lemma shows that the number of stable (independent) sets of vertices in a graph (#SS) can be approximated in this way, even

744

M. Bordewich, M. Freedman, L. Lov´ asz and D. Welsh

though it is #P-complete and does not admit an FPRAS unless NP = RP. Essentially this is because the ‘natural’ upper bound on the number of stable sets, 2n , is far too big unless the graph has very few edges. For details of the proof see [2]. Lemma 3.3. Let G be a graph on n vertices. For r ∈ Z, determining for which k, #SS(G) ∈ n k n [ (k−1) r 2 , r 2 ) is computable in time polynomial in n and r. Lemma 3.1 suggests that we cannot hope to ﬁx a partition of the range and then determine in polynomial time in which section the answer lies; the diﬃculty associated with an NP-complete decision problem can be shifted to exactly the boundary between two parts of our partition. We therefore consider an alternative method of approximation which will meet our needs. 3.1. Additive approximation Our approach to approximation consists of determining a small section of the range depending on the input, and in which we can say the answer lies with high probability. This gives rise to an additive approximation. Deﬁnition 1 (Additive Approximation (AA)). Given any function f : I → C and a normalization u : Z+ → R+ , an additive approximation for (f, u) is a probabilistic algorithm ˆ such that which, given any I ∈ I, > 0, produces an output f(I) ˆ Pr[|f(I) − f(I)| > u(|I|)] < 1/4, in time polynomial in |I| and −1 . Note that the 1/4 in the deﬁnition could be replaced by any δ ∈ (0, 1/2), since we could reduce this error probability in polynomial time by taking several runs of the algorithm. Note also that most of the time we shall be considering the case where f is real. In contrast to the set of functions admitting an FPRAS, which is closed under addition ¯ but not under subtraction (e.g., #DNF(f) has an FPRAS, but #SAT(f) = 2n − #DNF(f) does not), we have the following result, whose proof we leave to the reader. Proposition 3.4. Suppose (f, u) and (g, v) admit AA algorithms, then there exists AA algorithms for (−f, u), (f + g, u + v) and (f − g, u + v). If, in addition, |f(I)| u(|I|) and |g(I)| v(|I|) for all I, then there is an AA algorithm for (fg, uv). The normalization is crucial. Since we are most interested in determining where in the range of possible values the answer lies, we shall usually be taking u to be an upper bound on |f| depending only on input size. An additive approximation allows errors up to an absolute value of u(|I|), whereas an FPRAS allows only errors up to an absolute value of f(I). It is therefore a weaker notion of approximation, and it is easy to check that any function that admits an FPRAS also admits an AA algorithm under any upper bound.

Approximate Counting and Quantum Computation

745

Lemma 3.5. Let f : I → R be a function that admits an FPRAS, and let u : Z+ → R satisfy |f(I)| u(|I|) for all inputs I ∈ I. Then (f, u) has an AA algorithm. Note also that a given function will have an AA with respect to some normalizations but not others. For example, we show later that for the number of proper 3-colourings of a connected graph G on n vertices, PG (3) where PG is the chromatic polynomial of G, we have an AA for (PG (3), 2n ). However, for any constant δ > 0, (PG (3), (2 − δ)n ) does not have an AA unless NP = RP (Theorem 4.4). In other words we can determine PG (3) to within an additive error 2n in polynomial time, but we cannot approximate to within an additive error (2 − δ)n . Note that if (f(I), u(|I|)) has an AA, then for any ﬁxed polynomial p, (f(I), u(|I|)/p(|I|)) also does, since we can absorb the polynomial factor in the normalization into at only a polynomial slowing of the algorithm. It is the determination of the ‘best’ normalization for a given function that causes the greatest diﬃculties, particularly in relation to approximating VL (t). Nevertheless our ﬁrst positive result shows that any function belonging to #P does have an AA algorithm under very natural normalizations.

4. Additive approximations for #P functions The class of functions which constitute #P can be regarded as the set of functions that count certiﬁcates of membership of a language belonging to NP. For a given NP-language L there will be inﬁnitely many NDTMs which check membership of L, and the certiﬁcates for a given input I will depend on the machine used in veriﬁcation. The main result of this section is that all such counting functions have additive approximation schemes under the ‘natural normalization’ associated with the corresponding NDTM. For example, if we take f(G) to be the number of Hamiltonian circuits in a graph G, then two possible NDTMs for checking membership of L are M1 , which takes as certiﬁcates subsets of the edges, and checks that these form a cycle of length |V |, and M2 , which takes as certiﬁcates an ordering of the vertices v1 , v2 , . . . , vn and checks that the edges between any two adjacent vertices in the ordering, and between vn and v1 , do appear in the graph (to avoid double counting we must insist that relative to some ﬁxed ordering of the vertices π : V → 1, . . . , n, we have π(v1 ) = 1 and π(v2 ) < π(vn )). In each case the number of good certiﬁcates for a given graph G is exactly the number of Hamiltonian circuits of G; however, M1 has 2|E(G)| possible certiﬁcates, while M2 has (|V | − 1)!/2 possible certiﬁcates. In either case the number of possible certiﬁcates is a natural upper bound on the number of Hamiltonian circuits. We show below that there is an additive approximation algorithm under the normalization associated with any such bound. Theorem 4.1. Let f be a function in the class #P , with an associated NDTM M, so that, for a given instance I, M has f(I) accepting certiﬁcates, each of length p(|I|). Then there exists an additive approximation algorithm for (f, 2p(|I|) ) that runs in time polynomial in |I| and −1 .

746

M. Bordewich, M. Freedman, L. Lov´ asz and D. Welsh

Proof. Given an instance I of f, we will select t computation paths, or certiﬁcates, uniformly at random from the 2p(|I|) possible. We then run M using these inputs, and let Xi , i = 1 . . . t be indicator functions which take value 1 if and only if the ith computation p(|I|) t path accepts I. The estimator for f(I) is then X = 2 t i=1 Xi . Clearly E[X] = f(I). It remains to show that we can select t only polynomially large, such that the error bounds given in Deﬁnition 1 are satisﬁed. First note from Chebyshev’s inequality that Var(X) Pr |X − f(I)| 2p(|I|) 2 2p(|I|) 2 f(I) 1 2p(|I|) 1 − t 2 1 2. t

f(I) 2p(|I|)

Now if t = 4−2 + 1, we have Pr |X − f(I)| 2p(|I|) < 1/4.

Turning brieﬂy to GapP functions, we get the following immediate corollary. Theorem 4.2. Let f be a GapP function such that f = g − h where g, h ∈#P. (i) Suppose that there are additive approximations for (g, u) and (h, v), then there is an additive approximation scheme for (f, max{u, v}); (ii) Suppose that g(I) and h(I) have certiﬁcates of length p(|I|) for all I, then there is an additive approximation scheme for (f, 2p ). Proof. From Proposition 3.4 we have that there is an additive approximation for (f, u + v). From Deﬁnition 1 we can halve the permitted error for only a polynomial increase in running time, hence there is an AA for (f, u+v 2 ) and therefore also (f, max{u, v}), which gives (i). When g and h have certiﬁcates of length p, by Theorem 4.1 there are AA schemes for (g, 2p ) and (h, 2p ), (ii) now follows from (i). We have seen that all functions contained in #P have an AA algorithm relative to normalization by the size of the certiﬁcate space, and it is reasonable to ask if we could do better. However, we give two results that suggest this is already the best we can do in general. First we will see that sharpening our approximation to a logarithmic scale for the number of proper 5-colourings of a graph is NP-hard. Secondly, we show that the normalization by the number of possible certiﬁcates cannot be improved signiﬁcantly in the case of the number of k-colourings of a graph. Theorem 4.3. Let PG (5) be the number of proper 5-colourings of a graph. Then for a general graph G on n vertices, there cannot be an additive approximation algorithm for (log(PG (5) + 1), 3n) that runs in time polynomial in n and −1 unless NP = RP.

Approximate Counting and Quantum Computation

747

Proof. Consider an NDTM for PG (5) that takes as certiﬁcates any 5-colouring of the graph, hence the certiﬁcates are of length n log 5 = 3n, where n is the number of vertices in G. We show that an AA algorithm for (log(PG (5) + 1), 3n) would be able to solve the NP-complete problem of determining whether a graph is 5-colourable. Let G be a graph on n vertices and consider the following polynomial time transformation. We form G+ by adding n isolated vertices to G. If G is not 5-colourable, then nor is G+ . However, if G is 5-colourable, each 5-colouring can be extended to 5n 5-colourings of G+ . Therefore, if G is not 5-colourable log(PG+ (5) + 1) = 0, whereas if G is 5-colourable, log(PG+ (5) + 1) log(5n .5! + 1) > 2n. Hence an additive approximation algorithm for (log(PG+ (5) + 1), 6n) could determine whether or not G is 5-colourable in random polynomial time. Theorem 4.1 shows that for connected graphs there exists an AA algorithm for (PG (k), (k − 1)n ) as follows. We can take an arbitrary spanning tree on G, and take the set of certiﬁcates to deﬁne colourings relative to this spanning tree, giving k(k − 1)n−1 possible certiﬁcates. We can then adjust the normalization by a constant factor (k − 1)/k. We show that this cannot be improved, in the sense that the normalization (and therefore the error) cannot be reduced by any exponential factor. We have already noted that the normalization can be improved by any ﬁxed polynomial factor. Theorem 4.4. If NP = RP then for any ﬁxed k 3, δ > 0 there cannot be a polynomial time AA algorithm for (PG (k), φ(n)) for connected graphs G on n vertices, for any function φ(n) of order O((k − 1 − δ)n ). Proof. Let φ(n) c(k − 1 − δ)n for suﬃciently large n. Take r such that (k − 1 − δ) (k − 1)1−1/r . Given any graph G, we form a graph H by attaching a path of length n(r − 1) to a vertex of G. Now PG (k)(k − 1)n(r−1) = PH (k), PH (k) nr , PG (k) = (k − 1)1−1/r φ(nr) cPH (k) . PG (k) = φ(nr) c (k − 1)1−1/r nr

(4.1) (4.2) (4.3)

Now suppose that there is an AA algorithm for (PH (k), φ(|H|)), then we can get an 1 φ(nr). Using PˆH (k) and equation (4.2), approximation PˆH (k) within an additive error of 2c we obtain an approximation PˆG (k). By equation (4.3), PˆG (k) is within an additive error of 1/2, since φ(nr) φ(nr) nr 1. 1−1/r c(k − 1 − δ)nr c (k − 1) Since PG (k) is integral, we can therefore determine it exactly.

748

M. Bordewich, M. Freedman, L. Lov´ asz and D. Welsh 5. Approximating VL (t) and related quantities

We have seen in Section 2.1 that our primary problem is to decide whether or not there m/2 exists an additive approximation scheme for (VL (e2πi/5 ), [2]5 ) where L is the plat closure of a braid on m strings, indeed an additive approximation for the absolute value of the Jones polynomial suﬃces. We make this precise in the following theorem. Theorem 5.1. Let A be a oracle which takes as input a braid b on m strings and > 0, and m/2 returns an additive approximation for (|VL (e2πi/5 )|, [2]5 ), where L is the plat closure of b. A Then BQP = P . Proof. Recall from Section 2.1 that given a braid on m strings, a topological quantum 2πi/5 2 computer can be constructed such that the probability of output zero is |VL (e[2]m )| and 5 the computer runs in time polynomial in m. Given > 0, using independent runs of this computer and a standard sampling approach, the probability of zero can be estimated to within an error of 2 , where the number of runs is polynomial in −1 . Hence we may m/2 estimate |VL (e2πi/5 )| to within an absolute error of [2]5 in polynomial time. Therefore A P ⊆ BQP. Secondly, suppose we have a BQP language and an input x. By Theorem 2.1 we can determine a link L, of size polynomial in |x|, such that L satisﬁes equation (2.1), and the number of minima of L is |x| + 1. If x is in the language, Pr(0) < 1/4, hence (−1)c(L)+w(L) (−a)3w(L) VL e2πi/5 1 1 + < 1/4, 0 |x|−1 1 + [2]25 [2]5 2 2πi/5 |x|+1 |x|+1 c(L)+w(L) 3w(L) −2 1 + [2]5 − 1 , e < [2] −[2]5 [2]−2 (−1) (−a) V [2] L 5 5 5 4 2πi/5 < [2]|x|+1 0.39. VL e (5.1) 5

Whereas, if x is not in the language, Pr(0) > 3/4, hence (−1)c(L)+w(L) (−a)3w(L) VL e2πi/5 1 1 + > 3/4, |x|−1 1 + [2]25 [2] 5

3(1 + [2]25 ) |x|+1 − 1 , (−1)c(L)+w(L) (−a)3w(L) VL e2πi/5 > [2]5 [2]−2 5 4 2πi/5 VL e > [2]|x|+1 0.65. (5.2) 5

|x|+1

Clearly use of an oracle giving an additive approximation for (|VL (e2πi/5 )|, [2]5 ) will enable us to distinguish these two cases with probability at least 3/4. Hence BQP ⊆ PA . We saw in Section 2.1 the equivalence of the Jones polynomial and a specialization of the Tutte polynomial for alternating links, hence we would like an AA for a general planar graph G for T G; −e2πi/5 , −e−2πi/5 , u , where u is some reasonable upper bound.

Approximate Counting and Quantum Computation

749

Hyperbolae of the form Hq := (x − 1)(y − 1) = q play a crucial role in the manipulation of the Tutte polynomial; loosely speaking, the process of performing a tensor product on an input graph G with some other ﬁxed graph N enables us to ‘move around’ the Tutte plane. That is, the new graph G ⊗ N satisﬁes T (G ⊗ N; x, y) = f(N; x, y)T (G; X, Y ),

(5.3)

where f and the arguments X, Y can be computed in time polynomial in |x|, |y| and |N|. However, for any choice of N, the new points X, Y satisfy (X − 1)(Y − 1) = (x − 1)(y − 1) = q.

(5.4)

Thus, such transformations restrict us to remain on the initial hyperbola Hq ; see [10] for further details. The close relationship between points on the hyperbola enables us to use an additive approximation at one point to get an additive approximation at any other point (X, Y ) on the same hyperbola for which there exists a suitable planar N which transforms (x, y) to (X, Y ) by (5.3). Proposition 5.2. Let x, y ∈ Q and N a planar graph on k vertices be ﬁxed. Suppose there is an AA scheme for (T (G; x, y), u(n)) for any planar G on n vertices and m edges. Then there is also an AA for (T (G; X, Y ), u(n + m(k − 2))), where X and Y are the points determined by the transformation in (5.3) (depending only on x, y and N). Proof. Let X and Y be the points satisfying (5.3). Since G ⊗ N is planar (see the construction in [10]) we may use the AA scheme for (T (G ⊗ N; x, y), u(|V (G ⊗ N)|)) to get an approximation to within an error u(|V (G ⊗ N)|) with probability at least 3/4 in polynomial time. Note that |V (G ⊗ N)| = n + m(k − 2). Since the running time of the AA scheme is polynomial in −1 , and f(N; x, y) is a constant, we can approximate to within an error of |f(N; x, y)|u(n + m(k − 2)) and still run in polynomial time. By (5.3) we have T (G; X, Y ) =

T (G ⊗ N; x, y) . f(N; x, y)

Hence the AA for T (G ⊗ N; x, y) yields an AA for T (G; X, Y ) with error at most u(n + m(k − 2)) in polynomial time. Because of the important role of these hyperbolae, it is natural to look at the hyperbolae 2πi 2πi containing the roots of unity (−e n , −e− n ). These are Hqn , where qn = 2 + 2 cos(2π/n), which cut the x-axis at x = −1 − 2 cos(2π/n),

(5.5)

corresponding to an evaluation of the chromatic polynomial at one of the well-known Beraha numbers Bn = 2 + 2 cos(2π/n). Since for real x and y and any graph N, the related

750

M. Bordewich, M. Freedman, L. Lov´ asz and D. Welsh

points X and Y will also be real, we cannot ﬁnd an N such that we can directly relate 2πi 2πi T (G ⊗ N; 1 − B5 , 0) and T (G; −e 5 , −e− 5 ). Whether or not we can ﬁnd a point within 2πi 2πi absolute value of (1 − B5 , 0) that can be directly related to (−e 5 , −e− 5 ) is an interesting ongoing question. We present some positive results below, and return to these diﬃculties in Section 7. First note that by Theorems 4.1 and 4.2 we know that T (G; x, y), x, y ∈ Z will have an AA scheme with respect to an appropriate normalization, since evaluations at these points are GapP functions. However, the drawback is that often the naive normalization will be too large. This will not always be the case, for example the point (1 − λ, 0), λ ∈ Z, gives the number of proper λ colourings, and by Theorems 4.3 and 4.4 here we have a best possible normalization. When we consider the non-integer points, the situation is more complicated. A straightforward sampling approach gives the following result. Proposition 5.3. For rational (x, y) and a connected graph G, there exists a AA algorithm for the following: (i) (T (G; x, y), y |E| (y − 1)−|V |+1 ) when {x = 1, y > 1}, (ii) (T (G; x, y), x|E| (x − 1)|V |−|E|−1 ) when {x > 1, y = 1}, (iii) (T (G; x, y), y |E| (x − 1)|V |−1 ) when {x > 1, y > 1}. In other regions, in particular where there are negative terms in the expansion of T , cancellation between terms means that there is no longer a natural upper bound by which to normalize. We return to this problem in Section 7.

6. An alternative approach Returning to our original motivation, at the moment we are unable to determine whether m/2 there is an AA algorithm for (VL (e2πi/5 ), [2]5 ) where L is the plat closure of a braid on m strings. However, we now show that in order to simulate a quantum computation it would be suﬃcient to determine the sign of the real part of VL (e2πi/5 ). Particularly in the case that the writhe of L is zero, and hence VL (e2πi/5 ) is real, this seems an easier problem. Theorem 6.1. Let A(L) be an oracle that returns the sign of the real part of the Jones polynomial of the link L evaluated at e2πi/5 . Then BQP ⊆ PA . Proof. This proof follows that of Theorem 5.1. Suppose we have a BQP language and an input x. By Theorem 2.1 we can determine a link L, of size polynomial in |x|, such that L satisﬁes equation (2.1), and the number of minima of L is |x| + 1. We now assume that w(L) = 0; the proof in the cases w(L) = 4 and w(L) = −4 follow by a similar argument. Simplifying equation (2.1) in the case w(L) = 0, we have (−1)c(L) VL e2πi/5 1 1+ . (6.1) Pr(0) = 1 + [2]25 [2]m(L)−2 5

Approximate Counting and Quantum Computation

751

If x is in the language, Pr(0) < 1/4, hence (−1)c(L) VL e2πi/5 1 1+ < 1/4, |x|−1 1 + [2]25 [2]5 2 2πi/5 |x|−1 1 + [2]5 c(L) −1 , < [2]5 (−1) VL e 4 |x|−1 (−1)c(L) VL e2πi/5 < −[2]5 0.09 < 0.

(6.2)

Whereas, if x is not in the language, Pr(0) > 3/4, hence (−1)c(L) VL e2πi/5 1 1+ > 3/4, |x|−1 1 + [2]25 [2]5 2 |x|−1 3(1 + [2]5 ) −1 , (−1)c(L) VL e2πi/5 > [2]5 4 2πi/5 |x|−1 c(L) (−1) VL e > [2]5 1.71 > 0.

(6.3)

Clearly use of an oracle giving an additive approximation for the sign of VL (e2πi/5 ) will enable us to distinguish these two cases with probability at least 3/4. Hence BQP ⊆ PA . In the previous section we outlined the importance of the hyperbolae Hq := (x − 1)(y − 1) = q to the Tutte polynomial. For x, y, X, Y and N related as in equation (5.3), we can determine the sign of T (G; X, Y ) if we can determine the sign of T (G ⊗ N; x, y). This gives rise to the natural question of the complexity of determining whether a function is greater than or less than zero, in particular the Tutte polynomial, of which the Jones is a specialization. It is immediate from the deﬁnitions that the Tutte is non-negative in the region x, y 0. At all other integer points on the axes the Tutte polynomial counts either colourings or ﬂows, up to easy multiplicative factors. Since these factors may be positive or negative, we can always select one of either ‘T (G; x, y) is non-negative’ or ‘T (G; x, y) is non-positive’ that is true, in polynomial time. In the above situation we are not concerned with cases in which the value is exactly zero, hence this would suﬃce. We consider the situation at other points in the next section.

7. Some combinatorial and complexity questions We close with the following questions which have been prompted by this work. In Section 5 we noted that we are unable to ﬁnd a suitable normalization for approximating the Tutte polynomial when the expansion included negative terms. We return to this here and examine the chromatic polynomial to highlight the diﬃculties. We have seen that for a connected graph G, we have an additive approximation for (PG (λ), (λ − 1)n )) for all λ ∈ Z+ . However, we are most interested in an additive approximation at the non-integral Beraha numbers. One might hope to achieve the above approximation for all λ ∈ R>1 ; however, this seems unlikely as (λ − 1)n is not even close

752

M. Bordewich, M. Freedman, L. Lov´ asz and D. Welsh

to being an upper bound for PG (λ). Indeed, consider the complete graphs: for small δ, PKn (1 + δ) = (1 + δ)(δ)(−1 + δ) · · · (−n + δ + 1) ≈ (−1)

n−2

δ(n − 2)!.

(7.1) (7.2)

This prompts the ﬁrst open question. Question 1. What is the best upper bound depending on λ, n and m for |PG (λ)| for all (planar) graphs G on n vertices and m edges? As far as we are aware the best upper bound known [19] is |PG (λ)| |λ|n−m (|λ| + 1)m

λ ∈ C.

For general graphs we can make the following small improvement. Proposition 7.1. Let G be a graph and let λ ∈ C, then n−m m m m m −1 |λ| + 1, for |PG (λ)| n n n m |PG (λ)| (|λ|)n−m (|λ| + 1)m < |λ| + 1. for n If G is a connected graph then n−m−1 m m m |PG (λ)| −1 |λ| n−1 n−1 |PG (λ)| (|λ − 1| − 1)n−m−1 (|λ − 1|)m |λ|

m |λ − 1|, n−1 m < |λ − 1|. for n−1 for

These bounds hold for all λ ∈ C; however, the Beraha numbers have special characteristics. The evaluations of the chromatic polynomial at these points have some beautiful, but not totally understood, properties [16]. The√ values begin 4, 0, 1, 2, 1 + τ, 3, . . . and converge towards 4, where τ is the golden ratio 1+2 5 . The integers in this series are clearly central to the theory of chromatic polynomials. Writing B5 = 1 + τ, then for any plane triangulation T on n vertices: |PT (B5 )| τ5−n .

(7.3)

For a connected graph G with average degree at least 3.24 (note that a planar triangulation has average degree 6 − 12/n), the above proposition gives n−m−1 m m m |PG (B5 )| −1 B5 . n−1 n−1 Hence we ask the following. Question 2. Is there a better bound for |PG (Bn )| than there is for an evaluation at a general point?

Approximate Counting and Quantum Computation

753

Following the results of Section 6 we are also prompted to examine the complexity of determining whether the Tutte polynomial is greater than or equal to, or less than zero at a given point. Recall that this decision problem is trivial for x, y 0, and for integer points on the axes. Again considering the specialization to the chromatic polynomial we ask the following. Question 3. For ﬁxed λ ∈ Q, is it NP-hard to decide whether PG (λ) is greater than or equal to, or less than zero? Note that this is trivial for λ ∈ Z. It is also P-time decidable for λ < 32/27 by the following theorem of Woodall [19] and Jackson [9]. Theorem 7.2. Let G be a graph without loops on n vertices, κ components and b blocks. (i) If λ < 0, then PG (λ) is nonzero with the sign of (−1)n . (ii) If 0 < λ < 1, then PG (λ) is nonzero with the sign of (−1)n−κ . n−κ−b . (iii) If 1 < λ < 32 27 , then PG (λ) is nonzero with the sign of (−1) Note that PG (λ) = 0 for λ ∈ Q\Z, since the chromatic polynomial has integer coeﬃcients. It is easy to show the following. • Let λ ∈ Q\Z. If deciding whether PG (λ) > 0 is NP-hard, then it is also NP-hard to decide whether PG (λ + 1) > 0 for a general graph G. However, since it is easy to decide for λ < 32/27, the converse cannot be true for all λ ∈ Q\Z unless these questions are all in P. It would be interesting to know the answer to the following questions. Question 4. Does there exist a critical α > 0 such that deciding whether PG (λ) is greater than or less than zero is NP-hard for all rational λ > α, λ ∈ Z? Question 5. Is this critical α equal to 32/27? As before we are more interested in evaluating the chromatic polynomial at the Beraha points than at general non-integers, and the graphs we are most interested in are planar. Hence we ask the following speciﬁc question. Question 6. For planar graphs, is the problem of deciding whether PG (Bn ) is greater or less than zero NP-hard? For any graph G, not necessarily planar, it is known that PG (Bn ) = 0 for n 5, n = 6, 10, [13]. Also Tutte [16] has √ shown that for any planar triangulation the following equation holds, writing B10 = τ 5, √ PT (B10 ) = 5τ3(n−3) (PT (B5 ))2 . (7.4) So PT (B10 ) > 0 for all plane triangulations T , indeed a simple reverse induction shows that for any planar graph G, PG (B10 ) > 0 holds. Further, for any outerplanar graph G, we can

754

M. Bordewich, M. Freedman, L. Lov´ asz and D. Welsh

form the planar graph G+ by adding a new vertex adjacent to all original vertices. Since PG+ (λ + 1) = (λ + 1)PG (λ) holds for all positive integers, it holds for all λ ∈ R. Noting that B10 = B5 + 1, we conclude that PG (B5 ) > 0 for all outerplanar graphs G. Acknowledgements The authors would like to thank the referee for many helpful comments and suggestions, in particular for suggesting a simpler proof of Theorem 4.3. We also thank Graham Brightwell and Colin McDiarmid for comments on an earlier version of this work [2]. References [1] Adleman, L., DeMarris, J. and Huang, M. (1997) Quantum computability. SIAM J. Computing 26 1524–1540. [2] Bordewich, M. (2003) The complexity of counting and randomised approximation. PhD thesis, New College, Oxford University. [3] Fenner, S. (2003) PP-lowness and a simple deﬁnition of AWPP. Theory Comput. Syst. 36 199–212. [4] Fortnow, L. and Rogers, J. (1999) Complexity limitations on quantum computation. J. Comput. Syst. Sci. 59 240–252. [5] Freedman, M., Kitaev, A., Larsen, M. and Wang, Z. (2003) Topological quantum computation. Bull. Amer. Math. Soc. 40 31–38. [6] Freedman, M., Kitaev, A. and Wang, Z. (2002) Simulation of topological ﬁeld theories by quantum computers. Commun. Math. Phys. 227 587–603. [7] Freedman, M., Larsen, M. and Wang, Z. (2002) Density representations of braid groups and distribution of values of Jones invariants. Commun. Math. Phys. 228 177–199. [8] Freedman, M., Larsen, M. and Wang, Z. (2002) A modular functor which is universal for quantum computation. Commun. Math. Phys. 227 605–622. [9] Jackson, B. (1993) A zero-free interval for chromatic polynomials of graphs. Combin. Probab. Comput. 2 325–336. [10] Jaeger, F., Vertigan, D. and Welsh, D. J. A. (1990) On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Camb. Phil. Soc. 108 35–53. [11] Karp, R., Luby, M. and Madras, N. (1989) Monte Carlo approximation algorithms for enumeration problems. J. Algorithms 10 429–448. [12] Kitaev, A. (2002) Quantum computations: algorithms and error correction. Russian Math. Survey 52:61 1191–1249. [13] Salas, J. and Sokal, A. (2000) Transfer matrices and partition-function zeros for antiferromagnetic Potts models. J. Statist. Phys. 98 551–588. [14] Solovay, R. Private communications. [15] Thistlethwaite, M. B. (1987) A spanning tree expansion of the Jones polynomial. Topology 26 297–309. [16] Tutte, W. T. (1970) On chromatic polynomials and the golden ratio. J. Combin. Theory Ser. B 9 289–296. [17] Vertigan, D. and Welsh, D. J. A. (1992) The computational complexity of the Tutte plane: the bipartite case. Combin. Probab. Comput. 1 181–187. [18] Wang, Z. (2003) Addendum: Derivation of the formula in [FKLW]. www.tqc.iu.edu. [19] Woodall, D. R. (1978) Zeros of chromatic polynomials. In Combinatorial Surveys: Proceedings of the Sixth British Combinatorial Conference (P. J. Cameron, ed.), Academic Press, London, pp. 199–223.