6.845 Quantum Complexity Theory, Lecture 16

6.896 Quantum Complexity Theory Lecture 16 1 Recap Last time we introduced the complexity class QM A (quantum Merlin-Arthur), which is a quantum version for NP. In particular, we have seen Watrous’s Group Non-Membership (GNM) protocol which enables a quantum Merlin to prove to a quantum Arthur that some element x of a group G is not a member of H, a subgroup of G. Notice that this is a problem that people do not know how to solve in classical world. To understand the limit of QM A, we have proved that QM A ⊆ P P (and also QM A ⊆ P SP ACE). We have also talked about QM A-complete problems, which are the quantum version of N P ­ complete problem. In particular we have introduced the Local Hamiltonians problem, which is the quantum version of the SAT problem. We also have a quantum version of the Cook-Levin theorem, due to Kitaev, saying that the Local Hamiltonians problem is QM A complete. We will prove Kitaev’s theorem in this lecture. 2 Local Hamiltonians is QMA-complete Definition 1 (Local Hamiltonians Problem) Given m measurements E1 , . . . , Em each of which acts on at most k (out of n) qubits where k is a constant, the Local Hamiltonians problem is to decide which of the following two statements is true, promised that one is true: � 1. ∃ an n-qubit state |ϕ� such that m i=1 Pr[Ei accepts |ϕ�] ≥ b; or �m 2. ∀ n-qubit state |ϕ�, i=1 Pr[Ei accepts |ϕ�] ≤ a. (Here b − a > 1 p(n) for some polynomial p(·).) Theorem 1 (Kitaev) The Local Hamiltonians problem is QM A-complete (as a promised prob­ lem). To prove this theorem, first of all, it is easy to see that the Local Hamiltonians problem is indeed in QM A, because to prove � that there exists a state making all measurements accept, Merlin can simply send |ψ� = max|ϕ� m i=1 Pr[Ei accepts |ϕ�] as a witness. Now we want to prove that every QM A problem can be reduced to the Local Hamiltonians problem. The first trial would be to start from the proof that 3SAT is NP-complete —the famous CookLevion Theorem we talked about last time— and just put the word “quantum” in front of every­ thing. So what happens if we do this? Let’s say Arthur has asked Merlin to send him a computation tableau |ψ1 �, . . . , |ψT �, and want to check it’s valid by making a bunch of local measurements — that is, measurements on O(1) qubits each. The trouble is, while Arthur can indeed check that 16-1 |ψt+1 � = Ut |ψt � —that is, |ψt+1 � is the state that results from applying the t-th local gate to |ψt �—, the measurement that checks this point itself is not local. Arthur has to do a swap test between |ψt+1 � and Ut |ψt � (like on the pset), but that involves all the qubits of |ψt � and all the qubits of ψt+1 , and is not local any more. Therefore instead, Arthur will ask Merlin to send him the witness state T 1 � √ |t�|ψt �. T t=1 � (To allow Arthur to do repeated test, the state sent is actually ( √1T Tt=1 |t�|ψt �)⊗poly(n) , but this is not the critical point.) Further more, in this state, the time t is encoded in unary, that is, |1� = |100000�, |2� = |110000�, |3� = |111000�, etc. Now we can check such a state is correct using a set of measurements on at most 5 qubits each —3 adjacent qubits from the clock register, and at most 2 qubits from the computation register. Each measurement does the following: pick a random t, and measure the (t − 1)-th and (t + 1)-th qubits of the clock register. See if we get |1� and |0� respectively. If we do, that means we are now at the t-th time step, and the state left in the t-th qubit of the clock register and in the computation register is |0�|ψt �+√|12�|ψt+1 � . (Notice that if the clock register is “bad”, we can detect it with 1/poly(n) probability. The error probability can be reduced by repeating polynomial times.) Now apply Ut−1 to the two relevant qubits in the computation register (Ut is local and applies only on 2 qubits), conditioned on the t-th qubit is |1�. The state becomes |0�|ψt � + |1�Ut−1 |ψt+1 � = |0�|ψt � + |1�|ψt � (unnormalized). Finally, apply a Hadamard to the t-th qubit in the clock register, measure it, and accept if we get |0�, reject otherwise. Notice that the final Hadamard translates the state into |0�|ψt � + |1�|ψt � + |0�|ψt � − |1�|ψt � = |0�|ψt �, therefore the final measurement will always get |0� if the computation history is correct and we will accept with probability 1. The key fact that Kitaev proved is that if the history is far from correct, we’ll detect that with probability at least 1/poly(n). It is worth mention that people actually showed that a bunch of measurements acting on 2 qubits each is enough. Notice that 2SAT is in P. Do these results contradict with each other? No, because what we do in the local measurement above is actually sufficient to solve the max-k SAT problem, which is already NP-complete. Another interesting issue is that there are many variants of the Cook-Levin Theorem in the classical world. One of them is the PCP Theorem, saying that, given a 3SAT formular ψ(x1 , . . . , xn ), deciding whether (1) ψ is satisfiable, or (2) at most 9/10 of ψ’s clauses can be satisfied, is NPcomplete. People still don’t know whether we can have the quantum version of the PCP Theorem, says that the approximation of the Local Hamiltonians problem is already QMA-complete. Scott conjectures that this statement is true. 3 QMA vs QCMA Last time we also talked about QCM A, where the proof sent by Merlin is classical, while Arthur ? can do a quantum check. As mentioned before, the problem QM A = QCM A is still a major open problem in quantum computation. Actually, people still don’t know whether there exists an oracle A which separates the two class, that is, QM AA = � QCM AA . In a recent paper, Aaronson and Kuperberg managed to give a “quantum oracle separation” between QM A and QCM A. Just like an oracle is some Boolean function A : {0, 1}n → {0, 1} that 16-2 an algorithm can call as a black box, a quantum oracle is some unitary transformation U that an algorithm can apply as a black box. As it turns out, sometimes it’s extremely useful to let the oracles themselves be quantum. Just like the oracle that separates P from N P , we expect that the quantum oracle U separating QM A from QCM A will encode a hard unitary search problem. The n-qubit unitary U is defined such that either (i) U = I, that is, the identity matrix; or (ii) there exists a secret “marked state” |ϕ� such that U |ϕ� = −|ϕ�, and U |ψ� = |ψ� for all |ψ� orthogonal to |ϕ�. As expected, the YES case that Merlin is going to prove is Case (ii). Using a QM A protocol, Merlin simply send |ϕ� to Arthur. To verify, Arthur performs a con­ trolled query to U and get the state |0�|ϕ� + |1�U |ϕ�. Arthur will get |0�|ϕ� − |1�|ϕ� if the statement is true, while |0�|ϕ� + |1�|ϕ� if false (i.e., U = I). Arthur then performs a Hadamard on the first register and measures it, accepts if getting |1�, rejects otherwise. Therefore this problem is in QM A. Is it in QCM A? In other words, are there poly(n) classical bits that Merlin can send to Arthur, that will enable Arthur to find |ϕ� with only poly(n) queries to U ? Aaronson and Kuperberg prove the answer is no. The intuition is, Merlin’s advice divides the set of all n-qubits quantum states into at most 2poly(n) “advice regions”. But remember, the space of n-qubit states is doubly exponentially n large (in the sense that there are 22 states, every pair of which has large inner product). Hence at least one of those advice regions must be extremely large. And using a generalization of the BBBV hybrid argument, they prove that searching any large enough advice� region for a random marked �� 2n state requires exponentially many queries (in particular, Ω m+1 , where m is the number of advice bits). So how about a classical oracle separation between QM A and QCM A? Aaronson and Ku­ perberg showed that the Group Non-Membership problem cannot lead to such a separation. In particular, they gave a GNM protocol that uses a polynomial-size classical proof and poly(n) quan­ tum queries to the group oracle (though also an exponential amount of postprocessing). The idea is: Merlin can just tell Arthur what the black-box group is. He can say, “it’s the symmetric group,” or “it’s a semidirect product of the Monster group with a twisted Chevalley group of Ree type.” It’s a consequence of the Classification of Finite Simple Groups that Merlin can say what the group is using a polynomial number of bits. Then Merlin also gives Arthur a mapping from that explicit group into the black-box group. Then Arthur just has to check two things: that the mapping is homomorphism, and that it’s 1-to-1. Checking that the mapping is a homomorphism can be done classically, and checking that it’s 1-to-1 can be done by solving the Nonabelian Hidden Subgroup Problem. By the result of Ettinger, Hoyer, and Knill, that requires only a polynomial number of quantum queries. Once Arthur has an embedding from the explicit group into the black-box group, he can then solve the Group Non-Membership problem by looking only at the explicit group, without making any further queries to the black-box group. 16-3 4 QMA(k) The last topic today is QM A(k), quantum Merlin Arthur with multiple proofs. The scenario is that there are k Merlins, and each of them can send to Arthur a quantum proof. This is not interesting in the classical world, because we can just concatenate the k proofs into one, and thus M A(k) = M A. But in the quantum case, suppose Arthur knows that the k proofs are unentangled with each other. Can Arthur use that promise to his advantage? In a paper of Aaronson, Beigi, Drucker, Fefferman, and Shor, they give evidence that indeed Arthur can. For example, if a 3SAT formula of size n √ is satisfiable, then this satisfiability can be proved to Arthur using O( npolylog(n)) unentangled quantum proofs with log(n) qubits each. Next time we will talk about quantum interactive proofs. 16-4