Quantum Computing and #P-Complete Problems

18.405J / 6.841J Project report: Quantum computing and #P-complete problems Abstract As part of the more general quest of understanding how quantum complexity classes relate to classical complexity classes, it is interesting to consider how quantum computing relates to #P-complete problems. In particular, this issue goes deeper than just the BQP containment BQP ⊆ P#P . This report surveys some results which connect quantum computation with #P-complete problems, for a theoretical computer science audience. Basic familiarity with quantum computing and BQP is assumed. I survey the 1993 Bernstein-Vazirani result that BQP ⊆ P#P , the 1999 Fenner-Green-Homer-Pruim result that P#P ⊆ NPNQP , the 2004 Aaronson BosonSampling result PostBQP = PP, and the 2011 Aaronson-Arkhipov result P#P ⊆ BPPNP . 1 Introduction Quantum computing is a model of computation which generalizes probabilistic computation by exploiting quantum effects. More specifically, a classical probabilistic Turing machine has an associated transition matrix P , where Px,y is the probability of the machine transitioning to configuration y from configuration x in a single step. Since probabilities must sum to 1, this is a P row stochastic matrix: P = 1 for all x. The probability of a particular computational path y x,y x0 → x1 → · · · → xt occurring is Px0 ,x1 Px1 ,x2 · · · Pxt−1 ,xt . The total probability that the configuration of the machine is xt after t steps is simply the sum of the probabilities of all computational paths which go from x0 to xt in t steps. Now consider the quantum case. The stochastic transition matrices are replaced by matrices corresponding to quantum gates. Whereas all entries of the classical transition matrices had to be nonnegative real numbers corresponding to probabilities, the matrices corresponding to quantum gates are complex in general. Also, the row stochastic constraint in the classical case is replaced by the constraint that the matrices in the quantum case be unitary. Say we have a quantum circuit consisting of t gates U1 , U2 , . . . , Ut . The total amplitude corresponding to a particular computational path |x0 i → · · · → |xt i is given by hxt | Ut |xt−1 i hxt−1 | Ut−1 |xt−2 i · · · U1 |x0 i ∈ C and the total amplitude to go from |x0 i to |xt i is the sum of the amplitudes of every computational path from |x0 i to |xt i (for physicists, this is essentially just a Feynman path integral). The crucially unique aspect of the quantum case which is not present in the classical case is the fact that since amplitudes are in C rather than R+ , the amplitudes corresponding to different computational paths can interfere destructively. In fact, quantum algorithm design can be viewed as an attempt to orchestrate the circuit such that computational paths going to a wrong answer interfere destructively and cancel each other other, leaving only the right answer. 1 Since the amplitudes of a quantum computation are sums of exponentially many complex numbers, it seems natural to investigate the relationship between quantum computing and the classical counting class #P. First we recall the definition. Definition 1.1 (#P). A function f : {0, 1}∗ → N is in #P if there exists a polynomial p : N → N and a polynomial-time TM M such that for every x ∈ {0, 1}∗ : n o p(|x|) f (x) = y ∈ {0, 1} : M (x, y) = 1 It is also convenient to record here the definition of BQP, the class of problems generally considered to be efficiently solvable by a universal quantum computer. Definition 1.2 (BQP). A language L is in BQP if and only if there exists a uniform family of polynomial-size quantum circuits {Cn : n ∈ N} such that • ∀n ∈ N, Cn inputs n qubits and outputs 1 bit
• ∀x ∈ L, Pr C|x| (x) = 1 ≥ 23
• ∀x 6∈ L, Pr C|x| (x) = 1 ≤ 31 In Section 2 we will review a 1993 result of Bernstein and Vazirani [4] which says that the set of decision problems efficiently solvable with a #P oracle subsumes the set of decision problems efficiently solvable with a quantum computer: BQP ⊆ P#P . In Section 3, based on the 1999 work of Fenner, Green, Homer, and Pruim [7], we define the language QAP (standing for Quantum Acceptance Possibility) which is complete for NQP, the quantum analog of NP. This language essentially encodes whether a quantum circuit has a nonzero acceptance probability on some input. We show that this language is also complete for the counting class coC= P (co-Exact-Counting Polynomial-Time). Since P#P ⊆ NPcoC= P , we find that this language is hard for P#P under nondeterministic reductions. In Section 4, following Aaronson’s 2005 paper [1], we define PostBQP – a variant of BQP in which one can postselect on a certain result occurring. This class is extremely powerful – we will see that PostBQP = PP. Since P#P = PPP , this implies that a quantum computer with postselection is able to solve #P-complete problems. In Section 5, which reviews parts of Aaronson and Arkhipov’s 2011 paper [2], we consider an alternative and presumably quite weak (non-universal) model of computation based on the statistics of non-interacting bosons. Despite the simplicity of the model, we show that if a classical computer were able to efficiently simulate the output of a boson computer, then a BPPNP machine would be able to compute the square of the permanent of an arbitrary complex matrix (a #P-complete problem). Note that by Toda’s Theorem, this would imply a collapse of PH. 2 BQP and P#P In [4], Bernstein and Vazirani formalized many complexity-theoretic notions in the quantum setting (such as defining BQP) and also proved several foundational results, the most relevant of which for this report being that BQP ⊆ P#P . We adapt their proofs here, first proving a similar but weaker result, and then moving on to the desired result. Proposition 2.1. BQP ⊆ PSPACE 2 Proof. We show how to simulate a BQP circuit in PSPACE. Let the circuit consist of gates U1 , U2 , . . . , Ut(n) where t(n) is some polynomial and n is the input length. Note that each gate acts on O(1) qubits. Without loss of generality we can assume each gate acts on 3 qubits (for example, choose the Hadamard and Toffoli gates as the universal base set). Let the input be |xi. The amplitude for state |yi is X hy| Ut Ut−1 · · · U1 |xi = hy| Ut |zt−1 i hzt−1 | Ut−2 |zt−2 i . . . hz1 | U1 |xi {z1 ,...,zt−1 } Note that a classical computer can compute this sum recursively. To compute an amplitude after the Ut gate, it can compute an amplitude after the Ut−1 gate, multiply by the relevant Ut matrix element, and add the result to a running total for the amplitude. It can reuse any space besides the space used to store the running total for the amplitude. So, if the space required to calculate an amplitude after t gates is S(t), we have the recursion relation S(t) = S(t − 1) + O(l) where O(l) is the space required to store the sum of the amplitudes, which is polynomial because we only need to keep track of amplitudes to a reasonable precision. So by the recursion relation, it can compute arbitrary amplitudes in polynomial space. Hence the result follows, because to compute the total probability of the quantum circuit outputting 1 it needs only to sum over the squares of the relevant amplitudes, which it can do in polynomial space by reusing space. Proposition 2.2. BQP ⊆ P#P Proof. Consider the decomposition as in the proof above: X hy| Ut Ut−1 · · · U1 |xi = hy | Ut |zt−1 i hzt−1 | Ut−2 |zt−2 i . . . hz1 | U1 |xi {z1 ,...,zt−1 } To some approximation, the entries of the Ui are all complex rationals. Consider splitting the contributions to the amplitude of |yi into positive reals, negative reals, positive imaginaries, and negative imaginaries. We first consider the contributions from positive reals. Let c be some fixed constant which will control the accuracy of the simulation. Let M be a polynomial-time TM which takes as input a sequence of quantum gates, an initial state |xi, a final state |yi, a computational path from |xi to |yi, and an integer k between 0 and 2c . M outputs 1 if the input is valid and if k < a · 2c where a is the amplitude of the path. Otherwise, it outputs 0. Note that the total contribution to the amplitude of |yi from the positive reals is given by 1 2c X M ({U1 , . . . , Ut }, |xi , |y i , path, k) paths from |xi to |yi, k But this quantity can be computed in polynomial time with help from the #P oracle. Similarly, we can use this method to calculate the contributions from the negative reals, positive imaginaries, and negative imaginaries to find the total amplitude of |yi in P#P . We now claim that for a P#P machine to simulate a BQP machine, it suffices to compute a single amplitude. This is true because one can first amplify the success probability of the BQP 3 machine using a majority voting procedure, and then one can use uncomputing to ensure that the squared amplitude of the final state is highly concentrated on |xi |f (x)i, where f (x) denotes the correct output of the circuit on input |xi. This is a good exercise for the reader, and it is proven in [3]. Hence, the P#P machine just needs to compute the amplitude of the state |xi |0i after |xi goes through the modified BQP circuit. This is essentially the best bound we have on BQP. 3 QAP and coC= P Of course, there are other questions one can ask about a quantum circuit than whether it can decide some language with bounded error. In 1999, Fenner, Green, Homer, and Pruim [7] considered the problem of determining whether a quantum circuit accepts with nonzero probability. Specifically, we are interested in the language QAP (Quantum Acceptance Possibility). Definition 3.1 (QAP). QAP = {hCn , xi : Cn encodes a uniform polynomial-size quantum circuit family that has non-zero probability of accepting x} One can check that this is a natural complete language for NQP, the quantum analog of NP. Definition 3.2 (NQP). A language L is in NQP if and only if there exists a uniform family of polynomial-size quantum circuits {Cn } such that
x ∈ L ⇐⇒ Pr C|x| (x) = 1 = 6 0 To see why this is a natural quantum analog of NP, note that a language is in NP if and only if there is a probabilistic polynomial-time TM with the property that a string is in the language if and only if the TM has a nonzero probability of accepting. We will show that NQP is equal to a certain classical counting class called coC= P, but first we need a few more definitions. Definition 3.3 (GapP). Given any L ∈ {0, 1}∗ , let Lx = {y ∈ {0, 1}∗ : hx, yi ∈ L}. A function f : {0, 1}∗ → Z is in GapP if there is a language L in P and an integer k such that, k k |{0, 1}n ∩ Lx | − |{0, 1}n − Lx | f (x) = 2 where n = |x|. Note that if f ∈ GapP, then f (x) corresponds to the difference between the number of accepting and rejecting paths of some nondeterministic TM on input x. Definition 3.4 (C= P). A language L is said to be in the class C= P if there is a GapP function f such that for any x, x ∈ L if and only if f (x) = 0. The class coC= P is the set of all languages with complements in C= P. We will now show that NQP = coC= P. We first show that NQP ⊆ coC= P, due to Fortnow and Rogers [8]. 4 Lemma 3.5. For any quantum circuit family Cn of size bounded by a polynomial s(n), there is a GapP function f and a constant c such that for all inputs x,
f (x) Pr C|x| (x) accepts = 2s(|x|) c Proof. Approximate the entries of the quantum gates by rationals such that for each quantum gate U , cU has all integral entries. Let the initial state be |xi, and the final state before measurement be |yi = Ut · · · U1 |xi. Consider the state ct |yi, and note that each amplitude of this state consists of a sum of products of polynomial-time computable functions. But one can check that FP ⊆ GapP and that GapP is closed under addition and multiplication (for proofs and more analysis of gap-definable counting classes, [6] is a good review). Hence, it follows that the probability that C|x| (x) accepts is f (x) c2s(|x|) for some f ∈ GapP. Note that it follows from this lemma that L ∈ NQP ⇒ L ∈ coC= P. We now show the converse, due to Fenner, Green, Homer, and Pruim. Lemma 3.6. For any f ∈ GapP, there exists a polynomial-time uniform family of quantum circuits Cn and a polynomial p such that, for all x of length n,
f (x)2 Pr C|x| (x) accepts = p(n) 2 Proof. Let L be the language corresponding to f as in Definition 3.3, and let M be the polynomial time machine recognizing L (i.e., M (x, y) = 1 if and only if hx, yi ∈ L). Let m = nk , and define a circuit family as follows. On input |xi, prepare the state |xi |0i⊗m |0i. Now perform a Hadamard transform on the middle m qubits: 1 X |xi |0i⊗m |0i 7→ m/2 |xi |yi |0i 2 y Next, using classical reversible computation, compute M (x, y) ≡ by and write the answer into the last qubit, yielding 1 X |xi |yi |by i 2m/2 y Next, perform a Hadamard transform on the last m + 1 qubits, yielding 1 1 XX 0 0 |ψi = √ m (−1)y·y +by b |xi y 0 b0 2 2 y y 0 ,b0 Now consider the amplitude of |xi |0i⊗m |1i: 1 1 X 1 1 X 1 1 hx| h0|⊗m h1| ⊗ |ψi = √ m (−1)y·0+by 1 = √ m (−1)by = − √ m−1 f (x) 22 22 22 y y Hence, defining the circuit to accept on measurement outcome |xi |0i⊗m |1i, we have the desired result. The above lemma implies that if L ∈ coC= P, then L ∈ NQP. Hence, putting the results together, we see that NQP = coC= P. Since P#P ⊆ NPcoC= P , we see that the problem of determining whether a quantum circuit accepts with non-zero probability is hard for P#P under nondeterministic reductions. 5 4 PostBQP and PP We now consider postselected BQP, PostBQP, the set of languages decidable by a fantasy version of quantum computation defined by Aaronson in 2004 [1]. This class is defined similarly to BQP, but now we have the ability to postselect on certain events happening. That is, we have the ability to instantly throw out all runs of a circuit where a certain event does not happen. This section closely follows his original paper. Definition 4.1 (PostBQP). A language L is in PostBQP if and only if there exists a uniform family of polynomial-size quantum circuits {Cn } such that for all inputs x, • The first qubit of Cn (|0 · · · 0i |xi) has nonzero probability of being measured to be |1i. • If x ∈ L, then the conditional probability of the second qubit being measured to be |1i assuming the first qubit is measured to be |1i is at least 2/3. • If x 6∈ L, then the conditional probability of the second qubit being measured to be |1i assuming the first qubit is measured to be |1i is at most 1/3. One can check that PostBQP has strong closure properties. In particular, it is closed under union, intersection, and complement. Furthermore, being able to postselect on multiple qubits does not change the class, and PostBQP = BQPPostBQP (assuming the queries are classical and nonadaptive). This is a very powerful class. For example, it is not hard to show that NP ⊆ PostBQP. We can simply randomly guess a string, check if the string is a witness for the input, and if it is, set the first and second qubits to |1i. If it’s not a witness, set the second qubit to |0i, and set the first qubit to |1i with an extremely small probability. Then with arbitrarily high probability, conditioned on the first qubit being measured |1i, measurement of the second qubit will give the correct answer. In fact, we will prove that PostBQP = PP. As a consequence, since PPP = P#P , postselection gives quantum computers the ability to solve #P-hard problems! It should be noted that PostBQP has proven surprisingly useful. For example, as explained in Aaronson’s original paper, after proving that PostBQP = PP it trivially follows that PP is closed under intersection since PostBQP is trivially closed under intersection. But the question of whether PP is closed under intersection was open for eighteen years before being proven with some heavy machinery. This is one of several examples of quantum computing yielding insight into purely classical questions. In contrast, the proof that PostBQP = PP is quite short. Another setting in which PostBQP is useful is in proving that certain quantum systems are not simulable by a classical computer unless the polynomial hierarchy collapses. As just one example, this method can be used to prove that quantum computation in which one uses only commuting gates cannot be simulated by a classical computer unless PH collapses to the third level [5]. The fact that PH ⊆ PPostBQP is used as an intermediate step in these proofs. Proposition 4.2. PostBQP ⊆ PP Proof. Since they form a universal basis set, we can assume without loss of generality that the circuit consists only of Hadamard and Toffoli gates. As in the earlier proofs, we know that the final amplitude of some basis state |yi is a sum of exponentially many contributions, each contribution being a product of matrix elements. Note that due to our choice of gates, each nonzero contribution 6 has the same magnitude; only the sign differs. If we denote these contributions, P ay,1 , . . . , ay,N , then 2 the probability of getting |yi upon measurement is (ay,1 + · · · + ay,N ) = ij ay,i ay,j . We want to know which is greater: the probability of measuring |11 . . .i or the probability of measuring |10 . . .i. We can do this in PP by selecting a computational path ending on |1 . . .i uniformly at random which has nonzero amplitude, and outputting 1 if the path has positive sign and ends on |11 . . .i or has negative sign and ends on |10 . . .i. Otherwise, output 0. Proposition 4.3. PP ⊆ PostBQP Proof. Consider L ∈ PP. Then there exists a polynomial r and an efficiently computable function g : {0, 1}|x| × {0, 1}r(|x|) → {0, 1} such that x ∈ L ⇐⇒ |{y : g(x, y) = 1}| ≥ 2r(|x|)−1 . Hence it suffices to show that if f : {0, 1}n → {0, 1} is efficiently computable and s = |x : f (x) = 1|, there exists a PostBQP circuit which decides whether s < 2n−1 or s ≥ 2n−1 . To do so, first apply a Hadamard transform and use reversible classical computation to prepare the state X 1 |xi |f (x)i n/2 2 n x∈{0,1} Now, apply a Hadamard transform to the first n qubits, and then postselect on those qubits being in |0i⊗n . This puts the final qubit in the state (2n − s) |0i + s |1i |ψi = p (2n − s)2 + s2 Now, prepare another qubit in the state α |0i + β |1i, and do a controlled-Hadamard operation to prepare the state α |0i |ψi + β |1i H |ψi. Next, postselect on the second qubit being |1i. This prepares the state p αs |0i + β 1/2(2n − 2s) |1i ϕβ/α = p α2 s2 + (β 2 /2)(2n − 2s)2 in the first qubit. Notice that if s < 2n−1 , the coefficients of both |0i and |1i are positive. Now, through elementary algebra, one can show that in this case, for some i ∈ [−n, n], √ 1+ 2 | h+|ϕ2i i | ≥ √ 6 where |+i ≡ √12 (|0i + |1i). The intuition is that changing the value of i rotates the direction of |ϕi in the first quadrant in the plane spanned by |0i and |1i, and some value of i will get it close to |+i. On the other hand, if s ≥ 2n−1 , then for √ no value of i will |ϕ2i i be in the first or third quadrants, and so one can show that | h+|ϕ2i i | ≤ 1/ 2 in this case. Hence, a PostBQP circuit of polynomial size can distinguish between these two scenarios with high probability by repeating the algorithm with varying values of i. 5 BosonSampling and the Permanent In the last section we analyzed a modified, more powerful model of quantum computation and found that it is hard for #P-complete problems. In this section, we will consider a very simple model 7 of computing due to Aaronson and Arkhipov in 2011 based on the quantum statistics of bosons that appears to not even be universal for classical computation, let alone quantum computation. Nonetheless, one can prove that if it can be simulated efficiently by a classical computer, then one could approximate the squared permanent of an arbitrary complex matrix with a BPPNP machine. But since approximating the squared permanent of an arbitrary complex matrix is #Phard, this would imply that P#P ⊆ BPPNP . Applying Toda’s Theorem [11], this implies that P#P = PH = ΣP3 = BPPNP and the polynomial hierarchy collapses to the third level. Hence, even though it is believed that a boson computer (or any quantum computer) could not compute the permanent of an arbitrary matrix efficiently, an efficient classical simulator for a boson computer could be used to compute a permanent efficiently! This subtly is more easily understood after seeing the proof. 5.1 Computing with noninteracting bosons If we have a quantum system consisting of two distinguishable particles and we find particle 1 at location a and particle 2 at location b, the state of the system is just |abi. But what if the particles are indistinguishable? In this case, if we catch one particle at a and one particle at b, we can’t say that we caught particle 1 at a and particle 2 at b. All we can say is that there is one at a and one at b. What this means for our mathematics is that |abi must describe the same physical state as |bai. Recalling that states correspond to rays in the hilbert space, we see |abi = eiφ |bai for some φ, where we are assuming |abi and |bai are normalized. This in turn implies |abi = ei2φ |abi, from which we find eiφ = ±1. The + sign corresponds to bosons and − to fermions, so for bosons we have |abi = |bai. So then if we catch one boson at a and one at b, how is the final state described in terms of |abi and |bai? The answer is that the state must be symmetrized: √12 (|abi + |bai). Note that this state treats |abi and |bai on a completely equal footing, and if the two particles are interchanged a ↔ b, the phase is simply multiplied by a +1 factor as desired. For the purposes of BosonSampling, a very interesting feature is that there appears to be some form of effective entanglement between the two particles just because they are identical: no interactions are required! (In other words, it is not possible to write the symmetrized state as a product state.) The presence of this effective entanglement suggests that perhaps we can do classically intractable feats with a computer just using noninteracting photons. We now define the model more specifically following Aaronson and Arkhipov. The computer will be built out of linear optical elements. The particles will be photons (which are bosons). There will be n particles in m possible modes (where a mode can simply be thought of as a place that a photon can be). We assume that n ≤ m ≤ poly(n). Photons are never created or destroyed, and any mode can have any nonnegative integer number of photons. The basis states of the computer can be written as |Si = |s1 , . . . , sm i where si is the number of photons in mode i. Further, S must satisfy S ∈ Φm,n where Φm,n is the set of tuples S = (s1 , . . . , sm ) such that each si ≥ 0 and s1 + · · · + sm = n. The boson computer works as follows. It starts in the computational basis state |1n i ≡ |1, . . . , 1, 0, . . . , 0i where there is exactly one photon in modes 1 through n, and modes n + 1 through m have no photons. It then applies a unitary transformation by applying some sequence of phaseshifters and beamsplitters. Finally, a projective measurement in the computational basis is performed. Let U be the unitary matrix corresponding to this sequence of phaseshifters and beamsplitters for the case of 1 photon. Note that in this case, there are m computational basis states and so 8 U is m × m. Define the matrix A to be the m × n matrix obtained by keeping only the first n columns of U. Now, let S ∈ Φm,n , and define the matrix AS as follows. If S = (s1 , . . . , sm ), take si copies of the i’th row of U for all i ∈ [m]. Hence, AS is an n × n matrix. Now, if DA is the probability distribution corresponding to the outputs of the boson computer upon measuring in the computational basis, we have Pr[S] = DA |Per(AS )|2 s1 ! · · · sm ! (1) The derivation of this result is beyond the scope of this overview, but is essentially a consequence of the statistics of identical bosons. See [2] for details. The BosonSampling problem is to sample from DA , given A as input (note that A fully specifies the distribution of the boson computer). We now give an outline of the proof of how a BosonSampling oracle O would allow one to compute the square of an arbitrary Cn × Cn permanent in BPPNP , but first we record a few ingredients which are necessary for the proof. By BosonSampling oracle, we mean an oracle which takes a string r ∈ {0, 1}poly(n) and an m × n matrix A specifying the boson computer whose distribution over r chosen uniformly at random is equal to DA . Note that the oracle is a deterministic function of r and A – repeatedly querying the oracle with the same values of r and A will result in the same output. Theorem 5.1 (Stockmeyer [10]). Given a Boolean function f : {0, 1}n → {0, 1}, let p= Pr x∈{0,1}n [f (x) = 1] = 1 2n X f (x). x∈{0,1}n f 1 Then for all g ≥ 1 + poly(n) , there exists an FBPPNP machine that approximates p to within a multiplicative factor of g. Intuitively, this result says that a BPPNP machine can approximate the acceptance probability of a BPP machine to within a polynomially small factor, even if that acceptance probability is exponentially small. Famously, Valiant [12] proved that computing the permanent is #P-complete: Theorem 5.2 (Valiant [12]). The following problem is #P-complete: given a matrix X ∈ {0, 1}n×n , compute Per(X). Since the output distribution of the boson computer involves the square of permanent, a somewhat different result for the hardness of the permanent is needed for BosonSampling applications: Theorem 5.3 (Aaronson-Arkhipov [2]). The following problem is #P-hard, for any g ∈ [1, poly(n)]: given a matrix X ∈ Rn×n , approximate Per(X)2 to within a multiplicative factor of g. We also need the following lemma, also proved in the original BosonSampling paper: Lemma 5.4 (Aaronson-Arkhipov [2]). Let X ∈ Cn×n . Then for all m ≥ 2n and ε ≤ 1/kXk, there exists an m × m unitary matrix U which can be computed in polynomial time that contains εX as a submatrix. Given all of the requisite ingredients, the desired result follows straightforwardly: 9 O Theorem 5.5. For any BosonSampling oracle O, P#P ⊆ BPPNP . Proof. Given a matrix X ∈ Rn×n , we show how to approximate the squared permanent of X in O BPPNP . By Theorem 5.3 this is a #P-hard task, and so the result follows. The strategy is to embed X into a unitary matrix corresponding to a boson computer, so that the squared permanent of X corresponds to the probability of the boson computer outputting |1n i. Then by Stockmeyer’s result, if one has an oracle for BosonSampling, then one can approximate this probability in BPPNP and hence approximate the squared permanent of X. More explicitly, let m ≡ 2n and ε ≡ 1/kXk. Let U be a m × m unitary matrix whose n × n upper-left submatrix Un,n is equal to εX. Such a U exists by Lemma 5.4. Let A be the m × n submatrix of U corresponding to selecting the first n columns. Note that A can be interpreted as a description of a boson computer. Let pA be the probability that the boson computer outputs |1n i. Now we have pA = Pr[O(A, r) = 1n ] = |Per(Un,n )|2 = ε2n |Per(X)|2 r The first equality is by definition of the BosonSampling oracle, the second follows from Equation 1, and the third follows from the embedding of X into U . But by Theorem 5.3, we can approxiO mate pA in BPPNP , and hence we can approximate |Per(X)|2 in the same. But by Theorem 5.3 approximating this quantity is #P-complete, and so the desired result follows. This result does not imply that a boson computer can solve a #P-complete problem. In particular, the permanent that one is trying to compute corresponds to a probability that is in general exponentially small. Hence, one would need an exponential number of samples to get a good estimate of it. This is why the deterministic nature of the BosonSampling oracle is crucial for the above proof. It should be noted that a possible objection to the above proof is that the oracle is assumed to be perfect. That is, it is assumed that the distribution of outputs of the oracle is exactly the same as the distribution of outputs of the boson computer. However, in reality, a boson computer will have at least a small amount of noise, and so it can be argued that even a boson computer can’t sample perfectly from DA ! Unfortunately, the above proof completely breaks down when even a small amount of noise in the oracle is permitted, since the proof relies on the accurate estimation of exponentially small quantities. However, Aaronson and Arkhipov prove that assuming two highly plausible conjectures involving random matrices are true, then even an efficient approximate sampling algorithm would imply that a #P-complete problem could be solved relatively efficiently by a classical computer, and PH would collapse. But this proof is beyond the scope of the report. 6 Conclusion One task for quantum computing researchers is to better understand the relationship between quantum complexity classes and classical complexity classes. In this report, I have surveyed some work which relates quantum computing to complete problems for the classical counting class #P. That such formal relationships exist is not too surprising, considering the fact that amplitudes of a quantum computation are sums of an exponentially large number of complex numbers. In fact, this consideration leads naturally to the proof that BQP ⊆ P#P . What seems a bit more surprising is the fact that #P-completeness appears in many varied quantum contexts. We have seen that it appears when one asks about whether a quantum circuit accepts with nonzero probability, when 10 one considers quantum computation with the extra resource of postselection, and even when one considers the weak, non-universal, and extremely simple model of BosonSampling. Given this, it seems likely that further connections between #P-complete problems and other aspects of quantum computing will appear in the future, and an open task is to discover such connections. For example, are there other non-universal models of quantum computation like BosonSampling in which one can embed a #P-complete problem as the permanent problem was embedded into BosonSampling? On the other hand, the hardness for BosonSampling is based on the fact that the embedded matrix could have both positive and negative entries – it is known due to an algorithm of Jerrum, Sinclair, and Vigoda [9] that there exists a fully polynomial randomized approximation scheme (FPRAS) for approximating the permanent of a matrix with nonnegative real entries. Is there some model of quantum computation that can be efficiently simulated classically due to a connection to the permanent of a nonnegative matrix? For example, some classes of Hamiltonians (so-called “stoquastic” Hamiltonians) correspond to classical stochastic transition matrices. So, perhaps some model of computation based on stoquastic Hamiltonians could be classically simulable due to the efficient approximation of the permanent of nonnegative matrices. References [1] S. Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proc. Roy. Soc. London, A461(2063):3473–3482, 2005. quant-ph/0412187. [2] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. In Proceedings of the 43rd ACM Symposium on Theory of Computing, pages 333–342, 2011. [3] C. Bennett, E. Bernstein, G. Brassard, U. Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Computing, 26:1510-1523, 1997. quant-ph/9701001 [4] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM J. Comput., 26(5):1411– 1473, 1997. First appeared in ACM STOC 1993. [5] M. Bremner, R. Jozsa, and D. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. Roy. Soc. London, 2010. arXiv:1005.1407. [6] S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes. Journal of Computer and System Sciences, 48(1):116–148, 1994. [7] S. Fenner, F. Green, S. Homer, and R. Pruim. Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy. Proc. Roy. Soc. London, A455:3953– 3966, 1999. quant-ph/9812056. [8] L. Fortnow and J. Rogers. Complexity limitations on quantum computation. J. Comput. System Sci., 59 (1999), no. 2, pp. 240?252. [9] M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. J. ACM, 51(4):671–697, 2004. Earlier version in STOC?2001. 11 [10] L. J. Stockmeyer. The complexity of approximate counting. In Proc. ACM STOC, pages 118– 126, 1983. [11] S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865–877, 1991. [12] L. G. Valiant. The complexity of computing the permanent. Theoretical Comput. Sci., 8(2):189–201, 1979. 12